Хеш-функции

Хеш-функция – функция, преобразовывающая входную последовательность данных произвольного размера в выходную последовательность фиксированного размера. Процесс преобразования данных называется хешированием. Результат хеширования – хеш-код (хеш-сумма, хеш).

При решении класса практических задач выбирается такая хеш-функция, которая является наиболее оптимальной именно для данного класса. В общем случае следует использовать «хорошую» функцию. Когда хеш-функцию называют «хорошей», то подразумевают под этим, что она:

  1. вычисляется достаточно быстро;
  2. сводит к минимуму число коллизий.

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

Использовать хеш-функцию или нет, зависит от того насколько целесообразно применение ее свойств, а также свойств алгоритма, по которому она может быть реализована на ЯП. В одних ситуациях наиболее важна высокая скорость работы, в других равномерное распределение хеш-кодов и т. п. Далее будут рассмотрены два наиболее известных метода хеширования.

Метод деления.

Пусть k – ключ (тот, что необходимо хешировать), а N – максимально возможное число хеш-кодов. Тогда метод хеширования посредством деления будет заключаться во взятии остатка от деления k на N:

h(k)=k mod N, где mod – операция взятия остатка от деления.

Например, на вход подаются следующие ключи:

3, 6, 7, 15, 32, 43, 99, 100, 133, 158.

Определим N равным 10, из чего последует, что возможные значения хешей лежат в диапазоне 0…9. Используя данную функцию, получим следующие значения хеш-кодов:

h(3)=3, h(6)=6, h(7)=7, h(15)= 5, h(32)=2, h(42)=2, h(99)=9, h(100)=0, h(133)=3, h(158)=8.

На C++ программу, выполняющую хеширование методом деления можно записать так:

#include "stdafx.h"
#include <iostream>
using namespace std;
int HashFunction(int k)
{
return (k%10);
}
void main()
{
setlocale(LC_ALL, "Rus");
int key;
cout<<"Ключ > "; cin>>key;
cout<<"HashFunction("<<key<<")="<<HashFunction(key)<<endl;
system("pause>>void");
}

Во избежание большого числа коллизий рекомендуется выбирать N простым числом, и не рекомендуется степенью с основанием 2 и показателем m (2m). Вообще, по возможности, следует выбирать N, опираясь на значения входящих ключей. Так, например если все или большинство k=10m (m – натуральное число), то неудачным выбором будет N=10*m и N=10m.

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

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

h(k)=N*({k*A})

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

  • ( ) – скобки приоритета;
  • ⌊ ⌋ – скобки взятия целой части;
  • { } – скобки взятия дробной части.

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

От выбора A и N зависит то, насколько оптимальным окажется хеширование умножением на определенной последовательности. Не имея сведений о входящих ключах, в качестве N следует выбрать одну из степеней двойки, т. к. умножение на 2m равносильно сдвигу на 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++ с использованием оговоренных N и A:

#include "stdafx.h"
#include <iostream>
using namespace std;
int HashFunction(int k)
{
int N=13; double A=0.618033;
int h=N*fmod(k*A, 1);
return h;
}
void main()
{
setlocale(LC_ALL, "Rus");
int key;
cout<<"Ключ > "; cin>>key;
cout<<"HashFunction("<<key<<")="<<HashFunction(key)<<endl;
system("pause>>void");
}

 

Рейтинг
( Пока оценок нет )
Загрузка ...