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

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

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

P(x)=xm + pm-1 xm-1 + … + p0.

Двоичный ключ K=(kn-1 … k1 k0 )2 можно рассматривать как многочлен K(x)=kn-1 xn-1+…+ k1x+ k0, и вычислить остаток

K(x) mod P(x) = hm-1 xm-1+…+ k1 x+ k0,

используя полиномиальную арифметику по модулю 2: h(K)=( hm-1… h1 h0)2. При правильном выборе 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]: [_Λ ]

HEAD[9]: [ ] [ SEKS ][ Λ ]

Рис. Раздельные цепочки.

ключа мы просто выполняем последовательный поиск в списке с

номером h(K)+1.

Рисунок иллюстрирует этот простой метод цепочек при M=9 для

последовательности семи ключей

K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|

(так называются числа от 1 до 7 по-норвежски), имеющих соответственные хеш-коды

h(K)+1 = 3, 1, 4, 1, 5, 9, 2.

Первый список содержит два элемента, три списка пусты.

Метод цепочек является весьма быстрым, поскольку списки коротки. Если в одной комнате собрать 365 человек, то найдется много пар, имеющих один и тот же день рождения, но данный день рождения в среднем имеет лишь один человек! Вообще, если имеется N ключей и M списков, средний размер списка равен N/M; таким образом, хеширование уменьшает количество работы, требуемое на последовательный поиск, примерно в M раз.

В целях экономии времени желательны большие M , но в этом случае многие ссылки будут пустыми, так что большая часть пространства, отводимого под M головных узлов, потратится зря. Для небольших по размеру записей напрашивается другой подход: можно наложить пространство для записей на пространство для головных узлов, отводя в таблице место под M записей и M ссылок, а не под N записей и M+N ссылок.

Иногда можно совершить один проход по данным и выяснить, какие головные узлы будут использоваться, вставляя на следующем проходе "переполняющие" записи в свободные щели. Часто, однако, это нежелательно или невозможно; нам хотелось бы иметь метод, при котором каждая запись обрабатывается лишь один раз, при первом поступлении в систему. Следующий алгоритм, принадлежащий Ф.Уильямсу, является общепринятым способом решения этой задачи.

alg C.(Поиск с вставкой по рассеянной таблице с цепочками.) Предлагаемый

алгоритм позволяет отыскать в таблице из M элементов данный ключ K.

Если K нет в таблице и она не полна, K вставляется в нее.

Элементы таблицы обозначаются через TABLE[i], 0≤i≤ M, и могут

быть двух различных типов: свободный и занятый. Занятый узел

содержит ключевое поле KEY[i], поле ссылки LINK[i] и, возможно,

другие поля.

Алгоритм использует хеш-функцию h(K). Для облегчения поиска свободного пространства используется вспомогательная переменная R; если таблица пуста, R=M+1; по мере проведения вставок будет оставаться в силе утверждение, что узлы TABLE|[j] заняты для всех j в диапазоне R≤j≤M.

Условимся, что узел TABLE[0] всегда будет свободен.

C1.[Хеширование.] Установить i←h(K)+1. (Теперь 1≤i≤M.)

C2.[Список?] Если узел TABLE[i] свободен, то перейти на C6.

(В противном случае этот узел занят, и мы последуем на имеющийся здесь

список занятых узлов).

C3.[Сравнение.] Если K=KEY[i], поиск завершен удачно.

C4.[Переход к следующему.] Если LINK[i]≠0, установить i←LINK[i] и вернуться на

C3.

C5.[Найти свободный узел.] (Поиск был неудачным, и мы хотим найти в

таблице свободное место.) Уменьшать R до тех пор, пока не будет получено

такое значение, что узел TABLE[R] свободен. Если R=0, алгоритм

заканчивается по переполнению (свободных узлов больше нет); в противном

случае установить LINK[i]←R, i←R.

C6.[Вставить новый ключ.] Пометить TABLE[i] как занятый узел

С KEY[i]←K и LINK[i]←0.

В алгоритме допускается срастание нескольких списков, так что после вставки в таблицу записи перемещать не нужно.