지식
Algorithm
해시 테이블 (Hash Table)
키-값 쌍을 O(1) 평균으로 저장·조회하는 해시 테이블의 구조, 충돌 해결 전략, Python dict 내부 동작까지 알아봅니다.
지난 글에서 정렬 데이터를 평균 O(log n)에 처리하는 스킵 리스트를 살펴봤습니다. 이번에는 더 빠른 O(1) 평균 탐색·삽입·삭제를 제공하는 해시 테이블(Hash Table)을 다룹니다. Python의 dict와 set, Java의 HashMap, JavaScript의 객체 리터럴 등이 모두 해시 테이블 기반입니다.
해시 테이블의 구조
해시 테이블은 해시 함수(hash function)로 키를 정수 인덱스로 변환해 배열의 해당 위치(버킷)에 값을 저장합니다.
인덱스 = hash(key) % capacity이상적인 경우 모든 연산이 O(1)이지만, 충돌(collision)이 발생하면 성능이 저하됩니다.
로드 팩터 (Load Factor)
로드 팩터 α = 저장된 원소 수 n / 배열 용량 capacityα가 높을수록 충돌이 잦아져 성능이 저하됩니다. 일반적으로 α < 0.75를 유지하며, 초과 시 rehashing(용량 2배 확장 + 전체 재삽입)을 수행합니다.
충돌 해결 전략
1. 체이닝 (Chaining)
같은 버킷의 원소들을 연결 리스트로 연결합니다.
class HashTableChaining:
def __init__(self, capacity=16):
self._cap = capacity
self._buckets = [[] for _ in range(capacity)]
self._size = 0
def _index(self, key):
return hash(key) % self._cap
def put(self, key, val):
idx = self._index(key)
for i, (k, v) in enumerate(self._buckets[idx]):
if k == key:
self._buckets[idx][i] = (key, val)
return
self._buckets[idx].append((key, val))
self._size += 1
if self._size / self._cap > 0.75:
self._resize()
def get(self, key):
for k, v in self._buckets[self._index(key)]:
if k == key:
return v
raise KeyError(key)
def _resize(self):
old_buckets = self._buckets
self._cap *= 2
self._buckets = [[] for _ in range(self._cap)]
self._size = 0
for bucket in old_buckets:
for k, v in bucket:
self.put(k, v)2. 개방 주소법 (Open Addressing)
충돌 시 다른 빈 슬롯을 탐사합니다.
class HashTableOpenAddressing:
DELETED = object() # tombstone
def __init__(self, capacity=16):
self._cap = capacity
self._slots = [None] * capacity
self._size = 0
def _probe(self, key, i):
"""선형 탐사: (h + i) % cap"""
return (hash(key) + i) % self._cap
def put(self, key, val):
for i in range(self._cap):
idx = self._probe(key, i)
slot = self._slots[idx]
if slot is None or slot is self.DELETED:
self._slots[idx] = (key, val)
self._size += 1
return
if slot[0] == key:
self._slots[idx] = (key, val)
return
raise OverflowError("해시 테이블이 가득 찼습니다")
def get(self, key):
for i in range(self._cap):
idx = self._probe(key, i)
slot = self._slots[idx]
if slot is None:
raise KeyError(key)
if slot is not self.DELETED and slot[0] == key:
return slot[1]
raise KeyError(key)
def delete(self, key):
for i in range(self._cap):
idx = self._probe(key, i)
slot = self._slots[idx]
if slot is None:
raise KeyError(key)
if slot is not self.DELETED and slot[0] == key:
self._slots[idx] = self.DELETED # tombstone
self._size -= 1
return
raise KeyError(key)Python dict의 내부 동작
Python 3.6+ dict는 개방 주소법 기반 해시 테이블입니다.
- 초기 capacity = 8
- 로드 팩터 임계값 = 2/3 (약 0.67)
- 삽입 순서 보장 (Python 3.7+)
# dict의 해시 테이블 특성 확인
d = {}
for i in range(100):
d[f"key_{i}"] = i
# 실제 크기는 가장 가까운 2의 제곱수
import sys
print(sys.getsizeof(d)) # 버킷 배열 크기 포함
# 해시 충돌 확인 (정수는 자기 자신이 해시값)
print(hash("hello")) # 고정되지 않음 (Python은 PYTHONHASHSEED 사용)
print(hash(42)) # 42
print(hash(42.0)) # 42 (42 == 42.0 이므로)복잡도 정리
| 연산 | 평균 | 최악 |
|---|---|---|
| 조회 get | O(1) | O(n) |
| 삽입 put | O(1) amortized | O(n) |
| 삭제 delete | O(1) | O(n) |
| 공간 | O(n) | O(n) |
최악 O(n)은 모든 키가 동일한 버킷으로 해시되는 경우지만, 좋은 해시 함수 사용 시 실용적으로 무시 가능합니다.
실전 팁
# 빈도 세기 — Counter 활용
from collections import Counter
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq = Counter(words)
print(freq.most_common(2)) # [('apple', 3), ('banana', 2)]
# defaultdict — 키 없을 때 기본값 자동 생성
from collections import defaultdict
graph = defaultdict(list)
graph[1].append(2)
graph[1].append(3)
print(dict(graph)) # {1: [2, 3]}
# 두 리스트의 교집합
a, b = [1, 2, 3, 4], [3, 4, 5, 6]
common = set(a) & set(b) # O(min(len(a), len(b)))정리
- 해시 테이블은 해시 함수로 키를 인덱스로 변환해 평균 O(1) 접근을 제공합니다.
- 로드 팩터 α < 0.75를 유지하는 것이 성능의 핵심입니다.
- 체이닝은 로드 팩터 1 이상도 허용하고, 개방 주소법은 캐시 친화적입니다.
- Python
dict는 개방 주소법 기반으로 삽입 순서를 보장합니다.
지난 글: 스킵 리스트
다음 글: 해시 함수
읽어주셔서 감사합니다. 😊