如何解决哈希冲突？
1.什么是哈希冲突？
1.1哈希算法
哈希算法是将任意长度的输入通过散列算法变成固定长度的输出。
1.2哈希表
哈希表是通过key可以直接访问到key-value存储位置的数据结构，通过hash函数将key映射到表中的某个位置，来加快数据的查找。
1.3哈希冲突
不同的key可能计算出相同的hash值
哈希冲突就是当前key的计算出hash值找到的位置已经被占用了
2.解决哈希冲突
哈希冲突不能完全避免，只能尽可能降低发生冲突的概率。
2.1链地址法（拉链法）
HashMap中使用链地址法解决哈希冲突
扩展
HashMap如何解决哈希冲突？
- 使用链地址法来连接具有相同hash值的数据
将哈希表中发生哈希冲突的位置做成链表，将相同哈希值的key使用链表连接，数组中存储链表的头结点。
- 计算当前key的哈希地址若地址对应链表为空，将数据插入链表中，不为空执行2
- 计算key的下一个哈希地址，若改地址对应链表不为空，使用头插法or尾插法将元素插入链表
2.2开放定址法
ThreadLocal中使用开放定址法解决哈希冲突
使用key计算hash地址p=hash(key),若发生冲突（该位置不为空），继续计算 p1,p2…，直到找到不冲突的哈希地址。
2.2.1线性探测法
- 如果
hash(key) % m的位置已经被占用
尝试(hash(key) +1) % m的位置，若也被占用
尝试+2，+3…依次类推，直到找到空位置
2.2.2二次探测法
- 如果
hash(key) % m的位置已经被占用
尝试(hash(key) + 1^2) % m，若也被占用
尝试(hash(key) + -(1^2))% m…直到找到空位置
12,-12,22,-22,32,-32…
2.3再哈希法
发生冲突时，使用不同的哈希函数计算新的哈希地址，直到不再发生冲突。
-
第二个哈希函数的特点
- 不能和第一个哈希函数相同
- 不能输出0，会死循环
公式：Hi =
常量 - （key % 常量）
其中常量是小于数组容量的质数
2.4建立公共溢出区
为所有发生冲突的key，建立一个公共溢出区来存储。
- 在查找时，计算出key的哈希地址
- 先和基本表进行比对，如果相等查找成功
- 若不相等，去公共溢出表中查找。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/15589.html
