讨论：解决哈希冲突的几种方法

1. 什么是哈希

哈希是通过对数据进行再压缩，提高效率的一种解决方法。

2. 什么时候会产生哈希冲突

通过哈希函数产生的哈希值是有限的，当数据量比较大时经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。

3. 常见的哈希函数

1） 直接定制法

原理： 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点 ： 简单、均匀

缺点 ： 需要事先知道关键字的分布情况

场景： 适合查找比较小且连续的情况 。

2） 除留余数法

原理： 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m), 将关键码转换成哈希地址。

3） 平方取中法

原理： 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。

场景： 适合不知道关键字的分布，而位数又不是很大的情况 。

4） 折叠法

原理： 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

场景： 适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。

5） 随机数法

原理： 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key)。

6） 数学分析法

原理： 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

4. 产生哈希冲突的影响因素

• 装填因子（装填因子=数据总数 / 哈希表长）
• 哈希函数
• 处理冲突的方法

5. 解决哈希冲突的几种方法

方法1：开放定址方法（闭散列）

① 线性探测

原理 ：

• 插入 ： 按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。

• 删除 ： 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。因此线性探测采用标记的伪删除法来删除一个元素。

优点 ： 实现简单

缺点 ： 一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

② 再平方探测

原理 ： 按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

③ 伪随机探测

原理 ： 按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

方法2： 链式地址法

链式地址法，也叫开散列，Hashmap的哈希冲突解决方法。

原理 ：对于相同的值，使用链表进行连接。使用数组存储每一个链表。

优点 ：

• 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短。
• 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况。
• 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，节省空间。
• 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点 ：指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。

方法3： 建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。

方法4： 再哈希法

对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

6.几种解决哈希冲突方法的比较

开散列表：运用单链表存储方式，不产生堆积现象，但因为附加了指针域而增加了空间开销。

闭散列表：运用顺序表存储，存储效率较高，但容易产生堆积，查找不易实现，需要用到二次再查找。

溢出表：开、闭散列的结合运用，第一个顺序表存放类似指针域，第二个则存放溢出。