Хеш-таблицы

Хеш-таблица — структура, превращающая произвольный ключ в индекс массива через хеш-функцию: index = h(key) mod capacity. Среднее время операций get/set/delete — O(1). Это фундаментальный инструмент: hash-таблицы лежат в основе индексов БД (Redis HASH, MongoDB), реализаций Map/Set в любом языке и решают примерно треть всех алгоритмических задач, заменяя «искать в массиве» (O(n)) на «искать в map» (O(1)).

Когда применять / Мотивация

Hash используется везде, где нужен быстрый lookup по ключу:

кэш и memoization;
группировка / counting (anagrams, frequency analysis);
проверка существования (Set для seen-set);
индексирование в БД (Redis, hash join в SQL движках);
дедупликация потоков данных;
символьные таблицы в компиляторах.

Паттерн «смотри, что уже видел» — мощнейший трюк, применимый к сотне задач: Two Sum, Longest Substring Without Repeating Characters, Subarray Sum Equals K, Group Anagrams.

Идея / Как работает

Хеш-функция должна равномерно распределять ключи. Хорошая функция минимизирует коллизии (разные ключи → один индекс). Качественные хеши: SipHash (Python, Rust), Murmur, FNV, xxHash.

Разрешение коллизий — два подхода:

Chaining — каждый слот хранит список (или дерево) элементов. Java 8+ HashMap использует связный список, но при 8+ элементах в bucket переходит на Red-Black tree → O(log n) даже при атакующем хеше.
Open addressing — при коллизии ищем альтернативный слот по схеме (linear probing, quadratic probing, double hashing). Python dict использует randomized probing.

Load factor — отношение size / capacity, типично порог 0.75. При превышении делается resize: выделяется массив удвоенного размера, все элементы пересчитываются (rehash). Эта операция O(n), но выполняется редко → amortized O(1) на вставку (геометрическая прогрессия удвоений).

Worst case O(n) возникает при плохом хеше или hash flooding attack — злоумышленник подбирает ключи с одинаковым хешем, все элементы попадают в один bucket. Защита: рандомизация seed (SipHash в современных языках), tree-bins при длинных цепочках, rate limiting.

Реализация

Two Sum через Hash Map

Задача: nums = [2, 7, 11, 15], target = 9 → [0, 1].

Идея: один проход. Для каждого nums[i] ищем need = target - nums[i] в map. Если есть — нашли пару. Иначе сохраняем текущий элемент. Map хранит “историю просмотренных”.

function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>(); // value → index

  for (let i = 0; i < nums.length; i++) {
    const current = nums[i];
    const need = target - current;

    if (seen.has(need)) {
      return [seen.get(need)!, i];
    }
    seen.set(current, i);
  }
  return null;
}

Group Anagrams

function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const word of words) {
    // Отсортированные буквы — канонический ключ для всех анаграмм
    const key = word.split('').sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(word);
  }
  return Array.from(groups.values());
}

Subarray Sum Equals K (prefix sum + hash)

function subarraySum(nums: number[], k: number): number {
  // Map: prefixSum → сколько раз встречалась
  const prefixCount = new Map<number, number>();
  prefixCount.set(0, 1); // префикс длины 0 имеет сумму 0
  let sum = 0, count = 0;

  for (const x of nums) {
    sum += x;
    // Если sum - k встречался — есть подмассив с суммой k
    count += prefixCount.get(sum - k) ?? 0;
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }
  return count;
}

Трассировка Two Sum

nums = [2, 7, 11, 15], target = 9, seen = {}
──────────────────────────────────────────────
i=0: current=2, need=7
     seen.has(7) → false
     seen.set(2, 0)        seen = {2 → 0}
i=1: current=7, need=2
     seen.has(2) → true ✓
     return [seen.get(2), 1] = [0, 1]
──────────────────────────────────────────────
Результат: [0, 1]   (nums[0]+nums[1] = 2+7 = 9) ✓

Почему O(n), а не O(n²)? Hash-таблица заменяет внутренний цикл поиска константным lookup’ом.

Сложность

Операция	Average	Worst
get / set / delete	O(1)	O(n)
has	O(1)	O(n)
iterate	O(n)	O(n)
resize	O(1) amortized	O(n) (одна операция)

Worst case O(n) — все ключи в одном bucket. На практике с хорошей хеш-функцией и random seed — практически невозможно случайно.

Типичные ошибки и подводные камни

Ключ-объект в {}: Object конвертирует в строку через toString() — все объекты дают "[object Object]". Используйте Map, который поддерживает любые ключи.
Прототипное наследование в Object: ключи "toString", "constructor", "__proto__" конфликтуют с методами и могут вызвать prototype pollution. Map свободен от этого.
Дубликаты ключей: seen.set(3, 0); seen.set(3, 5); — второй вызов перезаписывает. Если нужен список индексов: Map<number, number[]>.
Один элемент дважды: в Two Sum проверяем seen.has(need) до seen.set(current, i) — это исключает использование одного индекса дважды.
Большие числа: JS number — 64-bit float, точность до 2⁵³−1. Для больших целых используйте BigInt или строки в качестве ключей.
NaN ключи: NaN !== NaN, но Map хранит NaN как отдельный ключ корректно (использует SameValueZero).
Hash flooding: на бэкенде злоумышленник может намеренно слать ключи с одинаковым хешем. Защита — random seed в хеш-функции.
Memory leak: hash map с большими value (например, кэш без eviction) растёт неограниченно. Используйте WeakMap (если ключи-объекты) или LRU-cache.

Follow-up вопросы интервьюера

Three Sum. Сортируем O(n log n), для каждого nums[i] запускаем two pointers на остаток. Итого O(n²).
Four Sum. Фиксируем два элемента (O(n²)), на остальных — two pointers. O(n³).
Group Anagrams. Hash map: sortedWord → list of words. O(n · k log k), k — длина слова. Альтернатива — счётчик букв [count_a, count_b, ...] как ключ за O(n · k).
Subarray Sum Equals K. Prefix sum + hash. O(n). Ключевая идея: sum[j] - sum[i] = k ⇔ sum[i] = sum[j] - k.
Longest Consecutive Sequence в O(n). Все числа в Set. Для каждого x, у которого нет x-1 (значит, начало последовательности), идём вперёд x+1, x+2, ... и считаем длину. Каждое число посетим максимум 2 раза → O(n).
Longest Substring Without Repeating Characters. Sliding window + hash: запоминаем последнюю позицию каждого символа, при повторе сдвигаем left.
LRU Cache. Hash map + doubly-linked list. Map даёт O(1) доступ к узлу, list — O(1) перемещение в начало (used recently).
Защита от hash flooding. Рандомизация seed, переход на tree-bins при длинной цепочке (Java HashMap), rate limiting на endpoint.
Почему Map сохраняет порядок вставки? ES2015 спецификация требует insertion order — внутри обычно реализуется через doubly-linked list поверх hash table.

Чеклист на собес

Использую Map/Set, не {}/массив.
Назвал average O(1) и worst O(n).
Проверяю наличие до записи (Two Sum логика).
Знаю паттерны: seen-set, frequency map, prefix sum + hash.
Помню про коллизии и hash flooding.
Понимаю load factor и amortized resize.
Знаю trade-off Map vs Object в JS.
Использую WeakMap для кэша с объектными ключами без leak’ов.