Хэш-функции на основе деления

Пусть требуется для числа A получить значение хэш-функции. Предлагается в качестве хэш-функции использовать остаток от деления A на некоторое K

h(A)=A (mod K)

Если A имеет довольно большую длину (например, A – строка текста), то данный алгоритм применим и в этом случае. Будем далее остаток от деления обозначать через оператор %. Представим A как число в позиционной системе счисления

A=S_k=0^k<N r ^kc_k

где r=256 (в общем случае r – основание системы счисления, в которой представляется число A), c_k –значение k -ой цифры в представлении A (в нашем случае = код k -ого символа строки), N – количество знаков (цифр) в представлении A. Будем предполагать, что

K<r.

Легко увидеть, что

(r ^N-1 c_N-1 + r ^N-2 c_N-2)%K= (r ^N-2 ((r c_N-1 + c_N-2)%K))%K

Из чего сразу получаем, что

h(A)=(S_k=0^k<N r ^kc_k)%K = (S_k=0^k<N-1 r ^kd_k)%K,

где d_N-2=(r c_N-1 + c_N-2)%K, d_i = c_i (i<N-2).

Т.о. следующая подпрограмма вычисляет хэш-функцию на основе деления от строки текста

int hash(unsigned char *str, int K)

{unsigned short int p=0;

if(str[0]=='\0')return 0;

if(str[1]=='\0')return str[0]%K;

p=str[0];

while(str[1]!='\0')

{

p=(p<<8)|str[1];

p=p%K;

str++;

}

Return p;

}

Хэш-функции на основе умножения

Алгоритм вычисления хэш-функции, основывающийся на умножении, задается следующей формулой

h(A) = [M({AK/ R})]

здесь фигурные скобки являются оператором взятия дробной части, квадратные скобки являются оператором взятия целой части, R – размер машинного слова, в котором размещается A (например, если A размещается в целой 32-битной переменной, то R=2³²), K – некоторое число, взаимно простое с R. В качестве M часто выгодно брать M=2^m.

Алгоритм является обобщением алгоритма, основанного на делении. Действительно, пусть K есть некоторое приближение к R/S, M=S, то

h(A) = [M({AK/ R})] = [S({A / S})]» A%S

Практически, алгоритм сводится к следующему: ставится десятичная точка перед числом A, полученное число умножается на K, из результата берутся первые m бит, расположенных после десятичной точки (здесь под десятичной точкой имеется в виду разделитель целой и дробной части в позиционной системе отсчета).

В случае, когда A представляет собой строку текста, состоящую из n байт, то, опять же, A рассматривается как число в позиционной системе исчисления. В этом случае R=256 ⁿ.

Умножение можно производить `столбиком’, тогда для m£16 подпрограмма вычисления хэш-функции имеет следующий вид

int hashm(unsigned char *str, int K, int m)

{union ICHAR {unsigned int i; unsigned char c[4];}s,srez,sm;

int rez,l,i; l=strlen((char*)str); srez.i=s.i=sm.i=0;

for(i=l-1;i>=0;i--)

{

srez.c[0]=s.c[0]; //кладем младший байт из пред.знач.

s.i=0; s.c[0]=str[i];

s.i*=K; //умножаем K на очередную цифру

s.i+=sm.i; //добавляем запомненное

sm.c[0]=s.c[1];sm.c[1]=s.c[2];sm.c[2]=s.c[3];sm.c[3]=0;

srez.c[1]=s.c[0];

}

rez=srez.i>>(16-m); //извлекаем m бит после точки

Return rez;

}

Здесь мы ввели union ICHAR для того, чтобы иметь возможность обращаться к отдельным байтам целой переменной.В цикле мы умножаем K на каждый байт строки и добавляем к результату то, что осталось от переполнения в предыдущем умножении. При этом под переполнение отводится 3 старших байта переменной s, а под основную цифру – один младший байт. Результат переполнения хранится в переменной sm. Т.к. конечный результат может занимать до двух байт, приходится вводить дополнительную переменную srez, для хранения последних байт произведения str*K.

Дата добавления: 2015-10-30