字符串哈希算法

以下内容为个人整理，因为自身水平的限制，所以出现一些错误或模糊不清的地方是很正常的现象，如果有人有缘看到本篇博客或其他本人所写的博客，请尽量谅解，可以通过各种方式联系本人，欢迎交流和指教。

第一节 简介

  哈希表作为一种常用的数据结构，是程序员必须要熟悉的知识模块，从最初数据结构课了解到哈希表到现在已经只剩下模糊的印象了，所以是时候重新复习一下这块的知识了。

  哈希表：通过映射函数计算一组映射的键码，将其存储到对应的集合位置，又称散列表。

  装填因子：a = n / m，即Key数目/表长，由装填因子来决定什么时候进行再散列。

第二节 再散列

  一般会在创建散列表时设置一个初始大小，表长或者Java的桶数(bucket)一般为预测元素个数的75%~150%，一般设置为素数以防止键的集聚。

  若散列表过满时，就需要再散列(rehashed)，即创建一个更大的散列表，将原有元素移到新的表中，丢弃原表，如装填因子为0.75，当集合已有元素超过75%时就会用双倍的大小进行再散列。

  根据散列表的结构可以联想到一个问题：如果不同的Key值计算出相同的结果怎么办？

  这种情况叫做哈希冲突或哈希碰撞，这种冲突根据哈希表的设计是无法避免的，因为空间是有限的，为了避免冲突而增大存储空间有些得不偿失了。只能尽量去避免冲突发生，比如尽量平均分配地址，略微改变键码会使计算结果大相径庭等等。

第三节 哈希冲突的解决方法

1.开放定址法

  当遇到哈希冲突时，依照增量规则向后取地址直到有未被占用地址为止。

  实例公式：Hash(key) = (Hash(key) + di) mod TableSize

  di表示增量序列，di不同的增长可分为：线性探测，二次探测，双散列探测。

  线性探测：di = i++ [1,2,3……，TableSize-1]，即依次按地址后取，弊端是元素积聚，没有均匀的分布元素，导致性能降低，多查询了越来越多的无关项。

  二次探测：di = (i++)^2 * (di / |di|) [1,-1,4,-4,9,-9……]，弊端是当剩余空间较少时，在还有空间的情况下会极有可能插入失败。

  双散列探测：di = (i++) * Hash2(key) [1H,2H,3H……]，Hash2(key) = p – (key mod p)，Hash2(key) = (key % 97) + 1，其中p为小于表长的任意素数。通过另外一个散列函数来减少积聚问题，第二个函数需要排出散列值为0的情况，计算的散列值要和表长互素。

  当装填因子越来越大时，不可避免会导致性能降低，所以会根据散列函数确定一个装填因子比例(一般要求a <= 0.7)，超过比例时需要进行表格扩张或减半。

2.链地址法/拉链法

  即将散列表每一个地址都对应一个链表，似乎链表会占用更多的空间，但实际使用中，因为装填因子的存在所以链地址法可能会更节省空间。

  通常情况下哈希表都非常高效，插入或查询都是O(1)，最差情况是集中映射到少量地址上，就会退化为链表查询，若被人通过Hash攻击的方式产生大量的碰撞，会导致本来高效的服务处理变得异常缓慢，可以通过限制表单提交长度等方法来防止此类攻击。低版本的Tomcat服务器存在此漏洞，较新版本中增加了对最大参数量的限制配置。

第四节 代码实现

  待抽空实现，博主是个又菜又忙的懒货~