Hash函数及其几种经典的查找算法

作者:课课家教育更新于： 2019-02-27 20:09:52

      在密码学当中，我们有学习很多种的密码，每一种的密码都有它的存在性以及特殊性，它们的一些算法结构以及用途都对网络的安全起着重要的作用。在这里，小编要讲的是密码学当中的Hash函数，我们可以通过学习几种经典的用于查找的Hash算法来学习Hash函数的部分知识。

      Hash，一般翻译做“散列”，也有直接音译为"哈希"的，HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码里，叫做HASH值。也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。实际上，Hash函数也可以指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。除此以外，Hash函数往往应用于查找上。

　　在信息安全方面，Hash算法的应用主要为文件校验、数字签名以及鉴权协议，这三个方面的具体解释为如下：

　　1.文件校验

　　奇偶校验和CRC校验是我们较为熟悉的校验算法，这2种校验不存在抗数据篡改的能力，在一定程度上它们能够检测并纠正数据传输中的信道误码，但不能防止对数据的恶意破坏。

　　2.数字签名

　　由于非对称算法的运算速度较慢，单向散列函数在数字签名协议中扮演了一个重要的角色。对Hash值，也称"数字摘要"进行数字签名，与对文件本身进行数字签名在统计上可以认为是等效的。而且这样的协议还有其他的优点。

　　3.鉴权协议

      现在的鉴权协议又被称为"挑战--认证模式：可以在传输信道被侦听，在不可被篡改的情况下是一种简单而安全的方法。

      几种经典的Hash算法

　　Hash函数应用的主要对象是数组(比如，字符串)，而其目标一般是一个int类型。按照这种的说明可以将Hash函数简单分为加法Hash、位运算Hash、乘法Hash、除法Hash、查表Hash、混合Hash这几种，这些算法在实际中的应用小编在下面来一一地介绍。

　　1.加法Hash

　　加法Hash的含义简单地讲就是将输入元素一个一个的加起来，然后构成最后的结果。它的标准构造为：

　　static int additiveHash(String key, int prime)

　　{

　　int hash, i;

　　for (hash = key.length(), i = 0; i < key.length(); i++)

　　hash += key.charAt(i);

　　return (hash % prime);

　　}

　　这里的prime指的是任意的质数，从这里可以看得出，结果的值域为[0,prime-1]。

　　2.位运算Hash

　　位运算Hash一般是通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。例如标准的旋转Hash的构造为：

　　static int rotatingHash(String key, int prime)

　　{

　　int hash, i;

　　for (hash=key.length(), i=0; i

　　hash = (hash<<4)^(hash>>28)^key.charAt(i);

　　return (hash % prime);

　　}

　　先移位，然后再进行各种位运算是这种类型Hash函数的主要特点。比如，以上的那段计算hash的代码还可以有如下几种变形：

　　1. hash = (hash<<5)^(hash>>27)^key.charAt(i);

　　2. hash += key.charAt(i);

　　hash += (hash << 10);

　　hash ^= (hash >> 6);

　　3. if((i&1) == 0)

　　{

　　hash ^= (hash<<7) ^ key.charAt(i) ^ (hash>>3);

　　}

　　else

　　{

　　hash ^= ~((hash<<11) ^ key.charAt(i) ^ (hash >>5));

　　}

　　4. hash += (hash<<5) + key.charAt(i);

　　5. hash = key.charAt(i) + (hash<<6) + (hash>>16) – hash;

　　6. hash ^= ((hash<<5) + key.charAt(i) + (hash>>2));

　　3.乘法Hash

　　乘法Hash是利用了乘法的不相关性(平方取头尾的随机数生成算法虽然效果不好，但它依旧是乘法的这种性质中最有名的)。比如，

　　static int bernstein(String key)

　　{

　　int hash = 0;

　　int i;

　　for (i=0; i

　　return hash;

　　}

      jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过，它使用的乘数是31。推荐的乘数还有：131,1313,13131,131313等等。

　　使用这种方式的著名Hash函数还有：

　　// 32位FNV算法

　　int M_SHIFT = 0;

　　public int FNVHash(byte[] data)

　　{

　　int hash = (int)2166136261L;

　　for(byte b : data)

　　hash = (hash * 16777619) ^ b;

　　if (M_SHIFT == 0)

　　return hash;

　　return (hash ^ (hash >> M_SHIFT)) & M_MASK;

　　}

　　以及改进的FNV算法：

　　public static int FNVHash1(String data)

　　{

　　final int p = 16777619;

　　int hash = (int)2166136261L;

　　for(int i=0;i

　　hash = (hash ^ data.charAt(i)) * p;

　　hash += hash << 13;

　　hash ^= hash >> 7;

　　hash += hash << 3;

　　hash ^= hash >> 17;

　　hash += hash << 5;

　　return hash;

　　}

　　除了乘以一个固定的数，常见的还有乘以一个不断改变的数，比如：

　　static int RSHash(String str)

　　{

　　int b = 378551;

　　int a = 63689;

　　int hash = 0;

　　for(int i = 0; i < str.length(); i++)

　　{

　　hash = hash * a + str.charAt(i);

　　a = a * b;

　　}

　　return (hash & 0x7FFFFFFF);

　　}

　　虽然Adler32算法的应用没有CRC32广泛，不过，它可能是乘法Hash里面最有名的一个了。关于它的介绍，大家可以去看RFC 1950规范。

　　4.除法Hash

　　除法同样也具有表面上看起来的不相关性，这个与乘法是一样的。但是为除法太慢，这种方式基本就找不到真正的应用。值得注意的是，我们在前面看到的hash的结果除以一个prime只是为了保证结果的范围这一个目的。假如我们不需要它限制一个范围的话，可以使用hash = hash ^ (hash>>10) ^ (hash>>20)这个代码来替代”hash%prime”。

　　5.查表Hash

　　CRC系列算法是查表Hash最有名的一个例子。即使CRC系列算法本身并不是查表，查表却是它的一种最快的实现方式。查表Hash中有名的例子有：Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。

　　6.混合Hash

　　混合Hash算法利用了以上各种方式。各种常见的Hash算法，比如MD5、Tiger都属于这个范围。它们一般很少在面向查找的Hash函数里面使用。

      Hash算法也是现代密码体系中的一个重要组成部分，在信息安全工程师这一课程当中也是非常重要的一个知识点，当然啦，在这门课程中对于Hash算法的讲解也比小编这里的讲解要详细得多，小编在这里主要是围绕着几种经典的用于查找的Hash算法来展开阐述。如果大家是想要学习更具体的关于Hash函数的知识的话，可以到课课家教育来学习信息安全工程师教程这门课程，里面关于Hash函数的内容是非常详细的，保证能让大家学得满意哦。