Building a Hash Table From Scratch in Python: Buckets, Collisions, Chaining
A hash table maps keys to values by hashing each key to a bucket index, then storing the (key, value) pair in that bucket. This post builds a HashTable class with fixed-size buckets and separate chaining (a list per bucket, appended to on collision), then runs put/get/delete on 8 string keys and looks at where each one landed.
The code
class HashTable:
# Fixed-size array of buckets; each bucket is a list of (key, value)
# pairs. Collisions (two keys landing in the same bucket) are handled
# by just appending to that bucket's list — "separate chaining".
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _index(self, key):
# A simple deterministic hash (sum of char codes, weighted by
# position) instead of Python's built-in hash() — str hashing is
# randomized per process by default, which would make bucket
# placement (and which keys collide) different on every run.
h = 0
for i, ch in enumerate(key):
h = (h * 31 + ord(ch)) % 1_000_003
return h % self.capacity
def put(self, key, value):
idx = self._index(key)
bucket = self.buckets[idx]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
idx = self._index(key)
for k, v in self.buckets[idx]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
idx = self._index(key)
bucket = self.buckets[idx]
for i, (k, _) in enumerate(bucket):
if k == key:
del bucket[i]
return
raise KeyError(key)
def bucket_sizes(self):
return [len(b) for b in self.buckets]
ht = HashTable(capacity=8)
pairs = [("apple", 1), ("banana", 2), ("cherry", 3), ("date", 4),
("elderberry", 5), ("fig", 6), ("grape", 7), ("honeydew", 8)]
print("=== put ===")
for k, v in pairs:
idx = ht._index(k)
ht.put(k, v)
print(f"put({k!r}, {v}) -> bucket {idx}")
print("\nbucket sizes:", ht.bucket_sizes())
for i, bucket in enumerate(ht.buckets):
if len(bucket) > 1:
print(f"collision in bucket {i}: {bucket}")
print("\n=== get ===")
for k, _ in pairs[:3]:
print(f"get({k!r}) ->", ht.get(k))
print("\n=== delete ===")
ht.delete("banana")
print("deleted 'banana', bucket sizes now:", ht.bucket_sizes())
try:
ht.get("banana")
except KeyError as e:
print("get('banana') raised KeyError:", e)8 keys go into a table with capacity=8. _index hashes each key deterministically so the same key always lands in the same bucket. After all 8 put calls, the code prints bucket sizes and flags any bucket holding more than one entry.
Running it
Real output:
=== put ===
put('apple', 1) -> bucket 3
put('banana', 2) -> bucket 7
put('cherry', 3) -> bucket 2
put('date', 4) -> bucket 5
put('elderberry', 5) -> bucket 2
put('fig', 6) -> bucket 4
put('grape', 7) -> bucket 5
put('honeydew', 8) -> bucket 1
bucket sizes: [0, 1, 2, 1, 1, 2, 0, 1]
collision in bucket 2: [('cherry', 3), ('elderberry', 5)]
collision in bucket 5: [('date', 4), ('grape', 7)]
=== get ===
get('apple') -> 1
get('banana') -> 2
get('cherry') -> 3
=== delete ===
deleted 'banana', bucket sizes now: [0, 1, 2, 1, 1, 2, 0, 0]
get('banana') raised KeyError: 'banana'Of the 8 keys, 2 pairs collided: 'cherry'/'elderberry' both hashed to bucket 2, and 'date'/'grape' both hashed to bucket 5 — bucket sizes ended up [0, 1, 2, 1, 1, 2, 0, 1], two buckets holding 2 entries each via chaining. get correctly returned each value including from the two-entry buckets. After delete('banana'), bucket 7 dropped to size 0 and a subsequent get('banana') raised KeyError: 'banana' as written.
Takeaway
With 8 keys in 8 buckets, this run landed 2 real collisions (bucket 2 and bucket 5), and both collided buckets still returned the correct value per key via the chained list — showing chaining resolving collisions correctly, not just avoiding them by luck.