HashMap的面试题你能回答几个？

答:数组。什么样的数组？答：Node[] table这样的。Node是什么？答：看下图：

也就是说这个数组每个元素都是个单向链表。

答:先得到key的hash值，再把这个hash值与length-1按位与（取余），得到table数组的下标。取出这个下标值的key，与传入的key比较，如果相同那就是这个了。如果不同呢，那就沿着这个单向链表向后找，直到找到或找到结束也找不到。

等等，这个hash值与length-1按位与就是等同取余么？为什么？

答:是的，几乎等同。因为这个length是有特点的，是2的n次方，length-1就是二进制全部为1。那么一个数的二进制按位与这些全为1的位，就会得到与这些全为1的位对齐的另一个数，如（15&6=1111&0110=6=0110）。这个按位与的结果数要么正好是取2的n次的余数（6%15=6=15&6），要么是比余数大的数（16%15=1=16&15+1,32%15=2=32&15+2）。 至于为什么这个length是2的n次方，下面的问题会回答 。贴下源码:

答：不是。那是什么呢？是比传入容量参数值大的最小的2的n次方，比如传入6，实际分配8。看下计算容量的源码。虽然这里源码计算的值只是threshold，而没有代码说明它是实际值，但本文最后的源码可以说明它就是实际值。

看到这个这个tableSizeFor方法,那么规则的1、2、4、8、16，是不是有点蒙。算法长成这样，是画画么？先了解下基础知识，一个整形由4个字节构成，那它转为二进制应该是32(4*8)位。但这是有符号的，其实正数和负数各占一半，也就是说各有2的31次方，最高位是符号位。我们这里是无符号操作就不用管这个符号了。上面的无符号右移16位就可以覆盖32位，16就是这么来的。其实这5个>>>(无符号右移)是为了把cap-1的最高二进制位及其后面的位都置成1。

最高二进制位是什么意思呢？ 一个整形转为二进制后，最左边的那位一定是1，前面补的0不能算哈，这个最左的1就是最高二进制位。

按上面的算法，第一次无符号右移1位再和原二进制按位或，至少把最左边和次最左边的两个位置为1了吧。那第二次再只移一位就没意义了，因为前两位都是1了，不需计算了，所以第二次是右移2位，这样就有4个1了。同理4位变8位，8位变16位，最后16位变32位，实际是只有31位（最前的是符号位）。这样就把cap-1变为一个从其二进制形式的最高位到0位全为1的二进制数了，而这个二进制数正好是比cap-1大一点的那个2的n次方的数-1（如2的3次方减1就是1000-1=0111=7）。

最后一行再+1就是2的n次方了(7+1=8=2的3次方).而第一行的n=cap-1,这也就是防止传入参数就是2的n次的情况（如8的二进制是1000），再把这个最高二进制位的后面都置成1，最后再加1就变成16了。这就不是与传入参数最接近的2的n次方了。

这里也就回答了为什么map.length是2的n次方了，后面扩容的机制会证明它总是保持着2的n次方。

答:在put时，添加的对象数量大于实际容量0.75倍（默认）的时候。看下源码put->putVal：

上面我们已经知道，HashMap的实际容量是2的n次方了。那么扩容也就是原来的容量*2，也就是扩到2的n+1次方。构造函数里有个加载因子（loadFactor),这个加载因子会改变threshold的值，默认的是0.75。改变过程如下:

从上面代码可以看出，这个扩容代码是相当精妙的，更多有意思的地方，请同学自行debug。

最后感谢海生和我讨论这些问题，打赏的钱分他1/3。

2020年6月24日，现在再去面试，还是有些程序员会问源码问题。像这篇文章这样的源码问题，平时不会用到，一年半载不看，全部忘完了。今天再看还是和以前一样再次赞叹。

今天产生了一个疑问：resize扩为原来的2倍(2的n+1) 次方，而设置值时的位置是按hash值与length位与的位置，那么扩容后，length(HashMap内数组长度)变了,那么值的位置就不正确了。如原来6%4位置是2,而现在 6%8是6,所以需要rehash,原来的值重新计算一遍。查看源码(resize方法)也是这样的:

 if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;