ハッシュは本当に遅いのか？いや、遅くない（反語）
この記事を簡潔にまとめた記事「ハッシュは二分木（ツリー）より速い」を掲載しました。（2008-08-04）
ハッシュと二分木（ツリー）*1では普通はハッシュの方が速いとされる（ハッシュは挿入、参照、削除の時間計算量がO(1)、二分木はO(log N)）。しかし、ハッシュは動作が複雑なため、実際はあまり二分木と速度が変わらないとも言われる。
それをC++で検証した記事を見つけた。結論は、二分木よりハッシュの方が遅いというものだ。
ハッシュは本当に速いのか? - S34
http://www.s34.co.jp/cpptechdoc/article/hash/
ハッシュは本当に遅いのか - 山に生きる
http://d.hatena.ne.jp/pmoky/20050502/1114966341
では、JavaのHashSetとTreeSet（またはHashMapやTreeMap）でも同じことが起こるのだろうかと思い、検証してみた。
データの数Nを、10000, 20000, ... , 640000と変化させて、そのときにかかったデータの挿入、参照、削除の時間を調べてみる。当然、データ数が多くなると繰り返しもそれだけ行われているわけで、1個あたりどれだけかかったのか、ということが重要なのでNで割った時間も計算する。
その結果が↓だ。
HashSetの結果
(挿入) hash(10000): 15 [ms], 1.5265906999999999 [ms/elements]
(参照) hash(10000): 6 [ms], 0.687322 [ms/elements]
(削除) hash(10000): 15 [ms], 1.5254732 [ms/elements]
(挿入) hash(20000): 13 [ms], 0.66115945 [ms/elements]
(参照) hash(20000): 7 [ms], 0.3906921 [ms/elements]
(削除) hash(20000): 10 [ms], 0.5364369 [ms/elements]
(挿入) hash(40000): 29 [ms], 0.7438585 [ms/elements]
(参照) hash(40000): 20 [ms], 0.522028625 [ms/elements]
(削除) hash(40000): 32 [ms], 0.8135810499999999 [ms/elements]
(挿入) hash(80000): 105 [ms], 1.3176360375 [ms/elements]
(参照) hash(80000): 93 [ms], 1.172062375 [ms/elements]
(削除) hash(80000): 125 [ms], 1.5711808250000001 [ms/elements]
(挿入) hash(160000): 163 [ms], 1.02348553125 [ms/elements]
(参照) hash(160000): 110 [ms], 0.690080725 [ms/elements]
(削除) hash(160000): 132 [ms], 0.82666058125 [ms/elements]
(挿入) hash(320000): 1011 [ms], 3.16175571875 [ms/elements]
(参照) hash(320000): 224 [ms], 0.700526359375 [ms/elements]
(削除) hash(320000): 263 [ms], 0.82408169375 [ms/elements]
(挿入) hash(640000): 2686 [ms], 4.198237834375 [ms/elements]
(参照) hash(640000): 481 [ms], 0.7527174375 [ms/elements]
(削除) hash(640000): 553 [ms], 0.86452459375 [ms/elements]
TreeSetの結果
(挿入) tree(10000): 14 [ms], 1.4922847 [ms/elements]
(参照) tree(10000): 15 [ms], 1.5876599 [ms/elements]
(削除) tree(10000): 24 [ms], 2.4928586999999998 [ms/elements]
(挿入) tree(20000): 25 [ms], 1.2912255499999998 [ms/elements]
(参照) tree(20000): 38 [ms], 1.9112065999999999 [ms/elements]
(削除) tree(20000): 42 [ms], 2.1247393 [ms/elements]
(挿入) tree(40000): 54 [ms], 1.368253525 [ms/elements]
(参照) tree(40000): 109 [ms], 2.7254651 [ms/elements]
(削除) tree(40000): 106 [ms], 2.664130475 [ms/elements]
(挿入) tree(80000): 117 [ms], 1.46314685 [ms/elements]
(参照) tree(80000): 313 [ms], 3.914603675 [ms/elements]
(削除) tree(80000): 303 [ms], 3.7911208 [ms/elements]
(挿入) tree(160000): 334 [ms], 2.09372804375 [ms/elements]
(参照) tree(160000): 718 [ms], 4.49078025625 [ms/elements]
(削除) tree(160000): 720 [ms], 4.50348263125 [ms/elements]
(挿入) tree(320000): 982 [ms], 3.068847609375 [ms/elements]
(参照) tree(320000): 1715 [ms], 5.360803540625 [ms/elements]
(削除) tree(320000): 1710 [ms], 5.346012028125 [ms/elements]
(挿入) tree(640000): 2017 [ms], 3.152671115625 [ms/elements]
(参照) tree(640000): 4580 [ms], 7.156315868750001 [ms/elements]
(削除) tree(640000): 4120 [ms], 6.437939825 [ms/elements]
おおおおおおおおお！！！！！
HashSetの方が速いじゃないか！！（参照、削除は）Nの影響も受けていないように見える（つまりO(1)）。一方TreeSetはNの増加に従って遅くなっている。その時間もO(log N)っぽい。教科書通りの結果だ。
とりあえずJavaではHashSetの方が速いようだ。
おいおい、ちょっと待った。HashSetだって挿入にかかった時間は長くなっていってるじゃないか。
そんな声が聞こえてきそうだか、これはHashSetの動作原理を考えれば当たり前だ。HashSetはデフォルトでは初期容量16、負荷係数0.75のハッシュテーブルを作成する。つまり、ハッシュテーブルのサイズが16で、ハッシュテーブルに16*0.75=12個分を超えるのデータが挿入されたら、ハッシュテーブルは2倍のサイズ（この場合は32）に拡張される。このときに、配列の生成、ハッシュの再計算などのコストが発生するわけだ。
この結果、「データ数が多い→テーブルの拡張がたくさん行われる→挿入は遅くなる」、ということになる。
挿入が遅いんじゃ、結局HashSetも大して変わらないんじゃないか。
そんなことはない。ハッシュテーブルの拡張を行わないようにするには次のようにすればいい。
Set set = new HashSet<String>(n * 4 / 3 + 1);
これで、ハッシュテーブルの初期容量がn*4/3に設定される。4/3をかけるのは、負荷係数を考慮してのことだ。こうしておけば、n個のデータが一切ハッシュの衝突を起こさずにハッシュテーブルに格納されたとしても、容量*0.75がnを超えることはない（4/3*0.75=1なので。+1してるのは、n*4/3が割り切れず切り捨てられたときのため）。
さて、ではこの設定(hash2とする）でHashSetの時間を計測してみると・・・。
HashSetの結果（テーブル拡張なし）
(挿入) hash2(10000): 12 [ms], 1.2928179 [ms/elements]
(参照) hash2(10000): 5 [ms], 0.5780344000000001 [ms/elements]
(削除) hash2(10000): 8 [ms], 0.8285130999999999 [ms/elements]
(挿入) hash2(20000): 12 [ms], 0.6072420000000001 [ms/elements]
(参照) hash2(20000): 8 [ms], 0.40608515 [ms/elements]
(削除) hash2(20000): 10 [ms], 0.506475 [ms/elements]
(挿入) hash2(40000): 24 [ms], 0.6130457749999999 [ms/elements]
(参照) hash2(40000): 20 [ms], 0.5092407 [ms/elements]
(削除) hash2(40000): 30 [ms], 0.759384225 [ms/elements]
(挿入) hash2(80000): 58 [ms], 0.7295305750000001 [ms/elements]
(参照) hash2(80000): 56 [ms], 0.7091613625 [ms/elements]
(削除) hash2(80000): 64 [ms], 0.8034331124999999 [ms/elements]
(挿入) hash2(160000): 119 [ms], 0.7443561249999999 [ms/elements]
(参照) hash2(160000): 147 [ms], 0.9210598 [ms/elements]
(削除) hash2(160000): 132 [ms], 0.82502280625 [ms/elements]
(挿入) hash2(320000): 253 [ms], 0.791681446875 [ms/elements]
(参照) hash2(320000): 224 [ms], 0.7015600093750001 [ms/elements]
(削除) hash2(320000): 272 [ms], 0.8514306624999999 [ms/elements]
(挿入) hash2(640000): 529 [ms], 0.8271747875 [ms/elements]
(参照) hash2(640000): 475 [ms], 0.7435184671875 [ms/elements]
(削除) hash2(640000): 567 [ms], 0.8864233281250001 [ms/elements]
速い！！なんて理想的な結果なんだ・・・。
こう考えると、一番最初に上げた二つの記事では、ハッシュへの挿入、削除を合計して時間を計算しているので、挿入時のハッシュテーブル再構築の負荷がハッシュのパフォーマンスを低下させているように思える（もしかするとC++固有の特性（最適化の結果、ライブラリの設計ミスなど）なのかもしれないが）。
結局、初期容量を的確に設定してやれば、時間計算量は教科書どおりハッシュはO(1)、二分木はO(log N)になるみたいだ（↓横軸はlogスケール。Hashは横ばい、Treeは直線的に増加しているのがわかる）。
結論。やっぱりハッシュは二分木よりも速い。
最後に、今回作成したプログラムを載せておく。
import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.TreeSet; public class HashVsTreeMain { public static void main(String[] args) { String typeName; typeName = "hash"; //typeName = "tree"; //typeName = "hash2"; for (int n = 10000; n < 1000000; n *= 2) { // setを生成。 Set<String> set; if ("hash".equals(typeName)) { // HashSetを生成。 set = new HashSet<String>(); } else if ("tree".equals(typeName)) { // TreeSetを生成。 set = new TreeSet<String>(); } else { // HashSetを、データ挿入時にテーブルの拡張が行われないように // 初期容量を設定して生成。 set = new HashSet<String>(n * 4 / 3); } // 挿入、参照、削除にかかる時間を表示。 time(set, typeName, n); } } static void time(Set<String> set, String typeName, int n) { // 重複のないn個のランダムな文字列を生成して、stringListに格納する。 List<String> stringList = new ArrayList<String>(); Set<String> strings = new TreeSet<String>(); while (strings.size() < n) { strings.add(getRandomString(8)); } for (String string : strings) { stringList.add(string); } // 時間を計るための変数begin, endを生成。 long begin; long end; // 挿入にかかる時間を測定して表示。 begin = System.nanoTime(); for (String string : stringList) { set.add(string); } end = System.nanoTime(); System.out.print("(挿入) "); show(typeName, begin, end, n); // 挿入順に取り出すと平均的なパフォーマンスが得られない場合があるので // 一応stringListをシャッフルしておく。 Collections.shuffle(stringList); // 参照にかかる時間を測定して表示。 begin = System.nanoTime(); for (String string : stringList) { set.contains(string); } end = System.nanoTime(); System.out.print("(参照) "); show(typeName, begin, end, n); // 削除にかかる時間を測定して表示。 begin = System.nanoTime(); for (String string : stringList) { set.remove(string); } end = System.nanoTime(); System.out.print("(削除) "); show(typeName, begin, end, n); // 空行を表示。 System.out.println(); } // 長さlengthのランダムな文字列を生成して返す。 static String getRandomString(int length) { if (length > 0) { char[] chars = new char[length]; int digit; for (int charIndex = 0; charIndex < chars.length; charIndex++) { digit = (int) (26 * Math.random()); chars[charIndex] = (char) ('a' + digit); } return new String(chars); } else if (length == 0) { return ""; } else { throw new IllegalArgumentException(Integer.toString(length)); } } // 結果を表示 static void show(String type, long begin, long end, int n) { System.out.print(type); System.out.print("("); System.out.print(n); System.out.print("): "); System.out.print((end - begin) / 1000000); System.out.print(" [ms], "); System.out.print(((end - begin) / 1000.0) / n); System.out.println(" [ms/elements]"); } }
※実行環境: Windows XP, Pentium4 3.33GHz, JRE5.0
*1:JavaのTreeSet、TreeMapが用いているのは、正確にはRed-Black treeというアルゴリズムらしい。
