Алгоритм умножения

По сути, он отличается от предыдущего тем, что значение ключа умножается не на себя самого, а на некоторую числовую константу. Алгоритм может быть реализован очень эффективно, если учитывать особенности двоичного представления чисел в компьютере.

Первой операцией, которая выполняется в этом алгоритме, является умножение ключа x на константу C с отбрасыванием старших разрядов произведения, не уместившихся в разрядной сетке. Цель этой операции – рассеять ключи по всему множеству допустимых целых чисел. Вторая операция – переход от диапазона всех целых чисел к диапазону индексов хеш-таблицы. Для этого выполняют умножение числа на размер хеш-таблицы N, но из произведения выделяют только те разряды, которые выходят за разрядную сетку целых чисел. Очевидно, что число, образованное этими разрядами, будет находиться в пределах от 0 до N–1, причем, если результат первого умножения был равномерно рассеян по множеству целых чисел, то значение хеш-функции будет так же хорошо рассеяно по множеству индексов.

Описанные действия можно записать в виде формул с использованием операций mod и div, однако это намеренно не сделано, чтобы не создавать соблазна использовать mod и div на практике. На самом деле, все гораздо проще, особенно если размер хеш-таблицы N = 2^k. При выполнении умножения на константу C старшие разряды произведения просто отбрасываются, а вместо умножения на N с выделением переполняющих разрядов выполняют просто сдвиг числа вправо, так, чтобы оставить только k старших разрядов.

Работа алгоритма показана на рис. 6.2.

Рис. 6.2. Хеширование по алгоритму умножения

Как видно из рисунка, весь алгоритм сводится к одной операции умножения и одному сдвигу на m – k разрядов вправо.

Важную роль в алгоритме умножения играет константа-множитель C. В литературе (например, [5]) можно найти рекомендации по выбору значения C, основанные на глубоком анализе алгоритма с использованием методов теории чисел. Приведем здесь лишь несколько простых советов, позволяющих избежать грубых ошибок при выборе. (Предполагается, что размер хеш-таблицы N = 2^k.):

· значение C обязательно должно быть нечетным, а еще лучше – простым числом;

· не следует выбирать слишком маленькие значения; лучше, если C, по крайней мере, не меньше 1000;

· нежелательно также использовать числа, лишь на несколько единиц отличающиеся от одной из степеней двойки, например, такие, как 2 047 (почти равно 2¹¹ = 2 048) или 4 099 (близко к 2¹² = 4 096).