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

Пусть 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.