美文网首页
HashMap面试总结:

HashMap面试总结:

作者: 我要离开浪浪山 | 来源:发表于2023-03-20 07:16 被阅读0次

1、HashMap的几个重要知识点

  • HashMap是无序且不安全的数据结构。
  • HashMap 是以key–value对的形式存储的,key值是唯一的(可以为null),一个key只能对应着一个value,但是value是可以重复的。
  • HashMap 如果再次添加相同的key值,它会覆盖key值所对应的内容,这也是与HashSet不同的一点,Set通过add添加相同的对象,不会再添加到Set中去。
  • HashMap 提供了get方法,通过key值取对应的value值,但是HashSet只能通过迭代器Iterator来遍历数据,找对象。

2、JDK7与JDK8的HashMap区别

  • jdk8中添加了红黑树,当链表长度大于等于8的时候链表会变成红黑树
  • 链表新节点插入链表的顺序不同(jdk7是插入头结点,jdk8因为要把链表变为红 黑树所以采用插入尾节点)
  • hash算法简化 ( jdk8 )
  • resize的逻辑修改(jdk7会出现死循环,jdk8不会)

3、为什么HashMap的默认负载因子是0.75,而不是0.5或者是整数1呢?

答案有两种:

  • 答案1、阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制,他会保证容量(capacity)的值永远都是2的幂 为了保证负载因子x容量的结果是一个整数,这个值是0.75(4/3)比较合理,因为这个数和任何2的次幂乘积结果都是整数。
  • 答案2、理论上来讲,负载因子越大,导致哈希冲突的概率也就越大,负载因子越小,费的空间也就越大,这是一个无法避免的利弊关系,所以通过一个简单的数学推理,可以测算出这个数值在0.75左右是比较合理的。

4、HashMap的扩容机制

写数据之后会可能触发扩容,HashMap结构内,我记得有一个记录当前数据量的字段,这个数据量字段到达扩容阈值的话,它就会触发扩容的操作

5、为什么计算扩容后容量要采用位移运算呢,怎么不直接乘以2呢?

这个问题就比较简单了,因为cpu毕竟它不支持乘法运算,所有的乘法运算它最终都是再指令层面转化为了加法实现的,这样效率很低,如果用位运算的话对cpu来说就非常的简洁高效。

6、为啥HashMap中初始化大小为什么是16呢?

首先我们看hashMap的源码可知当新put一个数据时会进行计算位于table数组(也称为桶)中的下标:

int index =key.hashCode()&(length-1);

hahmap每次扩容都是以 2的整数次幂进行扩容

因为是将二进制进行按位于,(16-1) 是 1111,末位是1,这样也能保证计算后的index既可以是奇数也可以是偶数,并且只要传进来的key足够分散,均匀那么按位于的时候获得的index就会减少重复,这样也就减少了hash的碰撞以及hashMap的查询效率。

那么到了这里你也许会问? 那么就然16可以,是不是只要是2的整数次幂就可以呢?

答案是肯定的。那为什么不是8,4呢? 因为是8或者4的话很容易导致map扩容影响性能,如果分配的太大的话又会浪费资源,所以就使用16作为初始大小。

7、jdk8中HashMap为什么要引入红黑树?

其实主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题,因为链表结构的查询效率是非常低的,他不像数组,能通过索引快速找到想要的值,链表只能挨个遍历,当hash冲突非常严重的时候,链表过长的情况下,就会严重影响查询性能,本身散列列表最理想的查询效率为O(1),当时链化后链化特别严重,他就会导致查询退化为O(n)为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题,当链表长度>=8的时候链表就会变成红黑树,红黑树其实就是一颗特殊的二叉排序树嘛,这个时间复杂…反正就是要比列表强很多。

8、扩容后的新table数组,那老数组中的这个数据怎么迁移呢

迁移其实就是挨个桶位推进迁移,就是一个桶位一个桶位的处理,主要还是看当前处理桶位的数据状态把,这里也是分了大概四种状态:这四种的迁移规则都不太一样

  • (1)第一种就是数组下标下内容为空:这种情况下就没什么可说的,不用做什么处理。

  • ( 2)第二种情况就是数组下标下内容不为空,但它引用的node还没有链化:当slot它不为空,但它引用的node还没有链化的时候,说明这个槽位它没有发生过hash冲突,直接迁移就好了,根据新表的tableSize计算出他在新表的位置,然后存放进去就好了。

  • ( 3)第三种就是slot内储存了一个链化的node:当node中next字段它不为空,说明槽位发生过hash冲突,这个时候需要把当前槽位中保存的这个链表拆分成两个链表,分别是高位链和低位链

  • (4)第四种就是该槽位储存了一个红黑树的根节点TreeNode对象:

9、HashMap内部的bucket数组长度为什么一直都是2的整数次幂

答:这样做有两个好处,第一,可以通过(table.length - 1) & key.hash()这样的位运算快速寻址,第二,在HashMap扩容的时候可以保证同一个桶中的元素均匀地散列到新的桶中,具体一点就是同一个桶中的元素在扩容后一般留在原先的桶中,一般放到了新的桶中。

10、HashMap默认的bucket数组是多大

答:默认是16,即时指定的大小不是2的整数次幂,HashMap也会找到一个最近的2的整数次幂来初始化桶数组。

11、HashMap什么时候开辟bucket数组占用内存

答:在第一次put的时候调用resize方法

12、ashMap何时扩容?

答:当HashMap中的元素熟练超过阈值时,阈值计算方式是capacity * loadFactor,在HashMap中loadFactor是0.75

13、桶中的元素链表何时转换为红黑树,什么时候转回链表,为什么要这么设计?

答:当同一个桶中的元素数量大于等于8的时候元素中的链表转换为红黑树,反之,当桶中的元素数量小于等于6的时候又会转为链表,这样做的原因是避免红黑树和链表之间频繁转换,引起性能损耗。

14、Java 8中为什么要引进红黑树,是为了解决什么场景的问题?

答:引入红黑树是为了避免hash性能急剧下降,引起HashMap的读写性能急剧下降的场景,正常情况下,一般是不会用到红黑树的,在一些极端场景下,假如客户端实现了一个性能拙劣的hashCode方法,可以保证HashMap的读写复杂度不会低于O(lgN)

15、HashMap如何处理key为null的键值对?

答:放置在桶数组中下标为0的桶中


参考1:https://baijiahao.baidu.com/s?id=1697100671034890568&wfr=spider&for=pc
参考2:https://blog.csdn.net/fedorafrog/article/details/115478407

相关文章

网友评论

      本文标题:HashMap面试总结:

      本文链接:https://www.haomeiwen.com/subject/lifurdtx.html