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

The Minimum Capacity Requirement for Treeification

Understand that treeification only occurs when the entire HashMap capacity is at least 64 entries.

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:

  1. Convert that bucket to a tree (complex operation)
  2. 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.