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

以下源码基于jdk1.8
1.HashMap用什么数据结构实现的?

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


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


2.HashMap的get过程是?

答:先得到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次方,下面的问题会回答 。贴下源码:


3.HashMap初始化传入的容量参数的值就是HashMap实际分配的空间么?

答:不是。那是什么呢?是比传入容量参数值大的最小的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次方。


4.HashMap扩容机制是什么,什么时候扩,每次扩多少?

答:在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;



文/程忠 浏览次数:0次   2017-11-28 09:05:21

相关阅读

微信扫描-捐赠支持
加入QQ群-技术交流

评论: