Реферат: Хеш-функции
8 [ FIRE ]
Рис. Линейная открытая адресация.
Эксперименты с линейным опробованием показывают, что этот метод работает прекрасно, пока таблица не слишком заполнена, но в конце концов процесс замедляется, длинные серии проб становятся все более частыми. Причину такого поведения можно понять, рассмотрев следующую гипотетическую рассеянную таблицу (M=19, N= 9):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Заштрихованные квадраты обозначают занятые позиции. Ключ K, который должен быть вставлен в таблицу следующим, попадет в одну из десяти свободных позиций, но не с равными вероятностями. В самом деле, K будет вставлен в позицию 11, если 11≤h(K)≤15, а в позицию 8 он попадет лишь при h(K)=8. Следовательно, вероятность попасть в
позицию 11 в пять раз больше, чем в позицию 8; длинные списки стремятся стать еще длиннее.
alg D. (Открытая адресация с двойным хешированием.)
Этот алгоритм почти совпадает с алгоритмом L, но использует несколько иную последовательность проб, вычисляя две хеш-функции h1 (K) и h2 (K). Как обычно, h1 (K) порождает величины от 0 до M-1 включительно; но значения h2 (K) должны лежать от 1 до M-1 и быть взаимно просты с M. (Например, если M - простое число, то h2 (K) может быть любой величиной от 1 до M-1 включительно, или, если M=2m , то h2 (K) может быть любым нечетным числом между 1 и 2m -1.)
D1 .[Первое хеширование.] Установить i ←h2 (K).
D2 .[Первая проба.] Если узел TABLE[i] свободен, то перейти
на D6. В противном случае, если KEY[i]=K, алгоритм
заканчивается удачно.
D3 .[Второе хеширование.] Установить c←h2 (K).
D4 .[Перейти к следующему.] Установить i←i-c; если теперь i<0,
Установить i←i+M.
D5 .[Сравнение.] Если узел TABLE[i] свободен, то перейти
на D6. В противном случае, если KEY[i]=K, алгоритм заканчивается
удачно; в противном случае вернуться на D4.
D6 .[Вставка.] Если N=M-1, алгоритм заканчивается по переполнению. В
противном случае установить N←N+1, пометить узел TABLE[i]как занятый
и установить KEY[i]← K.
Для вычисления h2 (K) было предложено несколько способов.
Если M - простое число и h1 (K)=K mod M, можно положить h2 (K)=1+(K mod (M-1)); но так как M-1 четно, было бы лучше положить h2 (K)=1+(K mod (M-2)).
Это наводит на мысль о таком выборе M, чтобы M и M-2были простыми числами-близнецами, например 1021 и 1019. Можно взять h2 (K)=1+([K/M] mod (M-2)), ибо частное [K/M] можно получить в регистре как побочный продукт вычисления h1 (K).
Сравнение методов. Итак, мы знаем много методов поиска;
чем же нам руководствоваться при выборе наилучшего из них;
для конкретного приложения? Трудно в нескольких словах описать все, что нам хотелось бы учесть при выборе метода поиска, однако следующие соображения, пожалуй, наиболее важны, если мы заинтересованы в сокращении времени поиска и объема занимаемой памяти.
Различные способы разрешения коллизий приводят к различному числу проб. Но это еще не все, так как с изменением метода меняется время пробы, что заметно отражается на времени работы. При линейном опробовании чаще, чем в других методах, происходит обращение к таблице, зато этот метод прост.