0%

hash冲突

hash冲突

在使用hash表时肯定会遇到hash冲突的情况(看你设计的hashCode如何,设计的好,冲突就少一些)

但是冲突再少也会存在冲突,那就需要有处理冲突的方法,下面列出来一些处理hash冲突的方法

开放定址法

一旦发生冲突,就去寻找下一个空的散列地址,只要散列表足够大,总能找到空位

线性探测法

f(key) = (f(key)+di) mod m (di=1,2,3,…,m-1)

这种每次加一向后遍历查找空位的方式是线性探测法,但是这样对于存入和查找的效率都会很低

二次探测法

基于线性探测法进行改进,使得其可以双向探测,di=1^2^,2^2^,3^2^…q^2^(q<=m/2),使用平方运算来使的不让关键字都聚集在某一区域

再散列法

使用不同的散列函数来进行散列,一个冲突则使用另一个,不过这样做也增加了计算的时间

链地址法

将所有冲突的记录存储在一个单链表中,只是这样在查找时需要遍历单链表

公共溢出法

对于冲突的数据,都存放到另一个溢出表中,在查找时,先在散列表中进行查找,如果没有则去溢出表中顺序查找

欢迎关注我的其它发布渠道