哈希算法

哈希算法

1  简单介绍

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。

计算理论中，没有哈希函数的说法，只有单向函数的说法。所谓的单向函数，是一个复杂的定义，大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是：如果某个函数在给定输入的时候，很容易计算出其结果来；而当给定结果的时候，很难计算出输入来，这就是单项函数。各种加密函数都可以被认为是单向函数的逼近。哈希函数（或者散列函数）也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。

2  哈希方法学

哈希函数通常是由他们产生哈希值的方法来定义的，两种主要方法包括基于加法和乘法的散列和基于移位的散列。

2.1  基于加法和乘法的散列

这种方式是通过遍历数据中的元素然后每次对某个初始值进行加操作，其中加的值和这个数据的一个元素相关。通常这对某个元素值的计算要乘以一个素数。

2.2  基于移位的散列

和加法散列类似，基于移位的散列也要利用字符串数据中的每个元素，但是和加法不同的是，后者更多的而是进行位的移位操作。通常是结合了左移和右移，移的位数的也是一个素数。每个移位过程的结果只是增加了一些积累计算，最后移位的结果作为最终结果。

3  哈希函数的选择

哈希函数之间性能的比较可以通过两个方面：一方面数据分布，另一方面是哈希函数的效率。可以参考这两个方面标准，通过试错方法来找到满足我们要求的哈希函数。

3.1  数据分布

在实践中人们普遍认识到，一个完美哈希函数的哈希函数，能将一组数据的哈希值进行很好的分布到特定的数据集上，在一个特定的数据集上产生的的碰撞最少哈希的函数。

3.2  哈希函数的效率

哈希函数得到哈希值的效率也是参考标准，一个好的哈希函数在得到哈希值理论上非常的快、稳定并且是可确定的。通常哈希函数不可能达到O(1)的复杂度，但是哈希函数在字符串哈希的线性的搜索中确实是非常快的，并且通常哈希函数的对象是较小的主键标识符，这样整个过程应该是非常快的，并且在某种程度上是稳定的。

4  hash构造方法

哈希的构造方法包括直接寻址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等。

4.1  直接寻址法

取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）

4.2  数字分析法

分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

4.3  平方取中法

取关键字平方后的中间几位作为散列地址。

4.4  折叠法

将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

4.5  随机数法

选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。

4.6  除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

5  解决冲突方法

hash冲突在所难免，解决冲突是一个复杂问题。

5.1  冲突产生的因素

1、与散列函数有关，一个好的散列函数的值应尽可能平均分布。

2、与解决冲突的哈希冲突函数有关。

3、与负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。

5.2  解决冲突的办法

1、开放定址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。

2、拉链法：把所有同义词，即hash值相同的记录，用单链表连接起来。

6  应用领域

哈希是一个在现实世界中将数据映射到一个标识符的工具，下面是哈希函数的一些常用领域。

6.1  字符串哈希

在数据存储领域，主要是数据的索引和对容器的结构化支持，比如哈希表。

6.2  加密哈希

用于数据/用户核查和验证。一个强大的加密哈希函数很难从结果再得到原始数据。加密哈希函数用于哈希用户的密码，用来代替密码本身存储在某个服务器很难。加密哈希函数也被视为不可逆的压缩功能，能够代表一个信号标识的大量数据，可以非常有用的判断当前的数据是否已经被篡改(比如MD5)，也可以作为一个数据标志使用，以证明了通过其他手段加密文件的真实性。

6.3  几何哈希

这个哈希表用于在计算机视觉领域，为在任意场景分类物体的探测。最初选择的过程涉及一个地区或感兴趣的对象。几何散列包括各种汽车分类的重新检测中任意场景的目的，典型的例子。检测水平可以多种多样，从刚检测是否是车辆，到特定型号的车辆，在特定的某个车辆。

6.4  布隆过滤器

布隆过滤器（Bloom Filter）允许一个非常大范围内的值被一个小很多的内存锁代表。在计算机科学，这是众所周知的关联查询，并在关联容器的核心理念。布隆过滤器的实现通过多种不同的hash函数使用，也可通过允许一个特定值的存在有一定的误差概率会员查询结果的。布隆过滤器的保证提供的是，对于任何会员国的查询就永远不会再有假阴性，但有可能是假阳性。假阳性的概率可以通过改变控制为布隆过滤器，并通过不同的hash函数的数量所使用的表的大小。 

随后的研究工作集中在的散列函数和哈希表以及Mitzenmacher的布隆过滤器等领域。建议对这种结构，在数据被散列熵最实用的用法有助于哈希函数熵，这是理论成果上缔结一项最佳的布隆过滤器（一个提供给定一个最低的进一步导致假阳性的可能性表的大小或反之亦然）提供假阳性的概率定义用户可以建造最多也作为两种截然不同的两两独立的哈希散列函数已知功能，大大提高了查询效率的成员。

布隆过滤器通常存在于诸如拼写检查器，字符串匹配算法，网络数据包分析工具和网络/ Internet缓存的应用程序。

6.5  哈希算法在信息安全方面的应用
    主要体现在以下的三个方面

6.5.1  文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。

6.5.2  数字签名

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

6.5.3  鉴权协议

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

7  常用的哈希方法

下面hash函数的实现代码是用java语言。

7.1  RS

RSHash函数是从Robert Sedgwicks的 Algorithms in C一书中得到了。

public long RSHash(String str) {
    int b = 378551;
    int a = 63689;
    long hash = 0;
    for(int i = 0; i < str.length(); i++)
    {
        hash = hash * a + str.charAt(i);
        a = a * b;
    }
    return hash;
}

7.2  JS

Justin Sobel写的一个位操作的哈希函数。

public long JSHash(String str) {
    long hash = 1315423911;
    for(int i = 0; i < str.length(); i++)
    {
        hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
    }
    return hash;
}

7.3  PJW

该散列算法是基于贝尔实验室Peter J. Weinberger的研究，在Compilers一书中（原则，技术和工具），建议采用这个算法的散列函数的哈希方法。

public long PJWHash(String str) {
    long BitsInUnsignedInt = (long)(4 * 8);
    long ThreeQuarters = (long)((BitsInUnsignedInt * 3) / 4);
    long OneEighth = (long)(BitsInUnsignedInt / 8);
    long HighBits = (long)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
    long hash = 0;
    long test = 0;
    for(int i = 0; i < str.length(); i++)
    {
        hash = (hash << OneEighth) + str.charAt(i);
        if((test = hash & HighBits) != 0)
        {
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
    return hash;
}

7.4  ELF

由于在Unix的Extended Library Function被附带而得名的一种hash算法，它其实就是PJW Hash的变。

public long ELFHash(String str) {
    long hash = 0;
    long x = 0;
    for(int i = 0; i < str.length(); i++)
    {
        hash = (hash << 4) + str.charAt(i);
        if((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
        }
        hash &= ~x;
    }
    return hash;
}

7.5  BKDR

这个算法来自Brian Kernighan 和 Dennis Ritchie的 The C Programming Language。这是一个很简单的哈希算法，使用了一系列奇怪的数字，形式如31，3131，31...31，看上去和DJB算法很相似。(这个就是Java的字符串哈希函数)

public long BKDRHash(String str) {
    long seed = 131; // 31 131 1313 13131 131313 etc..
    long hash = 0;
    for(int i = 0; i < str.length(); i++)
    {
        hash = (hash * seed) + str.charAt(i);
    }
    return hash;
}

7.6  SDBM

这个算法在开源的SDBM中使用，似乎对很多不同类型的数据都能得到不错的分布。

public long SDBMHash(String str) {
    long hash = 0;
    for(int i = 0; i < str.length(); i++)
    {
        hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
}

7.7  DJB      

这个算法是Daniel J.Bernstein 教授发明的，是目前公布的最有效的哈希函数。

public long DJBHash(String str) {
    long hash = 5381;
    for(int i = 0; i < str.length(); i++)
    {
        hash = ((hash << 5) + hash) + str.charAt(i);
    }
    return hash;
}

7.8  DJB2

这个算法是Daniel J.Bernstein 教授发明的另一种好哈希函数。

public long DJB2Hash(String str) {
    long hash = 5381;
    for(int i = 0; i < str.length(); i++)
    {
        hash = hash * 33 ^ str.charAt(i);
    }
    return hash;
}

7.9  DEK

本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。

public long DEKHash(String str) {
    long hash = str.length();
    for(int i = 0; i < str.length(); i++)
    {
        hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
    }
    return hash;
}

7.10  AP

这是本文作者Arash Partow贡献的一个哈希函数，继承了上面以旋转以为和加操作。

public long APHash(String str) {
    long hash = 0xAAAAAAAA;
    for(int i = 0; i < str.length(); i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ str.charAt(i) * (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) + str.charAt(i) ^ (hash >> 5)));
        }
    }
    return hash;
}

7.11  FNV

Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。

public long FNVHash(String str) {
    long hash = 2166136261L;
    for(int i = 0; i < str.length(); i++)
    {
        hash *= 16777619;
        hash ^= str.charAt(i);
    }
    return hash;
}

8  常用hash函数测试

       测试数据参考icefireelf博客中的数据，博客链接在本文的最下方已注明。

8.1  对100000个由大小写字母与数字随机的ANSI字符串（无重复，每个字符串最大长度不超过64字符）进行散列

8.2  对100000个由任意UNICODE组成随机字符串（无重复，每个字符串最大长度不超过64字符）进行散列

8.3  对1000000个随机ANSI字符串（无重复，每个字符串最大长度不超过64字符）进行散列

参考连接：

http://blog.csdn.net/eaglex/article/details/6310727

http://blog.csdn.net/icefireelf/article/details/5796529