Stage 4: HashMap internals, lesson 6 of 13

HashMap internals 6: How collisions are resolved

Intermediate3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

HashMap resolves collisions with separate chaining: each bucket holds a linked list of nodes, joined by their next field.

  • A new key in an occupied bucket is linked at the tail of the list (Java 8+).
  • Lookups walk the chain, comparing the stored hash first and then equals().
  • If a chain grows too long (more than 8 nodes, in a table of at least 64 buckets), Java 8+ converts that bucket into a red-black tree (part 11).

The other common strategy is open addressing: on a collision, try another slot in the array itself, for example the next one ("linear probing"). Java's IdentityHashMap and ThreadLocal's internal map work this way. Chaining handles high load and deletions more gracefully, which is why HashMap uses it.

Below is a tiny HashMap with chaining, the whole idea in about 25 lines.

HashMap lab

Example

Java
class MiniHashMap<K, V> {
    static final class Node<K, V> {
        final int hash; final K key; V value; Node<K, V> next;
        Node(int hash, K key, V value) { this.hash = hash; this.key = key; this.value = value; }
    }

    @SuppressWarnings("unchecked")
    private final Node<K, V>[] table = (Node<K, V>[]) new Node[16];   // no resizing, to keep it short

    public V put(K key, V value) {
        int h = key.hashCode() ^ (key.hashCode() >>> 16);
        int i = h & (table.length - 1);
        Node<K, V> last = null;
        for (Node<K, V> n = table[i]; n != null; n = n.next) {
            if (n.hash == h && n.key.equals(key)) { V old = n.value; n.value = value; return old; }  // same key
            last = n;
        }
        Node<K, V> node = new Node<>(h, key, value);
        if (last == null) table[i] = node; else last.next = node;     // collision: chain at the tail
        return null;
    }

    public V get(K key) {
        int h = key.hashCode() ^ (key.hashCode() >>> 16);
        for (Node<K, V> n = table[h & (table.length - 1)]; n != null; n = n.next) {
            if (n.hash == h && n.key.equals(key)) return n.value;
        }
        return null;
    }
}

Common mistake

Believing a bucket holds only one entry. A bucket is a chain (or tree) that can hold many.

Under the hood

Chaining keeps working even when the table is over-full, and removing an entry is just unlinking a node. Open addressing needs "tombstones" for deletions and degrades sharply as the table fills, but it's more cache-friendly, which is why some high-performance libraries prefer it.

Check yourself

Which technique does java.util.HashMap use to resolve collisions?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.