DSA Hash Tables
A hash table stores key and value pairs and finds any key almost instantly.
The Idea
Imagine a school with 26 cupboards, one for each letter. Ayesha's file goes in cupboard A, Bilal's in cupboard B. To find Bilal's file you go straight to B instead of searching every cupboard.
A hash table does the same with a hash function: it turns a key into a number, and that number decides the bucket where the value is stored.
A Tiny Hash Function
Here is a simple (not very good) hash function that adds the character codes and takes the remainder:
Example
def simple_hash(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
for name in ["Ali", "Sara", "Hamza"]:
print(name, "->", simple_hash(name, 10))Ali -> 8 Sara -> 1 Hamza -> 7
So "Ali" would be stored in bucket 8 of a table with 10 buckets.
Collisions
Sometimes two keys get the same bucket. This is a collision. A common fix is chaining: each bucket holds a small list of pairs.
Example
class HashTable:
def __init__(self, size=10):
self.buckets = [[] for _ in range(size)]
def _index(self, key):
return sum(ord(c) for c in key) % 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
prices = HashTable()
prices.put("chai", 60)
prices.put("samosa", 40)
prices.put("chai", 70)
print(prices.get("chai"))
print(prices.get("samosa"))
print(prices.get("pizza"))70 40 None
Costs
| Operation | Average | Worst case |
|---|---|---|
| Insert | O(1) | O(n) |
| Look up | O(1) | O(n) |
| Delete | O(1) | O(n) |
The worst case only happens if almost every key lands in the same bucket. Good hash functions spread keys evenly, so real hash tables are very fast.
Python's dict and set are hash tables built for you, with an excellent hash function. In real code, use them instead of writing your own.
Using a Dictionary to Count
Counting how often each item appears is a classic hash table job:
Example
words = "chai biryani chai nihari chai biryani".split()
counts = {}
for w in words:
counts[w] = counts.get(w, 0) + 1
print(counts)
print(max(counts, key=counts.get)){'chai': 3, 'biryani': 2, 'nihari': 1}
chaiThis is O(n). Doing the same with nested loops would be O(n^2).
Using a Set for Fast Checks
The two-sum problem: does any pair of numbers add up to a target? A set makes it O(n).
Example
def two_sum(numbers, target):
seen = set()
for n in numbers:
if target - n in seen:
return (target - n, n)
seen.add(n)
return None
print(two_sum([8, 3, 11, 5, 7], 12))
print(two_sum([1, 2, 3], 50))(5, 7) None
For each number we ask, "have I already seen the number that completes the pair?" Checking a set takes O(1) on average.
Exercise
Exercise
What is a collision in a hash table?