Номер корзины хеш-таблицы по остатку от деления

Как работает индексация

Хеш-функция сопоставляет ключу большое целое число, а таблица состоит из m ячеек с номерами от 0 до m − 1. Операция i = h mod m сжимает любое значение в этот диапазон, поэтому каждому ключу соответствует допустимый индекс.

Разные ключи могут получить одинаковый индекс. Это называется коллизией, и таблица решает её цепочками или открытой адресацией. Но выбор индекса всегда начинается с остатка.

Разобранные примеры

Пусть хеш равен 1 234 567, а корзин 16. Делим: 1 234 567 = 16 · 77 160 + 7, поэтому остаток 7 и ключ попадает в седьмую корзину, если считать с нуля. В двоичной записи это четыре младших бита 0111.

Для хеша 100 и семи корзин имеем 100 = 7 · 14 + 2, индекс 2. Сравнив несколько ключей, видно, что остатки распределены по всем ячейкам, но равномерность зависит от самих хешей.

Какой размер таблицы выбирать

Степень двойки удобна, потому что остаток заменяется побитовым И с маской, но она использует только младшие биты хеша. Если хеш-функция плохо перемешивает младшие биты, ключи кучкуются в немногих корзинах.

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

Отрицательные хеши

В некоторых языках хеш бывает отрицательным, а остаток наследует знак делимого. Тогда индекс может оказаться отрицательным, и обращение к массиву приведёт к ошибке. Калькулятор показывает именно такое поведение: остаток от −7 при делении на 3 равен −1.

Чтобы получить корректный индекс, прибавьте число корзин к отрицательному остатку или используйте беззнаковое представление хеша. Эту нормализацию обязательно проверяйте в собственной реализации.

Что стоит проверять дополнительно

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

Калькулятор не вычисляет сам хеш: его нужно получить в вашей программе. Страница лишь помогает проверить арифметику остатка и разобраться в примерах.

Нагрузка и перестроение таблицы

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

Проверить такое изменение просто: возьмите тот же хеш 1 234 567 и 32 корзины. Остаток по модулю 32 тоже равен 7 (1 234 567 = 32 · 38 580 + 7), и этот ключ остаётся на месте, тогда как у других ключей индекс при расширении меняется. Калькулятор подходит для таких экспериментов: введите один и тот же хеш при разных размерах таблицы и сравните результаты.

Формула расчёта

Проверенные примеры

Как пользоваться онлайн-калькулятором

1. Вычислите целочисленный хеш ключа вашей функцией.
2. Введите хеш и число корзин таблицы.
3. Нажмите «Вычислить» и получите индекс.
4. Повторите расчёт для нескольких ключей, чтобы оценить равномерность распределения.