Хеш-таблицы и множества

Интуиция: гардероб в театре

Ты сдаёшь куртку в гардероб и получаешь номерок 42. Вечером гардеробщик не обходит все вешалки, а сразу идёт к сорок второй. Хеш-таблица работает так же: по ключу она сразу вычисляет, где лежит значение, и не перебирает всё подряд.

Поэтому поиск, вставка и удаление в среднем занимают O(1). В массиве поиск стоит O(n), в отсортированном массиве O(log n). Многие задачи на собесе решаются переходом от «перебрать всё» к «спросить у хеш-таблицы», и ты сейчас научишься это делать.

Как она устроена

Внутри обычный массив. Его ячейки называют корзинами (buckets). Чтобы положить ключ, таблица делает два шага:

1. Хеш-функция превращает ключ в число: hash("кот") → 9182734.
2. Это число приводится к номеру корзины: 9182734 % 7 → 1. Ключ кладётся в корзину 1.

При поиске повторяются те же два шага, и мы сразу попадаем в нужную корзину.

Коллизии

Корзин конечное число, а ключей бесконечно много, поэтому два разных ключа иногда попадают в одну корзину. Это называется коллизия, и она возникает в любой хеш-таблице. Основных способов борьбы два:

• Цепочки (chaining): в корзине хранится маленький список, и при поиске таблица проходит по нему. На схеме выше «сыр» и «нос» лежат цепочкой.
• Открытая адресация: если корзина занята, таблица пробует следующую по определённому правилу.

Когда элементов становится много относительно числа корзин (это отношение называют коэффициентом заполнения), таблица расширяется. Обычно она увеличивается примерно вдвое и перекладывает все элементы. Одно такое расширение стоит O(n), но случается редко, поэтому в среднем вставка остаётся O(1). Это называется амортизированная оценка.

💡 Хорошая хеш-функция раскидывает ключи по корзинам равномерно. Тогда цепочки короткие и всё работает быстро. Писать её самому на собесе не придётся: ты пользуешься встроенными dict, HashMap, unordered_map, Map, map.

Множество vs словарь

	Множество (set)	Словарь (map / dict)
Что хранит	только ключи	пары ключ → значение
Главный вопрос	«есть ли такой элемент?»	«что лежит по этому ключу?»
Python	set()	dict()
Java	HashSet	HashMap
C++	unordered_set	unordered_map
JS	Set	Map
Go	map[K]struct{}	map[K]V

Устроены они одинаково. Множество можно представить как словарь, у которого значения не важны.

Три типовых приёма

1. «Видели ли раньше?» Идёшь по массиву и складываешь элементы во множество. Перед добавлением проверяешь, нет ли элемента там уже. Так находятся дубликаты, первый повторяющийся символ, цикл в последовательности.

2. Подсчёт частот. Ключом служит элемент, значением сколько раз он встретился. Этот приём нужен, когда спрашивают «самый частый элемент», «встречается ровно один раз», «одинаковый ли набор букв».

3. Группировка по ключу. Для каждого элемента вычисляешь «признак группы» и делаешь его ключом, а значением будет список элементов. Например, сгруппировать слова по первой букве: groups[w[0]].append(w). Самое интересное в таких задачах — придумать правильный ключ.

💡 Если в условии есть «найти пару», «встречался ли», «сколько раз», «сгруппировать», почти наверняка нужна хеш-таблица.

Шаблон кода: частоты и дубликаты

def count_freq(words):
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1  # 0, если ключа ещё нет
    return freq

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:      # уже видели — нашли дубликат
            return True
        seen.add(x)
    return False

print(count_freq(["a", "b", "a"]))  # {'a': 2, 'b': 1}
print(has_duplicate([1, 2, 3, 1]))  # True

Сложность

Операция	В среднем	В худшем
Вставка	O(1)*	O(n)
Поиск	O(1)	O(n)
Удаление	O(1)	O(n)
Память	O(n)	O(n)

* амортизированно, с учётом редких расширений.

Худший случай O(n) наступает, когда все ключи попадают в одну корзину и поиск превращается в проход по длинной цепочке. Так бывает при плохой хеш-функции или при специально подобранных ключах (хеш-атака). Оба примера выше работают за O(n) по времени и O(n) по памяти.

Как это звучит на собесе

«Наивно можно сравнить каждую пару, это O(n²). Я заведу хеш-множество и пройду по массиву один раз. Для каждого элемента проверю, есть ли он уже во множестве, за O(1) в среднем. Итого O(n) по времени и O(n) по дополнительной памяти. В худшем случае при коллизиях операции деградируют до O(n), но на практике это редкость».

Ты называешь наивное решение, улучшаешь его и честно оговариваешь худший случай. Интервьюеры такой ход ценят.

Частые ошибки

• Изменяемый ключ. В Python список нельзя сделать ключом, нужен tuple. В Java нельзя менять объект, который уже лежит в HashMap ключом: его хеш изменится, и таблица его «потеряет».
• Свой класс без equals/hashCode (Java) или без хешера (C++). Тогда два одинаковых по смыслу объекта таблица считает разными.
• Надежда на порядок. Хеш-таблица не гарантирует порядок обхода, а в Go он случайный специально. Если порядок нужен, отсортируй ключи отдельно.
• freq[w] при чтении в C++. Такая запись тихо создаёт ключ со значением 0. Для проверки используй count или find.
• Забыть про память. O(1) по времени достаётся ценой O(n) памяти, и об этом стоит сказать вслух.

Теперь ты знаешь, как устроена хеш-таблица, и умеешь применять три её главных приёма. Дальше будут задачи, где их нужно узнать в условии.