首页 > 面试官超级喜欢问的hashmap
头像
程序员面试鸭
发布于 2021-10-21 13:11
+ 关注

面试官超级喜欢问的hashmap

前言

阿巴阿巴约了面试,面试官问她对HashMap的理解。

回去等通知

面试官: HashMap了解吗?来谈谈你对这块的理解。

阿巴阿巴: 嗯嗯好,先从HashMap的结构开始吧,HashMap是一种散列表,由数组+链表+红黑树组成,初始默认的容量是16,负载因子是0.75,当链表上的元素大于8时链表进行红黑树化,当红黑树上元素减少到6时,红黑树会退化为链表。

阿巴阿巴: HashMap主要有2个重要方法,put/get,put方法就是将元素无序的加入到HashMap中,也就是无法保证元素的插入顺序,get方法就是获取HashMap中的元素。

阿巴阿巴: 此外还有一个扩容的方法,扩容阈值为当前容量 * 负载因子,每次扩容后的容量都是之前容量的2倍。

面试官: 很好,还有吗?

阿巴阿巴: 额......好像容量必须是2的次幂,嗯....额.....

面试官: 好的,今天面试先到这里,你先回去等通知😈。 

对HashMap理解不深,没有将知识点发散的思维。

这一年阿巴阿巴发奋图强,再次约面。


当场发offer

面试官: HashMap了解吗?来谈谈你对这块的理解。

阿巴阿巴: 嗯嗯好,先从HashMap的结构开始吧,HashMap是一种散列表,以Key/Value形式存储,Key和Value都可以为空,在JDK 1.7时是由数组+链表组成,JDK 1.8则由数组+链表+红黑树组成,这里主要介绍下JDK 1.8版本的HashMap,初始默认的容量是16,负载因子是0.75,当链表上的元素大于8 且数组容量大于64时链表进行红黑树化,当红黑树上元素减少到6时,红黑树会退化为链表。

阿巴阿巴: 数组的查询效率是O(1),链表的查询效率是O(N),红黑树的查询效率是O(logN)。

阿巴阿巴: 还有,HashMap的容量必须是2的次幂,在构造方法中传入的容量如果不是2的次幂,那么HashMap会调用tableSizeFor()方法来获取一个最接近传入容量且大于传入容量的2的次幂的值,比如传入的容量是17则tableSizeFor()会返回32。

面试官: 不错不错。

阿巴阿巴: HashMap空参数的构造方法创建出来的HashMap对象是不会初始化空间的,当使用空参构造方法创建出对象后,HashMap将在第一次插入元素时进行空间的初始化。

// 空参构造方法
public HashMap(){
this.loadFactor = DEFAULT_LOAD_FACTOR;
}

阿巴阿巴: HashMap主要有2个重要方法,put()/get(),put()方法就是将元素无序的加入到HashMap中,也就是无法保证元素的插入顺序,get方法就是获取HashMap中的元素。

阿巴阿巴: 当元素进行put时,首先要计算key的Hash值,为了更加分散,获取hash值后,HashMap会让hash值的高16位与hash进行异或。

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

阿巴阿巴: 然后判断HashMap有没有进行初始化,如果没有则进行初始化,再找到Key对应数组的位置,如果该位置没有元素则直接插入,如果有元素则判断是不是key与所在元素的key是不是一致,一致则新值替换旧值,如果不一致继续遍历这个节点下的链表或红黑树。

阿巴阿巴: 如果遍历过程中有元素的key与所在元素的key是一致的则新值替换旧值,否则将改元素加入到链表或红黑树中。

阿巴阿巴: get()方法首先计算key的hash值,然后找到hash对应数组中的位置的第一个元素,判断key是否一致,如果一致则返回否则继续查找这个元素下的链表或红黑树。

面试官: HashMap的扩容你了解吗?

阿巴阿巴: HashMap的扩容会调用resize()方法,扩容阈值为当前容量 * 负载因子,如果默认情况下hashMap容量为16,负载因子是0.75,则元素个数大于12就会触发扩容,resize()这个方***先判断HashMap是不是初始化了,扩容的时候会创建一个新的数组,然后旧数组中的元素进行搬移,JDK1.7 的HashMap在并发场景下扩容有可能会造成死循环,cpu飙升100%。

面试官: 嗯,那你知道为啥链表转红黑树的阈值是8吗?

阿巴阿巴: 哇,这个啊,这个在HashMap源码里有介绍,简单翻译就是:在使用分布良好的哈希码时,树是很少被使用的。理想情况下,随机哈希码遵循泊松分布,从上面给出的数据看,一个链表上有八个节点的概率为0.00000006 这个值要小于千万分之一。当这个阀值为8已经很小了,所以这就是阈值选8的原因。

面试官: 你刚有讲在put()/get()方法中要判断元素是否一致,那是如何判断元素一致的呢?

阿巴阿巴: 先判断hash值是不是相等,如果相等再进行equals()判断,如果仍相等,则认为这两个元素一致。

面试官: 好的,明天来上班。

阿巴阿巴: 嗯嗯,再见!

总结

对常用方法及过程进行了讲解,以及涉及到的一些细节进行了阐述,发散了一些知识点。面试不要慌记住下面六点即可。

  • 1、版本打好预防针(1.7.8版本)
  • 2、数据结构没法跑(数组 + 链表 + 红黑树)
  • 3、内置属性少不了(初始容量16、负载因子0.75、树化阈值8、树转链表阈值6、扩容大小2倍)
  • 4、put/get要记牢(把基本的put、get流程记牢)
  • 5、扩容方法不忘掉(扩容方法也要知道流程、并发环境下1.7版本扩容会造成死锁)
  • 6、边边角角都够到(对比了hash为啥还要对比equals方法,树化阈值为啥是8,key和value能为空吗,扩容一定是达到阈值才能扩容吗)

全部评论

(2) 回帖
加载中...
话题 回帖