Hash Functions and Collisions
DSA · Hashing
Theory
A hash function maps a key to an integer; the table uses hash % capacity as the bucket index. A good hash function is fast and spreads keys evenly. When two keys land in the same bucket, chaining stores both in a small list in that bucket, while open addressing probes for the next free slot. The load factor (items ÷ buckets) is kept low by resizing, which keeps operations O(1) on average.
Why we use it
Understanding collisions explains why hash tables are fast on average but can degrade, and how to design your own hashing.
When to use it
This matters when implementing a hash map, choosing keys, explaining worst-case behaviour in interviews, and designing consistent hashing in distributed systems.
How it works
- key
- Compute hash(key)
- Two keys share an index? Yes: Resolve: chaining (list) or open addressing (next slot). No: Store directly.
- Load factor too high? Yes: Resize and rehash. No: Continue.
- Done
Syntax
index = hash(key) % capacity
Chaining: buckets[index] = [(k1, v1), (k2, v2)]
Open addressing: try index, index+1, index+2 ...
Resize when load factor > ~0.7Example
class HashMap:
def __init__(self, size=4):
self.buckets = [[] for _ in range(size)]
def _index(self, key):
total = 0
for ch in str(key):
total = total * 31 + ord(ch)
return total % len(self.buckets)
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
def get(self, key):
for k, v in self.buckets[self._index(key)]:
if k == key:
return v
return None
m = HashMap()
for city, pin in [("Pune", 411001), ("Delhi", 110001), ("Goa", 403001), ("Agra", 282001), ("Ooty", 643001)]:
m.put(city, pin)
print("Delhi PIN:", m.get("Delhi"))
for i, b in enumerate(m.buckets):
print("Bucket", i, ":", b)Key points
- index = hash(key) % capacity
- Collisions are normal and must be handled
- Chaining vs open addressing
- Resizing keeps operations O(1) on average