Course contentsShow
← Java
Lesson 1120 of 2,87026. Map ImplementationsFree lesson

Untreeification: Converting Back to Linked Lists

Learn when HashMap converts tree bins back to linked lists after removal reduces entries below the threshold.

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:

  1. The bucket is currently a tree bin
  2. 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.