HASH算法简单介绍

　　HASH算法概述:　　Hash，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩 ...

　　HASH算法概述:

　　Hash，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

　　HASH算法的一般用途:

　　HASH算法一般用于数据的校验.

　　HASH算法原理:读者可以直接把HASH算法当成一个映射f : A  B . 输入为A, 长度不固定. 输出为B, B的长度是定好的. HASH算法也只是一类算法的统称, HASH算法有很多种. 我们也可以规定自己的HASH算法. 比如如下:

　　规定:

　　A: 字节序列, 长度不定.

　　B: 一个字节.

　　f : B = ∑A[i] % 256 . (I = 0,1,2, … length-1)

　　以上就是一个非常简单的HASH算法. 它将输入字节序列的各个字节累加然后对256取模得到B字节.

　　我们用C语言来表达这个算法可以如下:

　　unsigned char get_hash(unsigned char * A, int A_len)

　　{

　　unsigned short B = 0;

　　int i = 0;

　　for(;i　　{

　　B += A[i];

　　B %= 256;

　　}

　　return (unsigned char)B;

　　}

　　有的朋友会说, 咦, 你这个C实现的算法和你说的怎么不一样, 你说的f明明是先全部累加再对256取模的, 你这里怎么每次都取了一次摸了? 其实是这样的, 我们这里这样做的目的是防止当先全部累加时unsigned char 类型的B发生溢出现象, 所以这里每次都模了一次, 而这样对算法也没有影响的.

　　因为根据数论知识, (A+B) % C = A%C + B%C .

　　我们再来看另外一个例子:

　　A: 一串字符串

　　B: 四个字节的DWORD值.

　　f: 所有字符累乘然后模以0xffffffff

　　C语言算法如下:

　　DWORD get_hash(char *str)

　　{

　　__int B = 1;

　　__int N = 0xffffffff+1;

　　int i = 0;

　　for(;i　　{

　　B *= (__int)str[i];

　　B %= N;

　　}

　　return (DWORD)B;

　　}

　　相信大家都能很轻松的看懂上面的算法, 也能完全理解HASH的原理及思想.

　　那么这一节的介绍就到这里, 接下来的几节我将会带领大家一起体验HASH算法在实战中的作用.