Этот метод представляет собой очевидную комбинацию обсуждавшихся ранее технологий, поэтому нет необходимости детально описывать алгоритм для хеш-таблиц с цепочками. Часто удобно хранить отдельные списки упорядоченными по ключам, что делает вставку и неудачный поиск более быстрыми. Так, если бы в приведенном примере использовались списки в порядке возрастания, то узлы ТО и FIRE на рис. 38 поменялись бы местами, а все ссылки Л были бы при этом заменены указателем на вспомогательную запись с ключом оо (см. алгоритм 6.IT). Другой подход предусматривает использование концепции "самоорганизованности; обсуждавшейся в разделе 6.1; записи могут быть упорядоченными не по значениям ключей списка, а по последнему времени обращения к ним.

Для повышения быстродействия желательны большие значения М, однако в этом случае слишком многие списки будут пусты и будут зря расходовать память на содержание заголовков списков. При небольших размерах записей можно воспользоваться следующим подходом: совместить пространство для записей с пространством для заголовков списков, отводя место для М записей и М ссылок вместо места для записей и М + N ссылок. Иногда можно совершать проход по всем данным для поиска заголовков списков, которые будут использоваться, а затем при втором проходе вставлять "переполняющие" записи в пустые "щели". Однако зачастую это непрактично или невозможно, поэтому хотелось бы иметь метод, работающий с каждой записью только раз - при ее помещении в систему. Следующий алгоритм, предложенный в работе F. А. Williams, САСМ 2,6 (June, 1959), 21-24, позволяет быстро решить эту задачу.

Алгоритм С (Поиск и вставка в хеш-таблице с цепочками). Этот алгоритм (рис. 39) ищет данный ключ К в таблице из М узлов. Если К в таблице отсутствует, а таблица не заполнена, К вставляется в таблицу.

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

Алгоритм использует хеш-функцию h{K). Применяется также вспомогательная переменная R для упрощения поиска пустых мест; если таблица пуста, R- М + 1; по мере вьшолнения вставок всегда будет оставаться истинным утверждение, что узлы TABLE Tj] заняты для всех j в диапазоне R < j < М. По соглашению узел TABLE [0] всегда пуст.

С1. [Хеширование.] Установить г +- h(K) + 1. (Теперь 1 < г < М.)

С2. [Есть ли список?] Если TABLE [г] пуст, перейти к шагу Сб. (В противном случае TABLE [г] занят и мы приступим к поиску в списке, начинающемся в этом узле.)

СЗ. [Сравнение.] Если К = KEY [г], алгоритм успешно завершается.

С4. [Переход к следующему.] Если LINK [г] ф О, установить г +- LINK [г] и вернуться к шагу СЗ.

С5. [Поиск пустого узла.] (Поиск был неудачным, и необходимо найти пустое место в таблице.) Уменьшать R один или более раз, пока не будет найдено такое значение, при котором узел TABLE [i?] будет пуст. Если R - алгоритм завершается в связи с переполнением (свободных узлов больше нет); в противном случае установить LINK [г] R, i R.

3. CpaBHeHHeJ

Успешное завершение

Переполнение

Рис. 39. Поиск и вставка в хеш-таблице с цепочками.

Сб. [Вставка нового ключа.] Пометить узел TABLE [г] как занятый с KEY [г] i- К и LINKm<«-0. I

Алгоритм позволяет объединить несколько списков, поэтому записи не нужно перемещать после вставки в таблицу. Например, взгляните на рис. 40, на котором SEKS попадает в список, содержащий ТО и FIRE, поскольку последний уже был вставлен в позицию 9.

Рис. 40. "Сросшиеся" цепочки.

Для сравнения алгоритма С с другими алгоритмами этой главы можно написать следующую MIX-программу. Выполненный анализ показал, что цепочки, как правило, коротки, и приведенная программа написана с учетом этого факта.

Программа С {Поиск и вставка в хеш-таблице с цепочками). Для удобства считаем, что ключи состоят из трех байтов, а узлы имеют следующий вид:

Пустой узел Занятый узел

(13)

в качестве размера таблицы М выбирается простое число; TABLE [г] хранится по адресу TABLE -{-г. rll =г, тА = К.

01 KEY EQU 3:5

02 LINK EQU 0:2

Время работы программы зависит от следующих параметров:

С - число проверенных во время поиска узлов таблицы; А - [первая проверка обнаружила занятый узел]; 5 - [поиск был успешен];

Т - количество элементов таблицы, проверенных при поиске пустого пространства.

Здесь S - S1 + 52, где S1 = 1 при успешной первой попытке. Общее время работы поисковой фазы программы С равно (7С 4- 4>1 + 17 - 35 4- 2Sl)u, а вставка нового ключа при 5 = 0 требует дополнительного времени {8А + 4Т 4- 4) и.

Предположим, что в начале работы программы в таблице содержалось N ключей, и введем

а = N/M = коэффициент заполнения таблицы. (14)

Тогда среднее значение А при неудачном поиске, очевидно, равно а, если хеш-функция случайна; в упр. 39 доказывается, что среднее значение С для неудачного поиска равно

( + м) ---м)

-1-2Q

(15)