Реферат: Хеш-функции

В двоичной системе M обычно берут равным степени двойки, так что h(K) состоит из старших битов правой значащей половины произведения AK. В двоичном виде при M=2^m мультипликативная хеш-функция вычисляется так:

rA ←K.

rAX ←AK. (5)

rAX ← AK mod w.

Сдвиг rAX на m битов влево.

Результат получается в регистре A.

Одна из привлекательных черт мультипликативной схемы состоит в том, что в (5) не происходит потери информации; мы могли бы вновь найти K, зная лишь содержимое rAX после выполнения инструкций (5). Дело в том, что A взаимно просто с w, и при помощи алгоритма Евклида можно найти Константу A': AA' mod w = 1 ; отсюда следует, что K=(A'(AK mod w)) mod w. Иными словами,

K₁ ≠ K₂ влечет f(K₁ ) ≠ f(K₂ ). (6)

Конечно, f(K)принимает значения в диапазоне от 0 до w-1 и не является сколько-нибудь подходящей хеш-функцией, но она может быть очень полезной в качестве рассеивающей функции, а именно функции, удовлетворяющей (6) и обычно приводящей к рандомизации ключей.

Хорошая хеш-функция должна удовлетворять двум требованиям:

a)ее вычисление должно быть очень быстрым;

b)она должна минимизировать число коллизий.

Свойство (a) отчасти зависит от особенностей машины, а свойство (b)- от характера данных. Если бы ключи были действительно случайными, можно было бы просто выделить несколько битов и использовать их для хеш-функции, но на практике, чтобы удовлетворить (b), почти всегда нужна функция, зависящая от всех битов.

До сих пор мы рассматривали хеширование ключей, состоящих из одного слова. С ключами, состоящими из нескольких слов или имеющими переменную длину, можно работать как с представленными с многократной точностью числами и применить к ним рассмотренные методы. Однако обычно оказывается достаточной более быстрая процедура, когда отдельные слова сначала комбинируются в одно, а затем производится единственное умножение или деление. Для комбинирования можно использовать сложение по модулю w или операцию "исключающее или" (на двоичных ЭВМ). Достоинством обеих операций является их обратимость, т.е. их результат зависит от всех битов аргументов, причем "исключающее или" иногда предпочтительнее, так как не может привести к арифметическому переполнению. Заметим, что обе операции коммутативны, поэтому ключи (X, Y) и (Y, X) будут "брошены" по одному адресу. Чтобы избежать этого, Г.Д. Кнотт предложил предварительно делать циклический сдвиг.

Из других испытанных методов хеширования, пожалуй, наиболее интересным является способ, основанный на алгебраической теории кодирования. Идея аналогична методу деления, только вместо деления на целое число используется деление на многочлен по модулю 2. Для предлагаемого метода M должно быть степенью 2: M=2^m ; кроме того, используется многочлен m-й степени

P(x)=x^m + p_m-1 x^m-1 + … + p₀ .

Двоичный ключ K=(k_n-1 … k₁ k₀ )₂ можно рассматривать как многочлен K(x)=k_n-1 x^n-1 +…+ k₁ x+ k₀ , и вычислить остаток

K(x) mod P(x) = h_m-1 x^m-1+…+ k₁ x+ k₀ ,

используя полиномиальную арифметику по модулю 2: h(K)=( h_m-1… h₁ h₀ )₂ . При правильном выборе P(x) такая хеш-функция позволяет избежать коллизий, между почти равными ключами.

Разрешение коллизий методом цепочек. Мы уже говорили,

что некоторые адреса могут порождаться несколькими ключами. Пожалуй, наиболее очевидный способ решения проблемы состоит в том, чтобы поддерживать M связанных списков, по одному на каждый возможный хеш-адрес. Все записи должны содержать поля LINK; кроме того, нужно иметь M головных узлов списков HEAD[i], где i меняется от 1 до M . После хеширования

HEAD[1]: [__] [ TO ][ ] [ FIRE ][ Λ ]

HEAD[2]: [__] [ SYV ][ Λ ]

HEAD[3]: [__] [ EN ][ Λ ]

HEAD[4]: [__] [ TRE ][ Λ ]

HEAD[5]: [__] [ FEM ][ Λ ]

HEAD[6]: [_Λ _]

HEAD[7]: [_Λ _]

HEAD[8]: [_Λ ]