Как работает хеш-таблица

Короткий ответ. Хеш-таблица прогоняет ключ через хеш-функцию, берёт остаток от деления на размер массива и кладёт значение в эту ячейку. Чтение повторяет те же шаги, поэтому в среднем занимает константное время. Коллизии решают цепочками или открытой адресацией, а после заполнения примерно на 0,75 таблица удваивает массив.

Главный ход

Есть массив, скажем на 16 ячеек.

Прогоняем ключ через хеш-функцию. Получаем число. Берём остаток от деления на 16.

Получилась ячейка. Кладём значение в неё.

Чтение повторяет те же шаги и попадает туда же.

Поиска не было. Отсюда и константное время.

У хеш-функции одна работа. Равномерно раскидывать ключи по ячейкам.

Хеш-функция всегда даёт один ответ для одного ключа.

Коллизии

Два ключа обязательно попадут в одну ячейку.

При 16 ячейках и 20 ключах это гарантировано. Вероятно гораздо раньше.

Стандартных ответов два.

Цепочки. В ячейке лежит маленький список. Столкнулись, дописали в конец.

Чтение находит ячейку и проходит список. Обычно там один или два элемента.

Открытая адресация. Ячейка занята? Пробуем следующую. И так до свободной.

Списков нет. С кешем дружелюбнее. Удаление капризнее.

Оба быстрые, пока списки короткие.

Заполнение и расширение

За короткие списки отвечает коэффициент заполнения. Это записи, делённые на ячейки.

После примерно 0,75 коллизии становятся частыми, чтение замедляется.

Таблица берёт массив побольше, обычно вдвое. И перехеширует туда все ключи.

Расширение стоит O(n). Платит за него одна невезучая вставка.

В среднем по всем вставкам цена всё равно константная. Это честный смысл амортизированной оценки.

Что значит константное время, разобрано в Big O без математики.

Отсюда же сюрприз в проде. Вставка, которая обычно занимает микросекунду, иногда занимает сильно больше.

Если ты в этот момент держишь блокировку, это важно.

Почему худший случай O(n)

Все ключи в одной ячейке, и таблица вырождается в длинный список. Каждое чтение его сканирует.

На случайных данных так не бывает. На подобранных бывает.

Подобранные коллизии использовали как атаку. Отправить серверу тысячи намеренно сталкивающихся ключей и смотреть, как горит процессор.

Поэтому современные среды солят хеш-функцию случайным числом на каждый процесс.

На собеседовании отвечай «O(1) в среднем, O(n) в худшем». Проверяют как раз знание, что это среднее.

Два правила, которые теперь понятны

Не меняй ключ после вставки. Ячейку выбрали по старому содержимому.

Изменил, и запись лежит не там. Она недостижима, а не потеряна. Это хуже.

Равные ключи обязаны хешироваться одинаково. Переопределил равенство и не тронул хеш? Словарь начнёт терять записи.

Баг всплывает через месяцы.

Когда нужно другое

У хеш-таблицы нет порядка. Это сделка, а не упущение.

Поэтому «все ключи от 10 до 50» это полный проход. И «самый маленький ключ». И «всё по порядку».

Таким запросам нужно сбалансированное дерево. Log n на операцию, порядок по построению.

Базы данных держат обе. Хеш-индексы для точных совпадений, B-деревья для диапазонов.

Где это в треке

AlgoPath тратит шаги с 14 по 17 на то, чтобы ты её построил.

Ты сам напишешь код для коллизий и расширения, а не прочитаешь абзац.

Когда за ней вообще тянуться, разобрано в статье множество, словарь или массив.

Паттерн, который на ней стоит, это хеш-множество и словарь.

Первые 33 шага бесплатные.