How Does Java’s HashMap Resolve Hash Collisions? From Linked Lists to Red‑Black Trees

Solution Ideas for Hash Collisions

HashMap resolves collisions by first preventing them with a perturbation function that spreads hash values, then handling remaining conflicts through two main strategies: chaining (linked lists or red‑black trees) and open addressing.

Direct Conflict: Chaining

In the chaining approach, each bucket holds a linked list of entries that share the same index. When a new entry collides, it is inserted at the head of the list (Java 7) or at the tail (Java 8). If the list grows beyond a threshold, it is converted into a red‑black tree to improve lookup performance.

Alternative: Open Addressing

Open addressing stores colliding entries directly in the hash table by probing for the next free slot (e.g., linear probing). This method saves pointer space but can suffer from clustering, where long sequences of occupied slots increase lookup cost.

HashMap’s Method in Java

Java 7 uses only an array plus a singly linked list per bucket (head‑insertion). Java 8 adds red‑black trees and switches to tail‑insertion, eliminating the risk of circular lists during concurrent resizing.

// Java 7 HashMap put core logic
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold); // initialize array
    }
    if (key == null)
        return putForNullKey(value); // handle null key
    int hash = hash(key); // compute hash
    int i = indexFor(hash, table.length); // compute index
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

// Java 8 HashMap put core logic
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // init or resize
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Treeification Threshold

When a bucket’s linked list exceeds eight nodes and the table size is at least 64, HashMap converts the list into a red‑black tree, reducing lookup complexity from O(n) to O(log n). The reverse conversion occurs when the table shrinks below 64 and the tree size drops below six.

Resizing Logic

HashMap resizes when the number of entries exceeds threshold = capacity × loadFactor (default 0.75). During resize, the array length doubles (always a power of two), and each entry’s index is recomputed using the same hash value, with the new high-order bit determining the new bucket.

Why Red‑Black Tree Over AVL?

Red‑black trees provide a good balance between insertion/deletion cost and lookup speed. They require fewer rotations than AVL trees, making them faster for the frequent updates typical in HashMap usage, while still guaranteeing O(log n) lookup.

Summary

HashMap resolves collisions by using a perturbation function to spread keys, chaining (with optional red‑black tree conversion) or open addressing, and a resize mechanism that doubles the table size. Understanding these mechanisms helps developers answer interview questions and write efficient Java code.