Card 05/ 10
Copying Buckets Across Unchanged on a Resize
A key's slot depends on the capacity, so keys left in their old slot can no longer be found.
Growing a hash table by copying each bucket to the same index of a larger array leaves most keys where no lookup will search for them. This card covers the symptom, why it happens, and the fix, which is to work out every key's bucket again.
The symptom is a table that loses keys when it grows: a key inserted before the growth is reported missing after it, and inserting it again stores a second copy. The trigger is a resize written as a copy, bucket 0 into bucket 0 and bucket 1 into bucket 1, with the new buckets left empty after the old ones. The mechanism is the lookup. It computes the hash code mod the new capacity, so it searches the bucket the key belongs in now, not the one it was put in.
Before the run: seven keys sit in eight buckets, with 13 in bucket 5. After a copy into 16 buckets, which bucket does a lookup for 13 search?
Bucket 13, because 13 mod 16 is 13. The copy left 13 in bucket 5, so the lookup finds an empty bucket and reports 13 missing.
The listing grows the same table both ways, with keys that are their own hash codes. grow_by_copying keeps each bucket at its old index, and grow_by_rehashing places each key in its bucket for the new size. The highlighted lines are the two placements.
def bucket_of(key: int, capacity: int) -> int:
return hash(key) % capacity
def grow_by_copying(buckets: list[list[int]]) -> list[list[int]]:
grown: list[list[int]] = [[] for _ in range(len(buckets) * 2)]
for index, bucket in enumerate(buckets):
grown[index] = list(bucket)
return grown
def grow_by_rehashing(buckets: list[list[int]]) -> list[list[int]]:
grown: list[list[int]] = [[] for _ in range(len(buckets) * 2)]
for bucket in buckets:
for key in bucket:
grown[bucket_of(key, len(grown))].append(key)
return grown
def contains(buckets: list[list[int]], key: int) -> bool:
return key in buckets[bucket_of(key, len(buckets))]
def show(name: str, buckets: list[list[int]]) -> None:
used = ", ".join(f"{i}: {' '.join(map(str, b))}" for i, b in enumerate(buckets) if b)
print(f"{name}, {len(buckets)} buckets: {used}")
keys = [5, 13, 21, 37, 8, 30, 42]
table: list[list[int]] = [[] for _ in range(8)]
for key in keys:
table[bucket_of(key, 8)].append(key)
show("before", table)
copied = grow_by_copying(table)
show("copied", copied)
print(f"copied: finds {' '.join(str(k) for k in keys if contains(copied, k))}")
print(f"copied: contains 13? {contains(copied, 13)}")
copied[bucket_of(13, 16)].append(13)
print(f"copied: after adding 13 again, it is stored {sum(b.count(13) for b in copied)} times")
rehashed = grow_by_rehashing(table)
show("rehashed", rehashed)
print(f"rehashed: contains 13? {contains(rehashed, 13)}")before, 8 buckets: 0: 8, 2: 42, 5: 5 13 21 37, 6: 30
copied, 16 buckets: 0: 8, 2: 42, 5: 5 13 21 37, 6: 30
copied: finds 5 21 37
copied: contains 13? False
copied: after adding 13 again, it is stored 2 times
rehashed, 16 buckets: 5: 5 21 37, 8: 8, 10: 42, 13: 13, 14: 30
rehashed: contains 13? TrueThe copied table still finds 5, 21 and 37, which keep their bucket at 16, so a test that uses only those keys passes. It loses 13, and 8, 30 and 42 with it, since each of the four has a new bucket. Adding 13 again then stores it twice, so the count of keys is wrong as well. Nothing raises an error: the damage shows up later, as entries that are missing or duplicated.
The remedy is rehashing: take every key out of every old bucket and insert it into the new array at its hash code mod the new capacity, as grow_by_rehashing does. It costs O(n) for n keys, which is why a table doubles when it grows rather than adding a few buckets at a time.
← → move through sections and cards