Стр. 62 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
60
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Таким образом, неизбежны так называемые коллизии, когда для двух
различных ключей
x
i
≠
x
j
значения хэш - функций равны
h(x)=h(y)
. Ключи
x
i
и
x
j
в этом случае называются коллизирующими. Чем равномернее хэш-функция
использует пространство адресов, тем реже будут происходить коллизии, хотя
они будут происходить неизбежно.
Хэш-функцию следует выбирать, исходя из имеющегося пространства
адресов (
m
) и предполагаемого размера таблицы (
n
), таким образом, чтобы:
1) пространство
M
использовалось равномерно.
2) коллизии возникали как можно реже.
3) когда коллизии возникнут, их можно было разрешить.
Прежде чем переходить к методам построения
h
-функций и методам
разрешения коллизий, рассмотрим несколько тривиальных примеров.
Пример:
Пусть доступна память из 10 ячеек, т.е.
m
=10 и
M
={
М
0
,
М
1
,
М
2
, …,
М
9
}
Пусть имена
x
i
состоят из двух букв.
Причём букве
A
соответствует код 00000
B
00001
C
00010
…………………………………………………………….
Пусть в таблицу входят имена:
AN,AT,NO,ON,PI
.
Рассмотрим их двоичное представление:
0 0 0 1 0 1 1 1 1 0
1 0 1 1 0 0 1 1 1 0
0 1 1 1 0 1 0 1 1 0
1 1 0 0 1 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0
10
9 8 7 6 5 4 3 2 1
→
→
→
→
→
→
PI
ON
NO
AT
AN
b b b b b b b b b b
биты
Таким образом, каждое имя представляется десятью битами. Заметим, что
двоичная цепочка
b
4
b
5
b
6
однозначно определяет каждое из пяти имён и, кроме
того, если рассматривать
b
4
b
5
b
6
как двоичное число, то оно лежит в заданном
пространстве адресов.
Таким образом,
h
-функцию можно определить следующим образом:
h
(
x
)=(
b
4
b
5
b
6
)
2
Например:
h
(
AT
)=(001)
2
=1, т.е. для
AT
выделяем ячейку
M
1
.
h
(
ON
)=(100)
2
=4, т.е. для
ON
выделяем ячейку
M
4
.
Попытка включить в таблицу новое имя
OO
приведёт к коллизии, так как
h
(
OO
)=(100)
2
=4=
h
(
ON
).
