目录
一、哈希冲突
Hash冲突指的是在向Hash表中存数据时，首先要用Hash函数计算出该数据要存放的地址。但是在这个地址中已经有值存在，所以这个时候就发生了Hash冲突。也就是一句话：key值不同的元素可能会映象到哈希表的同一地址上。
二、 解决Hash冲突
2.1 开放地址法
一旦产生冲突，就去寻找下一个空的哈希地址。只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。其数学递推公式为
式中，i=1 , 2 , … , k(k<=m-1);m表示哈希表表长； 
为增量序列。
2.1.1 线性探测法
当=1 , 2 , … , m-1时称为线性探测法。其特点为：发生冲突时，顺序查看表中的下一个单元，当探测到表位地址m-1时，下一个探测地址是表首地址0，直到找出一个空闲单元（当表尾填满时一定能找到一个空闲单元）或查遍全表。
例如，哈希表表长为10，以关键字的末尾数字作为哈希地址，依次插入45、22、13、65、29、42、79、2共8个记录。若发生冲突则采用线性探测法。
1）首先先插入45,22,13,由于是在哈希表为空的时候插入，就直接插入在对应的地址上。（图a）
2） 在图a的基础上插入65,29,42,在插入42和65时，都发生了冲突，然后就都依次往下一个单元走，若有空闲单元则直接插入；若没有空闲单元，则继续往下一个单元走，直到找到空闲单元。（图b）
3） 在图b的基础上插入79,2，原理是跟上面一样的。但在插入79时，发生冲突，该位置为哈希表的表尾，所以就只能从哈希表的表首开始找空闲单元。（图c）
4） 在图c的基础上插入64，在插入64时，该位置已经被42给占了，但是这个位置原本不属于42的，像这种情况我们成为“堆积”。然后只能往下一个单元走，直到找到空闲单元。（图c）
2.1.2 二次探测法
当
，其中k<=m/2,m必须是一个可以表示成4k+3的质数时，称为二次探测法，又称平方探测法。二次探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到哈希表上的所有单元，但至少能探测到一半的单元。
例如，若有关键字集合{47,7,29,11,16,92,22,8,3}， 哈希表表长为11，哈希函数为H(k)=k%11,用二次探测法处理冲突，得到的哈希表如图2.2.2
为关键字寻找空的哈希地址时只有关键字3与线性探测法不同，H(3)=3,哈希地址发生冲突，有
,仍然冲突：，找到空的哈希地址，将3存入。
2.2 再哈希法
同时构造多个不同的哈希函数。
2.3 链地址法
将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
2.4 建立公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/177207.html原文链接：https://javaforall.net
