해시 테이블 — 딕셔너리의 원리

이 토픽을 마치면

해시 테이블이 어떻게 작동하는지 설명할 수 있고, Python 딕셔너리가 O(1) 검색을 달성하는 원리를 이해합니다.

문제: 100만 개에서 하나를 찾기

리스트에서 특정 값을 찾으려면 처음부터 하나씩 비교해야 합니다.

users = ["김훈", "이수", "박진", ...]  # 100만 명
"김훈" in users  # 최악 100만 번 비교 — O(n)

데이터가 10배 늘면 검색 시간도 10배 늘어납니다. 할 수 있는 방법이 없을까요?

해시 테이블은 데이터가 아무리 늘어도 검색 시간이 거의 일정한 자료구조입니다.

해시 함수 — 키를 주소로 변환

해시 테이블의 핵심 아이디어는 간단합니다: 키를 숫자(주소)로 변환해서, 그 주소에 바로 접근한다.

"김훈" → 해시 함수 → 427  → table[427]에 저장
"이수" → 해시 함수 → 12   → table[12]에 저장
"박진" → 해시 함수 → 891  → table[891]에 저장

도서관 비유가 적절합니다. 도서관에서 책을 찾을 때, 선반을 처음부터 훑지 않습니다. 분류 번호(청구기호)를 보고 해당 선반으로 바로 갑니다. 해시 함수가 바로 이 "분류 번호 부여기"입니다.

# Python 내장 해시 함수
hash("김훈")     # -4340382828924905128 (실행마다 다름)
hash("이수")     # 7421390584116839301
hash(42)         # 42 (정수는 자기 자신이 해시값)

# 테이블 크기로 나누어 인덱스 결정
index = hash("김훈") % 1000  # 0~999 범위의 인덱스

충돌 — 같은 주소에 두 개가 오면?

해시 함수가 다른 키에 같은 인덱스를 줄 수 있습니다. 이것을 충돌(collision) 이라고 합니다.

"김훈" → hash → 427
"최영" → hash → 427  ← 충돌!

해결 방법 중 가장 흔한 것이 체이닝(chaining) 입니다. 같은 인덱스에 연결 리스트를 만들어서 여러 항목을 담습니다.

table[427] → ("김훈", "010-1234") → ("최영", "010-5678")
table[12]  → ("이수", "010-9012")

충돌이 적으면 체인 길이가 1이라 O(1), 많으면 체인이 길어져서 느려집니다. 그래서 좋은 해시 함수는 데이터를 고르게 분산시키는 것이 중요합니다.

Python 딕셔너리 = 해시 테이블

Python의 dict는 해시 테이블로 구현되어 있습니다. 그래서 이런 성능이 나옵니다.

# 딕셔너리 — O(1) 검색
users = {"김훈": "010-1234", "이수": "010-5678"}
users["김훈"]     # 해시 계산 → 바로 접근 — O(1)
"박진" in users   # O(1)

# 리스트 — O(n) 검색
user_list = [("김훈", "010-1234"), ("이수", "010-5678")]
# "김훈"을 찾으려면 하나씩 비교 — O(n)

100만 건이든 1000만 건이든, 딕셔너리 검색은 거의 같은 시간이 걸립니다.

해시 테이블의 약점

만능은 아닙니다.

• 메모리 사용: 빈 슬롯을 미리 확보해야 하므로 리스트보다 메모리를 더 씁니다
• 순서 없음: 원래 해시 테이블은 삽입 순서를 보장하지 않습니다 (Python dict는 3.7부터 보장)
• 키 제약: 키는 불변(immutable) 이어야 합니다 — 문자열, 숫자, 튜플은 되지만 리스트는 키가 될 수 없습니다

# 리스트는 키로 사용 불가
d = {[1, 2]: "값"}  # TypeError: unhashable type: 'list'

# 튜플은 가능
d = {(1, 2): "값"}  # OK — 튜플은 불변이라 해시 가능

핵심 정리

해시 테이블은 "키 → 해시 함수 → 인덱스 → 바로 접근"이라는 단순한 원리로 O(1) 검색을 실현합니다. Python에서 dict를 쓸 때마다, 내부에서는 해시 함수가 돌고 있습니다. "이 데이터에서 뭔가를 자주 찾아야 한다"면, 리스트 대신 딕셔너리를 쓰는 것이 거의 항상 정답입니다.