Хеш-таблицы на практике: коллизии, коэффициент заполнения и хеширование с seed

Что это такое

Хеш-таблица сопоставляет ключ с индексом корзины, вычисляя hash(key) mod capacity. Два ключа, попавшие в одну корзину, образуют коллизию; таблица разрешает её методом цепочек (небольшой список на корзину) или открытой адресацией (проверкой других ячеек). Коэффициент заполнения — число элементов, делённое на вместимость. Документация Java HashMap описывает его как меру допустимой заполненности перед увеличением вместимости; значение по умолчанию — 0.75. Когда число элементов превышает произведение этого коэффициента и вместимости, таблица перехешируется с обращением ко всем элементам. Модель данных Python указывает, что хеши str и bytes «подсаливаются» непредсказуемым значением, отдельным для каждого процесса (рандомизация хеширования включена по умолчанию с 3.3), а спецификация Go не задаёт порядок обхода map.

Почему это важно

Средняя стоимость поиска O(1) зависит от равномерного распределения ключей. Атакующий, который может выбирать ключи (имена параметров запроса, полей JSON или формы) и знает хеш-функцию, способен вызвать коллизии тысяч ключей, превратив каждую вставку в линейный просмотр, а один запрос — в квадратичную работу. Это hash flooding; стандартная защита — отдельное начальное значение хеширования для каждого процесса. Перехеширование стоит O(n) и происходит при достижении порогов, поэтому цикл вставки n элементов оплачивает несколько таких раундов: амортизированная стоимость остаётся O(1), но отдельные вставки дают скачки.

Как применять

• Не сохраняйте, не передавайте и не сравнивайте между процессами хеш-значения уровня языка: они меняются с начальным значением, версией и сборкой. Если вывод должен быть стабильным, сортируйте его, а не полагайтесь на порядок map.
• Заранее задавайте вместимость, если число элементов известно (HashMap(initialCapacity), make(map[K]V, n)), чтобы избежать перехеширования в горячих циклах.
• Пока ключи находятся в таблице, они не должны меняться: изменение ключа после вставки не позволяет найти запись. Равные объекты должны иметь равные хеши; определяйте равенство и хеширование вместе.
• При собственной реализации таблицы (встраиваемый код, пользовательский аллокатор) используйте хеш с хорошим лавинным эффектом, задавайте начальное значение на процесс, ограничивайте коэффициент заполнения и проверяйте самую длинную цепочку проб на специально подобранных ключах.
• Для воспроизводимых тестов явно фиксируйте начальное значение (PYTHONHASHSEED), не полагаясь на случай, и дополнительно запускайте набор со случайным начальным значением.

Подводные камни

Тест, проходящий с одним начальным значением и падающий с другим, выявляет зависимость кода от порядка, а не нестабильность самого теста. Для ключей с плавающей точкой 0.0 и -0.0 равны и должны иметь одинаковый хеш; NaN не равен самому себе. Таблица, используемая как кеш без ограничения размера, становится утечкой памяти. Криптографические хеши вроде SHA-256 для таблиц не нужны и медленны; обычно используют быстрые хеш-функции с ключом, рассчитанные на таблицы.