Метод умножения

Получить из исходной последовательности ключей последовательность хеш-кодов, используя метод умножения (мультипликативный метод), значит воспользоваться хеш-функцией:

h (k)=⌊ n *({ k * A })⌋

Здесь A – рациональное число, по модулю меньшее единицы (0< A <1), а k и n обозначают то же, что и в предыдущем методе: ключ и размер хеш-таблицы. Также правая часть функции содержит три пары скобок:

· () – скобки приоритета;

· ⌊ ⌋ – скобки взятия целой части;

· { } – скобки взятия дробной части.

Аргумент хеш-функции k (k ≥0) в результате даст значение хеш-кода h (k)= x, лежащие в диапазоне 0… n -1. Для работы с отрицательными числами можно x взять по модулю.

От выбора A и n зависит то, насколько оптимальным окажется хеширование умножением на определенной последовательности. Не имея сведений о входящих ключах, в качестве n следует выбрать одну из степеней двойки, т. к. умножение на 2 ^m равносильно сдвигу на m разрядов, что компьютером производиться быстрее. Неплохим значением для A (в общем случае) будет (√5-1)/2≈0,6180339887. Оно основано на свойствах золотого сечения:

Золотое сечение – такое деление величины на две части, при котором отношение большей части к меньшей равно отношению всей величины к ее большей части.

Отношение большей части к меньшей, выраженное квадратичной иррациональностью:

φ =(√5+1)/2≈1,6180339887

Для мультипликативной хеш-функции было приведено обратное отношение:

1/ φ =(√5-1)/2≈0,6180339887

При таком A, хеш-коды распределяться достаточно равномерно, но многое зависит от начальных значений ключей.

Для демонстрации работы мультипликативного метода, положим n =13, A =0,618033. В качестве ключей возьмем числа: 25, 44 и 97. Подставим их в функцию:

1. h (k)=⌊13*({25*0,618033})⌋=⌊13*{15,450825}⌋=⌊13*0,450825⌋=⌊5,860725⌋=5

2. h (k)=⌊13*({44*0,618033})⌋=⌊13*{27,193452}⌋=⌊13*0,193452⌋=⌊2,514876⌋=2

3. h (k)=⌊13*({97*0,618033})⌋=⌊13*{59,949201}⌋=⌊13*0,949201⌋=⌊12,339613⌋=12

Реализация метода на C++:

int HashFunction(int k)

{

int n=13; double A=0.618033;

int h=n*fmod(k*A, 1);

return h;

}

void main()

{

int key;

cout<<"Ключ > "; cin>>key;

cout<<"HashFunction("<<key<<")="<<HashFunction(key)<<endl;

}

1.3 Хеш-таблица

Хеш-таблицей называется структура данных, предназначенная для реализации ассоциативного массива, в котором адресация реализуется посредством хеш-функции. Хеш-функция – это функция, преобразующая ключ key в некоторый индекс i равный h (key), где h (key) – хеш-значение (хеш-ключ) key. Весь процесс получения индексов хеш-таблицы называется хешированием.

Хеш-таблица позволяет организовать массив, специфика которого проявляется в связанности индексов по отношению к хеш-функции. Индексы могут быть не только целого типа данных (как это было в простых массивах), но и любого другого, для которого вычислимы хеш-значения. Данные, хранящиеся в виде такой структуры, удобны в обработке: хеш-таблица позволяет за минимальное время (O (1)) выполнять операции поиска, вставки и удаления элементов.

Предположим, имеется товарная накладная с информацией о датах и городах (когда и куда отправляются товары). Определенному товару соответствует его числовой код в диапазоне от 000000000 до 999999999:

Код	Дата	Город доставки
	2016-03-10	Тула
……	……	……
	2016-09-23	Москва
	2018-08-25	Орел
……	……	……
	2017-05-14	Казань
	2019-02-018	Крым
……	……	……
	2026-09-01	Хабаровск

Здесь ключами являются коды товаров. Такая организация данных не оптимальна, поскольку памяти для хранения списка выделяется больше чем нужно. Решением проблемы будет хеширование ключей списка. Хешировать можно те же коды или другие данные, например, даты. У девятизначных кодов ключи имеют целочисленный тип данных, а у дат – символьные (строковые). Для хеширования понадобиться хеш-функция. В качестве последней можно взять, например, следующую хеш-функцию:

string hashf(string key)

{

string h=key.erase(0, 5);

return (h);

}

Формальный параметр key это строка, состоящая из 10 символов, т. е. дата. Функция erase () удаляет из строки key 5 символов, после чего результат вида «месяц-число» присваивается переменной h, которая и будет индексом нового списка. Например, из ключа 2026-09-01, путем хеширования, получился хеш-ключ 09-01. Таким образом, размер накладной заметно сокращается, исчезают все пустые элементы. Но в некоторых местах возможно возникновения проблем следующего типа: пусть имеется два ключа: 2017-06-06 и 2025-06-06, тогда результат работы функции в двух случаях будет 06-06, следовательно, разные значения в хеш-таблицы попадут под один и тот же индекс, т.е. возникнет коллизия.