转载

手撕HashMap,女朋友再也不用担心我的面试

HashMap是Map中最为常见的一个接口，也是每逢面试必问的一个问题。对于Java求职者来说是非常重要的。网上一些关于HashMap的面试文章，小编看过之后并不是非常满意。原因有两：1.劈里啪啦一大堆，先不说自己理不理解记不记得住，读者已经懵了？2.文章有些技术点理解不是很准确。我们应该怎么巧妙的回答这个问题，打动面试官。那么接下来和小编再撸一次HashMap,以下仅为参考。

面试官：你平常有了解HashMap吗？说一下HashMap的底层原理？

小生：当然了解。首先JDK1.7和JDK1.8是有区别的。JDK1.7的时候用的是数组+单链表的数据结构。JDK1.8的时候是数组+链表+红黑树的数据结构，当链表长度超过8（阈值）并且数据总量达到64，就会自动扩容把链表转化为红黑树。时间复杂度从O(n)转化为O(logN)，大大的提高了效率。（如果不是特别了解别给自己挖坑，点到为止即可，给自己留点余地，也别给面试官感觉你在背书）。

面试官：那么为什么把链表转化为红黑树的阈值是8，不是6或者是其他的呢？

小生：这个只能从底层源码说起，通过源码我们知道，如果大于等于6是链表，大于等于8转为树。我们可以通过泊松分布计算结果得出，当桶中结点为8时，出现的概率是最低的，因此常见的情况是桶中个数小于8的情况，此时的性能是和红黑树差不多的，所以没有必要转化成红黑树。（回答到这步面试官一般不会再追问下去，因为他未必懂）

以下是源码作者给出的解释：

* Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million
 *
复制代码

泊松分布：是一种统计与概率学里常见到的离散概率分布（有兴趣的同学可以上网了解）。

桶：hashmap的table数组

面试官：那你说说HashMap的put方法过程？

小生：嗯.....我想下。大概过程如下：

1.调用哈希函数获取key所对应的hash值，计算数组下标。

2.如果没有冲突，直接放入数组，如果出现冲突，则以链表的方式放在链表后面。

3.如果链表长度超过阈值，转为红黑树，如果链表长度低于6，红黑树转为链表。

4.如果结点的key存在，替换其value。

5.如果集合键值对大于12，调用resize方法进行数组扩容操作。

面试官：好，你刚刚说了，数组扩容，那么数组是怎么扩容的？

小生：（WC，这是要逼死我的节奏，还好留了一手）。这时候会创建一个新的数组，其容量为旧数组的两倍，然后重新计算旧数组中结点的存储位置。结点在新数组的位置有两种情况，原来下标位置或者原来下标加上旧数组的大小。

原文 https://juejin.im/post/5e858ef76fb9a03c8d49ea34