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

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

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

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

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

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++ программу, выполняющую хеширование методом деления, можно записать так:

int HashFunction(int k)

{ return (k%10); }

void main()

{

int key;

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

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

}

 

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