3.3.4 뻐꾸기 해싱

뻐꾸기 해싱(cuckoo hashing)은 완벽한 해싱 기법 중의 하나입니다. 앞에서 언급했던 방법들은 최악의 상황에서는 O(1)의 시간 복잡도를 보장하지 않지만 뻐꾸기 해싱은 구현만 제대로 한다면 O(1)을 만족합니다.

뻐꾸기 해싱은 크기가 같은 두 개의 해시 테이블을 사용하고, 각각의 해시 테이블은 서로 다른 해시 함수를 가집니다. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있으며, 그 위치는 해당 해시 테이블의 해시 함수에 의해 결정됩니다.

뻐꾸기 해싱이 이전에 설명한 해싱 기법과 다른 점은 다음과 같습니다.

앞서 언급한 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없습니다. 그러나 뻐꾸기 해싱 방법에서는 모든 원소가 두 개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있습니다. 더 나은 성능을 얻고 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가시킬 수도 있지만 이 책에서는 두 개의 해시 테이블을 사용하는 뻐꾸기 해싱 방법에 대해서만 알아보겠습니다.

룩업의 경우, 특정 원소가 존재하는지를 알기 위해 저장 가능한 위치 두 군데만 확인해보면 됩니다. 그러므로 룩업 연산의 시간 복잡도는 항상 O(1)입니다.