해시 테이블: 빠른 검색의 비밀
딕셔너리와 집합이 100만 개 속에서도 값을 거의 한 번에 찾는 원리를 직접 만들어 보며 이해해요. 키를 칸 번호로 바꾸는 해시 함수, 생각보다 빨리 오는 충돌과 체이닝, 붐비면 칸을 두 배로 늘리는 부하율, 길이만 보는 나쁜 해시 때문에 찾기 한 번에 1,000번 넘게 비교하게 되는 모습을 확인해요. 문자열 해시가 실행할 때마다 바뀌는 이유인 해시 충돌 공격, 1과 1.0과 True가 같은 키가 되는 이유, 리스트를 키로 못 쓰는 이유와 넣은 뒤 바뀐 키가 사라지는 함정, 두 수의 합 문제, 그리고 해시 테이블이 못 하는 일까지 다뤄요.
지난 강의에서 배열은 번호를 알면 O(1)로 읽지만, 값으로 찾으려면 처음부터 훑어야 했어요. 그런데 딕셔너리는 내선번호["민지"]처럼 이름으로 찾아도 거의 한 번에 찾아요. 비밀은 간단해요. 이름을 번호로 바꿔서 배열의 그 칸에 바로 넣어 두는 거예요. 이번 강의에서는 이 해시 테이블을 직접 만들어 보고, 파이썬의 딕셔너리와 집합이 어떻게 움직이는지 속부터 이해해요.
키를 칸 번호로 바꿔요
키를 정수로 바꾸는 함수를 해시 함수, 그 결과를 해시 값이라고 해요. 해시 값을 칸 수로 나눈 나머지를 칸 번호로 쓰면, 어떤 키든 배열의 한 칸에 대응시킬 수 있어요. 파이썬의 hash()로 정수 키부터 볼게요.
for key in (42, 1_042, 7, 15):
print(f"키 {key:>5} → hash {hash(key):>5} → 8칸 중 {hash(key) % 8}번 칸")
키 42 → hash 42 → 8칸 중 2번 칸
키 1042 → hash 1042 → 8칸 중 2번 칸
키 7 → hash 7 → 8칸 중 7번 칸
키 15 → hash 15 → 8칸 중 7번 칸
파이썬에서 크지 않은 정수의 해시 값은 자기 자신이에요. 8칸짜리 배열이면 8로 나눈 나머지가 칸 번호예요. 계산 한 번이니 O(1)이에요. 그런데 42와 1,042가 같은 2번 칸, 7과 15가 같은 7번 칸이 됐어요. 서로 다른 키가 같은 칸을 가리키는 걸 충돌이라고 해요. 칸 수보다 키의 종류가 훨씬 많으니 충돌은 피할 수 없어요. 조합론 강의에서 본 비둘기집 원리예요. 그래서 해시 테이블은 충돌이 나도 제대로 동작하게 만들어야 해요.
직접 만드는 해시 테이블
가장 이해하기 쉬운 방법은 칸마다 작은 목록을 두고, 같은 칸에 온 키들을 그 목록에 차례로 넣는 거예요. 이걸 체이닝이라고 해요. 찾을 때는 칸 번호를 계산하고 그 칸의 목록만 훑어요. 문자열을 위한 간단한 해시 함수도 직접 만들어 볼게요.
def text_hash(key): # 글자마다 31을 곱해 가며 섞는 간단한 해시
h = 0
for ch in str(key):
h = (h * 31 + ord(ch)) % 2**32
return h
class HashTable:
def __init__(self, capacity=8, hash_func=text_hash):
self.buckets = [[] for _ in range(capacity)] # 칸마다 작은 목록을 둬요(체이닝)
self.size, self.hash_func, self.compares = 0, hash_func, 0
def _bucket(self, key):
return self.buckets[self.hash_func(key) % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for pair in bucket:
self.compares += 1
if pair[0] == key:
pair[1] = value # 이미 있는 키면 값만 바꿔요
return
bucket.append([key, value])
self.size += 1
if self.size / len(self.buckets) > 0.75: # 너무 붐비면 칸을 두 배로 늘려요
self._resize()
def get(self, key):
for k, v in self._bucket(key):
self.compares += 1
if k == key:
return v
raise KeyError(key)
def _resize(self):
pairs = [pair for bucket in self.buckets for pair in bucket]
self.buckets = [[] for _ in range(len(self.buckets) * 2)]
for pair in pairs: # 칸 수가 바뀌면 자리도 바뀌니 모두 다시 넣어요
self._bucket(pair[0]).append(pair)
extensions = HashTable()
for name, ext in [("민지", "내선 101"), ("준호", "내선 102"), ("서연", "내선 205"), ("도윤", "내선 310")]:
extensions.put(name, ext)
extensions.put("준호", "내선 120") # 같은 키로 다시 넣으면 바꾸기
print("준호:", extensions.get("준호"))
for i, bucket in enumerate(extensions.buckets):
print(f"{i}번 칸: {bucket}")
준호: 내선 120
0번 칸: [['준호', '내선 120'], ['도윤', '내선 310']]
1번 칸: []
2번 칸: []
3번 칸: []
4번 칸: [['민지', '내선 101'], ['서연', '내선 205']]
5번 칸: []
6번 칸: []
7번 칸: []
네 명을 넣었는데 0번 칸과 4번 칸에 둘씩 모였어요. 충돌이 났지만 같은 칸의 목록 안에서 키를 비교해 찾으니 답은 정확해요. "준호"를 다시 넣었을 때는 새로 추가하지 않고 값만 바꿨어요. 딕셔너리에 같은 키로 넣으면 덮어쓰는 것과 같아요.
get이 하는 일을 보면 왜 빠른지 알 수 있어요. 칸 번호 계산 한 번, 그 칸의 목록 훑기 몇 번이에요. 칸마다 목록이 짧게 유지된다면 키가 100만 개여도 찾는 데 드는 비교는 몇 번뿐이에요.
충돌은 생각보다 빨리 와요
칸이 넉넉하면 충돌이 드물 것 같지만 그렇지 않아요. 확률과 통계 트랙에서 계산한 생일 문제와 같은 이야기예요.
def collision_chance(n, m): # m칸에 n개를 무작위로 넣을 때 한 번이라도 겹칠 확률
p_none = 1.0
for i in range(n):
p_none *= (m - i) / m
return 1 - p_none
print(f"365일에 23명: {collision_chance(23, 365):.1%}")
print(f"칸 1,000개에 40개: {collision_chance(40, 1_000):.1%}")
print(f"칸 100만 개에 1,200개: {collision_chance(1_200, 10**6):.1%}")
365일에 23명: 50.7%
칸 1,000개에 40개: 54.6%
칸 100만 개에 1,200개: 51.3%
23명만 모여도 생일이 겹치는 사람이 있을 확률이 절반을 넘어요. 칸 1,000개에 40개만 넣어도, 100만 칸에 1,200개만 넣어도 마찬가지예요. 대략 칸 수의 제곱근 정도만 넣어도 충돌이 한 번쯤은 난다고 보면 돼요. 그러니 충돌을 없애려 하기보다 충돌이 나도 짧게 끝나게 만드는 게 목표예요.
충돌을 처리하는 방법은 크게 두 가지예요.
- 체이닝: 위에서 만든 방식이에요. 같은 칸에 온 것들을 목록으로 이어 둬요. 자바의
HashMap이 이 방식이고, 한 칸의 목록이 너무 길어지면 트리로 바꿔서 최악을 줄여요. - 개방 주소법: 칸마다 하나만 담고, 이미 차 있으면 정해진 규칙에 따라 다른 빈칸을 찾아가요. 파이썬의 딕셔너리와 집합이 이 방식이에요. 목록을 따로 만들지 않아서 메모리를 아끼고, 이어진 배열 안에서 움직이니 캐시에도 유리해요.
붐비면 칸을 늘려요
칸 수에 비해 키가 많아지면 목록이 길어지고 느려져요. 그래서 키의 수를 칸 수로 나눈 값, 즉 부하율이 기준을 넘으면 칸을 두 배로 늘려요. 위의 HashTable은 0.75를 넘으면 늘리게 했어요.
table = HashTable()
sizes = []
for i in range(1, 13):
table.put(f"key{i}", i)
sizes.append(len(table.buckets))
print("넣은 개수별 칸 수:", sizes)
넣은 개수별 칸 수: [8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16]
7개째를 넣자 부하율이 7/8, 즉 0.875가 되어 기준을 넘었고 16칸으로 늘었어요. 이때 중요한 점은 모든 키를 다시 넣어야 한다는 거예요. 칸 번호가 "해시 값을 칸 수로 나눈 나머지"라서, 칸 수가 바뀌면 키마다 자리도 바뀌거든요. 그래서 늘리는 그 순간은 O(n)이지만, 두 배씩 늘리니 드물게 일어나요. 복잡도 강의의 분할 상환 그대로 넣기 한 번은 평균 O(1)이에요. 파이썬 딕셔너리는 3분의 2쯤 차면 늘리고, 자바의 HashMap은 기준의 기본값이 0.75예요.
해시 함수가 나쁘면
해시 테이블의 속도는 해시 함수가 키를 칸에 얼마나 고르게 흩어 주느냐에 달려 있어요. 길이만 보는 나쁜 해시와 비교해 볼게요.
def length_hash(key): # 길이만 보는 나쁜 해시
return len(str(key))
keys = [f"user{i}" for i in range(4_000)]
for label, func in [("글자를 섞는 해시", text_hash), ("길이만 보는 해시", length_hash)]:
t = HashTable(hash_func=func)
for k in keys:
t.put(k, True)
t.compares = 0
for k in keys:
t.get(k)
used = sum(1 for b in t.buckets if b)
longest = max(len(b) for b in t.buckets)
print(f"{label}: 칸 {len(t.buckets):,}개 중 {used:,}개 사용, 가장 긴 칸 {longest:,}개, 찾기 한 번에 평균 {t.compares / len(keys):,.1f}번 비교")
글자를 섞는 해시: 칸 8,192개 중 2,767개 사용, 가장 긴 칸 4개, 찾기 한 번에 평균 1.4번 비교
길이만 보는 해시: 칸 8,192개 중 4개 사용, 가장 긴 칸 3,000개, 찾기 한 번에 평균 1,227.8번 비교
칸은 똑같이 8,192개로 늘었지만, 길이만 보는 해시는 그중 4칸만 써요. "user0"부터 "user3999"까지 길이가 5, 6, 7, 8 네 가지뿐이니까요. 길이가 8인 3,000개가 한 칸에 몰려서 찾기 한 번에 평균 1,228번을 비교해요. 사실상 리스트를 처음부터 훑는 O(n)이에요. 칸을 아무리 늘려도 소용없어요. 좋은 해시 함수는 이런 성질을 갖춰요.
- 같은 키에는 언제나 같은 값을 내요. 그래야 넣은 자리에서 다시 찾아요.
- 비슷한 키도 멀리 흩어 놓아요. "user1"과 "user2"가 한 칸에 몰리면 안 돼요.
- 빨라요. 넣고 찾을 때마다 계산하니까요. 보안 트랙에서 본 SHA-256 같은 암호용 해시는 되돌리기 어렵게 만드는 데 공을 들인 만큼 계산이 무거워요. 해시 테이블에는 그런 보장보다 빠르고 고르게 흩는 해시가 맞아요.
일부러 충돌시키는 공격
해시 함수가 좋아도, 공격자가 그 함수를 안다면 일부러 같은 칸에 몰리는 키를 수만 개 만들어 보낼 수 있어요. 웹 서버는 요청의 폼 값이나 JSON을 딕셔너리로 읽으니, 요청 몇 개로 서버를 O(n²)의 늪에 빠뜨릴 수 있어요. 2011년에 여러 언어의 웹 프레임워크가 이 해시 충돌 공격(해시 플러딩)에 한꺼번에 노출됐어요. 그래서 파이썬은 문자열 해시에 실행할 때마다 새로 뽑는 비밀 값을 섞어요.
import subprocess
import sys
def hash_in_new_process(text):
code = f"print(hash({text!r}))"
return subprocess.run([sys.executable, "-c", code], capture_output=True, text=True).stdout
print("새로 실행할 때마다 hash('민지')가 같나요?", hash_in_new_process("민지") == hash_in_new_process("민지"))
print("정수 hash(42)는요?", hash_in_new_process(42) == hash_in_new_process(42))
새로 실행할 때마다 hash('민지')가 같나요? False
정수 hash(42)는요? True
프로그램을 새로 실행할 때마다 hash('민지')가 달라져요. 비밀 값을 모르는 공격자는 어떤 문자열끼리 충돌할지 미리 계산할 수 없어요. 반면 정수의 해시는 그대로예요. 여기서 실용적인 교훈이 하나 나와요. hash()의 결과를 파일에 저장하거나 다른 프로그램과 주고받으면 안 돼요. 다음 실행에서는 다른 값이 나오니까요. 늘 같은 값이 필요하면 hashlib의 SHA-256 같은 함수를 써요.
키가 될 수 있는 것
해시 테이블이 제대로 동작하려면 키가 지켜야 할 약속이 있어요. 서로 같은(==) 키는 해시 값도 같아야 하고, 넣은 뒤에는 키가 바뀌지 않아야 해요.
print("1, 1.0, True를 키로 넣으면:", {1: "정수", 1.0: "실수", True: "참"})
try:
teams = {["민지", "준호"]: "1조"}
except TypeError as e:
print("리스트를 키로 쓰면:", type(e).__name__)
print("튜플은 돼요:", {("민지", "준호"): "1조"})
1, 1.0, True를 키로 넣으면: {1: '참'}
리스트를 키로 쓰면: TypeError
튜플은 돼요: {('민지', '준호'): '1조'}
- 1, 1.0, True는 파이썬에서 서로 같고(
1 == 1.0 == True) 해시 값도 같아서 한 키로 취급돼요. 처음 넣은 키 1이 남고, 값은 마지막에 넣은 "참"으로 덮였어요. - 리스트는 내용을 바꿀 수 있어서 키가 될 수 없어요. 오류 메시지에 unhashable, 즉 해시할 수 없다는 말이 나와요. 내용이 바뀌지 않는 튜플은 돼요.
직접 만든 클래스는 __hash__를 정의하면 키로 쓸 수 있어요. 그런데 넣은 뒤에 키의 내용을 바꾸면 어떻게 될까요?
class Point:
def __init__(self, x, y):
self.x, self.y = x, y
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
def __hash__(self):
return hash((self.x, self.y))
p = Point(1, 2)
visited = {p}
p.x = 5 # 넣은 뒤에 키의 내용을 바꾸면
print("p가 집합에 있나요?", p in visited)
print("하나씩 훑어보면 들어 있긴 한가요?", any(q is p for q in visited))
p가 집합에 있나요? False
하나씩 훑어보면 들어 있긴 한가요? True
p는 분명 집합 안에 있는데 in은 False라고 해요. p를 넣을 때는 (1, 2)의 해시로 자리를 정했는데, 지금은 (5, 2)의 해시로 다른 자리를 찾아보거든요. 그래서 키로 쓸 객체는 바꿀 수 없게 만들어요. 데이터 클래스라면 @dataclass(frozen=True)가 딱 그 용도예요. 참고로 __eq__만 정의하고 __hash__를 정의하지 않으면, 파이썬은 그 클래스를 해시할 수 없게 만들어요. 같은데 해시가 다른 상황을 막으려는 거예요.
해시 테이블로 푸는 문제
"본 적 있나?"를 O(1)로 물을 수 있다는 건 강력해요. 합이 딱 예산이 되는 두 상품을 찾는 문제를 볼게요. 모든 쌍을 보면 O(n²)이지만, 지나온 가격을 딕셔너리에 기억해 두면 한 번만 훑어도 돼요.
def two_sum(prices, budget): # 합이 딱 예산이 되는 두 상품 찾기
seen = {} # 가격 → 위치
for i, price in enumerate(prices):
need = budget - price
if need in seen: # 짝이 될 가격을 본 적 있나요?
return seen[need], i
seen[price] = i
return None
prices = [12_000, 7_500, 3_000, 15_500, 9_000, 4_500]
print("합이 16,500원인 두 상품의 위치:", two_sum(prices, 16_500))
print("합이 100원인 두 상품:", two_sum(prices, 100))
합이 16,500원인 두 상품의 위치: (1, 4)
합이 100원인 두 상품: None
7,500원을 지나며 기억해 두었다가, 9,000원을 만났을 때 "16,500원에서 9,000원을 뺀 7,500원을 본 적 있나?"를 한 번에 확인했어요. 전체가 O(n)이에요. 같은 원리로 개수 세기(Counter, 프로그래밍 기초 트랙), 같은 값끼리 묶기(defaultdict(list)), 중복 없애기(set), 계산 결과 기억해 두기(캐시, 재귀와 동적 계획법 강의)가 모두 해시 테이블 위에서 돌아가요.
해시 테이블이 못 하는 것
해시 테이블은 키를 일부러 흩어 놓아서 빨라요. 그래서 순서가 필요한 일에는 약해요.
- 범위 찾기: "점수가 80점에서 90점 사이인 학생"을 찾으려면 전부 훑어야 해요. 80과 81이 이웃한 칸에 있지 않으니까요.
- 가장 작은 값, 바로 다음 값 찾기: 역시 전부 훑어야 해요.
- 크기 순서로 꺼내기: 파이썬 딕셔너리는 넣은 순서를 기억하지만(3.7부터), 값의 크기 순서는 아니에요.
이런 일에는 정렬된 배열이나 트리를 써요. 데이터베이스가 인덱스를 기본적으로 B-트리로 만드는 이유도 범위 검색과 정렬이 필요해서예요. PostgreSQL처럼 해시 인덱스를 따로 제공하는 데이터베이스도 있지만 "같은 값 찾기"에만 쓸 수 있어요. 그리고 최악의 경우도 기억해 두세요. 해시 테이블의 O(1)은 평균이에요. 운이 나쁘거나 누군가 일부러 충돌시키면 O(n)까지 느려질 수 있어요.
실습
HashTable에 키를 지우는remove를 만들어 보세요. 지운 뒤get으로 찾으면KeyError가 나야 해요.- 부하율 기준을 0.75에서 3으로 바꾸고, 4,000개를 넣은 뒤 찾기 한 번의 평균 비교 횟수가 어떻게 달라지는지 보세요. 메모리와 속도를 어떻게 맞바꾸는 걸까요?
text_hash의 31을 1로 바꾸면 "ab"와 "ba"는 어떻게 될까요? 4,000개로 실험해 보세요.collision_chance로, 칸 100만 개에서 충돌 확률이 99%를 넘으려면 몇 개를 넣어야 하는지 찾아보세요.- 영어 단어 목록에서 철자 순서만 바꾼 단어(애너그램)끼리 묶어 보세요. 힌트:
"".join(sorted(word))를 키로 쓰는defaultdict(list).
자주 하는 실수
- 리스트에서 반복해서 찾는다.
in이나index로 계속 찾을 거라면 한 번 집합이나 딕셔너리로 바꿔 둬요. hash()값을 저장하거나 주고받는다. 문자열의 해시는 실행할 때마다 달라요. 늘 같은 값이 필요하면hashlib을 써요.- 넣은 뒤에 키를 바꾼다. 찾을 수 없게 돼요. 키는 바꿀 수 없는 값(문자열, 숫자, 튜플, frozen 데이터 클래스)으로 써요.
__eq__와__hash__가 따로 논다. 같다고 판단하는 기준과 해시를 계산하는 기준이 같아야 해요.- 해시 테이블로 범위를 찾는다. 정렬된 구조나 데이터베이스 인덱스를 써요.
- O(1)을 보장으로 믿는다. 평균이에요. 밖에서 들어온 키가 많다면 최악도 생각해요.
점검 문제
- 해시 테이블이 키로 값을 거의 한 번에 찾을 수 있는 이유는?
- 충돌이란 무엇이고, 왜 피할 수 없나요?
- 칸이 1,000개인데 키를 40개만 넣어도 충돌할 확률이 절반을 넘는 이유는?
- 체이닝과 개방 주소법은 충돌을 각각 어떻게 처리하나요? 파이썬 딕셔너리는 어느 쪽인가요?
- 칸 수를 늘릴 때 모든 키를 다시 넣어야 하는 이유는? 그런데도 넣기가 평균 O(1)인 이유는?
- 길이만 보는 해시 함수가 나쁜 이유는?
- 파이썬이 문자열 해시를 실행할 때마다 바꾸는 이유와, 그 때문에 조심할 점은?
- 리스트를 딕셔너리의 키로 쓸 수 없는 이유는?
정답
- 해시 함수로 키를 칸 번호로 바꿔서, 배열처럼 그 칸에 바로 가기 때문이에요. 칸마다 담긴 것이 몇 개 안 되게 유지하면 비교도 몇 번이면 끝나요.
- 서로 다른 키가 같은 칸 번호를 받는 거예요. 가능한 키의 종류가 칸 수보다 훨씬 많으니 비둘기집 원리에 따라 반드시 겹치는 키가 생겨요.
- 생일 문제와 같아요. 40개로 만들 수 있는 짝이 780쌍이나 되고, 그중 하나만 겹쳐도 충돌이에요. 대략 칸 수의 제곱근 정도만 넣어도 충돌이 한 번쯤은 나요.
- 체이닝은 같은 칸에 온 키들을 목록으로 이어 두고, 개방 주소법은 칸마다 하나만 담되 차 있으면 규칙에 따라 다른 빈칸을 찾아가요. 파이썬 딕셔너리는 개방 주소법이에요.
- 칸 번호가 해시 값을 칸 수로 나눈 나머지라서, 칸 수가 바뀌면 자리도 바뀌기 때문이에요. 두 배씩 늘려서 다시 넣기가 드물게 일어나니, 전체로 나누면 넣기 한 번은 평균 O(1)이에요.
- 길이가 같은 키가 모두 같은 칸에 몰리기 때문이에요. 칸을 아무리 늘려도 쓰는 칸은 몇 개뿐이라, 찾기가 리스트를 훑는 O(n)이 돼요.
- 공격자가 일부러 같은 칸에 몰리는 키를 만들어 보내는 해시 충돌 공격을 막으려고요. 그래서
hash()값은 저장하거나 다른 프로그램과 주고받으면 안 되고, 늘 같은 값이 필요하면hashlib을 써요. - 리스트는 내용을 바꿀 수 있어서, 넣은 뒤 내용이 바뀌면 해시 값도 바뀌어 다시 찾을 수 없게 되기 때문이에요. 바뀌지 않는 튜플은 키로 쓸 수 있어요.
다음 강의
해시 테이블은 "같은 것 찾기"에 강하지만 순서에는 약했어요. 다음 강의에서는 순서를 만드는 일, 정렬을 다뤄요. 선택 정렬과 삽입 정렬부터 병합 정렬과 퀵 정렬까지 직접 짜서 비교 횟수를 세어 보고, 정렬된 데이터에서 쓰는 이진 탐색을 제대로 다듬어요.