カッコウハッシュ：カッコウの卵のように鍵を追い出すことで探索を定数時間にした

標準的な開番地法のハッシュ表は、項目がクラスタ化してプローブ列が長くなると性能が劣化する。Rasmus Pagh と Flemming Friche Rodler は、各鍵が1つではなくちょうど2つの可能なスロットを持つとしたらどうなるかを問うた。

2001年にオーフスで BRICS により発表された彼らの辞書は、2つのハッシュ関数と2つの表を用いる。衝突が起きると、到着した鍵が占有者を追い出し、追い出された鍵は自身のもう一方の住処へと再帰的に移動する。探索は最大2回のプローブで保証される。

表は平均しておよそ半分程度埋まっていればよいため、この構造はメモリ効率を保ちながら、最悪の場合でも厳密に定数時間の探索を提供する。

すべての鍵に2つの場所を与え、負けた方を移し替える

可能な位置が2つあることで、鍵の集合がどうであれ探索は2回のプローブに収まる。

追い出しによって、長いプローブ列や連鎖リストを使わずに衝突を解決する。

高い占有率を維持するため、メモリを有効に使いながらキャッシュにも優しい。

平均時だけでなく最悪時にも高速なデータ構造を選ぶこと。2択の追い出しは、まれで高コストな衝突を、上限のある2回プローブの探索へと変える。

カッコウハッシュは辞書の理論と実践における参照すべき成果となった。定数時間の保証とキャッシュ局所性により、ハードウェアや高性能ルーティングに適したものとなり、追い出しのアイデアはその後のハッシュやスケッチの方式に影響を与えた。