Cuckoo Hashing
ハッシュテーブルからエントリーを検索する処理は,一般に定数時間で済むとされている。つまり,どんなにエントリーが増えても検索の速さは変わらない,ということ。データ構造の教科書には必ず載っていることだね。
でも実際には,ハッシュの衝突が起こった場合に,速度の低下が発生する可能性がある。例えば,一般的なチェイン法(オープンハッシュ)だと,衝突したエントリーに関して線形検索を行うことになるから,衝突が多ければ多いほど,定数時間からは遠のいてしまう。
この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing (カッコウ・ハッシング)は仕組みが面白い。こいつは,エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。
Cuckoo hashing では,2つのハッシュ関数と,2つのテーブルを用いる。ここでは,2つのハッシュ関数をそれぞれ h1, h2 として,2つのテーブルを T1, T2 としよう。
例として,ハッシュテーブルに x を挿入してみる。まず, T1 上の h1(x) が空いてるかどうかを調べる。
空いていれば,そこに x を入れてしまう。
空いてない場合はどうする? 例えば y が先に入っているとしよう。
そういう場合は, y を追い出して x を突っ込んでしまう。「x と y をスワップする」といった方がいいかもしれない。
次に,T2 上の h2(y) が空いてるかどうかを調べる。
空いていれば,そこに y を入れてしまう。
空いてない場合はどうするか? 例えば z が先に入っているとしよう。
そういう場合は, z を追い出して y を突っ込んでしまう。
そして,T1 上の h1(z) が空いてるかどうかを調べる。
空いていれば,そこに z を入れて,空いてなければ,それを追い出して z を入れて……というように,「先約がいたら追い出して,追い出されたやつをもう一方のテーブルに突っ込んで」という処理を,全部がどこかに納まるまで繰り返す。
こうしてできたテーブルでは, x は T1[h1(x)] か T2[h2(x)] のどちらかに入っていることが保証される。つまり,この2つを探すだけで,必ず x を見つけることができるというわけ。
挿入処理の擬似コードは以下のようになる。
この擬似コードを見てみると,ループ回数に制限を設けていることが分かると思う。「全部がどこかに納まるまで繰り返す」と書いたけれど,実は循環参照が生じると無限ループに陥ってしまう可能性があるんだ。だから実際には,適当な回数ループしてしまったら潔く諦めて,ハッシュ関数を取り替えたうえでテーブルの再構築を行うようにしている。この再構築のコストが cuckoo hashing における最大の弱点といえる。
……と,こんな感じの cuckoo hashing, 見ての通り挿入処理にかなりのクセがあるのだけれど,検索が必ず固定時間で終わるというのは面白い。ちょっと怖くて自分で使う気にはなれないけどね。なにかのときのために名前だけは覚えておくよ。