面试官超级喜欢问的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()判断，如果仍相等，则认为这两个元素一致。

面试官：好的，明天来上班。

阿巴阿巴：嗯嗯，再见！