[자료구조 08] 딕셔너리와 해시 테이블, 키로 한 번에 찾기

이름을 대면 전화번호가 바로 나오는 전화번호부를 떠올려 보세요. 몇 번째에 적혔는지 셀 필요 없이 이름만 알면 됩니다. 딕셔너리(dictionary, 사전)가 바로 이런 자료구조입니다. 키(key, 이름표) → 값(value) 쌍을 저장하고, 키를 대면 값을 평균 O(1)에 꺼냅니다. 이 빠르기의 비밀은 내부에 해시 테이블(hash table)이라는 구조를 쓰기 때문입니다. 개수 세기와 빠른 조회에서는 따라올 자료구조가 없습니다. 예제 여섯 개로 딕셔너리를 두루 익혀 보겠습니다.

08.1 키로 값 꺼내기와 안전한 get

재고 딕셔너리에서 사과 개수를 꺼내 보겠습니다. 그리고 없는 키를 조회할 때 안전하게 처리하는 방법도 함께 보겠습니다.

d = {"apple": 3, "banana": 5}

print(d["apple"])

print(d.get("cherry", 0)) # 없으면 기본값 0

3

0

d["apple"]처럼 키를 대괄호에 넣으면 그 값을 바로 꺼냅니다. 그런데 d["cherry"]처럼 없는 키를 대괄호로 조회하면 KeyError(키 없음 오류)가 나며 프로그램이 멈춥니다. 이럴 때 get을 씁니다. d.get("cherry", 0)은 cherry가 없으면 기본값 0을 돌려주어 오류 없이 넘어갑니다. 조회는 평균 O(1)입니다.

08.2 항목 추가와 수정

딕셔너리에 새 항목을 넣거나 기존 값을 바꾸는 방법은 같습니다.

d = {"apple": 3, "banana": 5}

d["cherry"] = 7

print(d)

{'apple': 3, 'banana': 5, 'cherry': 7}

d["cherry"] = 7처럼 없는 키에 대입하면 새 항목이 추가되고, 이미 있는 키에 대입하면 그 값이 새 값으로 바뀝니다. 추가와 수정을 똑같은 문법으로 하니 헷갈릴 일이 없습니다. 추가든 수정이든 평균 O(1)로 처리됩니다. 몇 번째에 넣을지 자리를 밀 필요가 없어 리스트보다 훨씬 가볍습니다. 참고로 항목을 지울 때는 del d["apple"]처럼 del을 쓰며, 이 삭제도 평균 O(1)입니다.

08.3 개수 세기, 딕셔너리의 대표 용도

딕셔너리가 가장 빛나는 일이 빈도(개수) 세기입니다. "banana"에서 각 글자가 몇 번 나오는지 세어 보겠습니다.

text = "banana"

freq = {}

for ch in text:

freq[ch] = freq.get(ch, 0) + 1

print(freq)

{'b': 1, 'a': 3, 'n': 2}

핵심은 freq[ch] = freq.get(ch, 0) + 1 한 줄입니다. 글자 ch가 처음 나오면 get이 기본값 0을 주어 1이 되고, 이미 있으면 기존 개수에 1을 더합니다. 그 결과 b는 1번, a는 3번, n은 2번으로 정확히 세어졌습니다.

만약 리스트로 이 일을 하면 글자마다 "이미 세어 둔 게 있나?"를 앞에서부터 뒤져야 해서 매번 O(n)이 듭니다. 딕셔너리는 그 확인이 평균 O(1)이라, 글자 전체를 세어도 O(n)에 끝납니다. 자료구조 선택 하나가 속도를 가르는 대표 사례입니다.

08.4 Counter로 한 줄에 세기

사실 이 빈도 세기는 표준 라이브러리가 자동으로 해 줍니다. collections의 Counter(개수 세개)입니다.

from collections import Counter

print(dict(Counter("banana")))

print(Counter("mississippi").most_common(1))

{'b': 1, 'a': 3, 'n': 2}

[('i', 4)]

Counter("banana")는 앞에서 직접 짠 것과 똑같은 결과를 한 줄로 냅니다. Counter는 사실 딕셔너리의 한 종류라, 결과를 dict로 감싸면 평범한 딕셔너리로 볼 수 있습니다. most_common(1)은 "가장 많이 나온 것 1개"를 돌려주는데, "mississippi"에서는 i가 4번으로 가장 많아 [('i', 4)]가 나왔습니다. 괄호 안 숫자를 3으로 바꾸면 상위 3개를 순서대로 줍니다. 직접 세는 원리를 이해했다면, 실무에서는 이렇게 Counter를 쓰면 편합니다.

08.5 키와 값을 함께 훑기

딕셔너리에 담긴 모든 쌍을 훑을 때는 items를 씁니다. 성적표를 "과목=점수" 형태로 만들어 보겠습니다.

scores = {"국어": 90, "수학": 80}

print([f"{k}={v}" for k, v in scores.items()])

['국어=90', '수학=80']

items()는 (키, 값) 쌍을 하나씩 내줍니다. 그래서 for k, v in scores.items()로 키는 k에, 값은 v에 받아 함께 다룰 수 있습니다. 참고로 딕셔너리는 파이썬 3.7 버전부터 넣은 순서를 그대로 유지합니다. 그래서 국어, 수학 순으로 넣은 순서가 출력에도 그대로 나옵니다. 전체를 한 번 훑으므로 O(n)입니다.

08.6 in은 키를 검사합니다 (초보 함정)

딕셔너리에 in을 쓸 때 무엇을 검사하는지 헷갈리기 쉽습니다. 결론부터 보겠습니다.

scores = {"국어": 90, "수학": 80}

print("국어" in scores)

print(90 in scores)

True

False

in은 키만 검사합니다. "국어"는 키에 있으니 True지만, 90은 값에는 있어도 키에는 없으니 False입니다. 값으로 찾고 싶다면 90 in scores.values()라고 써야 하는데, 이것은 값을 앞에서부터 훑어야 해서 O(n)입니다. 딕셔너리의 빠른 O(1) 조회는 어디까지나 키를 기준으로 할 때라는 점을 꼭 기억해 두시기 바랍니다.

08.7 해시 테이블은 왜 빠른가, 그리고 충돌

딕셔너리가 키로 한 번에 값을 찾는 비밀은 해시(hash, 키를 자리 번호로 바꾸는 계산)에 있습니다. 키를 특별한 계산식에 넣으면 "이 키는 몇 번 칸"이라는 자리 번호가 나옵니다. 그래서 앞에서부터 뒤지지 않고 그 칸으로 곧장 가 값을 꺼냅니다. 데이터가 100만 개여도 계산 한 번이면 자리를 알아내니 평균 O(1)인 것입니다.

다만 서로 다른 키가 우연히 같은 칸 번호를 받는 경우가 있습니다. 이를 충돌(collision)이라고 합니다. 칸은 정해져 있는데 키는 그보다 많을 수 있으니, 이런 겹침은 피할 수 없습니다. 파이썬은 이럴 때 같은 칸에서 몇 개를 이어 두고 살짝 더 확인하는 식으로 알아서 해결합니다. 충돌이 잦아지면 그만큼 확인이 늘어 최악의 경우 O(n)까지 느려질 수 있어, 조회 복잡도를 평균 O(1)이라고 "평균"을 붙여 말합니다. 실제로는 파이썬이 칸의 개수를 넉넉히 늘려 가며 충돌을 줄이도록 잘 만들어져 있어, 거의 언제나 O(1)로 동작하니 안심하고 써도 됩니다. 이 해시 테이블이 바로 집합(set)의 빠른 조회를 떠받치는 구조이기도 합니다.

08.8 정리

딕셔너리는 키로 값을 평균 O(1)에 꺼내는 자료구조이고, 추가와 수정도 평균 O(1)입니다. get으로 없는 키를 안전하게 다루고, get(키, 0) + 1이나 Counter로 빈도를 세며, items로 키와 값을 함께 훑습니다. in은 값이 아니라 키를 검사한다는 점, 그리고 이 빠르기가 해시 테이블 덕분이라는 점을 기억하면 됩니다. 오늘 예제들을 직접 쳐 보며 "이름표로 바로 꺼내는" 감각을 손에 익혀 보시기 바랍니다.