Hatena::ブログ(Diary)

Radium Software

About

Twitter

 | 

2008-05-31

Cuckoo Hashing

ハッシュテーブルからエントリーを検索する処理は,一般に定数時間で済むとされている。つまり,どんなにエントリーが増えても検索の速さは変わらない,ということ。データ構造の教科書には必ず載っていることだね。

でも実際には,ハッシュの衝突が起こった場合に,速度の低下が発生する可能性がある。例えば,一般的なチェイン法(オープンハッシュ)だと,衝突したエントリーに関して線形検索を行うことになるから,衝突が多ければ多いほど,定数時間からは遠のいてしまう。

この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing (カッコウ・ハッシング)は仕組みが面白い。こいつは,エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。

Cuckoo hashing では,2つのハッシュ関数と,2つのテーブルを用いる。ここでは,2つのハッシュ関数をそれぞれ h1, h2 として,2つのテーブルを T1, T2 としよう。

例として,ハッシュテーブルに x を挿入してみる。まず, T1 上の h1(x) が空いてるかどうかを調べる。

f:id:KZR:20080531234349j:image

空いていれば,そこに x を入れてしまう。

f:id:KZR:20080531234350j:image

空いてない場合はどうする? 例えば y が先に入っているとしよう。

f:id:KZR:20080531234351j:image

そういう場合は, y を追い出して x を突っ込んでしまう。「x と y をスワップする」といった方がいいかもしれない。

f:id:KZR:20080531234352j:image

次に,T2 上の h2(y) が空いてるかどうかを調べる。

f:id:KZR:20080531234353j:image

空いていれば,そこに y を入れてしまう。

f:id:KZR:20080531234354j:image

空いてない場合はどうするか? 例えば z が先に入っているとしよう。

f:id:KZR:20080531234355j:image

そういう場合は, z を追い出して y を突っ込んでしまう。

f:id:KZR:20080531234356j:image

そして,T1 上の h1(z) が空いてるかどうかを調べる。

f:id:KZR:20080531234357j:image

空いていれば,そこに z を入れて,空いてなければ,それを追い出して z を入れて……というように,「先約がいたら追い出して,追い出されたやつをもう一方のテーブルに突っ込んで」という処理を,全部がどこかに納まるまで繰り返す。

こうしてできたテーブルでは, x は T1[h1(x)] か T2[h2(x)] のどちらかに入っていることが保証される。つまり,この2つを探すだけで,必ず x を見つけることができるというわけ。

挿入処理の擬似コードは以下のようになる。

f:id:KZR:20080531234348p:image

この擬似コードを見てみると,ループ回数に制限を設けていることが分かると思う。「全部がどこかに納まるまで繰り返す」と書いたけれど,実は循環参照が生じると無限ループに陥ってしまう可能性があるんだ。だから実際には,適当な回数ループしてしまったら潔く諦めて,ハッシュ関数を取り替えたうえでテーブルの再構築を行うようにしている。この再構築のコストが cuckoo hashing における最大の弱点といえる。

……と,こんな感じの cuckoo hashing, 見ての通り挿入処理にかなりのクセがあるのだけれど,検索が必ず固定時間で終わるというのは面白い。ちょっと怖くて自分で使う気にはなれないけどね。なにかのときのために名前だけは覚えておくよ。

moritamorita 2008/06/01 09:34 Io で使われてるという話がありました。
足元でこっそり使われちゃうことはあるかも。
http://www.iolanguage.com/blog/blog.cgi?do=item&id=95
普通のハッシュというより perfect hashing の代替なんですね。

taostaos 2008/06/03 13:18 Cuckoo hashing、私はMonet DBという高速メモリDBの仕様を調べたときに偶然知りました。PDICTという名前でカラムデータの圧縮に使われるみたいです。
Super-Scalar Database Compression between
RAM and CPU Cache
http://homepages.cwi.nl/~heman/downloads/msthesis.pdf

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

 |