Хэш-таблица делит ключи по бакетам и даёт средний O(1) на поиск. Коллизии неизбежны: плохой хэш, высокий load factor и ресайз превращают константу в линейный обход и в паузы под нагрузкой.
Алгоритмы и структуры данных cs собеседование
Идея простая. Из ключа считают число — хэш. По хэшу выбирают корзину (bucket). В корзине ищут точное равенство ключа.
Если хэш хорошо перемешивает, в корзине мало элементов. Операция выглядит как O(1). Если плохо — все ключи в одной корзине, и вы идёте по списку.
Пример. Шкафчики в раздевалке. Номер шкафчика считают из фамилии. Два человека получили один номер — это коллизия. Их вещи кладут цепочкой: сначала ваши, потом его. Поиск идёт по цепочке, пока не найдут нужную фамилию.
Коллизия — это норма, не авария. Корзин конечное число. Разные ключи обязаны иногда попадать в один индекс. Это pigeonhole principle: голубей больше, чем клеток.
Две стратегии. Цепочки (chaining): в корзине список или дерево. Открытая адресация: ищем свободную ячейку рядом (linear probing, quadratic, Robin Hood). У обеих есть цена: locality в кэше, удаление, кластеризация.
Как устроена таблица
Load factor — доля занятых слотов. Высокий load factor экономит память и увеличивает коллизии. Среднее время растёт. В пределе корзина ближе к O(n). Поэтому таблица периодически расширяется.
Ресайз — копирование бакетов в новую таблицу. На огромной map в горячем процессе это видимый пик задержки. Средний lookup по-прежнему «константный». P99 в этот момент — нет.
В Go map — хэш-таблица с бакетами. Нулевая map равна nil: чтение даёт zero value, запись паникует. Итерация специально недетерминирована: порядок ключей не обещан.
Это не B-tree. Порядка ключей нет. Запрос «все ключи от A до Z» требует полного перебора, а не прогулки по листьям.
// bucket 3: "aa" -> "bb" -> "cc" // цепочка при коллизии
// lookup("cc"): hash -> bucket 3 -> сравнение трёх ключей
//
// range query "все ключи от a до z":
// в B-tree — спуск к листу + последовательный scan
// в map — for k := range m { if k >= "a" && k <= "z" }
func inRange(m map[string]int, lo, hi string) []string {
var out []string
for k := range m { // полный перебор ключей, не O(log n)
if k >= lo && k <= hi {
out = append(out, k)
}
}
return out
}Коллизии в одной корзине превращают средний O(1) в обход списка. Диапазон по ключам хэш не умеет.
Атаки и ресайз
Hash-flooding: злоумышленник подбирает ключи в одну корзину. Ваш «O(1)» становится горячей точкой CPU на каждом запросе.
В Go у map случайный seed на старте процесса. Предсказать коллизии извне сложнее. Это не магия безопасности всего приложения. Seed общий на процесс. Защита от внешних предсказуемых коллизий, не от логики вашего кода.
Пример. Кэш в памяти воркера — огромная map на миллионы ключей. Редкий рост бакетов совпал с пиком QPS. P99 внезапно прыгнул. Иногда проще шардировать map или не хранить миллионы ключей в одном процессе.
Хэш против дерева
Дерево (и B-tree на диске) даёт O(log n) стабильнее по худшему случаю. Умеет диапазоны и ближайшего соседа. Хэш быстрее в среднем на точечный lookup по точному ключу. Порядок не держит. Выбор — про паттерн доступа, не про «хэш всегда лучше».
Типичная ошибка
Обещать O(1) худший случай у хэш-таблицы. При высоком load factor и плохом хэше корзина деградирует к O(n). И вторая ловушка: ждать от map диапазонный запрос как от индекса Postgres — ключи придётся перебрать все.
На собеседовании
Хэш — точечный ключ и средний O(1). Дерево — порядок, диапазон, предсказуемый худший случай. Упомяните load factor, ресайз и случайный seed против hash-flooding в Go.