Hopscotch Hashingとその他

Hopscotch Hashingに入れ換える.
簡単なテストでは, Google Dense HashMapより速いよう.

キーからハッシュ等で計算した最初の位置を, ハッシュ値と呼ぶことにする.
その位置に, その位置から後ろの同じハッシュ値のキーが入っている場所を,
ビットマップとして保存する.
4bitのビットマップで, 位置nのビットマップが
bitmap=0101
なら, n, n+2に, ハッシュ値nのキーが入っている.
・検索は, ビットマップのビット数先までしか検索しない.
  ビットマップだけで空かどうかわかる.
・挿入は, 適当にビットマップのビット数 x M倍先までしか空きを検索しない.
  論文ではM=8だそうです.
  空きの位置を, ビットマップの範囲に入るまで移動してくる.
・削除は, 通常のマップの削除処理に追加で,
  ハッシュ値と削除位置の差分からビットマップをクリアするだけ.
  削除フラグは必要なし. 空きフラグは必要.

Cuckoo Hashingというのも.
Open Addressingに対して, ビットマップという余計なデータがある.
メモリ効率は仕方がないが, 追加の操作がビットマップに対する操作なのがポイントなのだろう.
ビットマップサイズ4バイト, M=8の場合で32バイト,
64バイトのキャッシュラインなら平均的に8割ぐらいキャッシュラインに入る.

Google Codeが終了のお知らせ.
引っ越し先はGitHubでいいのだろうけど,
お金払って安心を買いたい.