Hash冲突解决方法

Hash碰撞冲突

当关键字值域远大于哈希表的长度，并且事先并不知道关键字的具体取值时。冲突就不免会发 生。另外，当关键字的实际取值大于哈希表的长度时，并且表中已装满了记录，若是插入一个新记录，不只发生冲突，并且还会发生溢出。所以，处理冲突和溢出是 哈希技术中的两个重要问题。web

方法

1.开放地址法
开放地址法公式：:H=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di是产生冲突的时候的增量序列。若是di的值可能为1,2,3,…,m-1,称线性探测再散列。
若是di取1，则每次冲突之后，向后移动1个位置。
若是di取值为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。
若是di取值可能为伪随机数列，称伪随机探测再散列。
2.再哈希法
当发生冲突时，使用第二个，第三个，哈希函数计算地址，直到无冲突时。缺点：计算时间增长。好比上面第一次按照姓首字母进行哈希，若是产生冲突能够按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突。
3.拉链法
将Hash值相同的键放入同一线性链表之中。HashMap就用这种方法来解决冲突。
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所创建的哈希表以下图所示：

4.创建一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。svg

拉链法的优缺点：

优势：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，所以平均查找长度较短；
②因为拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前没法肯定表长的状况；
③开放定址法为减小冲突，要求装填因子α较小，故当结点规模较大时会浪费不少空间。而拉链法中可取α≥1，且结点较大时，拉链法中增长的指针域可忽略不计，所以节省空间；
④在用拉链法构造的散列表中，删除结点的操做易于实现。只要简单地删去链表上相应的结点便可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，不然将截断在它以后填人散列表的同义词结点的查找路径。这是由于各类开放地址法中，空地址单元(即开放地址)都是查找失败的条件。所以在 用开放地址法处理冲突的散列表上执行删除操做，只能在被删结点上作删除标记，而不能真正删除结点。函数

缺点：
指针须要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可以使装填因子变小，这又减小了开放定址法中的冲突，从而提升平均查找速度。3d