Topic 42 of 79

Hash Map Internals

Q: Why is the internal array size of a HashMap always a power of 2?

Performance. Calculating `hash % length` using division is relatively slow for a CPU. If the length is a power of 2 (16, 32, 64), Java can use a bitwise AND operation (`hash & (length - 1)`) instead of modulo. Bitwise math is executed at the hardware level in a single CPU cycle.

Overview

You know how to use a HashMap, but understanding exactly how it achieves O(1) performance is the most frequently asked data structure question in interviews.

Internally, a HashMap is an Array of Nodes (often called 'buckets'). When you call map.put("Key", 42), three things happen: 1. Hashing: The map calls "Key".hashCode() to get a massive integer (e.g., 2348923). 2. Index Calculation: It uses the modulo operator (hash % array_length) to squash that massive integer into a valid array index (e.g., index 5). 3. Storage: It stores a Node containing the Key and Value at array index 5.

A Collision happens when two completely different keys calculate to the exact same array index. Java handles this via Separate Chaining. Instead of storing just one Node at index 5, it stores a Linked List of Nodes. If too many collisions happen in one bucket (8+ in Java 8), that Linked List upgrades itself into a Red-Black Tree to keep search times fast (O(log N)).

Syntax

The Anatomy of a HashMap Bucket

java

// A simplified look at Java's internal HashMap Node
class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Pointer to the next node (Linked List for collisions)

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

// Pseudo-code of what put() actually does
public void put(K key, V value) {
    int hash = key.hashCode();
    
    // Bitwise AND is used instead of modulo for extreme speed
    int index = hash & (internalArray.length - 1); 
    
    Node bucket = internalArray[index];
    
    if (bucket == null) {
        // No collision! Store directly.
        internalArray[index] = new Node(hash, key, value, null);
    } else {
        // Collision! Traverse the linked list
        while (bucket.next != null) {
            // If key already exists, overwrite value
            if (bucket.key.equals(key)) {
                bucket.value = value;
                return;
            }
            bucket = bucket.next;
        }
        // Append to the end of the collision chain
        bucket.next = new Node(hash, key, value, null);
    }
}

Common Pitfalls

Overriding equals() without overriding hashCode(). If two objects are logically equal (e.g., two Person objects with the same ID), they MUST return the exact same hashCode(). If they don't, the HashMap will look in the wrong bucket and fail to find the object, effectively losing data.
Using mutable objects as keys. If you use a List as a key, insert it into a map, and then add an item to that List, its hashCode() changes! When you try to get() it later, the map will look in the wrong bucket based on the new hash, and return null. Keys should always be immutable (like String or Integer).
Poorly written hashCode() functions. If your hashCode() always returns 1, every single entry goes into bucket 1. Your HashMap degrades into a single massive Linked List, destroying O(1) performance and turning it into O(N).

Interview Questions

What is a Hash Collision, and how does Java's HashMap resolve it?

A collision occurs when two different keys hash to the same array index. Java resolves this using 'Separate Chaining'. The bucket at that index becomes a Linked List, holding all colliding entries. In Java 8+, if a bucket's chain exceeds 8 elements, it automatically transforms into a Red-Black Tree, improving worst-case search time from O(N) to O(log N).

What is the Load Factor and why is it important?

The Load Factor (default 0.75) determines when the HashMap resizes itself. When the map becomes 75% full (e.g., 12 items in a 16-bucket array), it triggers a 'rehash'. It creates a new array twice the size and recalculates the bucket index for every single existing entry. This is an expensive O(N) operation designed to maintain low collision rates and O(1) performance.

Why is the internal array size of a HashMap always a power of 2?

Performance. Calculating hash % length using division is relatively slow for a CPU. If the length is a power of 2 (16, 32, 64), Java can use a bitwise AND operation (hash & (length - 1)) instead of modulo. Bitwise math is executed at the hardware level in a single CPU cycle.

Real-World Example

Database caching layers (like Redis or local Memcached) are essentially massive HashMaps. They require strict O(1) performance. Understanding load factors is critical here: if a cache expects 10 million entries, initializing the HashMap with a capacity of 16 will trigger dozens of massive, thread-blocking rehashes. Pre-sizing the map to (10M / 0.75) prevents this.

example

java

// Bad: Will resize 15+ times, pausing the application
Map<String, UserData> cache1 = new HashMap<>();

// Pro: Pre-size the map to accommodate 10 million items
// Capacity = Expected Items / Load Factor (0.75) + 1
int expected = 10_000_000;
int capacity = (int) (expected / 0.75f) + 1;

Map<String, UserData> cache2 = new HashMap<>(capacity);
// Now 10 million items can be inserted with ZERO rehashing overhead!

Check Your Knowledge

Test your understanding of Hash Map Internals with these quick questions.

What happens in Java 8+ if a single HashMap bucket gets too many collisions?

Which two methods must be properly overridden to use a custom object as a HashMap key?

What is the primary reason keys in a HashMap should be immutable?

Take Java Quiz

Overview

You know how to use a HashMap, but understanding exactly how it achieves O(1) performance is the most frequently asked data structure question in interviews.

Syntax

The Anatomy of a HashMap Bucket

java

// A simplified look at Java's internal HashMap Node
class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Pointer to the next node (Linked List for collisions)

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

// Pseudo-code of what put() actually does
public void put(K key, V value) {
    int hash = key.hashCode();
    
    // Bitwise AND is used instead of modulo for extreme speed
    int index = hash & (internalArray.length - 1); 
    
    Node bucket = internalArray[index];
    
    if (bucket == null) {
        // No collision! Store directly.
        internalArray[index] = new Node(hash, key, value, null);
    } else {
        // Collision! Traverse the linked list
        while (bucket.next != null) {
            // If key already exists, overwrite value
            if (bucket.key.equals(key)) {
                bucket.value = value;
                return;
            }
            bucket = bucket.next;
        }
        // Append to the end of the collision chain
        bucket.next = new Node(hash, key, value, null);
    }
}

Common Pitfalls

Overriding equals() without overriding hashCode(). If two objects are logically equal (e.g., two Person objects with the same ID), they MUST return the exact same hashCode(). If they don't, the HashMap will look in the wrong bucket and fail to find the object, effectively losing data.
Using mutable objects as keys. If you use a List as a key, insert it into a map, and then add an item to that List, its hashCode() changes! When you try to get() it later, the map will look in the wrong bucket based on the new hash, and return null. Keys should always be immutable (like String or Integer).
Poorly written hashCode() functions. If your hashCode() always returns 1, every single entry goes into bucket 1. Your HashMap degrades into a single massive Linked List, destroying O(1) performance and turning it into O(N).

Interview Questions

What is a Hash Collision, and how does Java's HashMap resolve it?

What is the Load Factor and why is it important?

Why is the internal array size of a HashMap always a power of 2?

Real-World Example

example

java

// Bad: Will resize 15+ times, pausing the application
Map<String, UserData> cache1 = new HashMap<>();

// Pro: Pre-size the map to accommodate 10 million items
// Capacity = Expected Items / Load Factor (0.75) + 1
int expected = 10_000_000;
int capacity = (int) (expected / 0.75f) + 1;

Map<String, UserData> cache2 = new HashMap<>(capacity);
// Now 10 million items can be inserted with ZERO rehashing overhead!

Check Your Knowledge

Test your understanding of Hash Map Internals with these quick questions.