Untreeification: Converting Back to Linked Lists
What You'll Learn
You'll discover how HashMap automatically converts optimized tree bins back into simpler linked lists when entries are removed.
The Reverse Optimization
Remember how HashMap converts long linked lists into red-black trees when a bucket grows beyond 8 entries? Well, HashMap also performs the reverse transformation when you remove enough elements.
When entries in a tree bin are deleted and the count drops to 6 or fewer, HashMap converts the tree structure back into a regular linked list. This process is called untreeification.
Why the Reverse Threshold?
You might wonder: "Why treeify at 8 but untreeify at 6? Why not both at 8?"
This is called hysteresis — using different thresholds for going up versus coming down. It prevents thrashing: imagine if both thresholds were 8. Adding one element could trigger treeification, then removing one would trigger untreeification, then adding again would treeify... back and forth constantly!
By using 6 as the untreeification threshold, HashMap creates a "buffer zone" that ensures stability. Once you're in tree mode, you need to drop well below the treeify threshold before converting back.
When It Matters
Untreeification happens automatically during remove() operations when:
- The bucket is currently a tree bin
- The removal reduces the count to 6 or fewer entries
For small bins (6 or fewer entries), the overhead of maintaining a tree structure isn't worth it — a simple linked list performs just as well and uses less memory.
Key Takeaway: HashMap automatically converts tree bins back to linked lists when removals reduce the count to 6 or fewer entries, using a different threshold than treeification to prevent constant back-and-forth conversions.