Hopscotch Hashingを実装してみた

動機

数年前Cuckoo Hashingも知らないの？と友人から信じられないという目で見られた経験から、いつかCuckoo Hashingを超えるアルゴリズムを実装してやるという(考案してやるという程は高くない)野望を持っていました。そこで今回はHopscotch Hashingを実装してみました。

Herlihy, M., N. Shavit, and M. Tzafrir, “Hopscotch Hashing,” Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pp. 350-364, Arcachon, France, September 2008.

Hopscotch HashingはCuckoo Hashingと同様、定数時間での検索を可能にするハッシュテーブルのデータ構造です。 Cuckoo Hashingについては、ここや「日本語入力を支える技術」でも説明されている(らしい)ので詳細な説明は省略します。

Hopscotch HashingのCuckoo Hashingに勝るメリットは、高い充填率(ハッシュテーブル上の空き要素の数が少ないこと)でも高速に動作することらしいです。 (ただ、実装した限りでは、ハッシュ関数が悪いせいかあまり充填率を上げることができず、あまりメリットを感じられませんでした。) Hopscotch Hashingのアルゴリズムは、下記の通りです。

アルゴリズム

検索方法

Hopscotch Hashingでは、ハッシュテーブルを構成する各バケットにHop Informationと言われるビットマップの索引を持ちます。 Hop Informationは各バケットからH-1以内(Hは論文では32を指定)に、そのバケットのハッシュ番号を持つエントリが格納されてるかどうかを0/1のビットで保持します。

検索対象のキーは、キーから計算されたハッシュ値が指すバケットのH-1以内にあることが保証されているため、Hop Informationを元にH-1以内のエントリを調べるだけで必ず検索対象があるかないかを確認できます。これにより、最悪計算量がO(H)という定数時間での検索が可能となります。

キーからハッシュ値を計算して、ハッシュ値が指すバケットのHop Infromationを調べる
Hop Informationでフラグが立っているバケットに検索対象のキーが格納されているはずなので、そのバケットを検索する

Hを4とした場合に、検索アルゴリズムを図示した例は下記です。 (図1)

新規キーの挿入

「キーから計算されたハッシュ値が指すバケットのH-1以内に、検索対象のキーが格納されたバケットがある」という制約を保証するために、挿入する場合は少し複雑な処理が必要となります。 Cuckoo Hashing

キーからハッシュ値を計算して、ハッシュ値の指すバケットから、線形探索で未使用バケットを探索
未使用バケットがハッシュ値の指すバケットからH-1以内にあるならばそのバケットに挿入する
H-1より離れているならば、ハッシュ値に近い場所に空きバケットを作るため、未使用バケットに移動可能なバケットを調べ移動を繰り返す。
(移動可能なバケットを探す際に、Hop Informationがあるため、ハッシュ値を再計算する必要はない)
もしそのようなバケットが見つからなければ、ハッシュテーブルのサイズを変更して再度ハッシュを計算しなおす。

検索と同様Hを4とした場合の挿入アルゴリズムを図示した例を示します。 (図2)

(図3)

(図4)

結果

リサイズ部分の実装が適当だったためか、unordered_mapになかなか勝てず微妙な感じでしたが、ソースコードはこちらです。最初は実装も簡単で速度が早いが衝突しやすいハッシュ関数を使っていたのですが、あまりに衝突が多すぎたため結局unordered_mapで使われているハッシュ関数を利用することにしました。ハッシュ関数ってやはり大事ですね。。。ハッシュ関数さえあれば、C++03のunordered_mapが利用できない環境でもお手軽にそこそこ高速なハッシュテーブル実装を書けるというところがメリットであるように思います。

また、Hopscotch Hashingは並行処理可能なHashMapとしても考案されたものであるため、マルチスレッド環境下で本来の実力を発揮できるかと思いますが、今回はそこまで実験していません。今後の課題としたいと思います。

冒頭で書いたCuckoo Hashingについては、あまり詳しくないのですが、今でも研究されているようでたくさんの亜種が発生しているようです。(d-ary cuckoo hashingや、bucketize version Cuckoo Hashingなど) Hopscotch Hashingもその亜種の一つであると言えるでしょう。今回の実装を通じて、古典的アルゴリズムであるハッシュテーブルでさえ、今も研究され、日々進歩しているということを忘れないよう心に留めておく必要があると実感しました。