How does HashMap handle collisions?

• Collision: two keys produce the same bucket index via hash & (capacity - 1)
• Chaining: colliding entries are stored as a linked list in the bucket; each Node holds hash, key, value, and a next pointer
• Treeification (Java 8+): when a chain reaches 8 nodes (TREEIFY_THRESHOLD) and the table has at least 64 buckets (MIN_TREEIFY_CAPACITY), the list converts to a Red-Black tree
• Untreeification: when a tree shrinks to 6 or fewer nodes (UNTREEIFY_THRESHOLD), it converts back to a linked list
• A good hashCode() distributes keys evenly; treeification is a safety net, not the normal case

What is a hash collision?

A collision occurs when two different keys produce the same bucket index. Since the bucket index is computed as hash & (capacity - 1), and there are far more possible hash values than buckets, collisions are inevitable.

Two keys collide if they produce the same bucket index, even if their hash codes are different. For example, with capacity 16 (mask = 15 = 0b1111), hash values 3 and 19 both produce bucket index 3 because 3 & 15 = 3 and 19 & 15 = 3.

package com.bank.demo;

import java.util.*;

public class CollisionDemo {
    // Keys with deliberately bad hashCode – all return same value
    static class BadKey {
        final String value;
        BadKey(String value) { this.value = value; }
        @Override public int hashCode() { return 42; } // all same hash!
        @Override public boolean equals(Object o) {
            return o instanceof BadKey bk && bk.value.equals(this.value);
        }
        @Override public String toString() { return value; }
    }

    public static void main(String[] args) {
        Map<BadKey, String> map = new HashMap<>();

        // All keys collide – same bucket!
        for (int i = 0; i < 12; i++) {
            map.put(new BadKey("ACC" + i), "Holder" + i);
        }

        // All 12 entries are in ONE bucket
        // Before Java 8: one linked list of 12 nodes → get() is O(12)
        // Java 8+: after 8 nodes, converts to Red-Black tree → get() is O(log 12)

        long start = System.nanoTime();
        String result = map.get(new BadKey("ACC11")); // last element
        long elapsed = System.nanoTime() - start;
        System.out.println("Found: " + result + " in " + elapsed + " ns");
        System.out.println("Map size: " + map.size());
    }
}

Found: Holder11 in 1250 ns
Map size: 12

How does chaining work?

When a collision occurs, HashMap stores the new entry at the end of the linked list in that bucket. Each node in the list holds the hash, key, value, and a pointer to the next node.

When looking up a key, HashMap walks the chain: for each node, it checks node.hash == hash && node.key.equals(key). The hash check is fast (integer comparison) and short-circuits: if hashes differ, equals() is never called.

package com.bank.demo;

import java.util.*;

public class ChainingVisualization {
    public static void main(String[] args) {
        // With default capacity 16, keys that produce the same bucket index collide
        Map<String, String> map = new HashMap<>(16);

        // These keys may or may not collide depending on their hashCode
        // Let's force a collision scenario
        map.put("SAV2001", "Rajesh");
        map.put("CUR3001", "Priya");

        // To see actual bucket distribution, we can check hash & 15
        int bucket1 = "SAV2001".hashCode() & 15;
        int bucket2 = "CUR3001".hashCode() & 15;
        System.out.println("SAV2001 → bucket " + bucket1);
        System.out.println("CUR3001 → bucket " + bucket2);

        if (bucket1 == bucket2) {
            System.out.println("COLLISION: both in same bucket");
        } else {
            System.out.println("No collision: different buckets");
        }
    }
}

How does treeification work in Java 8?

When a bucket's linked list reaches 8 nodes (TREEIFY_THRESHOLD), HashMap checks if the table has at least 64 buckets (MIN_TREEIFY_CAPACITY). If yes, the list converts to a Red-Black tree. If the table is smaller than 64, it resizes instead of treeifying.

The Red-Black tree orders entries by their hash values. When hash values are equal, it uses the key's compareTo() method (if the key implements Comparable) or the key's identityHashCode as a tiebreaker.

When a tree shrinks to 6 or fewer nodes, it converts back to a linked list. The gap between 8 (treeify) and 6 (untreeify) prevents repeated conversion if entries are added and removed around the threshold.

// Internal constants from HashMap source
static final int TREEIFY_THRESHOLD = 8;    // list → tree
static final int UNTREEIFY_THRESHOLD = 6;  // tree → list
static final int MIN_TREEIFY_CAPACITY = 64; // min table size for treeify

// If chain length >= 8 AND table.length >= 64:
//   Convert linked list to Red-Black tree (TreeNode)
//   Lookup changes from O(n) to O(log n)

// If chain length >= 8 AND table.length < 64:
//   Resize the table instead (more buckets = better distribution)

Why threshold 8?

The HashMap source code comments explain this based on the Poisson distribution. With a good hash function and load factor 0.75, the expected number of entries per bucket follows a Poisson distribution with lambda = 0.5.

The probability of k entries in one bucket:

| k (entries) | Probability |
|---|---|
| 0 | 0.60653066 |
| 1 | 0.30326533 |
| 2 | 0.07581633 |
| 3 | 0.01263606 |
| 4 | 0.00157952 |
| 5 | 0.00015795 |
| 6 | 0.00001316 |
| 7 | 0.00000094 |
| 8 | 0.00000006 |

The probability of 8 or more entries in one bucket is about 0.00000006 (six in 100 million). This means treeification should almost never happen with a proper hash function. When it does happen, it is a strong signal that the hash function is bad.

What is the performance impact?

| Scenario | Linked list | Red-Black tree |
|---|---|---|
| Best case (no collision) | O(1) | O(1) |
| Average case (few collisions) | O(1) | O(1) |
| Worst case (all collisions) | O(n) | O(log n) |
| Memory per node | 32 bytes | 48 bytes |

The tree uses more memory per node (TreeNode has additional parent, left, right, and color fields), so it is only beneficial for long chains.

package com.bank.demo;

import java.util.*;

public class TreeificationBenchmark {
    static class ControlledHash {
        final int id;
        final int bucket;
        ControlledHash(int id, int bucket) { this.id = id; this.bucket = bucket; }
        @Override public int hashCode() { return bucket; } // force collision
        @Override public boolean equals(Object o) {
            return o instanceof ControlledHash ch && ch.id == this.id;
        }
    }

    public static void main(String[] args) {
        // All keys hash to bucket 0 – forces treeification
        Map<ControlledHash, String> map = new HashMap<>(64); // >= 64 for treeify
        for (int i = 0; i < 100; i++) {
            map.put(new ControlledHash(i, 0), "Account-" + i);
        }

        // Lookup in the tree bucket
        long start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            map.get(new ControlledHash(99, 0)); // last entry
        }
        long elapsed = System.nanoTime() - start;
        System.out.println("100 entries, tree bucket, 10K lookups: " + elapsed / 1000 + " us");
    }
}

What are common mistakes?

Mistake 1: Implementing hashCode() that always returns the same value

// WRONG – all entries collide in one bucket
@Override public int hashCode() { return 1; }
// HashMap degrades to a linked list (or tree), O(n) or O(log n)

// CORRECT – distribute across all buckets
@Override public int hashCode() {
    return Objects.hash(accountId, branchCode, accountType);
}

Mistake 2: Assuming HashMap is always O(1)

// HashMap is O(1) AVERAGE case, not guaranteed O(1)
// Worst case with bad hashCode: O(n) pre-Java 8, O(log n) Java 8+
// Always implement proper hashCode() for keys

What should a senior engineer know?

- TreeNode implements Comparable tiebreaker. When keys implement Comparable, the tree uses compareTo() to order them. When keys do not implement Comparable, it falls back to System.identityHashCode() as an arbitrary but consistent ordering.

- Treeification requires Comparable for efficiency. Without Comparable, the tree cannot use compareTo for ordering and must use identity hash codes, which may not distribute well. This is why String, Integer, and other standard types work well as keys.

- The hash spreading function. HashMap's hash() method XORs the upper 16 bits with the lower 16 bits: (h = key.hashCode()) ^ (h >>> 16). This ensures that high bits contribute to bucket selection even when the table is small (e.g., 16 buckets use only the bottom 4 bits).

- DoS attack mitigation. Before Java 8, an attacker could send keys with the same hash code to create O(n) lookup chains. Treeification limits the damage to O(log n).

What are common interview follow-up questions?

• "What is the difference between TREEIFY_THRESHOLD and UNTREEIFY_THRESHOLD?" – 8 to tree, 6 back to list; the gap prevents thrashing.
• "Why does HashMap require both hashCode() and equals()?" – hashCode finds the bucket; equals finds the exact key in the chain.
• "What happens before Java 8 with many collisions?" – O(n) lookup with linked list only.
• "Can you force treeification?" – Yes, by providing keys with identical hashCode values.