HashMap最全面试题 连环15问

目录

问1：JDK1.7与1.8中的HashMap底层数据结构有什么不同？

问2：何时会转为红黑树，何时会退化为链表？

问3：HashMap根据key查询的时间复杂度？

问4：为何一上来不树化？

问5：树化阈值为何是8？

问6：索引如何计算？hashCode都有了，为何还要提供hash()方法？数组容量为何是2的n次幂？

问7：容量不用2的n次幂行不行？

问8：介绍一下put方法流程，JDK7与JDK8有何不同？

问9：HashMap的扩容机制

问10：负载因子为何默认是0.75？

问11：多线程下1.7与1.8的HashMap会有什么问题？

问12：HashMap的key为null的时候存放在什么位置？

问13：HashMap底层是有序存放的吗？

问14：HashMap的key是否可以为null，作为key的对象有什么要求？

问15：String对象的hashCode()是如何设计的，为什么每次乘的都是31？

---

问1：JDK1.7与1.8中的HashMap底层数据结构有什么不同？

答：1.7是数组+链表，1.8是数组+（链表 | 红黑树）。

问2：何时会转为红黑树，何时会退化为链表？

答：当链表长度大于8并且数组容量大于等于64时，才会将链表转为红黑树。但如果仅仅是链表长度大于8，则会选择数组扩容的方式来减少链表长度。

退化情况1：在扩容如果拆分树时，树的元素个数<=6则会退化成链表。

退化情况2：remove树节点时，若root、root.left、root.right、root.left.left有一个为null，也会退化成链表。

问3：HashMap根据key查询的时间复杂度？

答：要看key是否发生hash冲突，如果没有发生hash冲突的情况下，时间复杂度为O1，也就是我只查询一次就查到了。如果发生了hash冲突，采用链表的形式存放，时间复杂度为On，也就是从头查询到尾部。如果发生了hash冲突，采用红黑树的形式存放，时间复杂度为Ologn。

问4：为何一上来不树化？

答：假如链表只有3个节点，你一上来就红黑树，难道就比链表的效率高吗？链表只需要从1查到3即可。而且红黑树占用内存也多，链表的数据结构是Node，红黑树底层数据结构是TreeNode，TreeNode的成员变量要比链表的Node多很多，因此对内存的占用也多。

问5：树化阈值为何是8？

答：红黑树用来避免DOS攻击，防止链表超长时性能下降，树化应当是偶然情况，大多数正常情况还是链表的性能高，而且hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现概率是0.00000006（一亿分之六），选择8就是为了让树化的几率足够小。

问6：索引如何计算？hashCode都有了，为何还要提供hash()方法？数组容量为何是2的n次幂？

答1：调用对象的hashCode方法，得到原始hash值，原始hash值还要调用hashmap中的hash方法进行二次hash，二次hash的结果再去跟我们哈希表中数组的容量（16）做（二次hash结果 & capacity - 1）位移运算，就可以得到索引（桶下标）。

答2：因为2的n次幂时哈希的分布性不是很好，所以二次hash为了让我们的数据分布的更加均匀一些，防止链表过长。

答3：数组容量是2的n次幂有两项好处，第一项好处是当计算索引时，如果是2的n次幂可以使用位移运算代替取模，效率更高；第二项好处是扩容时hash & 旧容量 = 0的元素留在原来位置，不等于0的元素就要移动到新的位置，新位置 = 旧位置 + 旧容量。

问7：容量不用2的n次幂行不行？

答：如果数组的容量不是2的n次幂，那上一问的3个答案都用不上了。例如Hashtable的容量就不是2的n次幂，并不能说哪种设计更优，应该是设计者综合了各种因素，最终选择了使用2的n次幂作为容量。

问8：介绍一下put方法流程，JDK7与JDK8有何不同？

答：流程：

① HashMap是懒惰创建数组的，首次使用才创建数组。

② 计算索引（桶下标）。

③ 如果桶下标没有占用，创建Node占位返回。

④ 如果桶下标已经有人占用

① 已经是TreeNode走红黑树的添加或更新逻辑。

② 是普通Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑。

⑤ 返回前检查容量是否超过阈值，一旦超过进行扩容。

不同点：

1、HashMap map = new HashMap(); //默认情况下，先不创建长度为16的数组

2、当首次调用map.put()时，再创建长度为16的数组。

3、1.7是头插法，1.8采用尾插法。

4、1.7是大于等于阈值（12）且没有空位时才扩容，而1.8是大于阈值就扩容。也就是说我已经有12个元素了，put第13个的时候对应的桶下标并没有任何元素在，所以1.7不会触发扩容。

5、当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置上的所有key-value对使用红黑树进行存储。

问9：HashMap的扩容机制

答：当HashMap中的元素个数超过数组长度 * 负载因子0.75时，就会进行数组扩容，也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16 X 0.75 = 12的时候，就把数组的大小扩展为2 X 16 = 32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap元素的个数，就能有效的提高HashMap的性能。

补充：当链表个数达到了8个，数组长度没有达到64，那也会触发扩容机制。

问10：负载因子为何默认是0.75？

答：

① 在空间占用与查询时间之间取得较好的平衡。

② 大于这个值，空间节省了，但链表就会比较长影响性能。

③ 小于这个值，冲突减少了，但扩容就会更加频繁，空间占用多。

问11：多线程下1.7与1.8的HashMap会有什么问题？

答：1.7会发生死链，1.7与1.8都会发生数据错乱。

JDK1.7采用头插法的危害：当扩容的时候，在里面有一个resize方法，它又调用了一个transfer方法（用来将原先table的元素全部移到newTable里面，重新计算hash，然后再重新根据hash分配位置）。把里面的一些Entry进行了一个rehash，在这个过程当中，可能会造成一个链表的循环。就可能在下一次Get的时候出现一个死循环的情况。

JDK1.8采用了尾插法解决了这么一个问题，因为采用了尾插法，没有改变数据插入的这么一个顺序。所以就不会造成一个链表循环的一个过程。

问12：HashMap的key为null的时候存放在什么位置？

答：存放到index为0位置。

问13：HashMap底层是有序存放的吗？

答：是无序的。

因为我们的哈希算法他是散列计算，比如说我们要存放key分别是1-10，但是这些key在计算存放到我们的数组index位置的时候有可能第一个key存放到index为2的位置，第二个key存放在index为1的位置。所以是无序的。如果想要实现有序的HashMap集合，我们可以使用LinkedHashMap集合，它底层才用的是双向链表形式来将我们的HashMap结构中的Entry进行通过双向链表来进行有序连接起来。

问14：HashMap的key是否可以为null，作为key的对象有什么要求？

答：HashMap的key可以为null，但Hashtable、TreeMap、ConcurrentHashMap的key都不能为null。一个对象要想作为HashMap的key需要重写hashCode()和equals()方法，并且key的内容不能修改（不可变），重写hashCode()是为了能有更好的分布性，提高查询性能。重写equals()方法是万一两个key计算出来的索引一样，得需要equals()进一步比较它们是不是相同的对象。

注意：如果hashCode相同，equals不一定相同。如果两个对象equals相同，hashCode肯定也相同。

问15：String对象的hashCode()是如何设计的，为什么每次乘的都是31？

答：