Q27: How does HashMap work under the hood (Buckets, Hash Collisions, Treeification)?
HashMap uses an array of Node<K,V> buckets. Index calculated as (n - 1) & hash(key).
- Collisions: Multiple keys mapped to the same bucket are chained as a Singly Linked List.
- Treeification (Java 8+): When bucket list length exceeds threshold 8 AND total capacity $ge 64$, the bucket converts from Linked List ($O(n)$) to a Red-Black Tree ($O(log n)$).
- Untreeification: Shrinks back to Linked List when node count drops to 6 during resizing.
HashMap Bucket Chain Treeification Architecture
Key Takeaways
- Collisions chain elements as Linked Lists initially.
- Converts to Red-Black Tree when bucket size $ge 8$ and capacity $ge 64$ ($O(log n)$ lookup).
Knowledge Check
What is the worst-case lookup time complexity in a Java 8 HashMap with high collisions?