The Treeification Threshold: TREEIFY_THRESHOLD = 8
What you'll learn: You'll discover the exact point at which HashMap converts a bucket's linked list into a tree structure for better performance.
The Magic Number: 8
In the previous lesson, you learned that HashMap can convert buckets from linked lists to trees when collisions pile up. But when exactly does this happen? The answer is defined by a constant in HashMap's source code: TREEIFY_THRESHOLD = 8.
When a single bucket accumulates 8 or more entries (meaning 8 or more keys have hashed to the same bucket), HashMap converts that bucket from a linked list into a balanced tree structure.
Why 8 Specifically?
This threshold represents a carefully chosen balance. With fewer than 8 entries, the overhead of maintaining a tree structure isn't worth it—linked lists are simpler and faster for small numbers of collisions. But once you reach 8 colliding entries, the O(n) lookup cost of scanning a linked list becomes painful enough that the O(log n) tree lookup becomes worthwhile.
The Conversion Process
Imagine a bucket that currently has 7 entries in a linked list. When you add an 8th key that hashes to the same bucket, HashMap triggers the treeification process:
- The linked list nodes are converted to tree nodes
- The tree is balanced for efficient searching
- Future lookups in that bucket now use tree traversal instead of linear scanning
This happens per bucket, not globally. Other buckets remain as linked lists until they also hit the threshold.
Key Takeaway: HashMap automatically converts a bucket from a linked list to a tree when it reaches 8 colliding entries, optimizing performance for buckets with many hash collisions.