Resizing, Average Cost and How dict and set Relate
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A table that never grows ends up with long chains and slow lookups. A table that grows at the right time stays fast. You will measure how full a table is, grow it, and see why the average cost stays constant. Then you will connect your map to Python's dict and set.
Load factor: how full is the table
The load factor is the number of stored keys divided by the number of slots. It predicts how long chains or probe runs are.
A table with 8 slots and 4 keys is half full. A table with 8 slots and 24 keys has chains of length 3 on average. The ratio of keys to slots tells you how long a typical chain is.
keys, slots = 12, 8load_factor = keys / slotsprint(load_factor)Example 1 · Load factor and chain lengths
keys = list(range(0, 36, 3))buckets = [[] for _ in range(8)]for key in keys: buckets[key % 8].append(key)print(len(keys) / len(buckets))print([len(b) for b in buckets])1.5 [2, 2, 1, 2, 1, 1, 2, 1]
What this code does
- Twelve keys in eight slots give a load factor of 1.5.
- The chains are close to that average, between 1 and 2 keys each. Even spread is what keeps lookups cheap.
With chaining, the average chain length equals the load factor. With probing, the load factor must stay below 1, and lookups slow down quickly as it approaches 1. Most tables resize when the load factor passes a limit such as 0.75, and CPython uses about 2/3.
Resizing: rehash into a bigger table
Rehashing is building a larger table and inserting every existing key again with the new size, which happens when the load factor passes a limit.
When the load factor passes the limit, make a table twice as big and put every key in again. The slot is hash % size, and the size changed, so most keys move to new slots.
def _grow(self): old = self.buckets self.buckets = [[] for _ in range(2 * len(old))] for bucket in old: for k, v in bucket: self.buckets[hash(k) % len(self.buckets)].append((k, v))Example 2 · A map that grows
class GrowingMap: def __init__(self): self.buckets = [[] for _ in range(4)] self.count = 0
def put(self, key, value): bucket = self.buckets[hash(key) % len(self.buckets)] for i, (k, _) in enumerate(bucket): if k == key: bucket[i] = (key, value) return bucket.append((key, value)) self.count += 1 if self.count > 0.75 * len(self.buckets): self._grow()
def _grow(self): old = self.buckets self.buckets = [[] for _ in range(2 * len(old))] for bucket in old: for k, v in bucket: self.buckets[hash(k) % len(self.buckets)].append((k, v))
def get(self, key, default=None): for k, v in self.buckets[hash(key) % len(self.buckets)]: if k == key: return v return default
m = GrowingMap()sizes = []for key in range(1, 11): m.put(key, key * key) sizes.append(len(m.buckets))print(sizes)print(m.get(7), m.get(99, "none"))[4, 4, 4, 8, 8, 8, 16, 16, 16, 16] 49 none
What this code does
- The table starts with 4 slots and doubles when the count passes three quarters of the slots: at the 4th key and again at the 7th and 13th.
- After growing, every key is still found, because each was rehashed into the new size.
You cannot copy the buckets as they are, because the new size gives new remainders. Every key is hashed again, so one resize costs time proportional to the number of keys.
Why the average cost is still constant
Amortized cost is the average cost per operation over a long run of operations, so a rare slow step is paid for by the many fast ones around it.
One resize is slow, but resizes are rare. Each time the table doubles, the next resize is twice as far away. Spread over all the inserts, the extra work per insert is a small constant.
moves, capacity = 0, 4for count in range(1, 1001): if count > 0.75 * capacity: moves += count - 1 capacity *= 2print(moves, capacity)Example 3 · Counting the moves
moves, capacity = 0, 4for count in range(1, 1001): if count > 0.75 * capacity: moves += count - 1 capacity *= 2print(moves, capacity)print(round(moves / 1000, 2))1533 2048 1.53
What this code does
- Each resize moves every key stored so far. Adding up all the resizes for 1000 inserts gives 1533 moves, about one and a half per insert.
- That is a small constant number of extra moves per insert, so insert is constant on average. This doubling idea is also how a Python list grows.
The total number of keys moved is only about twice the number of inserts at most. So each insert pays a few extra steps on average, even though a single insert may pay a lot.
How dict and set relate
A set is an unordered collection of unique hashable items, stored in a hash table that keeps keys but no values.
A dict is a hash table of key-value pairs. A set is the same machine with keys only. Both give constant average time for in, insert and delete, and both need hashable keys.
stock = {"pen": 4, "ink": 0, "pad": 9}print(set(stock) == stock.keys())print(stock.keys() & {"pen", "cap"})Example 4 · A dict is a set with values
orders = {"A12": 40, "B07": 15, "C33": 22}paid = {"B07", "C33", "D90"}print(sorted(orders.keys() & paid))print(sorted(paid - orders.keys()))print("A12" in orders, "A12" in paid)['B07', 'C33'] ['D90'] True False
What this code does
- Dictionary keys support set operations, so intersecting orders with paid ids is one expression.
inon a dict or set is one hash lookup, so it stays fast however many ids there are.
Example 5 · Comparisons: list scan against buckets
ids = list(range(1000))scan = 0for value in ids: scan += 1 if value == 999: break
buckets = [[] for _ in range(1024)]for value in ids: buckets[value % 1024].append(value)probe = 0for value in buckets[999 % 1024]: probe += 1 if value == 999: breakprint(scan, probe)1000 1
What this code does
- The list scan compares 1000 values to find the last one. The bucket holds one value, so one comparison is enough.
- Hash lookup trades some extra memory (the empty slots) for a lookup that does not grow with the data.
The keys of a dictionary behave like a set, so you can use &, | and - on them directly. The earlier lesson Hash Tables, Sets and Dictionaries Under the Hood (opens in a new tab) covers the compact layout that makes a dict remember insertion order. A map built from scratch, like the one here, does not.
Next step
Check your understanding
11 quick questions