Unordered Map

個人的メモ

robin hood hashing のアルゴリズムはとても単純でこの Lecture pdf の説明が分かりやすかった(他にも (参考 3), (参考 4) を参照した). データの挿入時すでにバケットが埋まっていた場合, 愚直に空いているバケットを探索する linear probing と異なり, 今挿入しようとしているデータとすでにバケットに存在するデータとを比べて今挿入しようとしているデータのほうが本来のバケット位置との距離が大きかったら swap する, そうでなければそのまま探索を続ける. という操作を空いているバケットが見つかるまで繰り返す. イメージで言うと富の再分配的な感じで本来のバケット位置に近いデータが遠いデータにバケットを譲ってあげるというトリックが用いられている. こうすることで linear probing と各データの本来のバケット位置からの距離, つまり探索距離の総和は変化しないもののその分散が小さくなっている. robin hood hashing はキャッシュに乗りやすいのが高速になる $1$ つの要因で, 同じ資料に Cuckoo Hashing が紹介されていて理論計算量は良いものの, 明らかに $2$ つのテーブル間の移動においてキャシュミスが起きていてあまり速くならなさそうな気はする(ただ計算量解析はおもしろかった).
robin hood hashing の期待計算量はハッシュ関数が真にランダムの場合, $\O( \log \log n)$ となりより詳しい計算量解析(concentration など) については この論文 が参考になりそう(まだ読んでいない & 読む時間がない).
また delete の際にこのページにあるような backward shift を行うと実測が速くなるようなので採用させていただいた. 具体的には要素を削除した際に, その後に続くバケットを見てバケットが空もしくは本来のバケット位置にいるデータを見つけるまでの要素をすべて後ろに $1$ つシフトするということをする.
(細かい実装の話)
キャッシュミスを防ぐために違和感はあるが dist や hash を data ではなく bucket に紐付けるようにしている.
高速版の方はキャッシュに乗りやすいようなデータの持ち方をした結果イテレーターが普通の std::unordered_map などと異なりイテレーターの参照(*it)の型が pair<const _Key&, _Tp&> になっている. 普通は pair<const _Key, _Tp>&. あとイテレーターの pointer は使えないようにしているので高速版の場合は常に *it の形で用いる. for_each 文も使えない.
alignment 等を気にした結果 dist が short int だったり aligned_storage を用いたりなどしてあがいている. 本実装では頻繁に new が呼ばれるので, 領域確保にかかる時間を短縮するために通常の new ではなくあらかじめ領域確保をした配置 new を用いて実装している. あとバケットのサイズは $2$ べきにしています. $2$ べきだと % ではなく & でバケットの位置を計算できて高速になるので.
関数 maximum_distance() は現在のハッシュテーブルにおいて find の際の linear probing にかかる時間の最大値を求めていて, 速度がなぜか遅くなるみたいな場合はこれを用いることでハッシュの衝突がその原因になっているかどうかを確かめることができる. 先述のように真にランダムなハッシュ関数を用いた場合期待値 $\O (\log \log n)$ でまたばらつきも小さくなるので maximum_distance() はちゃんとしたハッシュ関数を用いていればとても小さくなる.