Cuckoo Hashing은 Hash Table에서 발생하는 Collision을 처리하기 위한 해싱 기법입니다. 일반적으로 두 개 이상의 해시 함수를 사용하여 하나의 키가 여러 후보 위치를 가질 수 있도록 합니다.
h1(key)
h2(key)핵심 아이디어
새로운 키 A를 삽입한다고 가정합니다. h1(A) 위치가 비어 있다면 바로 저장합니다.
하지만 해당 위치에 B가 존재한다면 A가 그 위치를 차지하고 B는 자신의 다른 후보 위치로 이동합니다.
A 삽입
↓
B가 위치를 차지하고 있음
↓
A가 B를 밀어냄
↓
B가 다른 위치로 이동빈 공간을 찾을 때까지 이 과정이 반복될 수 있습니다.
검색
키를 검색할 때는 가능한 위치만 확인하면 됩니다.
h1(key)
h2(key)따라서 검색 시간 복잡도는 일반적으로 다음과 같습니다.
O(1)Cycle 문제
키 이동이 반복되면서 다음과 같은 Cycle이 발생할 수 있습니다.
A → B → C → A → B → C이를 방지하기 위해 실제 구현에서는 최대 이동 횟수를 제한합니다. 제한을 초과하면 Rehashing을 수행할 수 있습니다.
Rehashing
Rehashing에서는 새로운 해시 함수를 선택하거나 테이블 크기를 늘린 후 기존 데이터를 다시 삽입합니다.
시간 복잡도
| 연산 | 일반적인 복잡도 | |---|---| | Search | O(1) | | Delete | O(1) | | Insert | Expected O(1) | | Rehash | O(n) |
장점
- 매우 빠른 검색
- 확인해야 하는 위치의 수가 제한적임
- Bucket마다 Linked List가 필요하지 않음
- Lookup이 많은 시스템에 적합함
단점
- 삽입 과정이 상대적으로 복잡함
- Cycle이 발생할 수 있음
- Rehashing이 필요할 수 있음
- 해시 함수의 품질이 중요함
- 높은 Load Factor에서 삽입이 어려워질 수 있음
활용 분야
Cuckoo Hashing은 빠른 Lookup이 필요한 In-Memory 데이터 구조, Cache, 네트워크 시스템 및 고성능 검색 구조에 활용될 수 있습니다.
이 아이디어는 Cuckoo Filter라는 확률적 자료구조에도 사용됩니다. Cuckoo Filter는 Membership Query를 효율적으로 수행하며 Bloom Filter와 비교되는 경우가 많습니다.
결론
Cuckoo Hashing은 하나의 키에 여러 후보 위치를 제공하고 충돌 시 기존 키를 다른 위치로 이동시키는 독특한 Hash Collision 해결 방법입니다.
검색이 빠르고 예측 가능하다는 것이 가장 큰 장점이지만, 삽입 과정에서 Cycle과 Rehashing을 관리해야 한다는 점은 중요한 설계 요소입니다.