Implementing Hash Tables with Chaining and Linear Probing
Hash Function Implementation
def hash_func(key, size):
return sum(ord(c) for c in key) % size
Hash Table with Chaining
class HashTableChaining:
def __init__(self, size):
self.table = [[] for _ in range(size)]
self.comparisons = 0
Insert Method
def insert(self, name, number):
index = hash_func(name, len(self.table))
self.table[index].append((name, number))
Search Method
def search(self, name):
index = hash_func(name, len(self.table))
for n, num in self.table[index]:
self.comparisons += 1
if n == name:
return num
return None
Hash Table with Linear Probing
class HashTableLinearProbing:
def __init__(self, size):
self.table = [None] * size
self.comparisons = 0
Insert Method
def insert(self, name, number):
index = hash_func(name, len(self.table))
while self.table[index] is not None:
index = (index + 1) % len(self.table)
self.table[index] = (name, number)
Search Method
def search(self, name):
index = hash_func(name, len(self.table))
while self.table[index] is not None:
self.comparisons += 1
if self.table[index][0] == name:
return self.table[index][1]
index = (index + 1) % len(self.table)
return None
Client Data
clients = [
(“Alice”, “111”),
(“Bob”, “222”),
(“Charlie”, “333”),
(“David”, “444”)
]
names_to_find = [“Alice”, “David”, “Charlie”]
Using Hash Table with Chaining
chain = HashTableChaining(5)
for name, number in clients:
chain.insert(name, number)
for name in names_to_find:
chain.search(name)
Using Hash Table with Linear Probing
linear = HashTableLinearProbing(5)
for name, number in clients:
linear.insert(name, number)
for name in names_to_find:
linear.search(name)
Comparison Results
print(f”Chaining comparisons: {chain.comparisons}”)
print(f”Linear probing comparisons: {linear.comparisons}”)