Умножение

Построение хеш-функции методом умножения (multiplication method) состо­ит в следующем. Пусть количество хеш-значений равно т. Зафиксируем кон­станту А в интервале 0 < А < 1, и положим

h(k) = m(k A mod 1),

где kA mod 1 – дробная часть kA.

Достоинство метода умножения в том, что качество хеш-функции мало зависит от выбора m. Обычно в качестве т выбирают степень двойки, поскольку в большинстве компьютеров умножение на такое т реализуется как сдвиг слова. Пусть, например, длина слова в нашем компьютере равна w битам и ключ k помещается в одно слово. Тогда, если т = 2^Р, то вычисление хеш-функции можно провести так: умножим k на m-битовое целое число А2^w (предполагается, что это число является целым); получится 2w-битовое число. Пусть r₀ – число, образованное младшими w разрядами; старшие р битов в r₀ образуют искомое хеш-значение (рис. 4.5).

Метод умножения работает при любом выборе константы А, но некоторые значения А могут быть лучше других. Оптимальный выбор зависит от того, какого рода данные подвергаются хешированию.

Рисунок 4.5 – Хеширование с использованием умножения

В одной своей книге Кнут обсуждает выбор константы А и приходит к выводу, что значение

A(– 1)/2 = 0,6180339887…

является довольно удачным (золотое сечение).