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.
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.
In open addressing, when a collision occurs, the algorithm probes the hash table in a sequence to find an empty slot.
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