Stage 4: HashMap internals, lesson 11 of 13

HashMap internals 11: Treeification (Java 8+)

Advanced3 min read@since 16Code runs on your Java 25
Explain it forThe essentials plus production detail and pitfalls.

A long chain is slow: finding a key in a bucket of n nodes takes O(n). Java 8 fixed the worst case by turning crowded buckets into red-black trees, which take O(log n).

The rules, straight from the JDK source:

  • TREEIFY_THRESHOLD = 8. When a new node is added to a bucket that already holds 8 nodes, the bucket is treeified.
  • MIN_TREEIFY_CAPACITY = 64. If the table has fewer than 64 buckets, HashMap resizes instead, because spreading entries over more buckets usually fixes the crowding.
  • UNTREEIFY_THRESHOLD = 6. When a resize splits a tree bucket and a half ends up with 6 or fewer nodes, it goes back to a list. The gap between 6 and 8 stops buckets flip-flopping.

How the tree orders keys: by hash first. Keys with equal hashes are ordered with compareTo() if they're Comparable and of the same class, otherwise by a tie-breaker. So Comparable keys such as String get the most benefit.

With a decent hashCode(), trees almost never appear. They're a safety net against bad hash codes and attacks.

HashMap lab

Example

Java
// 16 different strings with the SAME hash code (each built from "Aa"/"BB" blocks)
List<String> keys = List.of("");
for (int i = 0; i < 4; i++) {
    keys = keys.stream().flatMap(k -> Stream.of(k + "Aa", k + "BB")).toList();
}
System.out.println(keys.stream().map(String::hashCode).distinct().toList());   // [-540425984]

Map<String, Integer> map = new HashMap<>(64);    // at least 64 buckets, so no "resize instead"
for (String k : keys) map.put(k, k.length());    // the 9th put finds 8 nodes in the bucket: treeify
System.out.println(map.get("BBAaBBAa"));         // 8   found by a tree search, not a list walk

Common mistake

Saying "a bucket becomes a tree at 8 entries". It only happens when adding to a bucket that already has 8 nodes, and only if the table has at least 64 buckets; otherwise HashMap resizes.

Under the hood

Tree nodes are roughly twice the size of normal nodes, which is why the thresholds are high. Treeification is also why deliberately colliding keys can't freeze a Java 8+ server the way they could with older HashMaps. In the lab below, try "Treeify demo" with a small table first: you'll see it resize to 32 and 64 before the bucket finally becomes a tree.

Check yourself

A bucket holds 8 colliding keys and the table has 16 buckets. What happens when a 9th colliding key is added?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.