Как работают хеш-таблицы: хеширование, коллизии, поиск
Основы3 минРедакция Innovialabs
Коротко
Хеш-таблица превращает ключ в номер ячейки массива с помощью хеш-функции, поэтому поиск, вставка и удаление в среднем занимают константное время, а коллизии решаются цепочками или открытой адресацией.
Суть в одном абзаце
Хеш-таблица — это массив ячеек (бакетов) плюс хеш-функция, которая превращает ключ в число. Из числа получают индекс ячейки, например остатком от деления на размер массива. Чтобы найти значение, не нужно перебирать все элементы: вычислили хеш — сразу пошли в нужную ячейку. Поэтому в среднем операции занимают O(1).
Хеш-функция
Хорошая хеш-функция для таблицы должна:
- быть детерминированной — один и тот же ключ всегда даёт один и тот же хеш;
- равномерно распределять ключи по ячейкам;
- быстро считаться.
Отсюда важное правило: если два ключа равны, их хеши обязаны совпадать. Поэтому в Java при переопределении equals нужно переопределять и hashCode, а в Python изменяемые объекты вроде list нельзя использовать как ключ словаря — их содержимое может поменяться, и хеш станет неверным.
Хеш-функции для таблиц не обязаны быть криптографическими. Для паролей и подписей используются другие алгоритмы.
Коллизии
Ячеек меньше, чем возможных ключей, поэтому два разных ключа иногда попадают в одну ячейку. Это коллизия, и есть два основных способа с ней справиться.
| Подход | Как работает | Плюсы | Минусы |
|---|---|---|---|
| Цепочки (chaining) | В ячейке хранится список всех элементов с этим индексом | Простота, спокойно переносит высокое заполнение | Дополнительная память на узлы, хуже для кеша |
| Открытая адресация | При занятой ячейке ищется следующая свободная по правилу пробирования | Данные лежат компактно, быстрее за счёт кеша | Удаление сложнее, сильно страдает при высоком заполнении |
При открытой адресации удалённый элемент нельзя просто стереть — иначе поиск остановится на пустом месте и не найдёт ключи, лежащие дальше. Поэтому ставят специальную метку «удалено».
Коэффициент заполнения и расширение
Load factor — отношение числа элементов к числу ячеек. Чем он выше, тем больше коллизий и тем медленнее операции. Когда коэффициент превышает порог, таблица расширяется: создаётся массив большего размера, и все элементы перераспределяются заново.
Отдельное расширение стоит O(n), но происходит редко, поэтому в пересчёте на одну операцию вставка остаётся O(1) — это называют амортизированной сложностью. Если заранее известно число элементов, многие языки позволяют задать начальную ёмкость и избежать лишних перестроек.
Как это устроено в популярных языках
Python dict и set. Используют открытую адресацию. Начиная с Python 3.7 словарь гарантированно сохраняет порядок вставки ключей. Ключи должны быть хешируемыми: строки, числа, кортежи из неизменяемых значений.
JavaScript Map и Set. Спецификация требует сохранять порядок вставки, а движки реализуют их на хеш-таблицах. В отличие от обычного объекта, Map принимает ключи любого типа и сравнивает объекты по ссылке, а не по содержимому.
const m = new Map();
const key = { id: 1 };
m.set(key, "a");
m.get({ id: 1 }); // undefined: другой объект
m.get(key); // "a"
Java HashMap. Использует цепочки. Коэффициент заполнения по умолчанию — 0,75. Если цепочка в одной ячейке становится слишком длинной, она превращается в сбалансированное дерево, чтобы худший случай оставался приемлемым. Порядок элементов не гарантирован — для него есть LinkedHashMap, а для сортировки по ключу — TreeMap.
Когда O(1) превращается в O(n)
- Плохая хеш-функция, которая отправляет много ключей в одну ячейку.
- Специально подобранные ключи от злоумышленника (атака на коллизии). Поэтому некоторые языки добавляют случайность в хеширование строк.
- Изменение ключа после вставки: элемент остаётся в старой ячейке и «теряется».
Частые ошибки
- Использовать изменяемый объект как ключ.
- Рассчитывать на определённый порядок там, где язык его не гарантирует.
- Переопределить равенство объектов, но забыть про хеш.
- Хранить в хеш-таблице данные, по которым нужны диапазонные запросы, — для этого лучше подходит дерево.