What is bucket treeification in HashMap (Java 8+), and under what exact conditions does it happen?
answer
- TREEIFY_THRESHOLD = 8, MIN_TREEIFY_CAPACITY = 64
- Both needed: 8 entries AND capacity>=64, else resize
- Red-black tree -> O(log n) worst case per bucket
- UNTREEIFY_THRESHOLD = 6 (hysteresis: 8 vs 6)
- Defense vs hash-flooding; 8 is statistically near-impossible by chance
basics
~20 sIn Java 8+, if too many keys collide into one bucket, HashMap turns that bucket's linked list into a balanced red-black tree so lookups in it become O(log n) instead of O(n). It happens when a bucket reaches 8 entries, but only if total capacity is at least 64.
solid answer
~50 sSince Java 8, a single overcrowded bucket can be converted from a linked list into a red-black tree to bound its worst-case lookup at O(log n) instead of O(n). The trigger is TREEIFY_THRESHOLD = 8: when a bucket gains its 8th entry, the map considers treeifying it. But there is a guard: if the table capacity is below MIN_TREEIFY_CAPACITY = 64, the map resizes instead of treeifying, because at small capacities a resize is the better fix for crowding. When entries are removed (e.g. during resize splits) and a tree shrinks to UNTREEIFY_THRESHOLD = 6 nodes, it reverts to a plain linked list. Treeification is a defense against worst-case collisions, including hash-flooding denial-of-service attacks where an attacker crafts keys that all collide. It requires keys to be Comparable for best ordering; otherwise the tree falls back to comparing by class name and identity hash for a stable tie-break.
go deeper
Aware that overcrowded buckets can become trees for performance, without the exact constants.
States the 8 / 64 / 6 constants and that treeification gives O(log n) per bucket.
Explains the dual condition (8 AND capacity>=64), the resize-instead path, hysteresis, and the hash-flooding motivation.
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. Lookups in that bucket then cost O(log n) instead of O(n). Only the offending bucket is treeified; the rest stay as lists. ## The exact conditions (the constants) - **TREEIFY_THRESHOLD = 8**: when a bucket's chain reaches 8 nodes, the map *wants* to treeify it. - **MIN_TREEIFY_CAPACITY = 64**: a guard. The map treeifies **only if** the overall table capacity is >= 64. If capacity is smaller, it calls `resize()` instead — at small sizes, growing the table (which re-spreads keys) is a cheaper, simpler remedy than building a tree. So: *bucket reaches 8 AND capacity >= 64 -> treeify; bucket reaches 8 AND capacity < 64 -> resize.* - **UNTREEIFY_THRESHOLD = 6**: the reverse direction. When a tree's node count drops to 6 or fewer (e.g. after removals or when a resize splits a tree across two buckets), it is converted back (**untreeified**) into a plain linked list, because tiny trees are not worth their overhead. The gap between 8 (treeify) and 6 (untreeify) is **hysteresis** — a deliberate buffer so a bucket hovering around the boundary does not flip back and forth repeatedly. ## Why 8? Under a good hashCode and load factor 0.75, bucket occupancy follows a Poisson distribution; the probability of a bucket reaching 8 entries by chance is astronomically small (~6 in ten million). So treeification effectively never triggers from ordinary data — it is a safety net for pathological or adversarial inputs. ## 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()` if the key type implements `Comparable`. If keys are not comparable (or compare equal), it uses a deterministic tie-break (`tieBreakOrder`) based on class name and `System.identityHashCode`, just to keep the tree well-formed. So you do not *need* Comparable keys, but the tree is cleaner when they are. ## Practical takeaways - Treeification bounds the worst case at O(log n) but is **not** a substitute for a good `hashCode()` — a proper hash avoids the crowding entirely. - It mitigates hash-flooding DoS on String-keyed maps. - Remember the pairing: treeify at **8** (with capacity >= **64**), untreeify at **6**.
- A bucket reaches 8 entries but 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). Resizing re-spreads keys and usually relieves the crowding.
- Do keys have to implement Comparable for treeification to work?No. The tree orders primarily by hash; for hash ties it uses compareTo if available, otherwise a deterministic tie-break on class name and identity hash. Comparable keys just give a cleaner ordering.
saying these in an interview costs you the question
- 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 untreeify happens at 8 (it is 6) or ignoring the hysteresis
- Believing it exists in Java 7 (it is a Java 8 feature)