Следовательно, если таблица заполнена наполовину, среднее число проб, выполняемых при неудачном поиске, составляет около (е -h 2) ?а 1.18. И даже если таблица заполнена полностью, среднее количество проб при вставке последнего элемента равно всего лишь j(e -h 1) « 2.10. Стандартное отклонение также невелико (что показано в упр. 40). Приведенные статистические выкладки показывают, что при случайной хеш-функции списки остаются короткими, хотя алгоритм допускает их "срастание". Конечно, С может оказаться равным даже Л, если функция плоха или вы - исключительно невезучий человек...

При успешном завершении поиска А всегда равно 1. Среднее количество проб можно вычислить путем суммирования величин С + А по первым N неудачным поискам и деления на iV в предположении, что все ключи равновероятны. Таким образом, получаем следующее среднее количество проб при случайном успешном поиске:

0<k<N

17V-1

- 1 - 2Q а 8а П-

Даже если таблица будет полностью заполненной, в среднем потребуется только 1.80 пробы для нахождения элемента! Аналогично (см. упр. 42) среднее значение 51 равно

S\n = \-\{{N -\)1М)к\-\а. (17)

На первый взгляд может показаться, что шаг С5 неэффективен, поскольку поиск пустой позиции на нем осуществляется последовательно. Но в действительности общее количество проб на шаге С5 при построении таблицы никогда не будет превышать количества элементов в таблице; значит, в среднем мы делаем не более одной такой пробы на вставку. В упр. 41 доказывается, что при случайном неудачном поиске Г « ае°.

Можно модифицировать алгоритм С так, что никакие два списка не будут "срастаться", но тогда придется прибегнуть к перемещению записей. Например, рассмотрим ситуацию, представленную на рис. 40, непосредственно перед вставкой SEKS в позицию 9. Чтобы списки оставались раздельными, необходимо переместить FIRE, а для этого нужно найти узел, указывающий на FIRE. Решить эту проблему можно, используя не двусвязный список, а хеширование FIRE и поиск в его списке, как было предложено Д. Э. Фергюсоном (D. Е. Ferguson), поскольку списки невелики по размеру. В упр. 34 показано, что среднее количество проб в случае раздельных списков уменьшается до

N(N-1) о?

С;г = 1 + д 1 + у («еудачный поиск); (18)

= 1 + ~2~~ * 1 f (успешный поиск). (19)

Это, пожалуй, не слишком большое улучшение по сравнению с (15) и (16), чтобы прибегать к такому изменению алгоритма.

с другой стороны, Батлер Лэмпсон (Butler Lampson) заметил, что большая часть пространства, в действительности занятая ссылками, может быть сэкономлена при использовании метода цепочек, если избавиться от "срастания" списков. Это позволяет получить интересный алгоритм, обсуждающийся в упр. 13. Метод Лэмпсона вводит дополнительный бит в каждый элемент, слегка уменьшая при этом среднее количество проб, которые необходимы при неудачном поиске: с (18) до

Раздельные цепочки, показанные на рис. 38, могут использоваться при > М; и, таким образом, проблема переполнения снимается. При срастании списков (см. рис. 40 и алгоритм С) можно поместить переполняющие элементы во вспомогательный пул памяти; Л. Гюиба (L. Guibas) доказал, что среднее количество проб при вставке (M-bL-h 1)-го элемента составляет (Z,/2M-h ) ((1-Ь2/М)- 1) 4-1. Однако обычно предпочтительнее использовать альтернативную схему, при которой первые вызывающие коллизию элементы помещаются во вспомогательную область памяти; в таком случае списки будут "срастаться" только при заполнении вспомогательной области (см. упр. 43).

Разрешение коллизий методом открытой адресации. Другой путь решения проблемы, связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок, просто просматривая различные записи таблицы одну за одной до тех пор, пока не будет найден ключ К или пустая позиция. Идея заключается в формулировании правила, согласно которому по данному ключу К определяется "пробная последовательность", т. е. последовательность позиций таблицы, которые должны быть просмотрены при вставке или поиске К. Если при поиске К согласно определенной этим ключом последовательности встречается пустая позиция, можно сделать вывод о том, что К в таблице отсутствует (поскольку та же последовательность проверок должна выполняться при каждом поиске К). Этот общий класс методов назван открытой адресацией [см. W. W. Peterson, IBM J. Research & DeveJopment 1 (1957), 130-146].

Простейшая схема открытой адресации, известная как линейное исследование, использует циклическую последовательность проверок

Н{К), h{K) - 1, ..., О, М - 1, М - 2, ..., Н{К) 4-1 (20)

и описывается следующим образом.

Алгоритм L {Линейное исследование и вставка). Этот алгоритм выполняет поиск данного ключа К в таблице с М узлами. Если К отсутствует в таблице и таблица не полна, ключ К будет вставлен в таблицу.

Узлы таблицы обозначаются как TABLE [г], О < г < М, и могут быть двух типов - пустыми и занятыми. В занятых узлах содержатся ключи KEY [г] и, возможно, другие поля. Вспомогательная переменная N используется для отслеживания количества занятых узлов; она рассматривается как часть таблицы и увеличивается на 1 при каждой вставке нового ключа.

Алгоритм использует хеш-функцию h{K) и линейную последовательность проб (20) для адресации таблицы. Модификации этой последовательности обсуждаются ниже.

Ll. [Хеширование.] Установить г h{K). (Теперь О < г < М.)

L2. [Сравнение.] Если узел TABLE [г] пуст, перейти к шагу L4. В противном случае, если KEY [г] = К, алгоритм успешно завершается.

L3. [Переход к следующему.] Установить г г - 1; если теперь г < О, установить г г + М. Вернуться к шагу L2.

L4. [Вставка.] (Поиск оказался неудачным.) Если N = М-1, алгоритм завершается в связи с переполнением (условие полного заполнения таблицы полностью в данном алгоритме выглядит как 7V = М - 1, а не как 7V = М; см. упр. 15). В противном случае установить iV iV + 1, пометить узел TABLE [г] как занятый и установить KEY [г] < К.

На рис. 41 показано, что происходит при вставке семи ключей нашего примера с норвежскими цифрами согласно алгоритму L из примера с хеш-кодами 2, 7, 1, 8, 2, 8, 1; при этом последние три ключа, FEM, SEKS и SYV, смещены со своих начальных позиций h{K).

SEKS

FIRE

Рис. 41. Линейная открытая адресация.

Программа L {Линейное исследование и вставка). Эта программа работает с ключами, занимающими полное слово; однако ключ О использовать нельзя, поскольку нулевое значение ключа означает, что данный узел в таблице свободен (другое решение состоит, например, в том, чтобы наложить на ключи условие неотрицательности, а пустые позиции пометить значением -1). Размер таблицы - М (предполагается, что это простое число), а узлы таблицы TABLE [г] имеют адреса TABLE4-г, О < г < М. Для ускорения внутреннего цикла в ячейке TABLE - 1 содержится 0. В ячейке VACANCIES хранится значение М - 1 - Л; и, наконец, гА = К, гИ = г.

Для ускорения внутреннего цикла этой программы из него удалена проверка "г < О", так что в нем остались только существенные части шагов L2 и L3. Общее время работы программы на фазе поиска составляет (7С + 9Е + 21- AS)u, а вставка в случае неудачного поиска добавляет к этой величине еще 8и.

01 START LDX К 1 Ы. Хеширование.

02 ENTA О

03 DIV =М=

04 STX *+1(0:2)

05 ENT1 * 1 i<-h{K).

06 LDA К

07 JMP 2F