Стр. 68 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
66
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
где
1 )(
> ∆
z
.
Часто приращение выбирают фиксированным, независимым от номера
итерации
i
, т.е:
)(
)(
z
z
i
∆= ∆
, таким образом,
m z i zh A
i
mod )) (
)((
∆+ =
.
Если
h
(
x
) =
h
0
(
x
) mod (
m
), то особенно интересно взять
∆
(
z
) =
h
0
(
x
) mod
k
,
где
k
число взаимно простое с
m
. (Проще всего
k
=
m
-2, так как
m
было простым,
а значит, нечётным, то (
m
-1) – чётное, т.е. “сильно” не простое).
Этот метод называется методом двойного совпадения и имеет следующие
плюсы.
1. Последовательность адресов
A
i
= ((
h
0
(
x
) mod
m
) + (
i
(
h
0
(
x
) mod (
m
– 2)) mod
m
.
включает все возможные адреса от 0 до (
m
-1).
2) На уровне вторичных адресов (т.е.
A
i
,
i
>0) практически исключаются
коллизии по модулю.
Алгоритм включения:
A = h
0
(z)
mod
m;
∆
= h
0
(z)
mod
(m-2);
for i=
0
to m-
1
{
if M(A)==z then < неуспех имя z уже есть>
else if M(A) ==
λ
then
{
M(A) = z;
< успех >
< конец >
}
A=(A+
∆
)
mod
m;
}
<Неуспех – вся таблица занята>
Алгоритм поиска:
A = h
0
(z)
mod
m;
∆
= h
0
(z)
mod
(m-
2
);
for i=
0
to m-
1
{
if M(A)==z then < успех , конец>
else if M(A) ==
λ
then < неуспех >
