哈希冲突解决方法

1、开放定址法:已发生哈希冲突的哈希地址为自变量,通过某种哈希函数得到一个新的空闲的内存单元的方法。

(1)线性探查法:是指从发生哈希冲突的地址开始,依次探查下一个地址(当地址为m-1的哈希表表尾时候,下一个探查地址是表首地址0,),直到找到一个空闲单元为止(当m>n时候一定能找到一个空闲单元)

他的数学递推公式为:d0 = h(k),di  =((d(i-1)+1)%m

(2)平方探查法:设发生冲突的地址是d,则平方探查法的探查序列为:d+2^0,d+2^1,d+2^2.....

平方探查法的数学地推描述公式为:d0  = h(k),di = (di-1 + 2^i-1 )%m,

由于平方探查法的探查跨步很大,所以可避免出现堆积问题。

(3)伪随机数法:

2、链表法:

若没有哈希冲突,直接存放数据元素,若是出现了哈希冲突,则吧哈希冲突的数据另外存放在单链表中。

原文地址:https://www.cnblogs.com/yjds/p/8598917.html