Алгоритмы с нуля
Хеширование: чтение кода
Суть Читаем реальные сниппеты hash table и hash map, предсказываем поведение и выбираем фикс: chaining-поиск, resize удвоением, баги дополнения и частотной map.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеБаги хеширования прячутся в коде, который выглядит корректным. Прочитайте каждый сниппет, предскажите, что он на самом деле делает под нагрузкой или на крайних случаях, и выберите фикс, который аккуратный инженер сделает первым.
Цель
Отработайте цикл, который вы прогоняете на каждой задаче с hash map: прочитать код, протрассировать на неудобном входе и взять точный фикс — а не отмахнуться расплывчатым «используй hash map».
Сниппет 1 — вставка и поиск с chaining
class HashTable {
constructor(size = 8) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let h = 0;
for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.buckets.length;
return h;
}
set(key, value) {
const b = this.buckets[this.hash(key)];
b.push([key, value]); // всегда push
}
get(key) {
const b = this.buckets[this.hash(key)];
for (const [k, v] of b) if (k === key) return v;
return undefined;
}
} Викторина
Completed
Вы вызываете set('a', 1), затем set('a', 2), затем get('a'). Что вернётся и в чём баг?
Heads-up get возвращает ПЕРВЫЙ совпавший ключ, который сканирует, а это устаревшая пара ['a',1]. Более новая пара стоит за ней в цепочке и не достигается.
Heads-up Ничего не гасится — обе пары хранятся в цепочке. get находит первую и возвращает 1; баг с дублирующимся ключом тихий.
Heads-up Эта реализация вообще не проверяет дубликаты ключей, поэтому исключения быть не может. Она молча хранит обе и возвращает устаревшее значение — что и есть баг.
Сниппет 2 — resize по load factor
set(key, value) {
if ((this.count + 1) / this.buckets.length > 0.75) this.resize();
const b = this.buckets[this.hash(key)];
b.push([key, value]);
this.count++;
}
resize() {
const old = this.buckets;
this.buckets = Array.from({ length: old.length * 2 }, () => []);
for (const bucket of old)
for (const [k, v] of bucket) {
const i = this.hash(k); // перехешируем по НОВОЙ длине
this.buckets[i].push([k, v]);
}
} Викторина
Completed
Почему resize обязан перехешировать каждый ключ по новой длине массива, а не копировать бакеты напрямую?
Heads-up Это корректность, а не оптимизация. После смены длины hash(key) даёт другие индексы; ключ, скопированный в старый слот, был бы недостижим для get, который использует новую длину.
Heads-up Hash function не меняется — меняется только модуль (длина массива). Одна эта смена модуля перемещает ключи, поэтому каждый ключ надо переразместить.
Heads-up Resize понижает load factor и укорачивает цепочки, но collision всё равно случаются. Перехеширование — про то, чтобы класть ключи в бакет по новому модулю, а не про устранение collision.
Сниппет 3 — 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 null;
} Викторина
Completed
Почему проверка need идёт ДО seen.set(nums[i], i), и что сломается, если поменять две строки местами?
Heads-up Итоговое содержимое map одинаково, но пошаговый поиск — нет. Set до проверки даёт элементу найти САМОГО СЕБЯ как своё дополнение, выдавая невалидный ответ [i, i] для случаев вроде 3 + 3 = 6 при единственной тройке.
Heads-up Дело не в скорости, а в корректности: set сначала допускает self-pairing. Has-вызов всё равно нужен; перестановка меняет ответ, а не объём работы.
Heads-up Эта дополнительная защита залатала бы баг, но чистый идиоматичный фикс — просто записывать после проверки. Сниппет уже корректен; перестановка вносит баг, который защите потом пришлось бы отменять.
Сниппет 4 — группировка анаграмм по частотному ключу
function groupAnagrams(words) {
const groups = new Map();
for (const w of words) {
const key = w.split('').sort().join(''); // канонический ключ
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(w);
}
return [...groups.values()];
} Викторина
Completed
Это корректно группирует анаграммы. Для длинных строк сколько стоит ключ, и какой более дешёвый канонический ключ даёт тот же результат группировки?
Heads-up Сортировка — O(L log L), а не O(L). Линейная сигнатура по счётчику символов асимптотически дешевле и группирует анаграммы идентично, потому что у анаграмм равные частоты букв.
Heads-up Сырое слово группирует одинаковые строки, а не анаграммы — 'eat' и 'tea' попали бы в разные группы. Ключ должен быть инвариантен по анаграммам, что даёт отсортированная форма (или сигнатура-счётчик).
Heads-up Опираться на collision хеша для группировки анаграмм неверно и небезопасно — не-анаграммы тоже коллидировали бы. Нужен детерминированный канонический ключ (сортировка или счётчик), а не поведение collision.
Итог
Каждая задача с hash map читается в коде: set с chaining должен обновлять существующий ключ на месте, а не слепо делать push; resize должен перехешировать по новому модулю, иначе поиски уходят не в тот бакет; паттерн дополнения записывает после проверки, чтобы элемент не паровался сам с собой; а группировке нужен канонический ключ, инвариантный по группе — счётчик символов бьёт сортировку на горячем пути. Сначала прочитайте неудобный вход, потом выберите точный фикс.