What is a Collision in HashMap

A collision in HashMap is a standard runtime condition in which two logically distinct keys (k1.equals(k2) == false) compute to the exact same bucket slot (table[index]) in the...

🟢 Junior Level

Short Interview Answer (30 Seconds)

A collision in HashMap is a standard runtime condition in which two logically distinct keys (k1.equals(k2) == false) compute to the exact same bucket slot (table[index]) in the underlying hash table array.

A collision is neither an error nor an exceptional state. It is mathematically inevitable because the universe of possible objects in memory is infinite, while the array of buckets is finite (defaulting to 16). HashMap resolves collisions using Separate Chaining: conflicting elements are linked together in a singly linked list within the bucket. Starting in Java 8, if a single bucket reaches 8 elements (and total table capacity is at least 64), the list is transformed into a balanced Red-Black Tree (TreeNode), safeguarding the application against $O(n)$ latency degradation.

Two Types of Collisions: Hash Collision vs. Index Collision

Collision Type	What Occurred	Concrete Example	Frequency of Occurrence
`hashCode()` Collision (Hash Collision)	Two distinct objects return the exact same 32-bit `int` value	`"Aa".hashCode() == 2112` `"BB".hashCode() == 2112`	Rare (under well-distributed hash algorithms)
Index / Slot Collision (Bucket Collision)	Keys have distinct hash codes, but `(n - 1) & hash` produces the same index	`hash1 = 100` (`...01100100_b`) `hash2 = 116` (`...01110100_b`) Index for $n=16$: 4	Frequent (the predominant form of collision)

Java 21 Demonstration

import java.util.HashMap;

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

        // 1. True hashCode() Collision:
        // In String.hashCode(), "Aa" and "BB" generate identical 32-bit hashes: 2112
        System.out.println("Aa hash: " + "Aa".hashCode()); // 2112
        System.out.println("BB hash: " + "BB".hashCode()); // 2112

        map.put("Aa", "FirstValue");
        map.put("BB", "SecondValue"); // Placed in the same bucket as "Aa"!

        // Both key-value pairs are stored independently and retrieved accurately:
        System.out.println("Aa -> " + map.get("Aa")); // FirstValue
        System.out.println("BB -> " + map.get("BB")); // SecondValue

        // 2. Index Collision (different hashes, identical bucket slot):
        // Strings "FB" (hashCode = 2236) and "Ea" (hashCode = 2236)
        // Any keys sharing the same lowest 4 bits map to the same bucket in capacity 16
        System.out.println("Total map size: " + map.size()); // 2
    }
}

🟡 Middle Level

Mathematical Inevitability of Collisions

Even under optimal engineering and perfect hash implementations, collisions are mathematically unavoidable:

1. The Pigeonhole Principle:

Java’s int primitive is bounded by $2^{32} \approx 4.29 \times 10^9$ possible values. The set of distinct string objects alone of length 10 or less exceeds $10^{15}$. It is mathematically impossible to map an infinite universe of objects into a finite 32-bit address space without duplicates.

2. The Birthday Paradox:

In probability theory, in a group of just 23 people, the probability that two share the exact same birthday exceeds 50% (out of 365 possible days).
In a HashMap with an initial capacity of $n = 16$ buckets, the probability of at least one bucket collision exceeds 50% after adding only 5 keys!

How `HashMap` Identifies the Correct Entry During Collisions

When multiple entries share a single bucket, calling map.get(key) traverses the linked list (or tree), executing an escalating three-tier check on each node:

// OpenJDK HotSpot HashMap.getNode() logic:
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    return p;

Cached Hash Equality: Evaluates p.hash == hash. If primitive hashes do not match, the node is rejected in 1 CPU cycle.
Reference Identity: Evaluates (k = p.key) == key. If both pointers reference the identical heap address, equals() is bypassed.
Deep equals() Evaluation: Only when hashes match and memory references differ does the JVM invoke key.equals(k).

🔴 Senior Level

Hardware Impact of Collisions: The Memory Wall and CPU Cache Misses

From the perspective of CPU hardware architecture, collision traversal incurs severe latency penalties:

Direct Hit (No Collision - O(1)):
CPU ──► table[i] ──► Direct Hit (L1/L2 Cache) ──► Returns Value (~1 ns)

Deep Collision Chain (O(n)):
CPU ──► table[i] ──► Node 1 ──(Pointer Chasing)──► Node 2 ──(RAM)──► Node 3...
   (L1/L2/L3 Cache Misses, Cache Line Loads from RAM, virtual equals() calls) (~50-100 ns)

Each Node is individually allocated on the heap by the garbage collector at non-contiguous memory addresses. Traversing a linked collision list represents classic Pointer Chasing, which defeats CPU hardware prefetchers and forces the processor to stall while waiting for main memory buses.

Hash Flooding DoS Attacks and Treeification Defense

In 2011, security researchers demonstrated vulnerabilities in web application servers: clients could issue an HTTP POST request with 10,000 form parameters whose string names were crafted to generate identical hash codes.

Mechanics of Hash Flooding in Java 7:

In Java 7, collisions were resolved strictly with singly linked lists;
Inserting $N$ colliding parameters required $O(N)$ comparisons for each item, ballooning the entire request parse time to $O(N^2)$;
A single 200 KB HTTP payload could saturate a server CPU core for 30–60 seconds, causing full denial of service.

Java 8+ Treeification Defense:

When a bucket exceeds 8 entries, the list converts into a balanced Red-Black Tree. Insertion and search drop from $O(N)$ to $O(\log N)$. The overall DoS payload processing drops to $O(N \log N)$, neutralizing the attack vector.

Ordering Nodes in `TreeNode`: `Comparable` and `tieBreakOrder`

A Red-Black Tree requires total ordering among elements ($<$ or $>$). How does HashMap order tree nodes when keys produce the exact same hash?

The Comparable Interface:
If the key class implements Comparable<K> (such as String, Integer, UUID), nodes are ordered via ((Comparable)k).compareTo(x).

Fallback via tieBreakOrder:
If keys do not implement Comparable or their compareTo() returns 0 (while equals() returns false), HashMap breaks the tie using tieBreakOrder():

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
    return d;
}

The final arbiter is System.identityHashCode(), reading the object’s native memory hash from its object header Mark Word.

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

A collision in HashMap occurs when distinct keys (equals == false) map to the same bucket. Collisions are divided into hashCode() collisions (identical 32-bit hash, rare) and bucket index collisions (identical (n-1) & hash, common). They are mathematically unavoidable due to the Pigeonhole Principle and the Birthday Paradox (5 entries in 16 buckets yield a $>50\%$ collision probability). HashMap resolves collisions via Separate Chaining, transforming lists into Red-Black Trees at 8 elements (when capacity $\ge 64$) to cap search complexity at $O(\log n)$ and eliminate Hash Flooding DoS vulnerabilities.

2. 4 Tricky Questions with Deep Answers

Question 1: What is the fundamental difference between a `hashCode` collision and a bucket index collision, and which occurs more frequently?

Answer:

hashCode Collision: Two distinct objects return the exact same 32-bit int from hashCode(). This is infrequent under well-designed hash algorithms.
Bucket Index Collision: Two objects produce distinct 32-bit hash codes, but applying the bitwise mask (table.length - 1) & hash produces the same array slot index.
Bucket index collisions occur millions of times more frequently because the array size (16, 32, 64) is vastly smaller than the $2^{32}$ range of int.

Question 2: How does the Birthday Paradox explain why collisions occur long before reaching the resize threshold?

Answer: Many developers mistakenly believe collisions only emerge as table occupancy nears threshold (12 out of 16 items). Under probability theory and the Birthday Paradox, the probability of zero collisions when placing $k$ items into $n$ slots is: $P(\text{no collisions}) = \prod_{i=1}^{k-1} \left(1 - \frac{i}{n}\right)$ For a table of 16 slots, at $k = 5$ items, the probability of encountering at least one collision reaches $\approx 51\%$. Collisions are a normal characteristic of hash tables from their earliest insertions.

Question 3: What occurs when a bucket reaches 8 colliding entries if the key class does NOT implement `Comparable`?

Answer: The bucket is still successfully converted into a TreeNode Red-Black Tree. HotSpot first checks comparableClassFor(key). If Comparable is not implemented, the tree insertion algorithm attempts a recursive traversal of both left and right subtrees. In ambiguous cases, it invokes tieBreakOrder(), which compares class names, and if identical, falls back to System.identityHashCode(). While functional, balancing a tree without Comparable incurs higher CPU comparison overhead.

Question 4: How does an attacker construct a Hash Flooding DoS attack, and how does Java 8 neutralize it?

Answer: An attacker generates thousands of string keys sharing identical hash codes (in Java’s polynomial string hash formula, collisions are easily generated, e.g., by permuting "Aa" and "BB"). Sending 20,000 such keys in an HTTP form maps all entries to a single bucket. In Java 7, inserting into an $N$-element list required $O(N)$ checks, yielding $O(N^2)$ computational complexity that starved server CPUs. In Java 8+, treeification transforms the bucket into a Red-Black Tree, dropping insertion complexity to $O(N \log N)$ and allowing the request to complete in milliseconds.

3. Common Pitfalls and Red Flags

❌ “A collision indicates a bug in the developer’s hashCode() implementation.”
Correction: Even with a mathematically perfect hash code, projecting onto 16 buckets produces collisions by the Pigeonhole Principle.

❌ “When a collision occurs, the existing value is overwritten.”
Correction: Values are overwritten only when both hash and equals() evaluate to true. In a collision (equals == false), both entries are preserved in the same bucket.

❌ “HashMap search complexity always degrades to $O(n)$ under collisions.”
Correction: In Java 8+, buckets with 8 or more entries treeify into Red-Black Trees, capping worst-case search complexity at $O(\log n)$.