Topic 21 of 30 · Intermediate
What really happens when HashMap collisions exceed the tree threshold?
Java 8+ HashMap may treeify a heavily collided bucket, but the minimum table-capacity condition matters: at small capacities it resizes instead of immediately using a tree.
Java 17+; compile each complete program as Main.java.
Detailed answer
Java 8+ HashMap may treeify a heavily collided bucket, but the minimum table-capacity condition matters: at small capacities it resizes instead of immediately using a tree.
The common constants are a treeification threshold of 8 and minimum capacity 64; these are implementation details rather than API guarantees. Resizing can split bucket contents according to new index bits.
Tree bins improve collision behavior, but HashMap is not thread safe. Capacity, load factor and hash quality matter; ConcurrentHashMap is the appropriate starting point for shared concurrent mappings.
Internal working
Hash spreading and power-of-two table indexing determine buckets. A resize reassigns entries; traversal order is unspecified and can change.
Practical scenario
A poor key hash returns the same integer for thousands of customer IDs. Fix the key hash rather than relying on collision rescue.
import java.util.*;
class Main { public static void main(String[] a){Map<Integer,Integer> m=new HashMap<>(128);for(int i=0;i<100;i++)m.put(i,i);System.out.println(m.size());}}Common mistakes
- Claiming every eighth entry always treeifies.
- Using HashMap concurrently without synchronization.
Key takeaways
- Thresholds have capacity conditions.
- Do not depend on implementation internals.
- Use a concurrent map for shared access.
Follow-up challenges
- How would you choose an initial capacity?
- Why is iteration order not a contract?