HashMap面试题精简

你的名字 2021-10-19 06:30 411阅读 0赞

**1. get方法流程**

1.  调用key的hashCode方法，将hashCode的低十六位与高十六位异或获得hash值
2.  用hash值与数组长度取模(由于数组长度为二的倍数，所以hashmap用效率更高的&位操作代替取模)获得数组下标
3.  遍历对应下标数组下链表，并与key做equls
4.  匹配成功返回value

**2.get方法时间复杂度**

*  根据get方法流程来看，只有第三步遍历链表对时间复杂度有影响，所有只有在链表长度为一时，hashmap的时间复杂度才为最好的O(1)

**3.put方法流程**

1.  判断键值对数组是否为空，如果为空就调用resiz方法进行初始化
2.  根据key计算出的hash值得到数组下标i，如果table\[i\]=为null，直接调用resize方法扩容并新建节点
3.  判断要插入key是否和table\[i\]的首元素key相同，相同则直接覆盖value
4.  判断table\[i\]的类型是否为treeNode，如果是就在红黑树中查找并插入，如果不是插入链表中
5.  遍历table\[i\]，如果发现相同key直接覆盖value，并判断长度是否大于8，大于就把链表转换为红黑树，直接在红黑树进行插入操作，否则进行链表插入
6.  插入成功，判断存在的键值对数量是否超过了最大容量，如果超过了就调用resize方法进行扩容

**4.HashMap扩容机制**

*  hashmap使用resize方法进行扩容，扩容流程如下：

1.  判断当前容量是否为0，如果大于0就进行2，否则进行3初始化
2.  先判断容量是否达到上限，如果超过将阈值设为Integer.MAX\_VALUE并直接返回oldTab，不进行扩容，没有超过就直接扩容两倍并判断当前容量是否大于等于默认容量16，如果是，就将阈值设为旧阈值的两倍并继续下面的流程
3.  判断当前阈值是否大于0，如果大于0新表的容量就等于旧的阈值，否则就赋予默认容量和默认阈值
4.  判断当前阈值是否为0，是的话就根据新表容量和负载因子赋予新的阈值并更新阈值
5.  根据新的容量构建新的哈希桶，并更新引用，然后将旧桶中的元素转移到新桶中，如果旧桶中只有一个元素，直接计算数组下标放入新桶中，否则进行6
6.  判断节点是否大于8，如果是就修剪红黑树（修剪主要分两部分，先分类、再根据元素个数决定是还原成链表还是精简一下元素仍保留红黑树结构），否则进行7
7.  由于扩容容量翻倍，所以原链表上的每个节点可能存放在原下标(low位)，也有可能存放在新下标(high位)，所以需要将当前节点的hash值与旧容量进行&位运算，判断应该存放的位置

**5.HashMap1.7和1.8扩容移动数据的区别**

1.  jdk1.7：根据扩容的新容量rehash并移动
2.  jdk1.8：由于新增容量是2的倍数，所以数据的位置肯定在原位置或者原位置+oldCap，也就是只需要查看hash值的新增bite为0还是1就可以判断位置了(concurrentHashMap并发扩容也是这个机制)

**6.HashMap的线程安全问题**  
HashMap的线程不安全问题主要在于put，jdk1.7会产生死循环问题，1.8则会导致数据被覆盖。而concurrentHashMap对于这个问题的解决方法是通过CAS和synchronize锁节点解决的

**7.HashMap初始化传入的容量参数就是实际分配的空间么？**

当然不是，实际分配的空间是比传入容量参数值大的最小2的次方，hashmap的构造函数中调用了tablesizefor方法计算实际分配空间

**8.为什么HashMap的大小总是2的n次方？**

我所了解的原因大概有两个：

1.  参考第五题分配实际空间
2.  可以使用效率更高的&位操作代替取模

**9.为什么loadfactory是0.75？**

*  jdk中的解释为：作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本
 *  StackOverFlow上有一个回答： 一个bucket空和非空的概率为0.5，通过牛顿二项式等数学计算，得到这个loadfactor的值为log（2），约等于0.693. 同回答者所说，可能小于0.75 大于等于log（2）的factor都能提供更好的性能

**参考：[HashMap的loadFactor为什么是0.75？][HashMap_loadFactor_0.75]**

[HashMap_loadFactor_0.75]: https://www.jianshu.com/p/64f6de3ffcc1