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

中中

发布时间:17-11-2809:07

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)。 至于为什么这个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时,容量不够用的时候。因为每个元素都是一个单向链表,所以map里放的实际数量总是大于等于申请的空间。那么容量不够用就是实际存放的数量等于申请的空间大小的时候。看下源码put->putVal:

上面我们已经知道,HashMap的实际容量是2的n次方了。那么扩容也就是原来的容量*2,也就是扩到2的n+1次方。构造函数里有个加载因子(loadFactor),我曾经以为扩容就是扩这个数(默认0.75)+1倍,看到这里的源码才发现错了。这个加载因子只是计算下一个2的n次用的中间变量。默认的是0.75,那计算下一个2的n次方的基准值就是old*2*0.75,那么下一个2的n次方就是比这个基准值大的最少值(old*2)。如下图:

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

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

返回顶部