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

  • 7
    いいね
  • 0
    コメント

概要

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

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

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

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

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

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

環境

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

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

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

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

Hopscotch Hashing

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

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

Robin Hood Hasing

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

結果

実行順に, 挿入, 検索, 半分削除, 検索1を測定しました.
std::unordered_mapとGoogleによるdense_hash_mapを加えています.
以下の値の単位は秒(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でコンストラクトにミスがあったため, 修正.