Словари и множества: хеши на службе скорости

Хеш-таблица — структура, превращающая поиск «есть ли элемент» из O(n) в O(1). В Python это dict и set.

Хеш-таблица — структура данных, которая по ключу за в среднем O(1) позволяет добавлять, удалять и проверять наличие элементов. В Python это dict и set.

Зачем это нужно

Огромное число задач сводится к вопросам «встречалось ли это значение?», «сколько раз?», «есть ли пара/дополнение?». Если отвечать на них перебором — O(n) на запрос и O(n^2) в сумме. Хеш-таблица отвечает за O(1) в среднем, превращая квадрат в линию. Это, пожалуй, самая используемая структура данных вообще: dict и set встречаются почти в каждом решении. Понимать их свойства и ограничения обязательно.

Идея «на пальцах»

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

Подсчёт частот и поиск пары

Покажем сразу несколько приёмов: подсчёт через Counter и поиск двух чисел с заданной суммой за один проход с помощью set.

from collections import Counter

a = [1, 2, 2, 3, 3, 3, 1]
cnt = Counter(a)                    # частоты за O(n)
print("Частоты:", dict(cnt))
print("Самый частый:", cnt.most_common(1)[0])

# Есть ли два числа с суммой target за O(n)?
target = 5
seen = set()
pair = None
for x in a:
    if target - x in seen:          # видели ли дополнение?
        pair = (target - x, x); break
    seen.add(x)
print("Пара с суммой", target, ":", pair)

В задаче о паре ключевая идея — хранить уже виденные числа в множестве и для каждого нового x спрашивать, встречалось ли его «дополнение» target − x. Проверка in для set — O(1), поэтому весь проход — O(n) вместо O(n^2).

Вывод:

Частоты: {1: 2, 2: 2, 3: 3}
Самый частый: (3, 3)
Пара с суммой 5 : (2, 3)

Множества: операции над наборами

Тип set поддерживает математические операции — пересечение, объединение, разность — и часто упрощает задачи о «общих элементах» или «уникальных». Все они работают за O(размера).

A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}
print("Объединение:", sorted(A | B))
print("Пересечение:", sorted(A & B))
print("Разность A\\B:", sorted(A - B))
print("Уникальных в A:", len(A))
print("5 в A?", 5 in A)

Эти операции читаются как математика: | — объединение, & — пересечение, - — разность. Удобно для задач вроде «сколько общих друзей», «какие элементы встречаются в обоих массивах».

Вывод:

Объединение: [1, 2, 3, 4, 5, 6, 7]
Пересечение: [4, 5]
Разность A\B: [1, 2, 3]
Уникальных в A: 5
5 в A? True

Группировка через defaultdict

Очень частый паттерн — сгруппировать элементы по ключу. collections.defaultdict избавляет от проверки «есть ли уже такой ключ».

from collections import defaultdict

words = ["apple", "banana", "avocado", "cherry", "blueberry"]
by_letter = defaultdict(list)
for w in words:
    by_letter[w[0]].append(w)      # группируем по первой букве
for letter in sorted(by_letter):
    print(letter, "->", by_letter[letter])

defaultdict(list) автоматически создаёт пустой список для нового ключа, поэтому append работает без подготовки. Аналогично defaultdict(int) удобен для подсчётов.

Вывод:

a -> ['apple', 'avocado']
b -> ['banana', 'blueberry']
c -> ['cherry']

Подводные камни

• «В среднем O(1)» ≠ «всегда O(1)». Существуют антитесты (специально подобранные ключи), вызывающие массовые коллизии и деградацию. На большинстве задач это не проблема, но на хеш-чувствительных стоит знать.
• Ключи должны быть хешируемыми. Список нельзя положить в set или использовать ключом dict (он изменяемый); используй tuple.
• Порядок. С Python 3.7 dict хранит порядок вставки, но set — нет; не полагайся на порядок элементов множества.
• Память. Хеш-таблицы тратят больше памяти, чем массивы — учитывай при жёстких лимитах.

Итог

• dict и set дают добавление/удаление/проверку за O(1) в среднем.
• Counter — мгновенный подсчёт частот; defaultdict — удобная группировка.
• Приём «храни виденное в set и спрашивай дополнение» превращает O(n^2) в O(n).
• Ключи должны быть хешируемыми (tuple, не list); «O(1)» — амортизированная оценка.