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

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

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

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

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

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

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

С1. Хеширование

Нет

Да

K=KEY[i] R=0

УДАЧА ПЕРЕПОЛНЕНИЕ

Рис. Поиск с вставкой по рассеянной таблице с цепочками.

TABLE[1]: [ TO ][ ]

TABLE[2]: [ SYV ][ Λ ]

TABLE[3]: [ EN ][ Λ ]

TABLE[4]: [ TRE ][ Λ ]

TABLE[5]: [ FEM ][ Λ ]

TABLE[6]: [_ Λ _]

TABLE[7]: [_ Λ _]

TABLE[8]: [ SEKS ][ Λ ]

TABLE[9]: [ FIRE ][ ]

рис. Сросшиеся списки.

На первый взгляд шаг C5 может показаться неэффективным, так как в нем поиск свободной позиции производится последовательно. Но в

действительности в процессе заполнения таблицы суммарное число проб в шаге C5 не превышает количества элементов в таблице; значит, в среднем на каждую вставку тратится не более одной такой пробы!

Разрешение коллизий "открытой адресацией". Другой способ решения проблемы коллизий состоит в том, чтобы полностью отказаться от ссылок и просто просматривать один за другим различные элементы таблицы, пока не будут найдены ключ K или свободная позиция. Не плохо было бы иметь правило, согласно которому каждый ключ K определяет последовательность проб, т.е. последовательность позиций в таблице, которые нужно просматривать всякий раз при вставке или поиске K. Если мы, используя определяемую K последовательность проб, натолкнемся на свободную позицию, то можно сделать вывод, что K нет в таблице, так как та же последовательность проб выполняется каждый раз при обработке данного ключа. Этот общий класс методов У. Петерсон назвал открытой адресацией.

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

опробование, использует циклическую последовательность