※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の実装が思いの外、苦戦しました。添字のミスがないように一つ一つ確かめながら実装したので身には付いたかなと思います。
テーブルの作り直しもバグが入りがちで、ループになったり、挿入がされていなかったりで理解してから実装までが大変でした。
