GolangでHopscotch Hashingを実装してみた
※2017/8/13 タイトルにtypoがあったので修正しました。 [前]GolfingでHopscotch Hashingを実装してみた [後]GolangでHopscotch Hashingを実装してみた
前回のCuckoo Hashingの実装記事から少し間が空きましたが、今回はHopscotch Hashingを実装してみようと思います。
Hopscotch Hashingとは
テーブルのハッシュ衝突を解決する目的で、Mauriceらによって導入された手法です。 論文はこちら。
Hopscotch Hashingでは、各bucketにitemとbitmapを持ちます。
今回の実装では、以下のようにしています。
H
はビットマップの大きさです。
type bucket struct { item int64 bitmap [H]bool } type Hopscotch []bucket
item
は、Insert
、Lookup
、Delete
したい要素そのものです。
bitmap
は、ハッシュ値が衝突した場合に、そのbucketから見てからH-1
番目までに、その要素が存在するかを表します。
図にすると以下のようなイメージです。
itema
とitemb
が同じハッシュ値を持っていることを保証します。
この構造を維持することで、Lookup
はbitmap
が1
になっているところのitem
のみをチェックすればよいので、
計算量がO(H)
となります。
Delete
もLookup
して対象となるitem
があれば、それを削除し、対応するbitmap
を0
としてあげればよいので簡単です。
問題はInsert
ですが、次節に記載します。
Insertのアルゴリズム
Hopscotch Hashingでは、ハッシュ衝突後に、空いているbucketを線形探索で探し、その空きbucketを順々に最初のハッシュ値のindexからH-1
番目以内まで持ってくるということをします。
言葉だけではわかりづらいので図にすると以下のようになります。
空きbucketが見つからない場合は、サイズを大きくしてテーブルを作り直してあげる必要があります。 今回の実装では2倍ずつ増やすことにしました。
実装
以上を実装したものが以下になります。
gisteb0ae2b452b62984e8b54c6298321238
テストも含めて、githubにあげてあります。
実行
テーブルサイズを10、bitmap
のサイズを2として、1から10までを挿入してみます。
gist806d61d8cd2522a4a797838694069293
実行結果
----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {0 [false false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {3 [true false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {3 [true false]} 3 | {0 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {0 [false false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true false]} 2 | {3 [true false]} 3 | {0 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true true]} 2 | {6 [false true]} 3 | {3 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {1 [true true]} 2 | {6 [false true]} 3 | {3 [false false]} 4 | {2 [true true]} 5 | {4 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {7 [true false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {6 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} 10 | {0 [false false]} 11 | {1 [true true]} 12 | {8 [false true]} 13 | {3 [false false]} 14 | {4 [true false]} 15 | {0 [false false]} 16 | {0 [false false]} 17 | {0 [false false]} 18 | {0 [false false]} 19 | {7 [true false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {6 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} 10 | {0 [false false]} 11 | {1 [true true]} 12 | {8 [false true]} 13 | {3 [false false]} 14 | {4 [true true]} 15 | {9 [false false]} 16 | {0 [false false]} 17 | {0 [false false]} 18 | {0 [false false]} 19 | {7 [true false]} ----------------------------- No. | bucket ----------------------------- 0 | {0 [false false]} 1 | {6 [true false]} 2 | {0 [false false]} 3 | {0 [false false]} 4 | {2 [true false]} 5 | {0 [false false]} 6 | {0 [false false]} 7 | {0 [false false]} 8 | {5 [true false]} 9 | {0 [false false]} 10 | {0 [false false]} 11 | {1 [true true]} 12 | {8 [false true]} 13 | {3 [false false]} 14 | {4 [true true]} 15 | {9 [false true]} 16 | {10 [false false]} 17 | {0 [false false]} 18 | {0 [false false]} 19 | {7 [true false]}
item
として8を挿入しようとしたときにテーブルの作り直しが起こっています。
感想
Insert
の実装が思いの外、苦戦しました。添字のミスがないように一つ一つ確かめながら実装したので身には付いたかなと思います。
テーブルの作り直しもバグが入りがちで、ループになったり、挿入がされていなかったりで理解してから実装までが大変でした。