Load Factor and Rehashing

The speed of a hash table depends on its load factor: α = n / m, where n is the number of elements and m the number of buckets. With chaining α is the average chain length, with open addressing it is the share of occupied cells. As α grows the table slows down, so when α exceeds a threshold the table is enlarged and all elements are placed again (rehashing).

Why rehash

When m changes, hash(key) % m changes too, so the old buckets cannot be copied as they are: every element is recomputed with the new m. In the example the keys 1, 5, 9, 13 share one bucket for m = 4, and split into two buckets for m = 8.

Implementation

The threshold is max_load = 0.75. After each put, if α > max_load the capacity doubles. The moves counter shows how many elements were moved during rehashing.

class ResizingMap:
    def __init__(self, capacity=4, max_load=0.75):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        self._max_load = max_load
        self.moves = 0

    def capacity(self):
        return len(self._buckets)

    def load_factor(self):
        return self._size / len(self._buckets)