Составители:
Рубрика:
80 Глава 6. Поиск
Алгоритм:
L1: i = h(K);
L2: если table[i].p= 0, то перейти к шагу L4;
если table[i].key= K, то УДАЧА;
L3: i = i − 1;
если i < 0, то i = i + M и перейти к шагу L2;
L4: если M = n − 1, то ПЕРЕПОЛНЕНИЕ;
M = M + 1; table[i].p= 1; table[i].key= K.
Оценки среднего времени работы этого алгоритма имеют вид:
C(n) =
1
2
(1 +
1
1−α
), C
0
(n) =
1
2
(1 +
1
(1−α)
2
).
Существует много других способов организации поиска при по-
мощи хеш-функций. Например, алгоритм поиска со вставкой по от-
крытой рассеянной таблице можно модифицировать введением вто-
рой h
2
(K) хеш-функции, которая задает порядок перебора ключей.
Шаг L3 будет теперь иметь вид i = i − h
2
(K). Такой метод называет-
ся ”открытая адресация с двойным хешированием”.
80 Глава 6. Поиск
Алгоритм:
L1: i = h(K);
L2: если table[i].p= 0, то перейти к шагу L4;
если table[i].key= K, то УДАЧА;
L3: i = i − 1;
если i < 0, то i = i + M и перейти к шагу L2;
L4: если M = n − 1, то ПЕРЕПОЛНЕНИЕ;
M = M + 1; table[i].p= 1; table[i].key= K.
Оценки среднего времени работы этого алгоритма имеют вид:
C(n) = 12 (1 + 1−α
1
), C 0 (n) = 12 (1 + (1−α)
1
2 ).
Существует много других способов организации поиска при по-
мощи хеш-функций. Например, алгоритм поиска со вставкой по от-
крытой рассеянной таблице можно модифицировать введением вто-
рой h2 (K) хеш-функции, которая задает порядок перебора ключей.
Шаг L3 будет теперь иметь вид i = i − h2 (K). Такой метод называет-
ся ”открытая адресация с двойным хешированием”.
