HashMap面试常见问题

HashMap面试常见问题

1、底层数据结构，1.7与1.8有何不同？

1.7 数组 + 链表

1.8 数组 +（链表 | 红黑树）

2、为何要用红黑树，为何不直接树化，树化阈值为何是8，何时会树化，何时会退化为链表？

当发生哈希冲突时，新元素会添加到链表尾部，可能导致链表长度比较长，查找元素时就需要一次次比较，比较耗时。

如何解决链表长度过长问题呢？

①通过扩容可以减少链表长度

链表长度过长是可能发生了较多的哈希冲突，而减少哈希冲突的办法可以通过扩容数组长度来解决，数组长度足够长可以容纳更多的元素。数组默认长度为16，当元素个数超过3/4时数组会扩容（参见putVal方法），扩大到原来的2倍，还有当哈希冲突比较严重使链表长度大于8，数组长度还没有到64时也会扩容（参见treeifBin方法）。

②将链表转为红黑树

如果大量key的hash值一样，那么即使扩容这些元素还会在同一个链表中，这种情况通过扩容解就决不了链表长度过长问题。

再添加新的元素追加到链表尾部时，当链表长度大于8，并且数组长度大于等于64，链表会转成红黑树，红黑树查找元素的时间复杂度O(logN)，而链表查找元素的时间复杂度为O(N)。

红黑树用来避免Dos攻击，防止链表超长时性能下降，树化应当是偶然情况。hash值如果足够随机，则在哈希表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现的概率为0.00000006，选择8就是为了让树化概率足够小。

3、树退化成链表

①扩容时树拆分后的树元素个数小于等于6时，树退化成链表。

②remove树节点前，若root、root.left 、root.right、root.left.left 有一个为null，也会退化为链表。

4、索引如何计算？有了hashCode为何还要提供hash方法？

计算对象的hashCode()，再调用HashMap的hash()方法进行二次哈希，最后&(capaticy -1)得到索引。二次哈希是为了综合高位数据，让哈希分布更均匀，避免出现长链表。

5、容量为何是2的N次幂？

计算索引时，如果数组容量是2的N次幂可以使用位&运算代替取模，效率更高。同时，扩容时hash & oldCap == 0 的元素留在原来位置，否则新位置= 旧位置 + oldCap。

6、说说put方法流程，1.7和1.8有何不同？

①HashMap是惰性创建数组的，首次put元素才创建数组；

②计算索引（桶下标，元素在数组中的位置）；

③如果桶下标上没有元素，创建Node占位返回；

④如果桶下标上已经有元素了

1）该元素已经是TreeNode了，走红黑树的添加和更新逻辑；

2）是普通Node，走链表的添加和更新逻辑，如果链表长度超过树化阈值，走树化逻辑；

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

⑥不同点

1）元素插入链表时，1.7是头插法，1.8是尾插法；

2）1.7是大于等于阈值且没有空位时才扩容，而1.8是大于阈值就扩容；

3）1.8在扩容计算Node新位置时会优化。

7、加载因子为何默认为0.75？

1）在空间占用和查询时间之间取得较好的权衡；

2）大于这个值，比如是1，那么当容量等于数组长度，需要添加更多的元素才会扩容，空间节省了，但链表就会比较长，会影响性能；

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

8、多线程下 *** 作HashMap会有什么问题？

①扩容死链（1.7）；由于头插法，链表顺序颠倒，多线程下可能会出现环形链表，查找元素会出现死循环。

②数据错乱（1.7和1.8）。

千万不要在多线程环境下 *** 作HashMap。

9、key能否为null，作为key的对象有什么要求？

①HashMap的key可以为null，并且key为null的元素在数组中索引0位置；

②作为key的对象必须重写hashCode和equals方法，并且key的内容不能更改，否则放入HashMap中的元素可能找不到了。

以上问题虽然面试经常会问，也不用死记硬背，最好是能结合源码理解。

更多精彩内容请关注公众号 geekymv，喜欢请分享给更多的朋友哦」