关于java:面试官超级喜欢问的HashMap

6次阅读

共计 2312 个字符，预计需要花费 6 分钟才能阅读完成。

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

<Center> 回去等告诉 </Center>

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

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

阿巴阿巴： HashMap 次要有 2 个重要办法，put/get，put 办法就是将元素无序的退出到 HashMap 中，也就是无奈保障元素的插入程序，get 办法就是获取 HashMap 中的元素。

阿巴阿巴： 此外还有一个扩容的办法，扩容阈值为以后容量 * 负载因子，每次扩容后的容量都是之前容量的 2 倍。

面试官： 很好，还有吗？

阿巴阿巴： 额 …… 如同容量必须是 2 的次幂，嗯 …. 额 …..

面试官： 好的，明天面试先到这里，你先 回去等告诉😈。

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

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

<Center> 当场发 offer</Center>

面试官： 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()判断，如果仍相等，则认为这两个元素统一。

面试官： 好的，今天来下班。

阿巴阿巴： 嗯嗯，再见！