ツリー化とパフォーマンス
Java 8 以降の衝突処理を学びます。
「ツリー化とパフォーマンス」はCoddyKit上の無料Java Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。
衝突の問題
Java 8より前は、衝突が多いバケットが長い連結リストになっていました。そのバケットの検索は O(n) まで低下します。
攻撃者は、すべてが1つのバケットにハッシュされるよう細工したキーを使って、この仕組みを悪用し、サービス拒否を引き起こせました。
public class Main {
public static void main(String[] args) {
// All these strings can be made to collide in one bucket
System.out.println("FB".hashCode() == "Ea".hashCode());
}
}Java 8 のツリー化
Java 8 ではツリー化が追加されました。1つのバケットにエントリが多く格納されると、連結リストが平衡赤黒木に変換されます。
これにより、そのバケットの検索は O(n) ではなく O(log n) になります。
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < 1000; i++) m.put(i, i);
System.out.println("Lookups stay fast: " + m.get(742));
}
}しきい値：TREEIFY_THRESHOLD
定数 TREEIFY_THRESHOLD は8です。バケットのエントリ数が8に達すると、バケットはツリーに変換されます。
ただし、もう1つ条件があります。テーブルのサイズも MIN_TREEIFY_CAPACITY（64）以上でなければなりません。そうでなければ、マップが先にリサイズされます。
public class Main {
public static void main(String[] args) {
int TREEIFY_THRESHOLD = 8;
int MIN_TREEIFY_CAPACITY = 64;
System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
}
}まずリサイズし、その後でツリー化する
バケットがあふれてもテーブルがまだ小さい場合（64未満）、HashMap はまずテーブルをリサイズします。
通常、リサイズによってエントリが再分散され、負荷の集中が解消されます。そのため、ツリー化は本当にハッシュ分布が悪い場合の最後の手段にすぎません。
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<Integer, Integer> m = new HashMap<>(16);
for (int i = 0; i < 50; i++) m.put(i, i);
// Many resizes happened before any treeify would
System.out.println("size = " + m.size());
}
}ツリー解除
ツリーは永続的なものではありません。削除によってバケットのエントリ数が UNTREEIFY_THRESHOLD（6）未満になると、ツリーは連結リストに戻ります。
8（ツリー化）と6（ツリー解除）の間に差を設けることで、境界付近で何度も行き来することを防ぎます。
public class Main {
public static void main(String[] args) {
System.out.println("TREEIFY_THRESHOLD = 8");
System.out.println("UNTREEIFY_THRESHOLD = 6");
System.out.println("Gap prevents flip-flopping at the edge");
}
}ツリーには Comparable または同一性による順序が必要です
赤黒木では、エントリに順序を付ける必要があります。HashMap はまずハッシュコードを比較し、同じ場合はキーが Comparable を実装していればそれを使います。そうでなければ、クラス名とオブジェクトの同一性にもとづく安定したタイブレークを使います。
Comparable であるキー（String や Integer など）は、最もわかりやすいツリーの順序を提供します。
public class Main {
public static void main(String[] args) {
System.out.println("String is Comparable: " + ("a" instanceof Comparable));
System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
}
}実際の影響
適切なハッシュコードを使うほとんどの実際のプログラムでは、ツリー化を目にすることはまずありません。バケットは短いままです。
ツリー化はセーフティネットとして機能し、ハッシュが不適切または攻撃的な入力によって悪化した場合でも、最悪時の検索を O(log n) に抑えます。
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, Integer> m = new HashMap<>();
m.put("alpha", 1);
m.put("beta", 2);
m.put("gamma", 3);
// Tiny buckets, plain linked lists, no trees needed
System.out.println(m.get("beta"));
}
}定数 hashCode はツリー化を引き起こします
意図的に定数の hashCode を返すと、すべてのキーが1つのバケットに入ります。容量が64以上になると、そのバケットがツリー化されます。
これはセーフティネットの仕組みを示す例ですが、設計上の問題です。代わりに hashCode を修正してください。
import java.util.HashMap;
import java.util.Map;
public class Main {
static class Bad implements Comparable<Bad> {
final int v;
Bad(int v) { this.v = v; }
@Override public int hashCode() { return 1; } // forces collisions
@Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
@Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
}
public static void main(String[] args) {
Map<Bad, Integer> m = new HashMap<>();
for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
}
}ツリーのメモリコスト
ツリーノードは、親、左、右、色への参照を保持するため、通常の連結リストのノードより大きくなります。
これも、ツリー化がデフォルトではなくフォールバックである理由の1つです。ツリーは最悪時の速度と引き換えにメモリを消費します。
public class Main {
public static void main(String[] args) {
System.out.println("Node: hash, key, value, next");
System.out.println("TreeNode: + parent, left, right, prev, red flag");
System.out.println("=> trees cost more memory per entry");
}
}ツリー化を避ける方法
ツリー化に頼る必要はほとんどありません。次の方法で避けてください：
- 分布のよい
hashCode()を実装します。 - キーには組み込み型またはレコードを使います。
- マップの容量をあらかじめ確保して、衝突を減らします。
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public class Main {
record Key(int a, int b) {}
public static void main(String[] args) {
Map<Key, Integer> m = new HashMap<>(256);
for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
}
}パフォーマンスのまとめ
HashMap の操作コスト：
- 適切なハッシュ：平均 O(1)。
- 連結リストのバケット：バケットごとの最悪時は O(n)。
- ツリー化されたバケット：バケットごとに O(log n)。
ツリー化によって最悪時の計算量は抑えられますが、適切な hashCode を使えば O(1) のまま処理できます。
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<Integer, Integer> m = new HashMap<>(1 << 14);
for (int i = 0; i < 10000; i++) m.put(i, i);
System.out.println("10k entries, O(1) get: " + m.get(9999));
}
}理解度チェック
ツリー化についての知識を確認してください。
まとめ
現在の HashMap が衝突を処理する方法を学びました：
- 容量が64以上の場合、エントリが8個になるとバケットがツリー化されます。
- ツリーにより、最悪時の検索がO(log n)になります。
- エントリが6個未満になると、バケットはツリー解除されます。
- 適切な hashCode を使えば、このセーフティネットが発動することはほとんどありません。
HashMap の内部構造コースを修了しました。
public class Main {
public static void main(String[] args) {
System.out.println("Treeification course complete");
}
}よくある質問
「ツリー化とパフォーマンス」レッスンは無料ですか？
はい。「ツリー化とパフォーマンス」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。
「ツリー化とパフォーマンス」で何を学びますか？
Java 8 以降の衝突処理を学びます。 ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Java Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「ツリー化とパフォーマンス」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このJava Academyレッスンでコードを書いて実行できますか？
はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- HashMap の仕組み
- equals/hashCode の契約
- hashCode の実装
- ツリー化とパフォーマンス