Hash简介

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

哈希表（Hash Table）是根据关键码值(Key value)而直接进行访问的数据结构，也叫散列表。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。不论哈希表中有多少数据，插入和删除只需要接近常量的时间即O(1)的时间级。

哈希表hashtable(key，value) 的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字(java中是int)，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。Hash表就可以结合两者的优点。

1. 哈希函数
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。
但另一方面，散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“哈希碰撞”也叫“哈希冲突”，这通常是两个不同长度的输入值，刻意计算出相同的输出值。输入一些数据计算出散列值，然后部分改变输入值，一个 具有强混淆特性的散列函数会产生一个完全不同的散列值。
一般来说，对任意一类的数据存在一个理论上完美的哈希函数。这个完美的哈希函数定义是没有发生任何碰撞，这意味着没有出现重复的散列值。在现实中它很难找到一个完美的哈希散列函数，而且这种完美函数的趋近变种在实际应用中的作用是相当有限的。在实践中人们普遍认识到，一个完美哈希函数的哈希函数，就是在一个特定的数据集上产生的的碰撞最少哈希的函数。

1.1 哈希方法学
哈希函数通常是由他们产生哈希值的方法来定义的，有两种主要的方法：
1)基于加法和乘法的散列
    这种方式是通过遍历数据中的元素然后每次对某个初始值进行加操作，其中加的值和这个数据的一个元素相关。通常这对某个元素值的计算要乘以一个素数。
2)基于移位的散列 
和加法散列类似，基于移位的散列也要利用字符串数据中的每个元素，但是和加法不同的是，后者更多的而是进行位的移位操作。通常是结合了左移和右移，移的位数的也是一个素数。每个移位过程的结果只是增加了一些积累计算，最后移位的结果作为最终结果。

1.2 哈希函数和素数
没有人可以证明素数和伪随机数生成器之间的关系，但是目前来说最好的结果使用了素数。伪随机数生成器现在是一个统计学上的东西，不是一个确定的实体，所以对其的分析只能对整个的结果有一些认识，而不能知道这些结果是怎么产生的。如果能进行更具体的研究，也许我们能更好的理解哪些数值比较有效，为什么素数比其 他数更有效，为什么有些素数就不行，如果能用可再现的证明来回答这些问题，那么我们就能设计出更好的伪随机数生成器，也可能得到更好的哈希函数。
围绕着哈希函数中的素数的使用的基本的概念是，利用一个素数来改变处理的哈希函数的状态值，而不是使用其他类型的数。处理这个词的意思就是对哈希值进行一些简单的操作，比如乘法和加法。这样得到的一个新的哈希值一定要在统计学上具有更高的熵，也就是说不能有位偏向。简单的说，当你用一个素数去乘一堆随机数的时候，得到的数在bit这个层次上是1的概率应该接近0.5。没有具体的证明这种不偏向的现象只出现在使用素数的情况下，这看上去只是一个自我宣称的直觉 上的理论，并被一些业内人士所遵循。
决定什么是正确的，甚至更好的方法和对散列素数的使用最好的组合仍然是一个很有黑色艺术。没有单一的方法可以宣称自己是最终的通用散列函数。最好的一所能做的就是通过试错演进和获得适当的散列算法，以满足其需要的统计分析方法。

1.3 常见的hash函数
可以从下面两个角度来选择哈希函数：（1）数据分布 （2）哈希函数的效率。
1)除法散列法
最直观的一种，公式：
      index = value % 16
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

2)平方散列法
求index是非常频繁的操作，而乘法的运算要比除法来得省时，所以我们考虑把除法换成乘法和一个位移操作。公式：
      index = (value * value) >> 28 
如果数值分配比较均匀的话这种方法能得到不错的结果。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

3)斐波那契（Fibonacci）散列法
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
1，对于16位整数而言，这个乘数是40503
2，对于32位整数而言，这个乘数是2654435769
3，对于64位整数而言，这个乘数是11400714819323198485
    这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
对我们常见的32位整数而言，公式：
  index = (value * 2654435769) >> 28

1.4 哈希冲突
当关键字值域远大于哈希表的长度，而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外，当关键字的实际取值大于哈希表的长度时，而且表中已装满了记录，如果插入一个新记录，不仅发生冲突，而且还会发生溢出。因此，处理冲突和溢出是哈希技术中的两个重要问题。这里主要讨论冲突。

1、开放定址法
  用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。
注意：
①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
  按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
（1）线性探查法(Linear Probing)
该方法的基本思想是：
    将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
        d，d+l，d+2，…，m-1，0，1，…，d-1
    即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
        hi=(h(key)+i)％m 0≤i≤m-1 //即di=i

用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。

（2）线性补偿探测法
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。

（3）随机探测
随机探测的基本思想是：
将 线性探测的步长从常数改为随机数，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避 免或减少堆聚。基于与线性探测法相同的理由，在线性补偿探测法和随机探测法中，删除一个记录后也要打上删除标记。

2、拉链法
（1）拉链法解决冲突的方法
拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。
按外链地址法所建立的哈希表如下图所示：


（2）拉链法的优点
这样就是前面说的结合了数组和链表的优点。与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④ 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

（3）拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间

1.5 应用
Hash算法在数据结构，加密，海量数据处理中有着广泛的应用。
Java中很多数据结构，比如HashTable, HashMap等都应用了hash算法。还有如果自定义对象重写了equals()方法则一定要重写hashCode方法，首先的一条是equals方法相等的对象一定要保证hashCode相等，然后就是hashCode的算法影响到键值的存放和查找，详细讨论可以参考: http://blog.csdn.net/michaellufhl/article/details/5833188
加密算法里也大量用到hash算法，比如MD5等，海量数据的查找也看好了hash的时间复杂度优点。

重写equals和hashcode可以参考：
http://zhangjunhd.blog.51cto.com/113473/71571/
http://www.cnblogs.com/happyPawpaw/p/3744971.html

参考资料：
http://blog.csdn.net/v_july_v/article/details/6256463
http://blog.csdn.net/mycomputerxiaomei/article/details/7641221
http://blog.csdn.net/lightty/article/details/11191971

评论

3 楼 足至迹留 2015-03-09  

mini188 写道

用MD5来解决碰撞是不是也是可行的呢？

个人觉得是可行的。虽然有传“山大”教授创造出了md5碰撞。但是看应用需要是否一定需要无碰撞的hash，否则md5本身的计算过程可能会影响性能。

2 楼 mini188 2015-03-06  

用MD5来解决碰撞是不是也是可行的呢？

1 楼 wwwcomy 2015-03-06  

写的不错~~ July大神貌似写过所有海量数据的万金油解法是先做Hash..