В методе цепочек (separate chaining) каждая ячейка хеш-таблицы (корзина, bucket) — это список. Все ключи, попавшие в одну корзину, лежат в этом списке. Коллизия перестаёт быть проблемой: просто удлиняется цепочка. Хеш-функции знакомы по предыдущей теме.

Массив и цепочки: ключи 1, 5, 9 попадают в одну корзину
Массив и цепочки: ключи 1, 5, 9 попадают в одну корзину

Операции

  • Вставка (put): номер корзины hash(key) % m. Если ключ в цепочке есть, обновляем значение, иначе добавляем в конец.
  • Поиск (get): находим ту же корзину и проходим по цепочке, сравнивая через ==.
  • Удаление (remove): убираем элемент из цепочки.

Сравнение идёт через ==, поэтому для ключей важен контракт __eq__/__hash__.

Реализация

python
class HashMap:
    def __init__(self, capacity=8):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]