Алгоритм середины квадрата
Он работает следующим образом. Значение ключа xвозводится в квадрат (с двойной точностью, чтобы избежать переполнения разрядной сетки), а затем из двоичного представления результата вырезается такое количество средних разрядов, которое достаточно для представления индекса таблицы.
Суть алгоритма иллюстрируется на рис. 6.1, где принято, что значение ключа есть 16-разрядное число, его квадрат занимает 32 разряда, а для представления индекса используется 12 разрядов.
Рис. 6.1. Выделение середины квадрата ключа
Для данного алгоритма, в отличие от предыдущего, в качестве размера хеш-таблицы удобно выбрать некоторую степень двойки, например, 1 024, 4 096, 65 536 и т.п. При этом разряды, вырезанные из середины квадрата (соответственно, 10, 12, 16 разрядов), образуют готовое значение индекса.
Почему рекомендуется брать разряды из середины квадрата, а не младшие либо старшие разряды? Потому что на значение средних разрядов в равной степени влияют как младшие, так и старшие разряды ключа. Это позволяет рассеять некоторые виды неравномерностей. Например, если значительная часть ключей – небольшие числа в пределах, скажем, 210, то их квадраты будут в пределах 220, т.е. старшие 12 разрядов будут содержать нулевые значения. И наоборот, если ключами являются числа, кратные некоторой степени двойки, то их квадраты будут содержать много нулей в младших разрядах. Использование средних разрядов позволяет избежать этих неприятностей (если нулей в ключе не слишком много).
В вычислительном отношении алгоритм середины квадрата также достаточно экономен. Фактически он требует одной команды целочисленного умножения, а затем команды сдвига средних разрядов вправо и команды конъюнкции для отбрасывания ненужных старших разрядов.
Недостатком алгоритма является то, что в случае большого количества нулей в младших или в старших разрядах ключа, результат может содержать много нулей даже в средних разрядах.
Алгоритм умножения
По сути, он отличается от предыдущего тем, что значение ключа умножается не на себя самого, а на некоторую числовую константу. Алгоритм может быть реализован очень эффективно, если учитывать особенности двоичного представления чисел в компьютере.
Первой операцией, которая выполняется в этом алгоритме, является умножение ключа xна константуCс отбрасыванием старших разрядов произведения, не уместившихся в разрядной сетке. Цель этой операции – рассеять ключи по всему множеству допустимых целых чисел. Вторая операция – переход от диапазона всех целых чисел к диапазону индексов хеш-таблицы. Для этого выполняют умножение числа на размер хеш-таблицыN, но из произведения выделяют только те разряды, которые выходят за разрядную сетку целых чисел. Очевидно, что число, образованное этими разрядами, будет находиться в пределах от 0 доN–1, причем, если результат первого умножения был равномерно рассеян по множеству целых чисел, то значение хеш-функции будет так же хорошо рассеяно по множеству индексов.
Описанные действия можно записать в виде формул с использованием операций modиdiv, однако это намеренно не сделано, чтобы не создавать соблазна использоватьmodиdivна практике. На самом деле, все гораздо проще, особенно если размер хеш-таблицыN = 2k. При выполнении умножения на константуCстаршие разряды произведения просто отбрасываются, а вместо умножения наNс выделением переполняющих разрядов выполняют просто сдвиг числа вправо, так, чтобы оставить толькоkстарших разрядов.
Работа алгоритма показана на рис. 6.2.
Рис. 6.2. Хеширование по алгоритму умножения
Как видно из рисунка, весь алгоритм сводится к одной операции умножения и одному сдвигу на m – kразрядов вправо.
Важную роль в алгоритме умножения играет константа-множитель C. В литературе (например, [5]) можно найти рекомендации по выбору значенияC, основанные на глубоком анализе алгоритма с использованием методов теории чисел. Приведем здесь лишь несколько простых советов, позволяющих избежать грубых ошибок при выборе. (Предполагается, что размер хеш-таблицыN = 2k.):
значение Cобязательно должно быть нечетным, а еще лучше – простым числом;
не следует выбирать слишком маленькие значения; лучше, если C, по крайней мере, не меньше 1000;
нежелательно также использовать числа, лишь на несколько единиц отличающиеся от одной из степеней двойки, например, такие, как 2 047 (почти равно 211= 2 048) или 4 099 (близко к 212= 4 096).