cc-dict: ハッシュテーブル

ハッシュテーブルを実装してみた。
・cc-dict-0.0.3
チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。

ベンチマーク

一応、ベンチマークも取ったので載せておく。
比較対象はg++のunordered_mapとGoogleのsparse_hash_map及びdense_hash_map。
ベンチマークプログラムにはHash Table Benchmarksに記載のものを使用させてもらった*1。
※ 実行環境は Ubuntu-11.11-64bit / Intel(R) Core(TM) i7 CPU L 620 @ 2.00GHz。

このベンチマーク結果を見る限りは、特別性能が悪い、ということはなさそう*2。

*1:ただし以下の追加・修正を施した。
　1: 検索処理時間の計測の追加
　2: もともとは文字列のベンチマークではキーの型const char*が使用されていたのをstd::stringに変更(関連)
　3: 処理時間にキー配列を生成する時間も含まれていたので、キー配列は最初にまとめて生成しておき、その後から計時を開始するように修正

*2:ベンチマークデータが結構恣意的(連番 or 乱数)なので、必ずしも実データで同様の性能がでるかは分からないけど・・・