Что такое хеш-таблица — и почему Set нашёл за 3 мс то, что массив искал 2 секунды

У тебя список из 100 000 email-адресов. Надо для каждого из 100 000 новых заявок проверить: этот адрес уже есть?
ИИ написал так:
for (const email of applications) {
if (emails.includes(email)) { /* ... */ }
}
Мы замерили в Node 22: около 2 секунд. Потом поменяли одну строку — сложили адреса в Set и спросили set.has(email). Те же 100 000 проверок заняли 3 миллисекунды. Разница — в сотни раз.
Смотри, в чём фокус. includes перебирает массив с начала до конца. А Set внутри устроен как хеш-таблица — и он вообще не перебирает. Разберём, как это возможно.
Что такое хеш-таблица
Хеш-таблица — это способ хранить пары «ключ → значение» так, чтобы по ключу сразу прыгнуть к значению, а не искать его.
Представь гардероб. Ты сдаёшь куртку и получаешь номерок 47. Когда возвращаешься, гардеробщик не обходит все вешалки, разглядывая куртки. Он идёт сразу к крючку 47.
Хеш-таблица делает то же самое. Только номерок она не выдаёт, а вычисляет из самого ключа.
Как она работает
Внутри — обычный ряд ячеек, как вешалки в гардеробе. Когда ты кладёшь что-то по ключу, происходит три шага:
- Ключ пропускают через хеш-функцию. Это формула, которая из любой строки делает число. Из
"[email protected]"выходит, скажем,839201. - Число превращают в номер ячейки. Например, берут остаток от деления на количество ячеек. Получилось 17.
- Значение кладут в ячейку 17.
Когда ты потом спрашиваешь has("[email protected]"), всё повторяется: та же формула → то же число → та же ячейка 17. Заглянули — есть. Неважно, сто там адресов или миллион: шагов столько же.
Формула всегда даёт одинаковый ответ на одинаковый ключ. Поэтому её результат и работает как номерок.
А если двум ключам выпала одна ячейка
Бывает. Ячеек конечное число, ключей — сколько угодно. Это называется коллизия.
Решается просто: в ячейке хранят маленький список. Пришли в ячейку 17, а там два адреса — сравнили оба и нашли нужный. Пока таблица не переполнена, в каждой ячейке одна-две записи, и поиск остаётся мгновенным.
Когда записей становится слишком много, таблица сама расширяется: заводит больше ячеек и раскладывает всё заново. Ты этого не замечаешь — это делает язык.
Где ты её уже используешь
Ты пишешь хеш-таблицы каждый день, просто под другими именами:
MapиSetв JavaScript. Спецификация языка прямо требует, чтобы поиск в них был быстрее перебора, и движки делают их хеш-таблицами.dictиsetв Python. Классические хеш-таблицы.- Обычный объект в JavaScript. Тоже хранит пары ключ-значение и ищет по ключу быстро.
- Индексы в базе данных. Один из видов индекса — хеш-индекс: «найди пользователя с таким email» без обхода всей таблицы.
- Кэши. Ответ уже посчитан? Найди его по ключу и не считай заново.
Ловушка: у объекта ключ всегда становится строкой
Хеш-функции нужен ключ, из которого можно получить число. Обычный объект JavaScript решает это грубо: превращает любой ключ в строку.
const seats = {}
seats[1] = 'Анна'
seats['1'] = 'Борис'
console.log(seats[1]) // 'Борис'
Число 1 и строка '1' стали одним ключом. А с объектами в роли ключа ещё хуже:
const visits = {}
const userA = { id: 1 }
const userB = { id: 2 }
visits[userA] = 5
visits[userB] = 9
console.log(Object.keys(visits)) // ['[object Object]']
Мы проверили: оба пользователя схлопнулись в один ключ '[object Object]'. Счётчик посещений первого молча затёрт.
Map так не делает. Он хранит ключ как есть — число отдельно от строки, каждый объект отдельно:
const visits = new Map()
visits.set(userA, 5)
visits.set(userB, 9)
visits.size // 2
Что забрать в свой код
Правило на каждый день: если ты много раз спрашиваешь «есть ли X в списке» — сложи список в Set.
const known = new Set(emails) // один раз
known.has(email) // мгновенно, сколько угодно раз
Если ИИ написал includes или find внутри цикла по большому списку — это первый кандидат на ускорение. Попроси: «Замени поиск в массиве внутри цикла на Set или Map».
Почему тогда не хранить всё в хеш-таблицах?
У них нет порядка «по смыслу» и номеров позиций. Нужно «третий по счёту» или сортировка — бери массив. Нужно «есть ли» и «найди по ключу» — хеш-таблицу.
Хеш-таблица и хеширование паролей — одно и то же?
Идея похожа: формула превращает данные в число. Но для паролей нужны медленные, криптостойкие функции, а для таблиц — максимально быстрые. Это разные инструменты под разные задачи.
Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.





