ハッシュは二分木（ツリー）より速い（ハッシュとツリーの速度比較）
ハッシュは遅いという意見があるようだが、実装や使い方を誤らなければ、基本的にツリーよりハッシュの方が速い。
（この記事は以前書いた「ハッシュは本当に遅いのか？いや、遅くない（反語）」を簡潔にまとめたものです）
ハッシュとツリーの速度を比較した結果が次のグラフだ（ハッシュはパラメータを適切に設定（後述））。挿入、参照（検索）、削除の合計時間を測定した。（横軸は要素数、縦軸は時間、横軸は対数スケール）
「ハッシュは本当に速いのか?」の検証
速いはずのハッシュが二分木にはかないません。ハッシュは速いという常識をくつがえす結果となりました。
http://www.s34.co.jp/cpptechdoc/article/hash/:itle=ハッシュは本当に速いのか?
Googleで「ハッシュ 速い」で検索すると上記のページが一番上に表示される（2008-08-04現在）。しかし、このページに掲載されている検証プログラムには問題がある。
次の部分では、データの挿入、削除をまとめて実行時間を測定している。
long tick = GetTickCount(); for ( i = 0; i < N; ++i ) c.insert(data[i]); for ( i = 0; i < N; ++i ) c.erase(data[i]); tick = GetTickCount() - tick;
そのため、ハッシュに要素を追加した際の、ハッシュテーブルの拡張にかかる時間がそのまま結果に反映されてしまっている。「テーブルの拡張にかかる時間もハッシュの性能のうち」という意見もありそうだが、それは違う。
ハッシュでは、ハッシュテーブルの初期容量を与えることができる*1。要素数がまったく検討がつかないというような状況でもない限り、ハッシュテーブルの拡張を最小限に抑えるように初期容量を設定すれば良い（冒頭で述べた適切な設定とはテーブルの拡張が起こらないように初期容量を設定すること）。
また、上記のページでは挿入と削除が一緒になって検証されているので、あたかもハッシュのすべての動作が遅いかのような印象を与えられる。しかし、削除や参照ではハッシュテーブルの拡張のような問題は起こらないため高速に動作する。
さらに、挿入と削除を繰り返すようなプログラムでは、一度大きなハッシュテーブルが構築された後は、要素数が際限なく増えることがない限り、以降の挿入ではテーブルの拡張が起こらない。つまり、この場合はプログラム実行初期の挿入は遅いが、それ以降の挿入は速いということになる。
要素が増えるとツリーは遅くなる。ハッシュは遅くならない。
冒頭のグラフを見ると、時間計算量がハッシュはO(1)*2、ツリーはO(log N)*3と、理論通りのきれいな結果となっていることがわかる。
つまり、要素が増えるにしたがってツリーは遅くなり、ハッシュは要素が増えても遅くならない。
検証はJavaのHashSetとTreeSetで行った。C++での結果への反論としてJavaで検証というのは不適切だという声が聞こえてきそうだが、JavaでO(1)を実現できているのに、C++でO(1)が実現できないとは考えにくい。
（検証プログラムや実験環境などの詳細は「ハッシュは本当に遅いのか？いや、遅くない（反語）」を参照）
結論:ハッシュは速い。初期容量と負荷係数を適切に設定する。
以上をまとめると次のとおり。
- ハッシュは基本的にツリーより速い
- ハッシュは初期容量を適切に設定しないと、テーブルの拡張によって挿入が遅くなることがある
- 挿入と削除を繰り返す場合はテーブルの拡張が起こらなくなるので、やがて挿入も速くなる
ハッシュのパフォーマンスが問題になるのは、ハッシュテーブルの容量（バケット数）が大きすぎるときに、全要素への繰り返し参照の速度が低下してしまう*4ことや、負荷係数を大きくしすぎて参照コストが増大してしまう*5ことだ。
結論:ハッシュは速い。ただし、ハッシュを使うときには初期容量と負荷係数を適切に設定することが重要だ。
（余談だが、「ハッシュ 速い」より「ハッシュ 早い」で検索した方が多くのページがヒットするのだが、「早い」は時間的に前であることを表す言葉なので、この場合は「速い」が適切ではないだろうか。）
