← Java roadmap

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.

IntermediateJunior · 1–3 yearsInternals

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?
Practise Java with the AI mentor

Can't find a Java topic you need for exams or placements? Request it and we'll add it.