Хеш-таблица: коллизии, dict и set в Python

Операции словаря и множества опираются на контракт хеша и механизм разрешения коллизий. Их обычная константная стоимость зависит от распределения ключей и не является worst-case гарантией.

Хеш-функция, бакеты и инвариант равенства

Хеш-таблица использует массив позиций — бакетов. В учебной модели индекс для пары (key, value) можно выбирать так:

bucket_index = hash(key) % capacity

capacity — размер массива, а hash(key) — целое число, полученное по протоколу хеширования конкретного типа. Оно не обязано вычисляться только «по содержимому»: объект с обычной identity-семантикой может наследовать хеш, связанный с его идентичностью.

Обязательный контракт выглядит так:

Если a == b, то hash(a) == hash(b).

Иначе равный ключ при поиске мог бы попасть в другую позицию. Обратное неверно: одинаковый hash не доказывает равенство. Более того, разные hashes после сведения по модулю тоже могут попасть в один бакет. Совпадение позиции для разных ключей — коллизия; таблица различает кандидатов дополнительной проверкой ==. При capacity = 8 и тысяче разных ключей совпадения бакетов неизбежны по принципу Дирихле.

Хеш ключа и свойства, влияющие на его равенство, должны оставаться стабильными, пока ключ хранится в таблице. Встроенные list, dict и set поэтому намеренно не поддерживают hash. Однако изменяемость сама по себе не является формальным запретом: пользовательский объект с identity-равенством может быть hashable. Опасен именно объект, у которого после вставки меняются hash или отношение равенства.

Разрешение коллизий цепочками: ожидаемая O(1) и худшая O(n)

Один из классических способов разрешать коллизии — цепочки: каждый бакет хранит список пар.

Поиск ключа k выглядит так:

1. Вычислить i = hash(k) % capacity.
2. Пройти по списку в бакете i.
3. Для каждой пары (stored_key, value) проверить stored_key == k.
4. При совпадении вернуть value.

Минимальная учебная реализация:

class HashTableChaining:
    def __init__(self, capacity: int = 8):
        if capacity <= 0:
            raise ValueError('capacity must be positive')
        self.capacity = capacity
        self.buckets: list[list] = [[] for _ in range(capacity)]

    def _bucket(self, key):
        return hash(key) % self.capacity

    def set(self, key, value):
        b = self._bucket(key)
        for pair in self.buckets[b]:
            if pair[0] == key:
                pair[1] = value
                return
        self.buckets[b].append([key, value])

    def get(self, key):
        b = self._bucket(key)
        for pair in self.buckets[b]:
            if pair[0] == key:
                return pair[1]
        raise KeyError(key)

Введём коэффициент заполнения α = n / capacity, где n — число хранимых элементов. Если хеши распределяются равномерно, ожидаемая длина цепочки равна α. При постоянном α, который полноценная таблица поддерживает расширением, поиск проверяет ожидаемо O(1) кандидатов. Учебный класс выше не реализует resize: при фиксированном capacity и растущем n его α растёт, поэтому ожидаемая стоимость перестанет быть константной.

Ожидаемая O(1) относится к распределению ключей по позициям и не является worst-case гарантией. Амортизированный анализ отвечает на другой вопрос — распределяет редкие дорогие изменения размера по последовательности вставок. В реальной расширяемой таблице вставка может одновременно иметь вероятностную ожидаемую оценку по коллизиям и амортизированную оценку по resize.

В худшем случае все n ключей попадают в один бакет. Тогда поиск или обновление может просмотреть цепочку длины n и стоит O(n); последовательность из n таких вставок может занять O(n²). Специальный пользовательский тип с постоянным __hash__ создаёт такой случай независимо от распределения обычных строк или чисел.

CPython dict не использует цепочки: это таблица с открытым адресованием, которая ищет другую позицию по последовательности проб. Общими остаются проверка равенства найденного кандидата и разрыв между ожидаемой O(1) и худшей O(n).

dict и set в Python: hashability, операции и сложность

Ключ Python-словаря обязан быть hashable: у него определён hash(), хеш и равенство стабильны во время хранения, а равные объекты дают одинаковый хеш.

Для встроенных типов:

• int, str, float, bytes — hashable.
• tuple — hashable, только если hashable все его элементы. (1, 2) подходит, (1, [2]) — нет.
• list, dict, set — unhashable; попытка использовать их как ключ даёт TypeError.
• Экземпляр класса, наследующего identity-равенство и identity-хеш от object, hashable. Если класс определяет __eq__, но не совместимый __hash__, Python по умолчанию делает его экземпляры unhashable.

print(hash((1, 2)))
try:
    hash((1, [2]))
except TypeError as error:
    print(type(error).__name__)  # TypeError

Hashability не является буквальным синонимом неизменяемости. Изменяемый identity-объект допустим как ключ, пока его hash и равенство не меняются. Если же __eq__ зависит от изменяемых полей, совместимый __hash__ не должен меняться после вставки; обычно такие value-объекты разумнее оставить unhashable.

Операции dict. Поиск d[key] и проверка key in d работают за ожидаемую O(1), в худшем случае O(n). Вставка имеет ту же ожидаемую оценку по коллизиям и амортизированную O(1) по серии расширений; отдельный resize или патологический поиск позиции может стоить O(n). Идиома для счётчика:

freq: dict[str, int] = {}
for word in ["apple", "banana", "apple", "cherry", "banana", "apple"]:
    freq[word] = freq.get(word, 0) + 1

print(freq)  # {'apple': 3, 'banana': 2, 'cherry': 1}

d.get(key, 0) возвращает default, не создавая запись. В отличие от него, d[key] поднимает KeyError при отсутствии ключа, а d.setdefault(key, 0) создаёт запись.

Операции set. s.add(x) и x in s имеют ожидаемую O(1); set тоже реализован как хеш-таблица с открытым адресованием, но хранит элементы без связанных значений.

Дедупликация с сохранением порядка первого появления:

def deduplicate(seq):
    seen = set()
    result = []
    for x in seq:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

print(deduplicate([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]))
# [3, 1, 4, 5, 9, 2, 6]

list(set(seq)) удаляет повторы, но не гарантирует порядок первого появления. Вариант с seen работает за ожидаемое O(n) и сохраняет первое вхождение каждого элемента.

Ожидаемая O(1) не является worst-case гарантией. Для обычных данных dict и set быстры, но одна операция может деградировать до O(n), а последовательность зависимых операций — до O(n²).

Алгоритмы «два числа в сумму» и «группировка анаграмм» на dict

Two Sum. Дан список nums и число target. Нужно найти два разных индекса i, j, для которых nums[i] + nums[j] == target.

Наивный подход перебирает пары за O(n²). Хеш-подход для каждого элемента проверяет, встречалось ли раньше значение target - nums[i]:

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # значение -> индекс
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []  # решение не найдено

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2]

Инвариант: проверка выполняется до записи текущего элемента. Если сначала записать seen[num] = i, то уже на первом элементе nums = [3, 3], target = 6 можно вернуть [0, 0] и использовать один индекс дважды.

Цикл делает O(n) ожидаемо-константных операций dict, поэтому ожидаемое время равно O(n), а память — O(n). При патологических коллизиях очередная операция может просмотреть O(n) кандидатов, и worst-case время всего алгоритма достигает O(n²).

Группировка анаграмм. Два слова являются анаграммами тогда и только тогда, когда у них одинаковое мультимножество символов. После сортировки "eat", "tea" и "ate" дают один канонический ключ "aet".

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = {}
    for word in words:
        key = "".join(sorted(word))   # hashable canonical key
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
for group in result:
    print(group)
# ['eat', 'tea', 'ate']
# ['tan', 'nat']
# ['bat']

sorted(word) упорядочивает символы, а join превращает их в hashable строку. Ключ одинаков для равных мультимножеств символов и различается, если отличается хотя бы символ или его кратность.

Сортировка слова длиной |w| стоит O(|w| log |w|), поэтому ожидаемое время по всем словам равно O(Σ |w| log |w|). Если максимальная длина слова равна L, эту оценку можно записать как O(n · L log L). Память на ключи, группы и результат — O(Σ |w|).

При обычном поведении dict сортировки определяют асимптотику. В worst case n операций со словарём могут суммарно добавить O(n²), поэтому полная оценка становится O(Σ |w| log |w| + n²); построение самих ключей от коллизий не меняется.

Как продолжить практику

После этого разбора важно уметь выбирать структуру данных под операции, а не использовать dict для любой задачи. Для сравнения решений открыт соседний урок: односвязный список. Текущий материал — бесплатное превью; полный курс алгоритмов и структур данных на Python платный. В его программе можно посмотреть последовательность тем и выбрать, подходит ли вам дальнейшая практика.