HashMap如何解决hash冲突？-Toy模板网

这篇具有很好参考价值的文章主要介绍了HashMap如何解决hash冲突？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

HashMap如何解决hash冲突？

这个问题我从3个方面来回答。

第一个方面,想要了解哈希冲突，首先我们要了解哈希算法和哈希表。
哈希算法把任意长度的输入通过散列算法变成固定长度的输出,这个输出结果就是一个散列值（用来记录元素的位置）
哈希表又叫做’散列表’,他是通过key直接访问到内存存储位置的数据结构。在具体的实现上，我们通过哈希函数把key映射到表中的某个位置,来获取这个位置的数据，从而区加快数据的查找。
第二个方面,哈希冲突是由于哈希算法被计算的数据是无限的,而计算后的结果范围是有限的，所以总会存在不同的数据计算后得到的值是一样的,那将会存在同一个位置,就会出现哈希冲突。比如 key = “name”，和key = “hobby” 计算后的哈希值一样。
第三个方面通常解决哈希冲突的方法有4种。
1.开放地址法：也称线性探测法,就是从发生冲突的那个位置,按照一定次序从Hash表中找到一个空闲的位置, 把发生冲突的元素存入到这个位置。而在java种ThreadLocal就用到了线性探测法,来解决Hash冲突。

2.链式寻址法：通过单向链表的方式来解决哈希冲突，Hashmap就是用了这个方法。(但会存在链表过长增加遍历时间)

3.再哈希法：key通过某个哈希函数计算得到冲突的时候,再次使用哈希函数的方法对key哈希一直运算直到不产生冲突为止（耗时间,性能会有影响）

4.建立公共溢出区:就是把Hash表分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放到溢出表中

补充：常见问题：如何扩容？
当容器中的元素个数大于默认长度16扩容因子0.75时,容器会调用方法resize()进行扩容,扩容为原有大小2的n次方

补充：在JDK1.8中HashMap通过链式寻址法以其红黑树来解决哈希冲突的，其中红黑树是为了优化哈希表的链表过长
导致遍历时间复杂度增加的问题。当链表长度大于8并且哈希表的容量大于64,再向链表中添加元素,会转化为红黑树。文章来源地址https://www.toymoban.com/news/detail-622732.html