Методы хеширования

Многочисленные эксперименты с реальными данными выявили удовле-творительную работу двух основных типов хеш-функций. Один из них основан на делении, другой – на умножении. Все рассуждения ведутся в предположении, что хеш-функция h(K): 0 ≤ h(K) ≤ N для всех ключей K, где N – размер памяти (количество ячеек).

Метод деления использует остаток от деления на М:

h(K)= К mod M (4.1)

Если М – чётное число, то при чётных К значение h(K) будет чётным, и наоборот, что даёт значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Вообще, М должно удовлетворять условию:

M ≠r^k±a,

где k и a – небольшие числа, а r – "основание системы счисления" для большинства используемых литер (как правило, 128 или 256), т.к. остаток от деления на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетворительные результаты даёт М = 1009.

Мультипликативный метод также легко реализовать. В соответствии с ним хеш-функция определяется так:

(4.2)

где w – размер машинного слова (обычно, 2³¹); А – целое число простое по отношению к w; а M – некоторая степень основания системы счисления ЭВМ (2^m). Таким образом, в качестве значения функции берутся M правых значащих цифр дробной части произведения значения ключа и константы A/w. Преимущество второго метода перед первым обусловлено тем, что произведение обычно вычисляется быстрее, чем деление.

При использовании любых методов хеширования для размещения записей должен быть выделен участок памяти размером N. Для того чтобы полученное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так:

А(К) = h(K) mod N (4.3)