skip to content

What is bucket treeification in HashMap (Java 8+), and under what exact conditions does it happen?

level: seniorimportance: should knowfreq 55%

answer

  1. TREEIFY_THRESHOLD = 8, MIN_TREEIFY_CAPACITY = 64
  2. Both needed: 8 already there AND capacity>=64, else resize
  3. Tree: O(log n) if hashes differ or keys orderable
  4. UNTREEIFY_THRESHOLD = 6 at resize; remove tests tree shape
  5. Defense vs hash-flooding; rare under random hash codes

basics

~20 s

Since Java 8, HashMap can turn a crowded bucket's list into a red-black tree, to limit worst-case lookups. A put converts it when adding to a bucket already holding 8 entries, if the table has at least 64 buckets; otherwise it resizes.

solid answer

~50 s

Since Java 8, an overcrowded bucket can convert from a linked list to a red-black tree, giving worst-case O(log n) operations when keys have distinct hashes or are orderable. The trigger is TREEIFY_THRESHOLD = 8: `put` calls `treeifyBin` when adding to a bucket that already holds 8 nodes, so the ninth colliding key converts it; `computeIfAbsent`, `compute` and `merge` count differently and convert on the eighth. The guard is MIN_TREEIFY_CAPACITY = 64: on a smaller table `treeifyBin` resizes instead. Going back, a resize split returns a side with UNTREEIFY_THRESHOLD = 6 or fewer nodes to a plain list; `remove` tests the tree's shape, and an iterator's `remove` does not convert back. Keys need not be Comparable: hash ties use `compareTo` when the key's class declares Comparable of itself, and otherwise a class-name and identity-hash tie-break orders insertions, but a lookup among equal hashes then searches both subtrees, close to O(n).

go deeper

for a junior

Aware that overcrowded buckets can become trees for performance, without the exact constants.

for a middle

States the 8 / 64 / 6 constants and that treeification gives O(log n) per bucket when keys have distinct hashes or are orderable.

for a senior

Explains the dual condition (8 already in the bin AND capacity>=64), the resize-instead path, why removal ignores the 6, and the hash-flooding motivation.

for a principal

Frames treeification as a worst-case/DoS safety net within hashing design trade-offs and stresses that good hashCode design makes it irrelevant in practice.

## The problem treeification solves A HashMap bucket normally holds colliding entries as a **linked list** (a chain). Looking up a key in a chain is **O(n)** — you scan every node. Normally chains are tiny, but if many keys collide (bad hashCode, or a malicious attacker crafting colliding keys to mount a *hash-flooding* denial-of-service), one chain can grow huge and a single bucket lookup degrades to linear time. ## The fix: convert the chain to a red-black tree A **red-black tree** is a self-balancing binary search tree: it keeps its height proportional to log(number of nodes), so search/insert/delete are **O(log n)**. Since Java 8, when one bucket becomes badly overcrowded, HashMap replaces that bucket's linked list with a red-black tree of `TreeNode`s. The source promises worst-case O(log n) "when keys either have distinct hashes or are orderable". Only the offending bucket is treeified; the rest stay as lists. ## The exact conditions (the constants) - **TREEIFY_THRESHOLD = 8**: the source says bins convert "when adding an element to a bin with at least this many nodes". So `put` calls `treeifyBin` when the bin already holds 8. On JDK 27, a bin with one hash on a 64-slot table stays plain through the eighth `put` and becomes a `TreeNode` bin on the ninth. `computeIfAbsent`, `compute` and `merge` count the existing nodes differently and converted on the eighth new key. - **MIN_TREEIFY_CAPACITY = 64**: a guard. `treeifyBin` builds a tree **only if** the table has at least 64 buckets. On a smaller table it calls `resize()` instead. The source asks that this constant be at least 4 * TREEIFY_THRESHOLD "to avoid conflicts between resizing and treeification thresholds". Growing helps only keys whose hashes differ in the new index bit: a default map given keys with one hash stayed plain through 8 puts, grew to 32 on the ninth, to 64 on the tenth, and formed a tree on the eleventh. - **UNTREEIFY_THRESHOLD = 6**: this one applies during a resize. `TreeNode.split` divides a tree bin on the `oldCap` bit, and a side with 6 or fewer nodes becomes a plain list. A 6 + 6 split leaves two plain bins, and a 7 + 2 split leaves a tree and a plain bin. **Removal does not use that count.** On a `remove(key)`, `removeTreeNode` converts the bin back when the tree's shape looks too small: a missing child of the root, or a root's left child with no left child. Its comment says the test "triggers somewhere between 2 and 6 nodes, depending on tree structure". On JDK 27, removing keys from a 40-node bin in five shuffled orders turned it plain with 2, 3, 5, 5 and 7 nodes left, so no count is a promise here. `Iterator.remove` skips the test, because it passes `movable` as false: emptying the same bin through an iterator still left a tree with 1 node, and `entrySet().removeIf` left a tree of 3. The source's stated reason for the 6 is that it be at most 6 "to mesh with shrinkage detection under removal". The gap between 8 and 6 is no guard against flip-flopping: with nine distinct hashes in one bin, removing and re-adding one key converts the bin to a list and back on every cycle. ## Why tree bins are rare A `TreeNode` is about twice the size of a plain node, so the source uses trees "only when bins contain enough nodes to warrant use". Under random hash codes and load factor 0.75, it estimates bucket sizes with a Poisson distribution, and a list of length 8 gets an expected frequency of 0.00000006, six in a hundred million. With well-distributed hash codes, tree bins are "rarely used". They are a safety net for poor or adversarial hash codes. ## Ordering inside the tree A binary search tree needs to order its keys. HashMap first compares by **hash**. For keys with equal hashes it uses `Comparable.compareTo()` when the key's class has the form "class C implements Comparable<C>". `comparableClassFor` checks that by reflection, so a subclass that only inherits `Comparable` does not qualify. Otherwise inserts use `tieBreakOrder`, on class name and then `System.identityHashCode`, which the source calls "a consistent insertion rule" and not a total order. That rule keeps the tree well-formed but cannot steer a lookup. With equal hashes and no usable `compareTo`, `TreeNode.find` searches both subtrees. On JDK 27, 4,096 keys sharing one hash average about 2,049 `equals` calls per `get`, against about 12 when the class declares `Comparable` of itself. So you do not *need* Comparable keys for treeification to work, but without them equal hashes get no O(log n). ## Practical takeaways - Treeification bounds the worst case at O(log n) only when keys have distinct hashes or are orderable, and it is **not** a substitute for a good `hashCode()`: a proper hash avoids the crowding entirely. - It mitigates hash-flooding DoS on String-keyed maps, because `String` declares `Comparable` of itself. - Remember the pairing: a `put` treeifies a bucket already holding **8** (with capacity >= **64**), a resize split untreeifies a side of **6** or fewer, and `remove` goes by tree shape.

  • A bucket already holding 8 entries gains another while the map's capacity is only 32. What does HashMap do?
    It resizes (doubles capacity) instead of treeifying, because capacity is below MIN_TREEIFY_CAPACITY (64). That relieves the crowding for keys whose hashes differ in the new index bit. Keys sharing one hash stay together until the table reaches 64, when the bin can become a tree.
  • Do keys have to implement Comparable for treeification to work?
    No. The tree orders primarily by hash; for hash ties it uses compareTo if the key's class declares Comparable of itself, otherwise a tie-break on class name and identity hash that only keeps insertions consistent. Without that ordering, a lookup among equal hashes searches both subtrees, so it gets no O(log n).

  • Saying a bucket treeifies at 8 regardless of capacity (the 64 guard is required)
  • Claiming the whole map becomes a tree (only the crowded bucket does)
  • Thinking treeification replaces the need for a good hashCode
  • Saying removal untreeifies a bin at exactly 6 nodes (that count applies to a resize split)
  • Believing it exists in Java 7 (it is a Java 8 feature)
  • Claiming tree bins give O(log n) for any keys, even equal hashes with no Comparable ordering

HashMap balanced-tree bins
Java 1.8

Assumes JDK 27; tree bins shipped in Java 8 per JEP 180, and these HashMap paths read the same at JDK 25.

context