ハッシュは速いとは限らないという話2008/09/01こちらの話から。ハッシュは本当に速いのか?関数benchはintを要素の型とするコンテナに[0,N)の範囲のN個の要素を挿入/削除し、それに要する時間および要素1個あたりの時間を出力します。(snip)ハッシュ・コンテナは二分木に比べて複雑です。ハッシュ値を求め、その値に対応するスロットに要素を挿入します。必要に応じて全要素の再配置を行わなければならないこともあるでしょう。それに比べたら要素の比較を繰り返す二分木の方が速いという結果もうなずけます。衝突時のアルゴリズムとテーブルサイズがどんなもんなのか分からないと,性能評価ができないんですけれど,二分木よりも遅くなる場合ってのはあるみたいです。そうなのかもな......。極端な話,衝突時のアルゴリズムにチェイン法を使って,テーブルサイズを1にしたら,データ構造上リニアリンクと変わりません。ハッシュキーを計算する時間分だけ,むしろリニアサーチより遅くなる可能性すらあります。型のデータを格納するハッシュってのが,どういう場面で使われるのか,あまり想像できません。取るだけ,といった,シンプルなもんで済むんだと思います。テーブルサイズも2の冪乗にすると最速になるはず(剰余をビット演算で求められるから)。値が入るわけで,奇妙っちゃ奇妙なんですが。取ってとかいった処理をしているはず。整数を収めればいいだけのことに,余計なことをしているんだと思います。二分木は単純に来た値を比較しているだけなので,そりゃ速いわな......と。整数入れるなら,普通は二分木なんだろうね......と。ハッシュで効果的なのは,やはり任意の長さを持った文字列を格納する場合なんだと思います。どんな長さの文字列が来ても,一定の長さの値(ハッシュ空間)に圧縮することができるので,格納時にやってくる文字列そのものに注目する必要がありません。いうことで,ハッシュに限らず,どんなデータに対しても万能なデータ構造ってのはないわけで,賢く使い分けたいところです。こゆのは公式的に覚えるもんでもないし(ハッシュ=速いのように),それぞれのコンテナにも特性があったりします。データ構造とアルゴリズムの特性や,使用するパッケージの特性を十分踏まえなきゃね,という話でした。