tiny hash table

practice programming algorithm

Cでコードを書いているとハッシュテーブル*1が欲しくなることが多々あります。というわけで小さいのを書いてみました。

ハッシュテーブルについて

ハッシュテーブルは、あるキーをハッシュ関数を使ってマッピングし、それに対応する値を関連付けるためのデータ構造です。連想配列として使われたり、ハッシュマップと呼ばれたりもします。ハッシュ関数によってキーをインデックスに変換し（これをハッシュと呼ぶ）、それに対応する配列の要素（スロットまたはバケツと呼ばれる）に値を入れておきます。そこそこメモリを使いますが、その分高速に動作します。


探索において、木構造などの二分探索をベースとした実装では、キーの比較回数がlog2(N)となりますが、ハッシュテーブルでは大抵これよりも小さくなります。比較回数がこれよりも多くなるような状況、つまり衝突が多発する状況では、衝突が多発しないようなハッシュ関数を選択するか、バケツを大きくするか、木構造など二分探索をベースとした実装を用いるなどの回避策があります。ほぼWikipediaな内容ですみません。

thtblの特徴

  • ハッシュ関数は自分で用意する
  • キーバリューは分けずに自分で管理する
  • 内部にコピーを持たずにポインタによる参照のみ行う
  • 線形探査型(linear-probing)のオープンアドレス法(open-addressing)による衝突回避を行う
  • 多分環境依存しない
  • バケツが溢れそうでも自動伸長しない
  • バケツのサイズは素数ではなく2のNä¹—
  • 巡回や前要素削除が遅い

工夫したところ

オープンアドレス法だと、ポインタの管理とは別に、その値が「空」「削除済み」「使用中」を区別する必要があります。ポインタと他にマーキング用のデータを用意するのは面倒だしメモリも使いそうで嫌だったので、ポインタのアドレッシングの仕組みを利用してポインタのみで管理することにしました。大抵のOSでは、カーネルランドとユーザランドでそれぞれアドレス空間が分かれています。以下のページを見ると、大抵のOSではカーネルランドが大きい番地を占めていることが分かります。


というわけで、以下のように区別することにしました。私はカーネルランドで動作するものは書かないので。

  • 空 → NULL
  • 削除済み → 0xffffffff または 0xffffffffffffffffLLU
  • 使用中 → 上記以外


GNU hashtabというハッシュテーブルライブラリも似たようなことをしていて、mallocなどは1を返さないという前提の元に実装されています。小さい番地は大抵何らかのアプリのスタックが使っているので、確かにその前提はたいてい成立するんでしょうね。

実行結果

いくつかのハッシュ関数、いくつかのバケツの大きさで衝突させまくりで挿入だけベンチマークをとってみました。衝突率の低さだけが性能の決定的要素ではなく、比較関数のコストも重要な要素だよ、ということがよく分かる結果になっていますね。

128
string
searches: 128, collisions: 204 (1.593750%)
0.000243 [sec]
zackw
searches: 128, collisions: 416 (3.250000%)
0.000212 [sec]
FNV-1a
searches: 128, collisions: 51 (0.398438%)
0.000214 [sec]

1024
string
searches: 1024, collisions: 5048 (4.929688%)
0.001869 [sec]
zackw
searches: 1024, collisions: 1920 (1.875000%)
0.001591 [sec]
FNV-1a
searches: 1024, collisions: 503 (0.491211%)
0.001523 [sec]

8192
string
searches: 8192, collisions: 43510 (5.311279%)
0.013948 [sec]
zackw
searches: 8192, collisions: 51554 (6.293213%)
0.012849 [sec]
FNV-1a
searches: 8192, collisions: 3827 (0.467163%)
0.011939 [sec]

16384
string
searches: 16384, collisions: 849376 (51.841797%)
0.042020 [sec]
zackw
searches: 16384, collisions: 38040 (2.321777%)
0.024676 [sec]
FNV-1a
searches: 16384, collisions: 6266 (0.382446%)
0.024592 [sec]

32768
string
searches: 32768, collisions: 1692528 (51.651855%)
0.083191 [sec]
zackw
searches: 32768, collisions: 23370 (0.713196%)
0.047768 [sec]
FNV-1a
searches: 32768, collisions: 17951 (0.547821%)
0.049201 [sec]

65536
string
searches: 65536, collisions: 2047008 (31.234863%)
0.141463 [sec]
zackw
searches: 65536, collisions: 121870 (1.859589%)
0.098748 [sec]
FNV-1a
searches: 65536, collisions: 45944 (0.701050%)
0.100855 [sec]

1048576
string
searches: 1048576, collisions: 30468520 (29.057045%)
2.362834 [sec]
zackw
searches: 1048576, collisions: 3814406 (3.637701%)
1.755987 [sec]
FNV-1a
searches: 1048576, collisions: 515284 (0.491413%)
1.933815 [sec]

その他

実装にあたり参考にしたページなど。

*1:http://en.wikipedia.org/wiki/Hash_table