Hash冲突的解决办法
发布时间
阅读量：
阅读量
Hash冲突的解决办法（参考资料）
开放定址法
亦称开放定址法为再散列技术。当关键字key的哈希地址p=H（key）发生碰撞时，则以p为基础来计算新的哈希地址N。其中N = (H_1(key) + H_2(key) + ... + H_m(key)) \mod m
/** * 说明：N 代表计算出来的新的哈希地址 TableSize为表长
*/
N = (H(key) + di) % TableSize i=1,2,3.....n这里根据 di 的计算公式不同又可分为 线性探测 、平方探测 、双散列
- 线性探测
线性探测所采用的公式为
> di = i
>
>
>
>
>在哈希地址p起始点开始依次搜索空余的插槽以放置新元素到相应的插槽中
- 平方探测
平方探测所采用的公式为
> di = \pm i ^ 2
>
>
>
>
>也就是从哈希地址p出发, 乘以i的n次方, 寻找向前与向后的可用空槽位置, 将新元素存入相应的空槽中。值得注意的是, 在平方探测法中可以向前或向后寻找可用位置, 而在线性探测中则仅限于向后寻找可用位置
- 双散列
双散列所采用的公式为
> di = i * H_2(key)
>
>
>
>
>其中
> H_2(key)
>
>
>
>
>为新的hash函数
链地址法
将所有被映射至同一位置p的元素组织为同一个链表，并接着使该hash表中位于位置p的所有节点均指向该链表。这正是Java中的HashMap类采用的方式以解决哈希冲突问题。
建立一个公共溢出区域
这种方法的核心理念是：将哈希表划分为两个组成部分——基本表和溢出表。对于所有产生冲突的元素，则全部放入溢出表。
再哈希法：
采用多个哈希函数来处理数据冲突的情况：首先计算出一组数据对应的冲突哈希值后，则改用另一个哈希函数进行计算；继续使用新的哈希函数进行计算直至获得不同的结果。
全部评论 (0)
还没有任何评论哟~