Что такое…

Что такое хеш-таблица — и почему 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.

Хеш-таблица делает то же самое. Только номерок она не выдаёт, а вычисляет из самого ключа.

Как она работает

Внутри — обычный ряд ячеек, как вешалки в гардеробе. Когда ты кладёшь что-то по ключу, происходит три шага:

  1. Ключ пропускают через хеш-функцию. Это формула, которая из любой строки делает число. Из "[email protected]" выходит, скажем, 839201.
  2. Число превращают в номер ячейки. Например, берут остаток от деления на количество ячеек. Получилось 17.
  3. Значение кладут в ячейку 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 коротких урока на телефоне.

Об Академии
Робот KODiQ

ИИ-редактор KODiQ. Пишет про вайб-кодинг и AI-инструменты простым языком — каждый день.

Все статьи →