Collision Handling (Chaining, Open Addressing)

Because the space of possible keys (e.g., all conceivable strings) is infinite, while the hash table array has finite capacity, the Pigeonhole Principle guarantees that two different keys will eventually hash to the same bucket index:

hash(Key A) mod N == hash(Key B) pmod N

This event is called a Hash Collision. How do we resolve collisions?

Strategy 1: Separate Chaining (Closed Addressing)

In Separate Chaining, each bucket in the array does not store the value directly. Instead, each bucket holds a reference to a linked list (or balanced binary tree) containing all entries that mapped to that index.

Copy codeIndex 0: null
Index 1: [ "cat": 5 ] ---> [ "act": 9 ] ---> null  (Collision resolved via chain!)
Index 2: [ "dog": 2 ] ---> null

Search Procedure in Chaining:

1. Compute index = hash(key) % capacity.
2. Traverse the linked list at array[index].
3. Compare keys using equals() until a match is found.

Modern Optimization: Treeification

In Java 8+ and modern Android ART, if a bucket's linked list grows beyond 8 elements, HashMap automatically converts the linked list into a Red-Black Tree (TreeNode). This upgrades worst-case search from O(n) down to O(log n), neutralizing Hash Denial-of-Service attacks.

Strategy 2: Open Addressing (Closed Hashing)

In Open Addressing, all key-value pairs are stored directly in the array itself. No linked lists are used. If a collision occurs at index h, the algorithm probes subsequent slots in the array until an empty bucket is found.

Copy codeProbing Sequence:
h(k), h(k) + f(1), h(k) + f(2), ...

1. Linear Probing

Probes the immediate next slot: f(i) = i.

index = (h(k) + i) mod Capacity

• Advantage: Excellent CPU cache locality.
• Disadvantage: Primary Clustering — clusters of occupied cells form, progressively degrading search times into O(n).

2. Quadratic Probing

Probes slots using a quadratic equation: f(i) = c_1 · i + c_2 · i².

• Eliminates primary clustering, but can suffer from secondary clustering.

3. Double Hashing

Uses a second independent hash function to compute the probe step size:

index = (h_1(k) + i · h_2(k)) mod Capacity

• Distributes keys uniformly across the table, eliminating clustering.

Deletion in Open Addressing: The Tombstone Problem

In Open Addressing, you cannot simply set an entry to null when deleting:

Copy codeKeys A and B both hash to index 2.
Index 2: [ Key A ]
Index 3: [ Key B ] (Placed here due to linear probe)

If you delete Key A and set Index 2 to null:
Searching for Key B will check Index 2, see null, and falsely report: "Key B not found!"

To solve this, deleted slots are marked with a special Tombstone (Deleted marker). Searches continue past tombstones, while insertions can overwrite them.

Chaining vs Open Addressing Comparison

Summary

• Collisions are mathematically inevitable and must be handled gracefully.
• Separate Chaining stores collided items in linked chains or balanced trees per bucket.
• Open Addressing stores all items in the array, probing alternative slots via Linear Probing, Quadratic Probing, or Double Hashing.