Паттерн: Хеш-таблица

Признак в условии

• «найти пару / дополнение до суммы»
• «есть ли повтор», «первый уникальный»
• «сгруппировать по признаку», «посчитать частоты»
• вложенный цикл, в котором внутренний ищет то, что уже видели

Идея

Меняем время на память: вместо поиска по массиву за O(n) кладём увиденное в Map или Set и проверяем за O(1). Почти всегда превращает O(n²) в O(n).

Шаблон

const seen = new Map();
for (let i = 0; i < nums.length; i++) {
  const need = target - nums[i];
  if (seen.has(need)) return [seen.get(need), i];
  seen.set(nums[i], i);
}

Сложность

Время O(n), память O(n).

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

• объект вместо Map там, где ключи не строки: 1 и '1' схлопнутся
• запись в словарь до проверки - элемент найдёт сам себя
• проверка if (map.get(k)) вместо map.has(k) ломается на значении 0

Мнемоника

«Сначала спроси, потом запиши»

Не путать с

• Два указателя - если вход отсортирован, пара ищется указателями за O(1) памяти - хеш-таблица тут избыточна
• Префиксные суммы - когда ищется не элемент, а участок с заданной суммой, одной таблицы мало - нужны префиксы
• Битовые операции - для набора из малого числа флагов битовая маска дешевле Set и быстрее

Задачи на этот паттерн

• Two Sum
• первый неповторяющийся символ
• группировка анаграмм
• есть ли дубликаты
• изоморфные строки
• слова по шаблону
• самая длинная цепочка подряд
• K самых частых слов
• все начала анаграмм

Суть

Хеш-таблица отвечает на вопрос «встречалось ли значение и что с ним связано» за O(1) в среднем. В JS это Map и Set. Большая часть задач «на массивы» решается заменой вложенного цикла на один проход с хеш-таблицей: платим памятью O(n), выигрываем время O(n²) → O(n).

Как распознать по условию

• «найти пару или элемент с условием» (сумма, разность, дубликат);
• «посчитать, сколько раз встречается»;
• «сгруппировать по признаку» (анаграммы, по первой букве);
• «первый неповторяющийся», «есть ли дубликат»;
• массив не отсортирован, а сортировать нельзя или дорого.

Шаблоны на JS

Частоты:

const freq = new Map();
for (const x of arr) freq.set(x, (freq.get(x) ?? 0) + 1);

Дополнение (Two Sum):

function twoSum(nums, target) {
  const seen = new Map(); // значение -> индекс
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);   // после проверки!
  }
  return [];
}

Группировка:

const groups = new Map();
for (const w of words) {
  const key = [...w].sort().join('');
  if (!groups.has(key)) groups.set(key, []);
  groups.get(key).push(w);
}

В ES2024 есть Map.groupBy(items, fn) и Object.groupBy, они делают то же одной строкой.

Map, Set или объект

• Map: ключи любого типа, порядок вставки, size. Выбор по умолчанию.
• Set: только наличие.
• Объект: ключи приводятся к строке (1 и "1" совпадут), есть прототип. Годится для коротких строковых словарей.
• Для 26 латинских букв быстрее массив new Array(26).fill(0) и индекс ch.charCodeAt(0) - 97.

Сложность

Вставка, поиск, удаление: O(1) в среднем, O(n) в худшем при коллизиях. Память O(n). Объекты-ключи сравниваются по ссылке: два одинаковых массива это разные ключи, поэтому составной ключ делают строкой (${r},${c}).

Ловушки

• includes в цикле вместо Set: тихий O(n²).
• Вставка до проверки в Two Sum: элемент сложится сам с собой.
• if (map.get(x)) ложно для значения 0: используй has.
• Массив как ключ Map: сравнение по ссылке.

Что спросят на собесе

• Как найти пару с заданной суммой за O(n)?
• Почему хеш-таблица O(1) в среднем, а не всегда?
• Чем Map отличается от объекта?
• Как сгруппировать анаграммы и какая будет сложность?
• Сколько памяти тратит решение и можно ли без неё?