Java HashMap Collisions and Key Quality

“How does HashMap work internally?” is asked in nearly every Java interview from junior to senior level. The interviewer is looking for a chain of reasoning: hashing to a bucket, handling collisions, resizing when the map fills up, and what changed in Java 8. The follow-up questions then test whether you understand why key quality matters, why mutable keys break maps, and what happens to performance in the worst case.

You do not need to recite the OpenJDK source. You do need to explain the mechanism clearly enough that the interviewer believes you could debug a slow or misbehaving map.

Before you start

You should know arrays, linked lists and the basic Map API. Read the equals and hashCode contract first if it is not fresh: HashMap relies on it entirely. Comfort with bitwise operators such as &, ^ and >>> helps you follow the index calculation.

The short answer

HashMap stores entries in an array of buckets. For each key it computes hashCode(), mixes the high bits into the low bits, and uses hash & (table.length - 1) as the bucket index. Keys that land in the same bucket are a collision; the bucket holds them in a linked list, compared with equals, and since Java 8 a bucket longer than eight entries becomes a red-black tree if the table has at least 64 slots. When the number of entries exceeds capacity times the load factor (16 times 0.75 by default), the table doubles and entries are redistributed. Average get and put are O(1); with poor hash codes they degrade to O(log n) with trees or O(n) without.

How it works

The core of a lookup in OpenJDK, simplified:

static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

int index = (table.length - 1) & hash(key);

The table length is always a power of two, so length - 1 is a mask of low bits: with 16 buckets, the index is the hash’s lowest four bits. Without the h ^ (h >>> 16) step, keys whose hash codes differ only in high bits would all collide. Spreading folds the high half into the low half cheaply. A null key hashes to 0, so HashMap allows one null key in bucket 0.

Each bucket holds nodes containing the key, value, cached hash and a next pointer:

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

put walks the bucket comparing the cached hash first (a cheap int comparison), then identity, then equals. If it finds a match it replaces the value; otherwise it appends a new node.

Resizing happens when size > threshold, where threshold = capacity * loadFactor. The new table is twice as large. Because the size is a power of two, each entry either stays at its index or moves to index + oldCapacity, depending on a single bit of its hash, so Java 8 splits each chain into a “low” and “high” list while preserving order.

Treeification protects against worst-case collisions. When a chain reaches TREEIFY_THRESHOLD (8) and the table has at least MIN_TREEIFY_CAPACITY (64) buckets, the chain becomes a red-black tree ordered by hash, then by compareTo if keys are Comparable. If the table is smaller, the map resizes instead. Trees shrink back to lists at 6 entries.

Step-by-step walkthrough

Step 1: Compute the index by hand

String key = "cat";
int h = key.hashCode();          // 98262
int spread = h ^ (h >>> 16);     // 98263 (h >>> 16 is 1)
int index = spread & 15;         // 7 with the default 16 buckets

Doing this once on a whiteboard shows the interviewer that you understand both the spreading step and the mask.

Step 2: Trace a collision

Map<String, Integer> m = new HashMap<>();
m.put("Aa", 1);
m.put("BB", 2);                  // "Aa" and "BB" both hash to 2112
System.out.println(m.get("BB")); // 2

Both keys land in the same bucket. get("BB") reaches the bucket, compares cached hashes (equal), then calls "BB".equals("Aa") (false) and moves on to the next node, where equals succeeds. The collision costs one extra comparison, not a wrong answer.

Step 3: Watch the threshold trigger a resize

Map<Integer, String> m = new HashMap<>();   // capacity 16, threshold 12
for (int i = 1; i <= 13; i++) {
    m.put(i, "v" + i);                        // the 13th put resizes to 32 buckets
}

If you know you will insert 1,000 entries, presizing avoids repeated resizes. Since Java 19, HashMap.newHashMap(1000) computes the right capacity for you; on older versions, use new HashMap<>((int) (1000 / 0.75f) + 1).

Step 4: Judge key quality

A good key is immutable, implements equals and hashCode from the same fields, and spreads its hash codes. String, Integer, UUID, enums and records of such types are all good keys. A key whose hashCode returns a constant still works correctly, but every entry shares one bucket.

Worked scenario

A pricing service caches quotes in a HashMap<QuoteKey, Quote>. Latency is fine in testing, but in production with 200,000 entries, lookups take milliseconds. Profiling shows time inside HashMap.getNode. The key:

class QuoteKey {
    final String currency;
    final long instrumentId;
    // equals compares both fields
    @Override public int hashCode() { return currency.hashCode(); }
}

There are only about 30 currencies, so 200,000 entries share roughly 30 distinct hash codes. Each bucket holds thousands of entries. Because QuoteKey is not Comparable, even treeified bins cannot order keys within the same hash and fall back to slow searches.

The fix uses every identifying field. Converting the class to a record does that automatically:

record QuoteKey(String currency, long instrumentId) {}

The generated hashCode combines both components, entries spread across the table, and lookups return to constant time. If keys come from untrusted input, such as request parameters, collision-heavy keys can also be an attack; the Java 8 tree bins exist partly to bound that damage.

Common mistake

• “HashMap is O(1) always.” It is O(1) on average with decent hashing. Worst case is O(log n) for treeified bins of Comparable keys and O(n) otherwise.
• “A collision means the map returns the wrong value.” Collisions only cost time; equals keeps lookups correct.
• Mutating a key after insertion. The entry stays in the bucket of its old hash and becomes unreachable through get.
• Assuming iteration order. HashMap order depends on hashes and capacity and changes after resizes. Use LinkedHashMap for insertion order or TreeMap for sorted order.
• Using HashMap across threads. Concurrent puts can lose entries. In Java 7, a concurrent resize could even create a cycle and an infinite loop. Use ConcurrentHashMap.

Verify the behavior

You can verify the index arithmetic with plain code and the collision behaviour with a test. The arithmetic below matches String.hashCode and the spreading function:

public class BucketDemo {
    static int spread(int h) { return h ^ (h >>> 16); }

    public static void main(String[] args) {
        for (String k : new String[] {"cat", "Aa", "BB"}) {
            int h = k.hashCode();
            System.out.printf("%s hash=%d index16=%d%n", k, h, spread(h) & 15);
        }
        // cat hash=98262 index16=7
        // Aa hash=2112 index16=0
        // BB hash=2112 index16=0
    }
}

To see degradation, time a million lookups with a constant-hash key versus a record key; the difference is several orders of magnitude.

Follow-up questions

Why is the capacity always a power of two? So the index can be computed with a fast bit mask instead of a modulo, and so resizing moves each entry to one of exactly two positions.

Why is the default load factor 0.75? It balances memory and collision probability. Lower values waste space; higher values lengthen chains.

What is the difference between HashMap and Hashtable? Hashtable is a legacy class with synchronized methods, no null keys or values, and no tree bins. Use HashMap or ConcurrentHashMap instead.

Why 8 for treeification? With a good hash and load factor 0.75, bucket sizes follow roughly a Poisson distribution and a chain of 8 is extremely unlikely, so trees appear only for genuinely bad hashing.

Interview exercise

An interviewer gives you a key class whose hashCode returns id % 16, where id is a sequential long. The map holds 10,000 entries. Describe the bucket distribution and the effect on get.

Answer and reasoning

id % 16 produces only 16 distinct hash codes, from 0 to 15. After spreading (the high bits are zero, so spreading changes nothing), they map to at most 16 buckets no matter how far the table grows. With 10,000 entries, each bucket holds around 625 keys. Since chains exceed 8 and the table quickly grows past 64, the bins become trees, but all keys in a bin share the same hash, so the tree can only order them by compareTo. If the key implements Comparable, lookups are about O(log 625); if not, the tree degrades to scanning. The fix is Long.hashCode(id), which uses all the information in the id. The reasoning shows you understand that the hash function, not the table size, limits distribution.

Continue learning

Practise with more Java interview questions and Java MCQs. Related notes: equals and hashCode contracts, concurrent collections and ArrayList capacity. The behaviour and tuning parameters are documented in the HashMap API documentation.