thenullpage.com
1. 이름표를 붙여 값을 찾는 구조
리스트는 값을 순서대로 놓고 몇 번째인지로 꺼냅니다. 그런데 실제 데이터는 순서보다 이름으로 찾을 일이 많습니다. 학생 이름으로 점수를 찾고 상품 코드로 재고를 찾습니다. 이럴 때 쓰는 것이 딕셔너리(dictionary)입니다. 값마다 키(key)라는 이름표를 붙여두고 그 이름표로 바로 꺼냅니다.
scores = {"민수": 88, "지연": 95}
print(scores["지연"])
scores["영희"] = 70
print(scores)
95
{'민수': 88, '지연': 95, '영희': 70}
중괄호 안에 키와 값을 콜론으로 묶어 적고, 꺼낼 때도 넣을 때도 대괄호 안에 키를 씁니다. 키가 있는지 묻는 in도 그대로 됩니다. 이 동작들은 데이터가 백만 개로 늘어나도 걸리는 시간이 거의 그대로입니다. 이름표를 보고 저장할 자리를 미리 계산해 두기 때문입니다.
2. 해시 함수가 값의 자리를 정합니다
딕셔너리 안에는 값을 담을 칸이 여러 개 늘어서 있습니다. 이 칸을 버킷(bucket)이라고 합니다. 키를 넣으면 해시 함수라는 계산기가 키를 정수 하나로 바꾸고, 그 정수를 칸 개수로 나눈 나머지가 자리 번호가 됩니다.
print(hash(42))
print(hash(42) % 8)
print(hash("민수") % 8)
42
2
5
hash는 파이썬 내장 함수입니다. 정수는 자기 자신이 그대로 나오고, 문자열은 길이와 상관없이 정수 하나로 압축됩니다. 문자열의 해시값은 보안상의 이유로 파이썬을 실행할 때마다 달라지므로 세 번째 줄은 돌릴 때마다 다른 숫자가 나옵니다.
찾을 때도 똑같은 계산을 합니다. "민수"를 다시 넣으면 다시 5번 칸이 나오니 그 칸만 열어보면 됩니다. 앞에서부터 하나씩 비교하는 과정이 통째로 사라지고, 그래서 평균 O(1)이 됩니다.
문제는 서로 다른 키가 같은 번호를 받는 경우입니다. 칸 수보다 키가 많으면 겹치는 것이 당연합니다. 이것을 충돌(collision)이라고 합니다. 가장 쉬운 해결책은 한 칸에 여러 쌍을 목록으로 담고 그 안에서만 비교하는 체이닝입니다.
3. 해시 테이블을 직접 만들어 봅니다
체이닝 방식으로 아주 작은 딕셔너리를 직접 만들어 보겠습니다.
class SimpleMap:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
def put(self, key, value):
b = self.buckets[hash(key) % len(self.buckets)]
for pair in b:
if pair[0] == key:
pair[1] = value
return
b.append([key, value])
def get(self, key):
b = self.buckets[hash(key) % len(self.buckets)]
for k, v in b:
if k == key:
return v
m = SimpleMap()
m.put("민수", 88)
m.put("민수", 100)
print(m.get("민수"))
print(m.get("영희"))
100
None
put은 자리를 계산해 그 칸의 목록을 꺼내고, 같은 키가 있으면 값을 바꾸고 없으면 뒤에 붙입니다. get도 같은 자리를 계산해 그 칸 안에서만 비교합니다. 칸마다 한두 쌍씩만 들어 있으면 비교 횟수가 거의 고정이라 O(1)로 보아도 됩니다.
반대로 모든 키가 한 칸에 몰리면 목록 하나를 처음부터 훑는 것과 같아져 O(n)이 됩니다. 해시 테이블의 최악이 O(n)인 이유입니다. 다만 파이썬은 칸이 차면 칸 수를 늘려 다시 배치하므로 이런 일은 좀처럼 없습니다.
4. 키가 될 수 있는 값과 안 되는 값
키에는 아무 값이나 넣을 수 없습니다.
d = {}
d[(1, 2)] = "출발점"
print(d[(1, 2)])
d[[1, 2]] = "여기서 멈춥니다"
출발점
TypeError: unhashable type: 'list'
튜플은 되고 리스트는 안 됩니다. 넣을 때와 찾을 때 계산한 자리가 같아야 하는데, 리스트처럼 내용이 바뀌는 값을 키로 쓰면 값이 바뀌는 순간 자리도 달라져 못 찾습니다. 그래서 숫자, 문자열, 튜플처럼 바뀌지 않는 값만 키가 됩니다. 좌표를 키로 쓰고 싶다면 [y, x]가 아니라 (y, x)로 적어야 합니다.
값 없이 키만 모아두는 형제가 셋(set)입니다. 저장이 목적이 아니라 본 적 있는지만 확인하면 될 때 쓰며, add로 넣고 in으로 묻는 두 동작 모두 평균 O(1)입니다.
5. 개수를 세는 일은 딕셔너리가 맡습니다
무엇이 몇 번 나왔는지 세는 문제는 코딩 테스트에 자주 나옵니다. 값을 키로, 횟수를 값으로 쓰면 한 번 훑는 것으로 끝납니다.
count = {}
for ch in "banana":
count[ch] = count.get(ch, 0) + 1
print(count)
{'b': 1, 'a': 3, 'n': 2}
없는 키를 대괄호로 꺼내면 KeyError가 납니다. get(키, 기본값)은 키가 없으면 오류 대신 기본값을 돌려주므로 처음 나온 글자도 0에서 시작해 더할 수 있습니다. 같은 일을 해주는 도구가 표준 라이브러리에도 있습니다.
from collections import Counter
c = Counter("banana")
print(c)
print(c.most_common(2))
Counter({'a': 3, 'n': 2, 'b': 1})
[('a', 3), ('n', 2)]
Counter는 딕셔너리와 똑같이 쓰면서 세는 일만 대신해 줍니다. most_common처럼 많이 나온 순서로 뽑아주는 기능이 붙어 있어 자주 쓰입니다.
6. 두 수의 합을 한 번에 찾기
목록에서 더해 목표 값이 되는 두 수의 위치를 찾는 문제가 있습니다. 두 겹 반복문으로 모든 짝을 비교하면 O(n^2)입니다. 이미 지나온 숫자를 딕셔너리에 적어두면 한 번 훑는 것으로 끝납니다.
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
[0, 1]
[1, 2]
숫자를 볼 때마다 짝이 되는 값이 앞에 나온 적 있는지 물어봅니다. 목표가 9이고 지금 숫자가 7이면 2가 있었는지만 확인하면 됩니다. 이 확인이 O(1)이라 전체가 O(n)입니다. 확인을 먼저 하고 그다음 자기 자신을 넣어야 같은 숫자를 두 번 쓰는 답이 나오지 않습니다.
7. 딕셔너리를 떠올려야 하는 상황
앞의 문제들에는 공통점이 있습니다. 지나온 것을 기억해 두었다가 나중에 빠르게 물어본다는 점입니다. 중복 검사, 빈도 집계, 짝 찾기가 여기에 해당합니다. 반복문 안에서 리스트를 뒤지고 있다면 그 자리가 딕셔너리나 셋으로 바뀔 자리입니다.
오해 하나만 짚겠습니다. 파이썬 3.7부터 딕셔너리는 넣은 순서를 그대로 유지하지만 이것은 정렬이 아닙니다. 크기순으로 보고 싶으면 sorted나 most_common을 따로 불러야 합니다.
정리하면 챙길 것은 세 가지입니다. 키로 찾는 동작은 자리를 계산해서 가므로 평균 O(1)이고 최악에는 O(n)이라는 것, 키에는 숫자와 문자열과 튜플처럼 바뀌지 않는 값만 쓸 수 있다는 것, 개수 세기와 본 적 있는지 확인하기는 딕셔너리와 셋으로 O(n)에 끝난다는 것입니다.