最速のハッシュテーブルを求めて

概要

いまだにアクセスがあるようなので, 書いておこう.
ディクショナリ, ハッシュマップ, 連想配列は万能のデータ構造ではない.

TL;DR
自作のハッシュテーブルで最速のハッシュテーブル実装を目指しましょう.
速度は検索に重きを置きます.
私のハッシュテーブルの用途では, 一度要素が挿入されると,
以降ほとんど挿入・削除が行われないためです.
我慢できない人はこちら->GitHub

たーのしー！すごーい！ と入れといたら閲覧数上がるだろ？

ハッシュテーブル（連想配列）が万能のデータ構造と勘違いしているフレンズがたくさんいるらしい. おそらくJavascriptとPHPのせい.

自作ハッシュテーブルの共通事項は以下でしょうか.

• インメモリ, 内部は配列
• オープンアドレッシング

３つの手法を実装してみました.

C++の連想配列について

C++ STLの連想配列は仕様に基づいて実装されます. これがなかなか厳しい制限があります.

• std::map
  • キーについて緩い順序関係を持つこと
    • つまり, iterationした場合に常に決まった順序があります
    • 平衡木で実装されることが多い理由です
• std::unordered_map
  • 要素の追加・削除によって, 要素のポインタ値が変化しない
    • ptr = &map[0] などとした後で, 要素の追加・削除してもptrは安全にアクセスできます.

仕様を知っていると, 用途に従った, より高速な実装を作ることは簡単です. ここで挙げた実装が, C++のSTLより高性能になるのは当然のことなのです.

環境

Windows 10 Pro バージョン 1703(OSビルド 15063.296) 64bit版
Visual Studio 2017 Ver 15.1 (26403.3)
CPU: Intel Core i7-6700T
Memory: 16GB (DDR4)

実装の概要

Hash Map

これは良くみる実装なのだが, 名前があるのかわかりません.
配列のインデックスをポインタとして, チェイニングを実現します.
オープンアドレッシングではないよねこれ.

この手法では, その位置に値があるかのフラグを持ちますが,
ハッシュ値の一部とそのフラグを混ぜることで, キー比較を遅延します.
ハッシュ値の衝突したキーのリストをたどります.

検索時に剰余演算は入りません, リストをたどるだけです.
懸念点は, メモリを飛び回る可能性があるため,
キャッシュミスは頻発するかも？, という点です.
メモリオーバーヘッドは, リストの先頭位置, 次へのポインタ, 存在フラグです.
雑な検索時の図解は以下です.

追記

実装では削除した空きを, 空リストにつないだりするので, ほとんどの状況で安定したパフォーマンスが出せます.
C#の実装はこれ, 一時期勝とうと頑張ったが, アルゴリズムが同じなら簡単に勝てるはずがない.

Hopscotch Hashing

Wikipedia
衝突したハッシュ値をビットマップフラグとして, その挿入位置を保存する.
位置Nのビットマップが0101なら, N+0, N+2に衝突したハッシュ値のキーが入っているということです.
ビットマップの1ビットを使って, その位置の値存在フラグにしています.
ビットマップが32ビットなら, 31個の衝突を管理できます. 衝突が31個を超えるか, テーブルの容量がいっぱいになれば最初から作り直しです.
検索時, 31個の衝突しているキー値の位置をレジスタにロードすることができます.
メモリオーバーヘッドは, ビットマップフラグです.
雑な検索時の図解は以下です.
図の赤が衝突したハッシュの挿入位置フラグ, 橙が値存在フラグです.
検索時はフラグが立っている位置でキー値を比較します.
剰余演算は必要です.

検索時に剰余演算を削除する実装を作ってみたがいまいちだった.

Robin Hood Hashing

Wikipedia
オープンアドレッシングでは, ハッシュ値から計算した位置が衝突した場合, 何かしらの方法で空きを検索します.
その時, なるべくハッシュ値から計算した位置に近くなるように並べ替えを行います.
I Wrote The Fastest Hashtableを参考に, 空き探索回数を制限し,
その探索回数分配列を余分に確保することで, 検索時の剰余演算を回避します.
メモリオーバーヘッドは, 理想の位置からの差分(distance)です.
雑な検索時の図解は以下です. 検索時にdistanceは使っていません.

結果

実行順に, 挿入, 検索, 半分削除, 検索1を測定しました.
std::unordered_mapとGoogleによるdense_hash_mapを加えています.
見逃しがちなのが, 削除があった後の検索速度です. 実際の使用状況に合わせて手法を選択すべきです.
RAMが厳しく一度構築したならば二度と追加・削除が発生しない状況ならば, ソート済み配列と二分探索が最適解の場合があります.
以下の値の単位は秒(seconds)なのかな？.

挿入

要素数	HashMap	Hopscotch	RobinHood	std::unordered_map	dense_hash_map
1000	0.000505582	0.000797684	0.00137657	0.000276385	0.000513568
1000000	0.608226	0.656709	1.11795	0.530152	0.67575
10000000	6.45611	9.80924	17.0729	7.5429	10.7126

検索

要素数	HashMap	Hopscotch	RobinHood	std::unordered_map	dense_hash_map
1000	4.25938e-05	5.25857e-05	3.82906e-05	4.99602e-05	4.72616e-05
1000000	0.0900752	0.0999662	0.0850392	0.168663	0.140268
10000000	1.09523	1.22309	1.15553	1.89413	1.98454

半分削除

要素数	HashMap	Hopscotch	RobinHood	std::unordered_map	dense_hash_map
1000	4.40158e-05	4.70062e-05	4.14632e-05	7.45753e-05	3.59567e-05
1000000	0.10376	0.132645	0.141789	0.135515	0.120155
10000000	1.26347	2.39569	2.63628	1.82736	2.1392

検索1

要素数	HashMap	Hopscotch	RobinHood	std::unordered_map	dense_hash_map
1000	3.69779e-05	4.26667e-05	5.92591e-05	4.34325e-05	7.74198e-05
1000000	0.06701	0.0849617	0.137875	0.108052	0.176014
10000000	0.816175	0.935425	1.83026	1.22621	2.19176

まとめ

HashMapはメモリオーバーヘッドが大きいが, どのような操作も安定して速いです.

Hopscotchは検索は速いが, 挿入時空きがビットマップの範囲になければ,
遠くから移動してくる処理のため遅くなってしまうようです.

RobinHoodは存在するとわかっているものを探すのは最速ですが,
ないものを検索する場合に遅くなります.
全探索せずに計算を打ち切る分dense_hash_mapより速いのでしょう.

std::unordered_mapは小さいメモリ確保が多いでしょうが,
その点を気にする必要がないなら安定した性能だと思います.

今後, cygwin+g++で実行した場合にクラッシュする問題を解決する.
各実装もまだ改善の余地があるように思います.

追記

2017/05/24

RHHashMapのreplaceでコンストラクトにミスがあったため, 修正.

2019/12/07

std::unordered_mapは重複を許す仕様なので, 不公平です.

2020/07/17

Cuckoo Hashingも実は高速なのでは？と思っています.