Стр. 64 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
62
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
и неудачной для другого. И даже для различных наборов имён из одного
пространства эффективность хэш-функции может быть различной.
В любом случае хэш-функция должна:
1) отображать пространство имён в пространство адресов (по возможности
равномерно).
2) по возможности использовать все биты или символы ключа.
3) любая хэш-функция должна быть оттестирована на контрольных
примерах.
В целом эффективность хеширования определяется возможностью
быстрого разрешения коллизий.
В некоторых задачах значительная часть ключей может начинаться с
одного и того же символа. В таких случаях может быть выгодно не
использовать одну или несколько начальных символов для построения хэш-
функции.
Примечание.
Пусть
h
(
x
)=|
x
|, где |
x
|- значение двоичного кода имени
x
. |
x
| всегда
заключено в некоторых пределах
const
| | 0
xx
≤
. Пространство адресов изменяется
от 0 до (
m
-1). Очевидно, чтобы рассматривать |
x
| как адрес, его необходимо
помножить на некоторую константу c:
h
(
x
)=
c
|
x
|.
Если
mx
<
, то
c
>1.
Такое хеширование называется мультипликативным.
Здесь также возникают “подводные камни”: часто таблица содержит такие
имена, двоичные представления которых представляют собой арифметическую
прогрессию, т.е.
∆+ =
|
| |
|
j
i
x x
,
∆+ =
|
| |
|
i
k
x x
и т.д. ,
где
const
−∆
.
Если
∆
случайно окажется делителем
m
, то будет использовано только
∆
1
-
часть пространства адресов.
Пример
Пусть |
x
1
|=0, |
x
2
|=5, |
x
3
|=10, |
x
4
|=15 и т.д.
Пусть
m
= 20.
Пусть
h
(
x
)=|
x
| mod 20.
Тогда
h
(
x
1
)=
h
(
x
5
)=
h
(
x
9
)=0,
h
(
x
2
)=
h
(
x
6
)=
h
(
x
10
)=5 и т.д., т.е. ячейки
M
1
,
M
2
,
M
3
,
M
4
,
M
6
,
M
7
,
M
8
,
M
9
, …,
M
19
, никогда не будут использованы.
Выводы
:
m
должно быть простым числом.
