Collision Resolution Techniques in Hashing

What is a Collision?

In hashing, a collision occurs when two or more keys are hashed to the same index in the hash table, causing a conflict in storing the data.

Common Collision Resolution Techniques

1. Separate Chaining

In separate chaining, each index of the hash table points to a linked list (or similar data structure) that contains all the elements hashed to that index.

2. Open Addressing

In open addressing, when a collision occurs, the algorithm probes the hash table in a sequence to find an empty slot.

Python Example: Separate Chaining

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return sum(ord(c) for c in key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])

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

# Usage
ht = HashTable()
ht.insert('Alice', 25)
ht.insert('Bob', 30)
ht.insert('Eve', 22)

print(ht.search('Alice'))  # Output: 25
print(ht.search('Bob'))    # Output: 30
print(ht.search('Charlie'))  # Output: None