首页 > 图灵资讯 > java面试题>正文

java基础面试题-详细介绍HashMap

2024-05-15 13:54:18

角度:数据结构+扩容情况+put查找的详细过程+哈希函数+容量为什么始终都是2^N,JDK1.7与1.8的区别。

 

参考:https://www.jianshu.com/p/9fe4cb316c05

数据结构:

HashMap在底层数据结构上采用了数组+链表+红黑树,通过散列映射来存储键值对数据。

扩容情况:

默认的负载因子是0.75,如果数组中已经存储的元素个数大于数组长度的75%,将会引发扩容操作。

【1】创建一个长度为原来数组长度两倍的新数组。

【2】1.7采用Entry的重新hash运算,1.8采用高于运算。

put操作步骤:

 

1、判断数组是否为空,为空进行初始化;

2、不为空,则计算 key的hash值,通过(n - 1) & hash计算应当存放在数组中的下标 index;

3、查看table[index] 是否存在数据,没有数据就构造一个Node节点存放在 table[index] 中;

4、存在数据,说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等,相等,用新的value替换原数据;

5、若不相等,判断当前节点类型是不是树型节点,如果是树型节点,创造树型节点插入红黑树中;

6、若不是红黑树,创建普通Node加入链表中;判断链表长度是否大于8,大于则将链表转换为红黑树;

7、插入完成之后判断当前节点数是否大于阈值,若大于,则扩容为原数组的二倍;

哈希函数:

通过hash函数(优质因子31循环累加)先拿到key的hashcode,是一个32位的值,然后让hashcode的高16位和低16位进行异或操作。该函数也称为扰动函数,做到尽可能降低hash碰撞,通过尾插法进行插入。

容量为什么始终都是2^N:

先做对数组的⻓度取模运算,得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。(n代表数组⻓度)。方便数组的扩容和增删改时的取模。

JDK1.7与1.8的区别:

JDK1.7 HashMap:

底层是 数组和链表 结合在⼀起使⽤也就是链表散列。如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。扩容翻转时顺序不一致使用头插法会产生死循环,导致cpu100%

JDK1.8 HashMap:

底层数据结构上采用了数组+链表+红黑树;当链表⻓度⼤于阈值(默认为 8-泊松分布),数组的⻓度大于 64时,链表将转化为红⿊树,以减少搜索时间。(解决了tomcat臭名昭著的url参数dos攻击问题)

上一篇 java基础面试题-List遍历快速和安全失败
下一篇 java基础面试题-ConcurrentHashMap

文章素材均来源于网络,如有侵权,请联系管理员删除。