Overview​

In hashing, collision handling refers to the methods used to resolve the issue when two keys hash to the same index in a hash table. Collisions are inevitable in hash tables due to the limited number of available slots compared to the potentially infinite number of input keys.

Video Explanation​

Watch

Methods of Collision Handling​

1. Chaining (Open Hashing)​

• Chaining stores multiple elements in the same bucket using a data structure like a linked list.
• When a collision occurs, the new key-value pair is added to the end of the linked list at that index.
• Advantages: Simple to implement, no need to resize the hash table.
• Disadvantages: Requires extra memory for pointers, performance degrades if many elements collide at the same index.

2. Open Addressing (Closed Hashing)​

• In open addressing, all elements are stored within the hash table itself, and when a collision occurs, alternative slots are probed to find an empty one.
• Common probing techniques include:
  • Linear Probing: Increment the index sequentially until an empty slot is found.
  • Quadratic Probing: Probe at quadratic intervals (i.e., 1, 4, 9, ...).
  • Double Hashing: Use a second hash function to determine the probe step.
• Advantages: No need for extra memory for pointers, can be efficient for smaller tables.
• Disadvantages: Can lead to clustering (for linear probing), needs good probing strategies to avoid performance degradation.

Example: Chaining in Python​

class HashTable:
    def __init__(self):
        self.table = [[] for _ in range(10)]  # Hash table with 10 slots

    def insert(self, key, value):
        index = hash(key) % len(self.table)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value  # Update if key exists
                return
        self.table[index].append([key, value])  # Add new key-value pair

    def search(self, key):
        index = hash(key) % len(self.table)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None

    def delete(self, key):
        index = hash(key) % len(self.table)
        for i, pair in enumerate(self.table[index]):
            if pair[0] == key:
                del self.table[index][i]
                return

            

# Example usage
hash_table = HashTable()
hash_table.insert('apple', 1)
hash_table.insert('banana', 2)
hash_table.insert('orange', 3)
print(hash_table.search('banana'))  # Output: 2
hash_table.delete('banana')
print(hash_table.search('banana'))  # Output: None

Example: Chaining in JavaScript​

class HashTable {
    constructor() {
        this.table = Array.from({ length: 10 }, () => []);  // Hash table with 10 slots
    }

    hash(key) {
        let hash = 0;
        for (let char of key.toString()) {
            hash += char.charCodeAt(0);
        }
        return hash % this.table.length;  // Simple hash function
    }

    insert(key, value) {
        const index = this.hash(key);
        for (let pair of this.table[index]) {
            if (pair[0] === key) {
                pair[1] = value;  // Update if key exists
                return;
            }
        }
        this.table[index].push([key, value]);  // Add new key-value pair
    }

    search(key) {
        const index = this.hash(key);
        for (let pair of this.table[index]) {
            if (pair[0] === key) {
                return pair[1];  // Return the value if key is found
            }
        }
        return null;  // Key not found
    }

    delete(key) {
        const index = this.hash(key);
        this.table[index] = this.table[index].filter(pair => pair[0] !== key);  // Remove the key-value pair
    }
}

// Example usage
const hashTable = new HashTable();
hashTable.insert('apple', 1);
hashTable.insert('banana', 2);
hashTable.insert('orange', 3);
console.log(hashTable.search('banana'));  // Output: 2
hashTable.delete('banana');
console.log(hashTable.search('banana'));  // Output: null