Коэффициент заполнения и рехеширование

Скорость хеш-таблицы зависит от коэффициента заполнения (load factor): α = n / m, где n — число элементов, m — число корзин. При цепочках α — это средняя длина цепочки, при открытой адресации — доля занятых ячеек. С ростом α таблица замедляется, поэтому при превышении порога таблицу увеличивают и перекладывают все элементы заново (рехеширование, rehashing).

Зачем рехеширование

Когда m меняется, меняется и hash(key) % m, поэтому старые корзины нельзя перенести как есть: каждый элемент пересчитывается с новым m. В примере ключи 1, 5, 9, 13 при m = 4 лежат в одной корзине, а при m = 8 расходятся по двум.

Реализация

Порог max_load = 0.75. После каждого put, если α > max_load, ёмкость удваивается. Счётчик moves показывает, сколько элементов было перенесено при рехешировании.

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)