Хеш-таблица
Хеш мгновенно говорит, в какой корзине ключ: вставка и поиск O(1) в среднем.
1function hash(key: string, buckets: number): number {2 let h = 03 for (const ch of key) h += ch.charCodeAt(0)4 return h % buckets5}6 7function set(table: Map<number, string[]>, key: string, buckets: number): void {8 const i = hash(key, buckets)9 const chain = table.get(i) ?? []10 chain.push(key)11 table.set(i, chain)12}13 14function get(table: Map<number, string[]>, key: string, buckets: number): string | undefined {15 const chain = table.get(hash(key, buckets))16 return chain?.find((k) => k === key)17}Проблема
Искать по ключу мгновенно среди миллионов: бинарный поиск требует сортировки, список — перебора. Хеш вычисляет «адрес» ключа прямо из его содержимого.
Что вы видите
Ключи сверху, корзины снизу. Хеш = сумма кодов символов по модулю числа корзин. Два ключа в одну корзину — коллизия: внутри корзины растёт цепочка.
Как это работает
Хеш-функция равномерно рассыпает ключи по корзинам; коллизии неизбежны (ящики и голуби) — цепочки или открытая адресация сглаживают их. В среднем O(1); худший случай — все в одной корзине, O(n). Лечится качественным хешем и рехешем при заполнении.
Пошаговый разбор
- 01
Хеш
h(key) = коды символов mod корзины.
- 02
Корзина
Вставка в свою цепочку.
- 03
Коллизия
Разные ключи — одна корзина: цепочка.
- 04
Поиск
Хеш → корзина → короткая цепочка.
Complexity и ограничения
O(1) в среднем. Хеш должен быть стабильным и равномерным; рост таблицы — рехеш.
Edge cases
- Все в одну корзину
Деградация до O(n) — плохой хеш или атака.
- Рехеш
При заполнении таблица растёт, всё переезжает.
- Порядок
Хеш не хранит порядок ключей.
Где встречается в реальности
Объекты и Map
Словари языков — хеш-таблицы под капотом.
Кэши
key → значение с мгновенным доступом.
Дедупликация
Set: «видели ли мы такой ключ».
Связанные алгоритмы
«Почему поиск по ключу — O(1): секрет хеша»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.