В литературе часто упоминается метод квадрата как один из первых методов
генерации последовательностей псевдослучайных чисел. При этом он
непременно подвергается критике за плохое качество генерируемых
последовательностей. Но, как упомянуто выше, для процесса хэширования
это не является недостатком. Более того, в ряде случаев это наиболее
предпочтительный алгоритм вычисления значения хэш-функции. Суть метода
проста: значение ключа возводится в квадрат, после чего берется
необходимое количество средних битов результата. Возможны варианты — при
различной длине ключа биты берутся с разных позиций. Для принятия
решения об использовании метода квадрата для вычисления хэш-функции
необходимо провести статистический анализ возможных значений ключей.
Если они часто содержат большое количество нулевых битов, то это
означает, что распределение значений битов в средней части квадрата
ключа недостаточно равномерно. В этом случае использование метода
квадрата неэффективно.
На этом мы закончим знакомство с методами хэширования, так как полное
обсуждение этого вопроса не является предметом книги. Информацию об
остальных методах (сегментации, перехода к новому основанию,
алгебраического кодирования) можно получить из различных источников.
В ходе реализации хэширования с помощью методов деления и умножения
возможные коллизии мы лишь обозначали без их обработки. Настало время
разобраться с этим вопросом.