Деление с остатком

Построение хеш-функции методом деления с остатком (division method) состоит в том, что ключу k ставится в соответствие остаток от деления k на m, где т – число возможных хеш-значений:

h(k) – k mod m.

Например, если размер хеш-таблицы равен m = 12 и ключ равен 100, то хеш-значение равно 4.

При этом некоторых значений m стоит избегать. Например, если m = 2^Р, то h(k) –это просто р младших битов числа k. Если нет уверенности, что все комбинации младших битов ключа будут встречаться с одинаковой частотой, то степень двойки в качестве числа т не выбирают. Нехорошо также выбирать в качестве т степень десятки, если ключи естественно возникают как десятич­ные числа: ведь в этом случае окажется, что уже часть цифр ключа полностью определяет хеш-значение. Если ключи естественно возникают как числа в си­стеме счисления с основанием 2^Р, то нехорошо брать m = 2^Р – 1, поскольку при этом одинаковое хеш-значение имеют ключи, отличающиеся лишь перестановкой «2^р-ичных цифр».

Хорошие результаты обычно получаются, если выбрать в качестве m про­стое число, далеко отстоящее от степеней двойки. Пусть, например, нам надо поместить примерно 2000 записей в хеш-таблицу с цепочками, причем нас не пугает возможный перебор трёх вариантов при поиске отсутствующего в таб­лице элемента. Что ж, воспользуемся методом деления с остатком при длине хеш-таблицы m = 701. Число 701 простое, 701 ~ 2000/3, и до степеней двойки от числа 701 тоже далеко. Стало быть, можно выбрать хеш-функцию вида

h(k) = k mod 701.

На всякий случай можно ещё поэкспериментировать с реальными данными на предмет того, насколько равномерно будут распределены их хеш-значения.