Стр. 63 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
61
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Примечание: В этом примере таблица имён была известна до того, как мы
начали создавать
h
-функцию.
Резюме: Если значение хэш-функции вычисляется на основе побитового
представления ключа, то желательно по возможности использовать либо все
биты, либо те, которые наиболее адекватно изменяются с изменением самого
ключа.
В общем случае значение хэш-функции должно лежать в интервале от 0 до
m
-1. Поэтому в качестве h-функций часто выбирают функции вида
h
(
x
)=
h
0
(
x
) mod (
m
), где
h
0
(
x
) – некоторая функция.
Пример
Пространство имён – названия животных. В качестве хэш-функции будем
использовать сумму порядковых номеров в алфавите.
Например,
h
0
(ЁЖ) = 7+8 = 15.
Предполагаем, что в таблицу одновременно входит не более
m
= 20 имён.
Тогда
h
(
x
)=
h
0
(
x
) mod (20).
h
(БЕГЕМОТ) = (2+6+4+6+13+15+19)mod 20 = 65 mod 20 = 5.
h
(ВАРАН) = 10.
h
(ЖИРАФ) = 15.
h
(ЗЕБРА) = 14.
h
(ПИТОН) = 15.
Последнее имя приводит к коллизии.
Очевидно, при такой структуре хэш-функции все возникающие коллизии
можно разделить на два вида:
1) непосредственная коллизия, когда
х
< >
y
, но
h
0
(
x
) =
h
0
(
y
) =>
h
(
x
) =
h
(
y
);
2) коллизии по модулю:
x
< >
y
,
h
0
(
x
) < >
h
0
(
y
), но
h
(
x
) =
h
(
y
).
Известно, что в реальных практических приложениях доля коллизий по
модулю резко уменьшается, если в качестве размера таблицы
n
брать простое
число. Так как в больших числах простые числа лежат достаточно далеко одно
от другого, то считается приемлемым вместо простого числа взять число, не
имеющее делителей меньше 20.
Выбор хэш-функции.
Не существует формализованных способов выбора хороших хэш-функций.
Одна и та же хэш-функция может быть удачной для одного пространства имён
