1. 導入
Java 8以降、HashMapはパフォーマンスの大幅な改善が行われました。特に、ハッシュ衝突が多発する状況下での検索速度低下を防ぐために導入されたのが「treeify threshold（ツリー化閾値）」です。本記事では、この仕組みがなぜ重要なのか、そして実務で避けるべき「ハッシュ値の偏り」について解説します。
2. 基礎知識
HashMapは内部的にバケット（配列）を持ち、キーのハッシュ値に基づいて要素を格納します。Java 7以前は、衝突した要素は連結リスト（Linked List）として保持されていました。しかし、特定のバケットに要素が集中すると、検索の計算量が最悪の場合 O(n) になり、パフォーマンスが著しく低下します。
Java 8では、同一バケット内の要素数が「8」を超えると、連結リストから「赤黒木（Red-Black Tree）」という平衡二分探索木へ構造を変換します。これにより、検索の計算量を O(log n) に改善しました。この切り替えの基準となる値が、定数 TREEIFY_THRESHOLD = 8 です。
3. 実装/解決策
実務において、ツリー化は自動的に行われるため、開発者が明示的にコードを書く必要はありません。しかし、重要なのは「ツリー化が頻発するような設計を避けること」です。ツリー化はメモリ消費を増やし、構造変換時のコストも発生します。
対策として、以下の3点を意識してください。
・hashCode()の適切な実装: 衝突を最小限にするため、フィールドの計算に素数を用いるなど、ハッシュの分散性を高める。
・HashMapの初期容量: 予測される要素数が明確な場合、コンストラクタで適切な初期容量を設定し、リハッシュ（再配置）を減らす。
・不変オブジェクトの使用: キーにはStringやRecordなどの不変オブジェクトを使用し、ハッシュ値が変化しないことを保証する。
4. サンプルプログラム
以下は、HashMapの挙動を理解するための基本的なコード例です。
import java.util.HashMap;
import java.util.Map;
public class HashMapDemo {
public static void main(String[] args) {
// 初期容量を指定してHashMapを生成（パフォーマンス向上の定石）
Map map = new HashMap<>(16);
// キーを投入
for (int i = 0; i < 10; i++) {
map.put("key" + i, "value" + i);
}
// 内部的にバケット数が8を超えると、以降のput/get操作で
// 必要に応じてツリー化が自動的にトリガーされる
System.out.println("Map size: " + map.size());
// 取得操作はO(1)〜O(log n)で高速に動作する
System.out.println("Result: " + map.get("key5"));
}
}
5. 応用・注意点
現場でよく陥る罠は「hashCodeが固定値を返すクラスをキーにしてしまうこと」です。これを行うと、すべての要素が単一のバケットに集まり、常にツリー化が発生します。これは「DoS攻撃の標的」にもなり得るため非常に危険です。
また、UNTREEIFY_THRESHOLD = 6 という値も存在します。これは、削除処理によって要素数が減った際、ツリーから連結リストへ構造を戻す閾値です。頻繁に要素の追加・削除が行われる環境では、この「構造変換の往復」がオーバーヘッドになる可能性があるため、極端なハッシュ衝突は避けるべきであると覚えておいてください。
コメント