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

Принцип. Хеш-функция превращает ключ в число, а остаток от деления на размер массива даёт индекс корзины. Вместо перебора мы вычисляем, где искать, — отсюда средняя сложность O(1).

Требования к хеш-функции: детерминированность (одинаковый ключ — одинаковый хеш), равномерное распределение по корзинам, быстрота. Равные ключи обязаны давать равный хеш.

Коллизии неизбежны: ключей больше, чем корзин. Два основных способа:

• метод цепочек — в корзине хранится список (или дерево) записей; при поиске идём по нему и сравниваем ключи. Так устроены HashMap в Java и unordered_map в C++;
• открытая адресация — все записи прямо в массиве; если ячейка занята, пробуем следующие по правилу: линейное пробирование (+1), квадратичное, двойное хеширование. Так устроен dict в Python. Удаление требует пометки «здесь было» (tombstone), иначе разорвётся цепочка поиска.

Коэффициент загрузки — отношение числа элементов к числу корзин. Чем он больше, тем больше коллизий. При превышении порога (около 0,75 для цепочек, 2/3 у Python) таблица увеличивается, обычно вдвое, и все ключи перераспределяются — дорого, но редко, поэтому вставка амортизированно O(1).

Худший случай — все ключи в одной корзине: O(n). Бывает при плохой хеш-функции или намеренной атаке; поэтому для строк используют хеш со случайной солью, а Java превращает длинные цепочки в деревья.

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

    def put(self, key, value):
        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.size += 1
        if self.size / len(self.buckets) > 0.75:
            self._resize()

    def get(self, key):
        bucket = self.buckets[hash(key) % len(self.buckets)]
        return next((v for k, v in bucket if k == key), None)

    def _resize(self):
        old = [pair for b in self.buckets for pair in b]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        self.size = 0
        for k, v in old:
            self.put(k, v)