Для этого метода нет ограничений на длину таблицы, свойственных методу деления. Вычисление хэш-адреса происходит в два этапа:
1. Вычисление нормализованного хэш-адреса в интервале [0..1] по формуле:
F(K) = (С*К) mod 1,
где С — некоторая константа из интервала [0..1], К —
результат преобразования ключа в его числовое представление, mod 1
означает, что F(K) является дробной частью произведения С*К.
2. Конечный хэш-адрес А(К) вычисляется по формуле А(К) = [M*F(K)], где
М — размер хэш-таблицы, а скобки [] означают целую часть результата
умножения.
Удобно рассматривать эти две формулы вместе:
А(К) = М*(С*К) mod 1. (2.4)
Кнут в качестве значения С рекомендует использовать «золотое сечение» — величину, равную ((л/5)-1)/2«0,6180339887. Значение F(K) можно формировать с помощью как команд сопроцессора, так и целочисленных команд. Команды сопроцессора вам хорошо известны и трудностей с реализацией формулы (2.4) не возникает. Интерес представляет реализация вычисления А(К) с помощью целочисленных команд. Правда, в отличие от реализации сопроцессором здесь все же Удобнее ограничиться условием, когда М является степенью 2. Тогда процесс вычисления с использованием целочисленных команд выглядит так:
Выполняем произведение С*К. Для этого величину «золотого
сечения» С~0,6180339887 нужно интерпретировать как целочисленное
значение,
обходимо стремиться к тому, чтобы появление 0 и 1 в выделяемых
позициях было как можно более равновероятным. Здесь трудно дать
рекомендации, просто нужно провести анализ как можно большего количества
возможных ключей, разделив составляющие их байты на тетрады. Для
формирования хэш-адреса нужно будет взять биты из тех тетрад (или
полностью тетрады), значения в которых изменялись равномерно.