记录HashMap的七个面试题

avatar 2021年05月16日00:51:38 1 762 views

第一题:当key为null时,这次put操作,数据将被放入哪个桶位?为什么?

​ 0号桶位,这是因为HashMap计算桶位是根据你传入key的hashcode进行一个扰动函数或者说二次hash之后,然后根据路由寻址公式:

(table.length-1)&node.hash  或 node.hash % table.length 来确定桶位的

然后我们看源码,如果key是null,hash值为0的

 

 

第二题:为什么HashMap内部的散列表数组的长度一定是2的次方数?

首先,HashMap底层数组的长度是大于等于初始容量的2的n次方,如下图,我设置初始容量为20,实际数组的容量是32

然后为什么HashMap这么设计呢?主要是解决上面那个indexFor即确定元素放在哪个桶(数组元素)里。

n -1 & hash

如果n是2的次方,n-1的二进制,如16-1的二进制是 1111,32-1的二进制是 11111,与 hash(key) 的二进制进行与运算,能保证每一位都能有机会存储元素。

假如,n不是2的次方,比如n=15,15-1的二进制是 1110,1110 & hash 最终最低位永远都是0,1111位置永远不可能有数据,所以会浪费空间。

相反,只有n为2的次方的时候,才会保证低位都可能有数据

 

 

第三题:HashMap内部的散列表结构,什么时候初始化?以及初始化大小分别有哪几种情况?

​ 在第一次put数据的时候初始化,初始化分3种情况,对应4个构造函数,因为有一个是套用了另一个构造函数;

 

​ 第一种情况,你没有传入任何参数,也是我们常用的方式,这种方式下,HashMap会根据它设定的缺省默认值来对HashMap进行初始化,也就是数组长度为16,达到0.75的负载因子,也就是扩容阈值达到12的时候触发扩容;

 

​ 第二种情况你传入了一个map,这样的话,HashMap会根据你传入的Map,进行初始化,初始化之后的大小取决于你传入的map的大小;

 

​ 第三种情况就是根据你输入了HashMap的大小,以及你设置的负载因子去构建;构建好之后,如果是map,他会先把数据移动到HashMap中之后,才会在把数据添加进去,而其他的情况会在构建好HashMap之后把数据填充进去;

 

​ 第四种情况情况其实和上一种情况一样,这种是你只输入了HashMap的大小但是没有设置负载因子,负载因子就成了默认的缺省值也即是0.75;而这种情况是套用了上一个的构造方法来构造的,所以这两个其实也可以说是一个;

 

第四题:HashMap为什么需要扩容?谈谈你的理解

​ 为了提高查询效率(如果不扩容,只能任由链表一直增长或者树化)

 

​ 当HashMap中的数据足够多的时候,他的查询效率变得很低,甚至退化成O(n),哪怕是使用红黑树也无法使查询效率有较大幅度提高的时候,也就是HashMap中的碰撞达到了负载因子的时候,就会触发HashMap的扩容;

 

​ 扩容会扩容为之前的两倍,这样扩容之后,可以大幅提高查找效率,在不碰撞的情况下,查询还是O(1);

 

第五题:HashMap扩容算法,请你描述一下!

​ 主要分两种情况,一种是第一次初始化,一种是已经初始化过的;

 

​ 第一次初始化,他会根据你传入的值对HashMap进行初始化,初始化好之后,会把表返回,为什么是直接初始化呢?其实是因为调用构造方法的时候就已经对数据进行校验了,所以这个时候直接初始化就可以了;

​ 如果已经经过初始化的话,首先它会根据传入现在表的值进行分析,如果扩容之后的大小超过了最大限制,那么HashMap就不会扩容了,而是把触发扩容的条件提高的Int的最大值,然后把旧表返回;

而如果可以扩容,那么会扩容为之前HashMap的两倍;扩容完成之后,HashMap会把旧表中的数据填充到新表中,数据的填充有三种情况:

 

​ 1.只有一个值,这是最好的情况,因为可以直接计算位置,并添加就可以了,为什么要计算位置?因为现在数组扩容成之前的两倍了,如果高位是0,那么就是现在这个位置,如果高位是1,那就是另一个位置了,所以需要对数据的位置进行计算;

 

​ 2.链表,链表的话和之前一个值的时候差不多,但是链表要遍历链表,并把一个链表分成高位链和低位链,这样分配之后,就可以计算并把数据插入了;

 

​ 3.红黑树,会把数据先拿出来放到新表中,如果新表会不会有红黑树取决于数据放进去之后,而不是把整个红黑树移动过去;其实和链表也差不多,它也会先分成两个链,高位链和低位链,然后把链放到新表中;

然后补充说下,如果链表树化有2个条件:1个是数组大于等于64,另一个是链表大于等于8

 

 

第六题:HashMap内部散列表中存放的节点元素中的散列属性值,与你插入的key的hashcode是否一致,为什么?

​ 不一致,也不能一致,这是因为HashMap中的Hash空间大小不一定和本来Hash空间大小一致,如果直接使用key的hashcode的话,可能会导致hash碰撞加剧,这样会破坏HashMap的性能,也会改变他们原本的位置;而经过HashMap再次hash或者扰动之后的hash值,会使得添加进来的数据更加分散,更加的适合HashMap;

​ HashMap中的Hash值,是根据key的hashcode进行二次扰动,或者说是二次Hash后的一个值,这个值从某种意义上来说就是适合当前HashMap大小的一个合理的Hash值,经过HashMap的扰动之后,会让数据更加的散列,从而提高存储效率,提高性能,也提高了存储效率;

 

第七题:JDK1.8中HashMap中为什么引入红黑树?谈谈你的理解!

​ 当HashMap中的数据量足够多的时候,HashMap的链化会很严重,他的查找效率会非常低,甚至退化成O(n),

而引入红黑树,就是为了提高查找效率的;因为红黑树是一种自平衡的二叉查找树;

这是HashMap解决查询效率低下的一种方式,还有一种方式是通过负载因子控制的扩容,每次Hash碰撞达到负载因子的时候,就会触发扩容,扩容为之前的两倍,从而大幅提高查找的效率;理论上扩容最高可以提升2倍的效率,但实际很难出现;

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

avatar 登录者:匿名
可以匿名评论或者登录后台评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0