扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: Java > Java集合高频面试题 > 25.HashMap是怎么解决哈希冲突的?

哈希冲突:hashMap在存储元素时会先计算key的hash值来确定存储位置,因为key的hash值计算最后有个对数组长度取余的操作,所以即使不同的key也可能计算出相同的hash值,这样就引起了hash冲突。hashMap的底层结构中的链表/红黑树就是用来解决这个问题的。

HashMap中的哈希冲突解决方式可以主要从三方面考虑(以JDK1.8为背景)

  • 拉链法HasMap中的数据结构为数组+链表/红黑树,当不同的key计算出的hash值相同时,就用链表的形式将Node结点(冲突的keykey对应的value)挂在数组后面。
  • hash函数key的hash值经过两次扰动,keyhashCode值与keyhashCode值的右移16位进行异或,然后对数组的长度取余(实际为了提高性能用的是位运算,但目的和取余一样),这样做可以让hashCode取值出的高位也参与运算,进一步降低hash冲突的概率,使得数据分布更平均。
  • 红黑树在拉链法中,如果hash冲突特别严重,则会导致数组上挂的链表长度过长,性能变差,因此在链表长度大于8时,将链表转化为红黑树,可以提高遍历链表的速度。

点击面试手册,获取本站面试手册PDF完整版