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

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

alg L. (Поиск с вставкой по открытой рассеянной таблице.)

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

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

Узлы таблицы обозначаются через TABLE[i], 0≤i<M, и принадлежат

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

содержит ключ KEY[i] и, возможно, другие поля. Значение вспомогательной переменной N равно числу занятых узлов; эта переменная рассматривается как часть таблицы, и при вставке нового ключа ее значение увеличивается на 1.

Данный алгоритм использует хеш-функцию h(K) и линейную

последовательность проб ( * ) для адресации. Модификации этой

последовательности обсуждаются ниже.

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

L2. [Сравнить.] Если узел TABLE[i] свободен, то перейти на L4 . В

противном случае, если KEY[i]=K, алгоритм заканчивается удачно.

L3. [Перейти к следующему.] Установить i←(i-1); если теперь i<0,

Установить i←i+M. Вернуться на L 2 .

L4. [Вставить.] (Поиск был неудачным.) Если N=M-1, алгоритм

заканчивается по переполнению. В противном

случае установить N←N+1, отметить, что узел TABLE[i] занят и

установить KEY[i]←K.

На рис.( см. ниже) показано, что происходит при вставке с помощью алгоритма~L семи "норвежских" ключей , имеющих коды хеширования 2, 7, 1, 8, 2, 8, 1

соответственно. Последние три ключа- FEM, SEKS и SYV-смещены по

сравнению со своими начальными адресами h(K).

0 [ FEM ]

1 [ TRE ]

2 [ EN ]

3 [ ]

4 [ ]

5 [ SYV ]

6 [_SEKS ]