Стр. 61 - Основы алгоритмов и структур данных

Содержание 59
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.9. Методы хеширования (методы ассоциативной адресации)
4.9.1. Основные понятия и обозначения
Пусть таблица T содержит имена x1 ,x 2,…,xn , которые мы будем хранить в
памяти из m ячеек - М0 ,…,Мm -1. Очевидно, что m≥n. К любой ячейке Mj можно
обращаться за время, не зависящее от индекса j.
Обозначим S пространство имён, в которое входят все возможные имена, в
том числе и имена x1 ,x2 ,…,xn , входящие в таблицу 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’;
}
вне зависимости от природы хэш-функции, так как мощность пространства
ключей в реальных задачах много больше размера пространства адресов (т.е.
памяти) и каждому имени невозможно отвести свою персональную ячейку.