HashMap Internals

TL;DR

• HashMap is backed by an Array of Buckets (each bucket is a Linked List or a Red-Black Tree).
• Keys are mapped to an array index using index = (n - 1) & hash(key).
• Java 8 Optimization: If a single bucket gets too many collisions (8 or more), the Linked List transforms into a Red-Black tree to maintain fast O(log N) lookup instead of O(N).

Concept

When you call map.put("Alice", 100), how does Java know where to store it so it can find it instantly later?

1. Hashing: It calls "Alice".hashCode(), which returns an integer (e.g., 63281940).
2. Indexing: It cannot create an array of 63 million buckets, so it applies a bitwise AND operator to fit the hash into the current array capacity (default size 16): 63281940 & (16 - 1). Let’s say this equals 4.
3. Storing: It goes to array index [4]. It stores a Node containing the Key, the Value, and the original Hash.
4. Collision Handling: If another key also hashes to index [4], it creates a Linked List inside bucket [4].
5. Retrieval: map.get("Alice") hashes “Alice”, jumps to index [4], iterates through the Linked List in that bucket, and uses .equals("Alice") to find the correct Node.

Examples

// A simplified visualization of a HashMap's internal structure
class HashMap<K, V> {
    
    // The main Array of Buckets. 
    // Size is always a power of 2 (16, 32, 64...)
    transient Node<K,V>[] table;
    
    // The structure stored inside the buckets
    static class Node<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next; // Pointer to the next node if there is a collision
        
        // ... constructor ...
    }
}

Interview Questions

Q: Why must the capacity of a HashMap always be a Power of 2?
A: Because bitwise operations are vastly faster than the modulo operator (%).
To fit a hash code into an array of size N, you would mathematically do hash % N.
However, if N is guaranteed to be a power of 2 (like 16), Java can use a bitwise trick: hash & (N - 1). This produces the exact same index as modulo, but executes significantly faster at the CPU hardware level.

Q: What is the “Load Factor” and when does a HashMap resize?
A: The default Load Factor is 0.75. The default initial capacity is 16.
If you add items to the map, eventually the array gets full and collisions increase, slowing down performance.
When the map reaches 75% capacity (12 items), the HashMap automatically triggers a Rehash. It creates a brand new array double the size (32), takes all existing nodes, recalculates their bitwise index for the new array size, and moves them over. This is a very expensive operation, which is why you should set an initial capacity if you know you are inserting 100,000 items.