Как устроена хеш-таблица и что такое метод цепочек?

Никакой магии — давай разберём по шагам, и всё встанет на места.

Хеш-таблица — это, по сути, массив «корзин» (бакетов) плюс хеш-функция, которая по ключу вычисляет, в какую корзину положить значение.

Шаг 1. Хеш-функция. Она превращает ключ (строку, число — что угодно) в число. Дальше берём остаток от деления на размер массива и получаем индекс бакета:

index = hash(key) % bucket_count

Так как мы сразу вычисляем индекс, нам не нужно перебирать все элементы — идём прямо в нужную ячейку. Отсюда и O(1) в среднем.

Шаг 2. Коллизии. Проблема: разные ключи могут дать один и тот же индекс (бакетов меньше, чем возможных ключей). Это называется коллизия, и её надо как-то разруливать.

Метод цепочек (chaining): в каждом бакете хранится не одно значение, а список пар (ключ, значение). При коллизии просто дописываем в этот список. При поиске идём в нужный бакет и перебираем его коротенький список.

class HashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        i = hash(key) % len(self.buckets)
        for pair in self.buckets[i]:
            if pair[0] == key:      # ключ уже есть — обновляем
                pair[1] = value
                return
        self.buckets[i].append([key, value])

    def get(self, key):
        i = hash(key) % len(self.buckets)
        for k, v in self.buckets[i]:
            if k == key:
                return v
        raise KeyError(key)

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

Альтернатива цепочкам — открытая адресация: при коллизии ищем следующий свободный бакет в самом массиве (без отдельных списков). Так устроен dict в CPython.

Итог: dict в Python — это хеш-таблица с открытой адресацией. set — то же самое, только без значений, одни ключи.