에듀테크 프로젝트 대시보드
쿠쿠 해싱 (Cuckoo Hashing)
보통의 해시 테이블은 충돌이 나면 체이닝(같은 칸에 연결 리스트)이나 개방 주소법(다음 빈 칸
찾기)으로 해결한다. 최악의 경우 조회가 O(n)까지 늘어질 수 있다.
쿠쿠 해싱은 다르게 생각한다 — 테이블 두 개와 해시 함수 두 개를 쓰고,
열쇠 하나는 정확히 두 칸 중 하나에만 살 수 있다. 조회는 항상 그 두 칸만 확인하면
끝이라 최악에도 O(1)이다. 대신 삽입할 때 자리가 차 있으면 거기 살던 열쇠를 둥지 밖으로
쫓아내고(뻐꾸기가 남의 알을 밀어내듯) 그 열쇠를 다른 테이블의 자기 자리로 보낸다.
연쇄적으로 쫓아내다 고리에 빠지면 새 해시 함수로 전체 재해싱한다.
아래는 크기 7짜리 테이블 두 개다. 파란 T1은
h1(k) = k % 7, 주황 T2는
h2(k) = (⌊k / 7⌋ + 2) % 7 을 쓴다. 새 열쇠는 먼저 T1의 자기 칸에 앉으려 하고,
이미 누가 있으면 그를 T2의 자기 칸으로 쫓아낸다. 거기도 차 있으면 또 쫓아내고… 이 연쇄를
따라가 보자.
체이닝이나 선형 탐사는 "운이 나쁘면" 여러 칸·여러 노드를 훑는다. 쿠쿠 해싱은 h1(key) 칸과 h2(key) 칸, 그 둘만 보고 없으면 없는 것이다. 그래서 조회·삭제가 상수 시간이 보장된다 — 라우터 하드웨어, 네트워크 스위치의 흐름 테이블처럼 "최악에도 빨라야 하는" 곳에서 쓰인다.
MAX_KICKS = 16 # 이 횟수를 넘기면 "고리에 빠졌다"고 판단 def lookup(key): if T1[h1(key)] == key: return True # 칸 1 if T2[h2(key)] == key: return True # 칸 2 return False # 최악에도 비교 2번 → O(1) def insert(key): for _ in range(MAX_KICKS): if T1[h1(key)] is None: # T1 자리 비었으면 앉는다 T1[h1(key)] = key; return key, T1[h1(key)] = T1[h1(key)], key # ★ 살던 놈을 쫓아내고 내가 앉는다 if T2[h2(key)] is None: # 쫓겨난 놈을 T2 자리로 T2[h2(key)] = key; return key, T2[h2(key)] = T2[h2(key)], key # T2도 차 있으면 또 쫓아낸다 rehash_with_new_hash_functions() # 고리 감지 → 전체 재구축 후 재삽입 insert(key)
50%를 넘어가면 고리가 자주 생겨 삽입이 급격히 느려진다. 해시 함수를 3~4개로 늘리거나 한 칸에 2~4개를 담는 버킷형 쿠쿠를 쓰면 90%+까지 올라간다.| 체이닝 | 개방 주소법(선형 탐사) | 쿠쿠 해싱 | |
|---|---|---|---|
| 조회 최악 | O(n) | O(n) | O(1) 보장 |
| 조회 평균 | O(1+α) | O(1) | 비교 ≤ 2 |
| 추가 메모리 | 포인터/노드 | 없음 | 테이블 2배 공간 |
| 삭제 | 쉬움 | tombstone 필요 | 쉬움 |
| 삽입 최악 | O(1) | O(n) | 재해싱(amortized O(1)) |
| 캐시 지역성 | 나쁨(포인터 추적) | 좋음 | 보통(두 곳 점프) |
정답은 없다. "조회가 절대 느리면 안 되고, 삭제도 자주 한다"면 쿠쿠 해싱, "메모리가 빡빡하다"면 개방 주소법, "구현이 간단해야 한다"면 체이닝이 무난하다.