Hash Functions, Buckets and a Small Map
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A hash table finds a key without looking at every item. A function turns the key into a number, the number picks a slot, and only that slot is searched. You will build one step by step. The earlier lesson Hash Tables, Sets and Dictionaries Under the Hood (opens in a new tab) showed how CPython does it. Here you write a small one yourself.
From a key to a slot
A hash table is a structure that stores key-value pairs in an array of slots, and uses a hash of the key to choose the slot. Lookup, insert and delete take constant time on average.
A shop has a million products and must find one by its id. Scanning a list takes up to a million steps. A hash table turns the id into a number and uses that number as a position, so one step is enough.
SIZE = 8for key in [105, 212, 37, 98]: print(key, "-> slot", hash(key) % SIZE)Example 1 · Slots for integer keys
SIZE = 8keys = [105, 212, 37, 98, 13, 45]for key in keys: print(key, "->", hash(key) % SIZE)105 -> 1 212 -> 4 37 -> 5 98 -> 2 13 -> 5 45 -> 5
What this code does
- Small integers hash to themselves, so the slot is just
key % 8. - 13 and 45 both give slot 5. Two keys sharing a slot is a collision, covered in the next lesson.
hash(key) gives an integer for the key. The remainder after % SIZE is always between 0 and 7, so it is a valid position in a list of 8 places. The same key always lands in the same slot.
A hash function you can print
A hash function turns a key into an integer. Equal keys must always give equal integers, and different keys should spread over many integers.
Python's own hash() of a string changes every time Python starts, on purpose. To get numbers that stay the same, write your own. Multiply the running value by a small number before adding each character, so the order of letters matters.
def text_hash(text): value = 0 for ch in text: value = (value * 31 + ord(ch)) % 1_000_003 return valueprint(text_hash("cat"), text_hash("act"))Example 2 · Order-blind and order-aware hashes
def text_hash(text): value = 0 for ch in text: value = (value * 31 + ord(ch)) % 1_000_003 return value
def letter_sum(text): return sum(ord(ch) for ch in text)
print(letter_sum("cat"), letter_sum("act"))print(text_hash("cat"), text_hash("act"))312 312 98262 96402
What this code does
- The plain sum gives the same value for every anagram, so those keys would crowd one bucket.
- The multiply-and-add hash treats each position differently, so "cat" and "act" separate. Real hash functions follow the same idea with better constants.
Adding only the letter codes would give "cat" and "act" the same number, because addition ignores order. With the multiplier 31 they differ. The % 1_000_003 keeps the number small.
Buckets: a list of lists
A bucket is one slot of a hash table. It holds every key whose hash maps to that slot, here as a short list of key-value pairs.
Each slot of the table is a bucket. A bucket here is a small list of key-value pairs. To put a key in, find its bucket and either replace an existing pair or add a new one.
class SimpleMap: def __init__(self, size=8): self.buckets = [[] for _ in range(size)]
def _bucket(self, key): return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value): bucket = self._bucket(key) for i, (k, _) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value))Example 3 · A small working map
class SimpleMap: def __init__(self, size=8): self.buckets = [[] for _ in range(size)] self.count = 0
def _bucket(self, key): return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value): bucket = self._bucket(key) for i, (k, _) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value)) self.count += 1
def get(self, key, default=None): for k, v in self._bucket(key): if k == key: return v return default
def remove(self, key): bucket = self._bucket(key) for i, (k, _) in enumerate(bucket): if k == key: del bucket[i] self.count -= 1 return True return False
stock = SimpleMap()for product_id, qty in [(101, 5), (205, 12), (101, 7), (333, 1)]: stock.put(product_id, qty)print(stock.count, stock.get(101), stock.get(999, "missing"))print(stock.remove(205), stock.remove(205), stock.count)3 7 missing True False 2
What this code does
- Key 101 is put twice. The second put replaces the first value, so the count is 3 and the value is 7.
removereturns True the first time and False the second time, because the pair is gone.
The loop walks only one bucket, never the whole table. If the table has 8 buckets and keys spread evenly, each bucket holds about one eighth of the keys.
Which keys are allowed
An object is hashable if it has a hash that never changes during its life and it can be compared with ==. Equal hashable objects must have equal hashes.
A key must keep the same hash for its whole life. If a key could change while stored, the map would look in the wrong bucket and lose it. That is why lists cannot be keys but tuples can.
prices = {(1, 2): "pair key"}try: prices[[1, 2]] = "list key"except TypeError as error: print(error)Example 4 · Hashable and unhashable keys
seats = {}seats[(2, 5)] = "Asha"seats[(2, 6)] = "Ben"print(seats[(2, 5)], len(seats))print(hash((2, 5)) == hash((2, 5)))try: seats[[2, 7]] = "Chen"except TypeError as error: print("TypeError:", error)Asha 2 True TypeError: unhashable type: 'list'
What this code does
- A tuple key such as a (row, seat) pair is a natural way to key a grid.
- The same tuple always hashes the same. The list is rejected before anything is stored.
A tuple of numbers never changes, so it is hashable. A list can change, so Python refuses it. Your own class is hashable by default, and if you define __eq__ you must define __hash__ to match.
Next step
Check your understanding
11 quick questions