Hashing - DSA | The Collision Phenomenon: Why Collisions Occur

Hashing is a fundamental technique designed to achieve constant-time complexity, $O(1)$, for data insertion, deletion, and search operations. However, because we map a potentially infinite key space to a finite array space, multiple distinct keys will inevitably map to the same array index. This phenomenon is known as a hash collision, and managing it efficiently is critical to maintaining the performance of a hash-based data structure.

1. The Core Promise of Hashing & The Naive Approach

The primary goal of hashing is to bypass sequential or logarithmic searching by computing the exact memory address of a data item directly from its key.

The Mathematical Mapping

If we know the exact index where a piece of data is stored, we can retrieve it in $O(1)$ constant time. To achieve this, we use a mathematical formula called a hash function ($h(key)$) to map keys to specific indices in a hash table of size $N$.

In this lecture, we use a simple modulo-based hash function with a table size of $10$:

Naive Insertion Walkthrough

Let's insert a series of keys into an empty hash table of size 10 (indices $0$ through $9$):

• Insert 23:

• Insert 47:

• Insert 58:

• Insert 25:

At this stage, our hash table looks highly organized, and retrieving any of these elements takes exactly one step:

Index 0: Empty
Index 1: Empty
Index 2: Empty
Index 3: 23
Index 4: Empty
Index 5: 25
Index 6: Empty
Index 7: 47
Index 8: 58
Index 9: Empty

2. The Collision Phenomenon (The Problem)

The naive approach fails as soon as we attempt to insert a key that maps to an already occupied index.

Suppose we now want to insert 97:

We look at Index 7 and find that it is already occupied by the value 47.

This situation is called a Hash Collision.

Definition: A hash collision occurs when two or more distinct keys produce the same hash value (index) through a hash function:

Because a standard array slot can only hold one value at a time, we cannot simply overwrite $47$ with $97$, nor can we discard $97$. This necessitates the use of Collision Resolution Techniques.

3. Visualizing the Collision Flow

The diagram below illustrates how the naive mapping workflow breaks down when a collision occurs:

4. Collision Resolution Strategy: Separate Chaining

The first major technique to resolve hash collisions is Separate Chaining (also known as Open Chaining).

The Core Mental Model

Instead of storing the data values directly inside the hash table array slots, we configure each slot of the array to store a pointer (or reference) to the head of a Linked List.

• If no keys map to a particular index, the pointer at that index remains null.
• When a key maps to an index, it is added as a node in the linked list associated with that index.
• If multiple keys map to the same index, they are chained together in the same linked list.

5. Step-by-Step Execution of Separate Chaining

Let us trace the insertion of the following sequence of keys using Separate Chaining with $h(key) = key \pmod{10}$:

Step 1: Insert 23, 47, 58, 25

These keys map to empty slots. We create a new linked list node for each and place them at their respective indices:

• Index 3: [23] -> null
• Index 5: [25] -> null
• Index 7: [47] -> null
• Index 8: [58] -> null

Step 2: Insert 97 (Collision at Index 7)

• $97 \pmod{10} = 7$.
• Index 7 already contains a chain: [47] -> null.
• To insert $97$ in $O(1)$ time, we insert it at the head of the linked list.
• The chain at Index 7 becomes: [97] -> [47] -> null.

Step 3: Insert 53 (Collision at Index 3)

• $53 \pmod{10} = 3$.
• Index 3 already contains [23] -> null.
• Inserting at the head, the chain at Index 3 becomes: [53] -> [23] -> null.

Step 4: Insert 73 (Collision at Index 3)

• $73 \pmod{10} = 3$.
• Inserting at the head of the chain at Index 3, it becomes: [73] -> [53] -> [23] -> null.

Step 5: Insert 82

• $82 \pmod{10} = 2$.
• Index 2 is empty. Chain becomes: [82] -> null.

Step 6: Insert 95 (Collision at Index 5)

• $95 \pmod{10} = 5$.
• Index 5 already contains [25] -> null.
• Inserting at the head, the chain at Index 5 becomes: [95] -> [25] -> null.

Final Hash Table State

The final memory layout of our hash table using Separate Chaining is represented below:

6. Head vs. Tail Insertion in Separate Chaining

When a collision occurs and we need to add a new node to the linked list, we have two design choices:

7. Complexity Analysis of Separate Chaining

1. Insertion Time Complexity

• Time Complexity: $O(1)$
• Reasoning: By using the Head Insertion strategy, we simply compute the hash index, instantiate a new node, point its next reference to the current head, and update the array index to point to this new node. This is a constant-time operation.

2. Search Time Complexity

To search for a key (e.g., searching for $23$):

1. Compute the hash index: $23 \pmod{10} = 3$.
2. Go directly to Index 3.
3. Traverse the linked list sequentially: check $73 \to$ check $53 \to$ check $23$ (Found!).

• Best Case: $O(1)$ (The target element is at the head of the list).
• Average Case: $O(1 + \alpha)$, where $\alpha$ is the Load Factor ($\alpha = \frac{N}{M}$, where $N$ is the total number of keys and $M$ is the table size).
• Worst Case: $O(N)$
  • Why? In the absolute worst-case scenario, our hash function might map every single inserted key to the exact same index. This turns our hash table into a single, long linked list of size $N$, reducing search performance to a linear scan.

8. Complete Code Implementation

Below is a clean, production-ready Java implementation of a Hash Table using Separate Chaining to demonstrate these concepts in practice.

import java.util.LinkedList;

public class SeparateChainingHashTable {
    private int capacity;
    private LinkedList<Integer>[] table;

    // Constructor
    @SuppressWarnings("unchecked")
    public SeparateChainingHashTable(int capacity) {
        this.capacity = capacity;
        this.table = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            this.table[i] = new LinkedList<>();
        }
    }

    // Hash Function
    private int hash(int key) {
        return Math.abs(key) % capacity;
    }

    // Insert key using Head Insertion (O(1))
    public void insert(int key) {
        int index = hash(key);
        // To avoid duplicate values in the chain, check if it already exists
        if (!table[index].contains(key)) {
            // LinkedList.addFirst() implements Head Insertion
            table[index].addFirst(key);
            System.out.println("Inserted " + key + " at index " + index);
        } else {
            System.out.println("Key " + key + " already exists at index " + index);
        }
    }

    // Search key (Average: O(1), Worst: O(N))
    public boolean search(int key) {
        int index = hash(key);
        return table[index].contains(key);
    }

    // Delete key
    public void delete(int key) {
        int index = hash(key);
        if (table[index].remove((Integer) key)) {
            System.out.println("Deleted " + key + " from index " + index);
        } else {
            System.out.println("Key " + key + " not found at index " + index);
        }
    }

    // Print the Hash Table state
    public void display() {
        System.out.println("\n--- Hash Table State ---");
        for (int i = 0; i < capacity; i++) {
            System.out.print("Index " + i + ": ");
            if (table[i].isEmpty()) {
                System.out.println("null");
            } else {
                for (int val : table[i]) {
                    System.out.print("[" + val + "] -> ");
                }
                System.out.println("null");
            }
        }
    }

    public static void main(String[] args) {
        SeparateChainingHashTable ht = new SeparateChainingHashTable(10);

        // Insertions from the lecture
        ht.insert(23);
        ht.insert(47);
        ht.insert(58);
        ht.insert(25);
        ht.insert(97); // Collision at Index 7
        ht.insert(53); // Collision at Index 3
        ht.insert(73); // Collision at Index 3
        ht.insert(82); // Maps to Index 2
        ht.insert(95); // Collision at Index 5

        ht.display();

        // Search Demonstration
        System.out.println("\nSearching for 23: " + ht.search(23)); // Expected: true
        System.out.println("Searching for 100: " + ht.search(100)); // Expected: false
    }
}

Summary and Key Takeaways

• The Core Promise: Hashing aims to provide $O(1)$ constant-time complexity for search, insertion, and deletion operations by computing data addresses directly.
• The Collision Problem: A collision occurs when two distinct keys map to the exact same index in the hash table ($h(k_1) = h(k_2)$).
• Inevitable Reality: Because the key space is typically much larger than the hash table size, collisions are mathematically guaranteed to occur (Pigeonhole Principle).
• Separate Chaining: A collision resolution technique where each slot of the hash table points to a linked list of elements that hash to that same index.
• Head Insertion Optimization: Inserting new colliding elements at the head of the linked list ensures that insertions always run in $O(1)$ constant time.
• Search Performance: Searching in a chained hash table takes $O(1)$ on average, but degrades to $O(N)$ in the worst-case scenario if all keys hash to the same index.