59
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.9. Методы хеширования (методы ассоциативной адресации)
4.9.1. Основные понятия и обозначения
Пусть таблица
T
содержит имена
x
1
,
x
2
,…,
x
n
, которые мы будем хранить в
памяти из
m
ячеек -
М
0
,…,
М
m
-1
. Очевидно, что
m≥n
. К любой ячейке
M
j
можно
обращаться за время, не зависящее от индекса
j
.
Обозначим
S
пространство имён, в которое входят все возможные имена, в
том числе и имена
x
1
,
x
2
,…,
x
n
, входящие в таблицу
T
.
В общем случае |
S
|>>
m
n
.
Пусть
M
состоит из 5 ячеек {
М
0
,
М
1
,
М
2
,
М
3
,
М
4
}. Назовём
A
={0,1,2,3,4} –
пространством адресов.
Функцию
h
, которая для каждого имени из пространства имён
S
вычисляет
некоторый адрес в пространстве адресов
A
, называют хэш-фунцией.
h
(
S
)
A
S
А
Природа самой хеш-функции может быть любой, лишь бы выполнялись
следующие ограничения:
1.
Функция не должна выходить за пределы пространства адресов.
2.
Функция должна быть вычислима для любого ключа. Желательно,
чтобы хэш-функция вычислялась достаточно быстро, а также
использовала бы пространство адресов по возможности более
равномерно.
Пусть имена состоят из прописных букв латинского алфавита
S
=
={
A,B,C,…,Z
}. Каждое имя состоит из 1 буквы. Тогда |
S
|=26. Пусть
пространство адресов
A
= { 0,1,2,3,…,25}. Тогда в качестве хэш-функции
можно взять просто порядковый номер буквы в алфавите
int h(char x)
{
return x – ‘A’;
}
вне зависимости от природы хэш-функции, так как мощность пространства
ключей в реальных задачах много больше размера пространства адресов (т.е.
памяти) и каждому имени невозможно отвести свою персональную ячейку.
1...,51,52,53,54,55,56,57,58,59,60 62,63,64,65,66,67,68,69,70,71,...106