Хеш-таблицы на практике: Two Sum и другие хиты

Цели урока

• Освоить паттерн подсчёта частот
• Решить классическую задачу Two Sum
• Научиться группировать элементы по хеш-ключу
• Понять комбинацию prefix sum + hash

Предварительные знания

• Хеш-таблицы: основы

• Хеш-таблицы: O(1) доступ

На собеседовании в Google вас просят найти два числа с заданной суммой. Наивное решение за O(n²) - это провал. Но с хеш-таблицей вы решаете за O(n) и получаете оффер.

• Spotify - подсчёт прослушиваний для Wrapped
• Amazon - Покупатели также покупали (частоты корзин)
• Антиспам - частота слов в email для фильтрации
• Plagiarism detection - хеши n-грамм текста

Хеширование выходит за пределы таблиц

Поняв, что хеш-функция превращает любой объект в число, инженеры стали строить на этом куда более хитрые структуры. В 1970 году Бёртон Блум описал фильтр Блума: вероятностную структуру, которая отвечает на вопрос есть ли элемент в множестве, используя несколько хеш-функций и битовый массив. Она может ошибиться в сторону ложноположительного ответа, но почти не тратит память, поэтому до сих пор стоит в базах данных и сетевых кешах. В 1987 году Ричард Карп и Майкл Рабин предложили алгоритм поиска подстроки Rabin-Karp с катящимся хешем: хеш окна пересчитывается за O(1) при сдвиге на символ. В 1997 году команда Дэвида Каргера в MIT придумала consistent hashing, чтобы распределять данные по серверам так, чтобы при добавлении или удалении узла переезжала лишь малая доля ключей. Этот метод стал фундаментом Akamai, а позже лёг в основу распределённых хеш-таблиц в Dynamo, Cassandra и Chord.

Подсчёт частот

**Задача:** подсчитать сколько раз встречается каждый элемент. Классика!

**Применения:**

• Поиск дубликатов
• Найти самый частый элемент
• Проверить, являются ли строки анаграммами
• Аналитика: популярные товары, частые слова

Two Sum: Легенда LeetCode

**Задача #1 на LeetCode:** найти два числа в массиве, сумма которых равна target.

С хеш-таблицей решаем за **один проход**:

**Паттерн:** вместо поиска пары (a, b) где a + b = target, ищем в хеше complement = target - current.

Проверка анаграмм

**Анаграммы** - слова с одинаковым набором букв: "listen" и "silent".

**Альтернатива:** sorted(s1) == sorted(s2) работает, но O(n log n) vs O(n) у хеша.

Группировка анаграмм

**Задача:** сгруппировать слова-анаграммы. ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]

**Трюк:** любой объект, по которому можно определить "эквивалентность", можно использовать как ключ хеша для группировки.

Subarray Sum: Prefix Sum + Hash

**Задача:** найти количество подмассивов с суммой равной k.

**Это сложная техника!** Комбинация prefix sum + hash часто встречается на собеседованиях в FAANG.

Паттерны для запоминания

• Частоты: hash[element] = count
• Two Sum: ищем complement = target - current в хеше
• Группировка: ключ = каноническая форма (sorted, частоты)
• Subarray Sum: prefix_sum в хеше → находим суммы подмассивов за O(1)

Следующие темы

Хеш-таблицы освоены! Теперь переходим к деревьям - иерархическим структурам данных.

• Введение в деревья — Иерархическая организация данных

Связанные уроки

• ds-07-hash-collisions — Collision resolution affects all applications
• ds-20-lru-cache — LRU cache uses hash map + doubly-linked list
• ds-24-bloom-filter — Bloom filters extend hashing to probabilistic membership
• ds-11-bst — Ordered map use cases where hash map falls short
• alg-10-binary-search