The Minimum Capacity Requirement for Treeification
You'll learn why HashMap won't convert long collision chains to trees until the map reaches a certain minimum size.
Beyond Just Chain Length
In the previous lesson, you learned that HashMap converts a linked list to a red-black tree when a single bucket's chain reaches 8 elements (the TREEIFY_THRESHOLD). However, there's a second condition that must be met: the entire HashMap must have a capacity of at least 64 entries.
This constant is called MIN_TREEIFY_CAPACITY, and it's set to 64 in HashMap's implementation.
Why This Requirement Exists
Think of it like a doctor choosing between two treatments. When a bucket has 8 colliding elements, HashMap could either:
- Convert that bucket to a tree (complex operation)
- Resize the entire array (simpler, redistributes elements)
If your HashMap only has 16 buckets total and one bucket has 8 elements, the problem isn't really collision handling—it's that the map is too small! Resizing to 32 buckets will naturally spread those 8 elements across more buckets, likely solving the performance problem without the overhead of tree structures.
Trees add complexity: more memory per node, more complex traversal logic, and maintenance overhead. HashMap only uses them when resizing alone won't help—that is, when the map is already reasonably large (64+ capacity).
The Combined Condition
// Treeification only happens when BOTH conditions are true:
// 1. Bucket chain length >= 8 (TREEIFY_THRESHOLD)
// 2. HashMap capacity >= 64 (MIN_TREEIFY_CAPACITY)
// If capacity < 64, HashMap resizes instead of treeifying
Key Takeaway: Treeification requires both a long collision chain (8+ elements) AND a HashMap capacity of at least 64; smaller maps resize instead of creating tree bins.