Java Technical Tutorial

How Java HashMap Works Internally: Hashing, Buckets & Red-Black Trees

Deep architectural dive into Java HashMap: hashing algorithm, bucket array, linked list collision chaining, treeification to Red-Black tree, and load factor.

Java

// Demonstrating HashMap insertion, collision resistance and traversal
import java.util.HashMap;
import java.util.Map;

public class HashMapDeepDive {
    public static void main(String[] args) {
        // Initial capacity: 16, Load factor: 0.75
        Map<String, Integer> studentScores = new HashMap<>();

        studentScores.put("Amit", 92);
        studentScores.put("Priya", 98);
        studentScores.put("Rohit", 85);

        // Accessing value via O(1) average time complexity
        System.out.println("Priya's Score: " + studentScores.get("Priya"));

        // Iterating over key-value entries safely
        for (Map.Entry<String, Integer> entry : studentScores.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

1. The Internal Architecture of HashMap

In Java, HashMap implements the Map interface based on a hash table data structure. Internally, a HashMap maintains an array of Node<K,V> buckets. The default initial capacity is 16, and the default load factor is 0.75.

2. The Put Operation & Index Calculation

When you invoke map.put(key, value), Java executes the following steps:

Compute Key Hash: Java invokes key.hashCode() and applies a supplemental bit-shift hash function: (h = key.hashCode()) ^ (h >>> 16) to spread higher bits into lower bits, minimizing collisions.
Compute Bucket Index: The target bucket array index is determined via bitwise AND: index = (n - 1) & hash, where n is the array length (always a power of two).
Collision Check: If the bucket at that index is empty, a new Node is stored directly. If a node already exists, a hash collision has occurred.

3. Collision Resolution: Linked List vs. Treeification

Prior to Java 8, colliding entries were linked sequentially as a singly-linked list. Under heavy collisions, lookup degraded from O(1) to O(n). From Java 8 onward, once a single bucket exceeds 8 nodes (TREEIFY_THRESHOLD) and total map capacity reaches at least 64, the linked list converts into a balanced Red-Black Tree (TreeNode). This guarantees worst-case lookup performance of O(log n).

Key Engineering Takeaways

HashMap is not thread-safe; use ConcurrentHashMap in multi-threaded environments.
Always override both hashCode() and equals() when using custom classes as keys.
Immutable classes like String and Integer make ideal keys because their hash code is cached.

Frequently Asked Questions

Why is HashMap capacity always a power of two?

Power-of-two sizing allows calculating the bucket index with bitwise AND (n - 1) & hash instead of expensive modulo division operations.

What happens when the load factor is exceeded?

When size exceeds capacity * load factor (16 * 0.75 = 12), the bucket array doubles in size (32), and all existing elements are rehashed.

Master This in Our Ghaziabad Coding Labs

Gain deep mastery over these concepts with direct instructor guidance, code reviews, and mock interviews at C-60 R.K Tower, 3rd Floor, RDC, Ghaziabad.

Explore Related Course Call 7503962162