HashMap Internals | Engineering Interview Kit

TL;DR

A HashMap is backed by an array of “Buckets” (Nodes).
It determines the bucket index for a key using: index = (n - 1) & hash.
Java 8 Optimization: When a bucket’s linked list gets too long (8 elements), it converts into a Red-Black Tree to guarantee $O(\log n)$ lookup time.

Concept

Understanding the internals of HashMap is one of the most common senior-level Java interview topics.

1. The Hash Function

When you call map.put(key, value), it calculates key.hashCode(). It then applies an internal hash function to spread the bits out to prevent clustering. Finally, it uses a bitwise AND operator to map that large hash integer to a valid index in its internal array.

2. Collisions and Linked Lists

If two keys map to the same array index, a Collision occurs. HashMap handles this via “Separate Chaining”—it stores the entries in a LinkedList at that bucket.

3. Java 8 Improvement (Treeification)

If many collisions occur at the same bucket, the linked list gets very long, degrading performance from $O(1)$ to $O(n)$ . Since Java 8, if a bucket reaches a threshold (TREEIFY_THRESHOLD = 8) and the total map capacity is $\geq 64$ , the linked list is converted into a Red-Black Tree. If elements are removed and the tree shrinks to 6, it converts back to a linked list.

Examples

// Conceptual visualization of HashMap internal structure

/*
Array Index [0] -> null
Array Index [1] -> Node(K1, V1) -> Node(K2, V2)  // Collision: Linked List
Array Index [2] -> null
Array Index [3] -> Node(K3, V3)                  // No Collision
...
Array Index [9] -> TreeNode(K4, V4)              // Heavy Collision: Red-Black Tree
                    /        \
          TreeNode(K5,V5)   TreeNode(K6,V6)
*/

Interview Questions

Q: What is the significance of the “Load Factor” and “Capacity”?
A: - Capacity: The number of buckets in the array (default is 16, and always a power of 2).

Load Factor: A measure of how full the map is allowed to get before resizing (default is 0.75).
When Number of Elements > (Capacity * LoadFactor), the HashMap is resized. Its capacity is doubled, and all elements are re-hashed and moved to new buckets.

Q: Why is the capacity of a HashMap always a power of 2?
A: Because it allows the HashMap to use an extremely fast bitwise AND operation (hash & (capacity - 1)) to calculate the array index instead of using the slower modulo operator (hash % capacity). If capacity is a power of 2, capacity - 1 is a bitmask of all 1s, which perfectly masks the hash value to fit within the array bounds.