Хеш-таблица, которая растёт

СложнаяНайти ошибку2 ошибкиГлава 5

#хеш-таблицы#коэффициент заполнения#коллизииid: ga-growing-hash-table

Хеш-таблица начинается с 4 корзин и удваивается, как только коэффициент заполнения (элементов / корзин) превышает 0.7. Так цепочки остаются короткими, а операции — O(1) в среднем. После вставки коэффициент не должен превышать 0.7. Но в коде две ошибки: таблица растёт не вовремя и после роста теряет ключи. Найдите и исправьте их.

Пример

table = GrowingHashTable()
for i in range(3):
    table.put(i, i * 10)      # 3 / 4 = 0.75 > 0.7 → 8 корзин
len(table.buckets)            # 8
table.get(2)                  # 20

Решение

class GrowingHashTable:
    """Хеш-таблица с цепочками, удваивается при коэффициенте заполнения > 0.7."""

    def __init__(self) -> None:
        self.buckets: list[list[tuple[object, object]]] = [[] for _ in range(4)]
        self.count = 0

    def load_factor(self) -> float:
        return self.count // len(self.buckets)

    def put(self, key: object, value: object) -> None:
        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.load_factor() > 0.7:
            self._resize()

    def _resize(self) -> None:
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        for i, bucket in enumerate(old):
            self.buckets[i] = bucket

    def get(self, key: object, default: object = None) -> object:
        for k, v in self.buckets[hash(key) % len(self.buckets)]:
            if k == key:
                return v
        return default

Вывод

tests.py — только для чтения
import math


def test_load_factor_value():
    """load_factor: 3 элемента в 4 корзинах → 0.75 до роста"""
    table = GrowingHashTable()
    table.count = 3
    got = table.load_factor()
    assert math.isclose(got, 0.75), f"ожидалось 0.75, получено {got!r}"


def test_grows_at_right_moment():
    """Третья вставка (3/4 = 0.75 > 0.7) удваивает таблицу до 8 корзин"""
    table = GrowingHashTable()
    table.put(0, "a")
    table.put(1, "b")
    assert len(table.buckets) == 4, f"после 2 вставок корзин {len(table.buckets)}, ожидалось 4"
    table.put(2, "c")
    assert len(table.buckets) == 8, f"после 3 вставок корзин {len(table.buckets)}, ожидалось 8"


def test_load_factor_bounded():
    """После каждой вставки коэффициент заполнения не больше 0.7"""
    table = GrowingHashTable()
    for i in range(200):
        table.put(f"key{i}", i)
        assert table.load_factor() <= 0.7, f"после {i + 1} вставок коэффициент {table.load_factor():.2f}"


def test_get_after_resize():
    """Все ключи находятся после нескольких удвоений"""
    table = GrowingHashTable()
    for i in range(50):
        table.put(i, i * 10)
    missing = [i for i in range(50) if table.get(i) != i * 10]
    assert not missing, f"не находятся ключи: {missing[:8]}"


def test_keys_in_right_buckets():
    """После роста каждая пара лежит в корзине hash(key) % size"""
    table = GrowingHashTable()
    for i in range(20):
        table.put(f"k{i}", i)
    size = len(table.buckets)
    for index, bucket in enumerate(table.buckets):
        for key, _ in bucket:
            assert hash(key) % size == index, f"{key!r} в корзине {index}, а должен в {hash(key) % size}"


def test_update_does_not_grow():
    """Обновление существующего ключа не увеличивает count"""
    table = GrowingHashTable()
    table.put("x", 1)
    table.put("x", 2)
    assert table.count == 1 and table.get("x") == 2, f"count = {table.count}, x = {table.get('x')!r}"


def test_missing_key():
    """Отсутствующий ключ → default"""
    table = GrowingHashTable()
    table.put("a", 1)
    assert table.get("b") is None and table.get("b", 0) == 0, "для отсутствующего ключа — default"

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 growing_hash_table.py — тесты те же, результат покажет ✓ / ✗ и итог.

Подсказка 1
Запустите тесты: видны две разные проблемы — таблица растёт не вовремя и после роста теряет ключи. Разберитесь с каждой по очереди.
Подсказка 2
Посчитайте load_factor вручную для 3 элементов в 4 корзинах. Что вернёт выражение из кода?
Подсказка 3
После увеличения массива корзин изменился делитель в hash(key) % size. В какой корзине теперь должен лежать каждый ключ?
Подсказка 4
Переносить корзины целиком нельзя — каждый ключ нужно разместить заново (rehash).

solution.py

class GrowingHashTable:
    """Хеш-таблица с цепочками, удваивается при коэффициенте заполнения > 0.7."""

    def __init__(self) -> None:
        self.buckets: list[list[tuple[object, object]]] = [[] for _ in range(4)]
        self.count = 0

    def load_factor(self) -> float:
        return self.count / len(self.buckets)

    def put(self, key: object, value: object) -> None:
        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.load_factor() > 0.7:
            self._resize()

    def _resize(self) -> None:
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        for bucket in old:
            for key, value in bucket:
                self.buckets[hash(key) % len(self.buckets)].append((key, value))

    def get(self, key: object, default: object = None) -> object:
        for k, v in self.buckets[hash(key) % len(self.buckets)]:
            if k == key:
                return v
        return default