뻐꾸기 해싱: 뻐꾸기 알처럼 키를 밀어내어 조회를 상수 시간으로 만든 방법

표준 개방 주소 해시 테이블은 항목이 군집화되고 탐사 연쇄가 길어지면 성능이 저하된다. Rasmus Pagh와 Flemming Friche Rodler는 각 키가 하나가 아닌 정확히 두 개의 가능한 슬롯을 가진다면 어떤 일이 일어날지 물었다.

2001년 오르후스의 BRICS에서 발표된 그들의 사전은 두 개의 해시 함수와 두 개의 테이블을 사용한다. 충돌 시 도착한 키가 점유자를 밀어내고, 그 점유자는 자신의 다른 집으로 재귀적으로 이동한다. 조회는 최대 두 번의 탐사로 보장된다.

테이블은 평균적으로 약 절반만 채워져 있으면 되므로, 이 구조는 엄격한 최악의 경우 상수 조회를 제공하면서도 메모리 효율성을 유지한다.

모든 키에 두 개의 자리를 주고 패자를 재배치한다

두 개의 가능한 위치는 키 집합에 관계없이 탐색을 두 번의 탐사로 제한한다.

밀어내기는 긴 탐사 연쇄나 연결 리스트 없이 충돌을 해결한다.

높은 점유율을 유지하므로 메모리를 잘 활용하면서도 캐시 친화적이다.

평균뿐 아니라 최악의 경우에도 빠른 데이터 구조를 선택하라. 두 선택지 밀어내기는 드물고 비용이 큰 충돌을 제한된 두 번의 탐사 조회로 바꾼다.

뻐꾸기 해싱은 사전의 이론과 실제에서 참조 결과가 되었다. 상수 시간 보장과 캐시 지역성은 하드웨어 및 고성능 라우팅에 매력적으로 만들었고, 밀어내기 아이디어는 이후의 해시 및 스케칭 기법에 영향을 주었다.