Своя хеш-таблица с цепочками

СредняяДописатьГлава 5

#хеш-таблицы#коллизии#хеш-функцииid: ga-chained-hash-table

Соберите хеш-таблицу своими руками. Массив из size корзин, ключ попадает в корзину hash(key) % size, коллизии разрешаются цепочками: в каждой корзине лежит список пар. Допишите методы put и get. Пользоваться встроенным dict внутри нельзя. Пропуски помечены # TODO.

Пример

table = ChainedHashTable(size=4)
table.put("яблоко", 120)
table.put("молоко", 90)
table.put("яблоко", 110)   # обновление, а не второй ключ
table.get("яблоко")        # 110
table.get("хлеб", 0)       # 0
len(table)                 # 2

Решение

class ChainedHashTable:
    """Хеш-таблица с разрешением коллизий цепочками."""

    def __init__(self, size: int = 8) -> None:
        self.buckets: list[list[tuple[str, int]]] = [[] for _ in range(size)]

    def _bucket(self, key: str) -> list[tuple[str, int]]:
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key: str, value: int) -> None:
        """Добавляет пару или обновляет значение существующего ключа."""
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            # TODO: если ключ уже есть — замените пару и выйдите из метода
            pass
        # TODO: ключа не было — добавьте пару в корзину

    def get(self, key: str, default: int | None = None) -> int | None:
        """Значение по ключу или default."""
        # TODO: найдите ключ в его корзине
        return default

    def __len__(self) -> int:
        return sum(len(bucket) for bucket in self.buckets)

Вывод

tests.py — только для чтения
def test_put_get():
    """put и get для нескольких ключей"""
    table = ChainedHashTable(4)
    table.put("яблоко", 120)
    table.put("молоко", 90)
    assert table.get("яблоко") == 120, f"яблоко: получено {table.get('яблоко')!r}"
    assert table.get("молоко") == 90, f"молоко: получено {table.get('молоко')!r}"


def test_update():
    """Повторный put обновляет значение, а не добавляет второй ключ"""
    table = ChainedHashTable(4)
    table.put("яблоко", 120)
    table.put("яблоко", 110)
    assert table.get("яблоко") == 110, f"получено {table.get('яблоко')!r}"
    assert len(table) == 1, f"len = {len(table)}, ожидалось 1"


def test_missing_default():
    """Отсутствующий ключ → default"""
    table = ChainedHashTable()
    assert table.get("хлеб") is None, "без default должно вернуться None"
    assert table.get("хлеб", 0) == 0, "с default=0 должно вернуться 0"


def test_zero_value():
    """Значение 0 хранится и возвращается (не путать с «нет ключа»)"""
    table = ChainedHashTable()
    table.put("соль", 0)
    assert table.get("соль", -1) == 0, f"получено {table.get('соль', -1)!r}"


def test_all_collide():
    """Одна корзина: все ключи в коллизии, но различаются"""
    table = ChainedHashTable(size=1)
    for i in range(20):
        table.put(f"k{i}", i)
    table.put("k7", 700)
    assert len(table) == 20, f"len = {len(table)}, ожидалось 20"
    assert all(table.get(f"k{i}") == (700 if i == 7 else i) for i in range(20)), "значения перепутались"


def test_keys_in_right_buckets():
    """Каждая пара лежит в корзине hash(key) % size"""
    table = ChainedHashTable(8)
    for i in range(30):
        table.put(f"товар-{i}", i)
    for index, bucket in enumerate(table.buckets):
        for key, _ in bucket:
            assert hash(key) % 8 == index, f"ключ {key!r} лежит в корзине {index}, а должен в {hash(key) % 8}"
    assert len(table) == 30, f"len = {len(table)}, ожидалось 30"


def test_many():
    """1000 ключей в таблице на 64 корзины"""
    table = ChainedHashTable(64)
    for i in range(1000):
        table.put(str(i), i * i)
    assert all(table.get(str(i)) == i * i for i in range(1000)), "не все значения найдены"
    assert table.get("1000") is None, "найден несуществующий ключ"

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

Подсказка 1
Корзина — обычный список пар (ключ, значение). Ключи с одинаковым индексом (коллизия) лежат в одной корзине.
Подсказка 2
put: пройдите по корзине. Если ключ уже есть — замените пару bucket[i] = (key, value) и выйдите. Иначе допишите пару в конец.
Подсказка 3
get: вычислите индекс, пройдите только по его корзине. Ничего не нашлось — верните default.

solution.py

class ChainedHashTable:
    """Хеш-таблица с разрешением коллизий цепочками."""

    def __init__(self, size: int = 8) -> None:
        self.buckets: list[list[tuple[str, int]]] = [[] for _ in range(size)]

    def _bucket(self, key: str) -> list[tuple[str, int]]:
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key: str, value: int) -> None:
        """Добавляет пару или обновляет значение существующего ключа."""
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key: str, default: int | None = None) -> int | None:
        """Значение по ключу или default."""
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def __len__(self) -> int:
        return sum(len(bucket) for bucket in self.buckets)