Деревья ищут за O(log N) — быстро. Но есть структура, которая ищет ещё быстрее: хеш-таблица даёт доступ по ключу в среднем за O(1) — постоянное время, не зависящее от объёма данных. Это самая быстрая структура для поиска по ключу, и потому одна из самых используемых. Плата — потеря порядка и особое поведение при переполнении.
Идея: превратить ключ в индекс
У массива есть суперсила — мгновенный доступ по индексу. Проблема лишь в том, что индекс — это число от 0 до размера массива, а ключи бывают любыми (большие числа, строки). Хеш-таблица наводит мост: она пропускает ключ через хеш-функцию, которая превращает его в индекс массива.
Простейший пример — взять ключ по модулю размера массива: индекс = ключ % размер. Тогда, чтобы положить или найти запись, мы вычисляем индекс за один шаг и сразу обращаемся к нужной ячейке. Никакого перебора и спуска по дереву — прямое попадание.
int hash(long key, int size) {
return (int)(key % size);
}
Коллизии — неизбежная проблема
Разных ключей много, а ячеек ограниченное число, поэтому рано или поздно два ключа дадут один и тот же индекс. Это коллизия. Хеш-таблица не может её избежать — она может только грамотно её разрулить. Есть два основных способа.
Открытая адресация
При коллизии ищем другую свободную ячейку в самом массиве. Варианты различаются тем, как именно искать:
- линейное пробирование — идём по соседним ячейкам (index+1, index+2…), пока не найдём свободную. Просто, но приводит к «слипанию» — длинным занятым участкам, которые замедляют поиск;
- квадратичное пробирование — шагаем всё дальше (index+1, index+4, index+9…), чтобы не слипаться так сильно;
- двойное хеширование — величину шага вычисляет вторая хеш-функция, поэтому разные ключи разбредаются по-разному. Лучший из вариантов открытой адресации.
Общая беда открытой адресации: чем плотнее заполнен массив, тем длиннее пробы. Отсюда важное понятие — коэффициент заполнения (load factor), отношение числа записей к размеру массива. Пока он невелик (скажем, до ~2/3), доступ остаётся близким к O(1); при приближении к единице таблица резко замедляется, и её нужно расширять (перехешировать в массив побольше).
Метод цепочек
Другой подход — в каждой ячейке массива хранить не одну запись, а связанный список всех записей с этим индексом. Коллизия просто добавляет элемент в список нужной ячейки. Здесь коэффициент заполнения может превышать единицу, и таблица не «застывает» при заполнении, а деградирует плавно. Метод цепочек проще в реализации и устойчивее к высокой загрузке, поэтому его часто предпочитают.
Хеш-функции
Качество хеш-таблицы во многом определяется хеш-функцией. Хорошая функция должна быть:
- быстрой — она вызывается на каждой операции;
- равномерной — разбрасывать ключи по всему диапазону индексов, не сваливая их в кучу (иначе коллизии зашкаливают).
Практические приёмы: размер массива берут простым числом — это уменьшает регулярные коллизии; строки хешируют, комбинируя коды символов с домножением (схема Горнера), чтобы разные строки давали разные хеши. Плохая хеш-функция превращает быструю таблицу в медленный список.
Чего хеш-таблица не умеет
За скорость приходится платить:
- нет порядка. Элементы разбросаны по массиву псевдослучайно, поэтому нельзя быстро обойти их по возрастанию или найти «следующий больший» — для этого берут деревья;
- бесполезна без ключа. Быстрый доступ есть только когда известен точный ключ; поиск по диапазону или частичному совпадению она не ускоряет;
- тратит память. Чтобы коллизий было мало, массив держат заметно просторнее, чем данных.
Коротко
- Хеш-таблица превращает ключ в индекс массива хеш-функцией и даёт доступ в среднем за O(1) — быстрее деревьев.
- Коллизии (разные ключи в одну ячейку) неизбежны; их разрешают открытой адресацией (искать другую ячейку: линейное/квадратичное пробирование, двойное хеширование) или методом цепочек (список в каждой ячейке).
- Коэффициент заполнения определяет скорость: заполненную таблицу нужно расширять. Хеш-функция должна быть быстрой и равномерной; размер массива — простое число.
- Плата за скорость — нет порядка, бесполезна без точного ключа и требует запаса памяти.
Дальше — пирамиды (кучи): структура, которая мгновенно отдаёт наибольший элемент и лежит в основе приоритетных очередей.