八股十问之Java集合HashMap
文章来源（公众号：八股bro，每天一篇经典面试题，还有大厂内推机会）
1、Map是什么？它的实现类有哪些？
Map是Java中一个集合接口，表示一个散列表，存储的内容是<Key, Value>，其中Key值不允许又重复。Map接口的实现类包括：HashMap，TreeMap，LinkedHashMap。
2、HashMap的底层数据结构是什么？
在JDK1.7时，HashMap的底层数据结构是 数组+链表。在JDK1.8时，HashMap的底层数据结构是 数组+链表+红黑树。
3、为什么HashMap中数据结构选择红黑树而不是平衡二叉树或者B+树？
如果选择平衡二叉树，插入删除操作后维持树平衡开销大于红黑树。如果选择B+树，会发生多个元素储存在一个树节点的情况，查找效率退化为链表查找。
4、HashMap中如何计算hash值？为什么这么做？
首先取key的hashcode值记为h，将h右移16为得到h1（即取h的32位中的高16位），将二者进行异或操作得到结果。异或操作可以看作是一次扰动函数，混合原始哈希码的高位和低位，增加低位可能性，减少碰撞可能性。
5、根据hash值如何计算数组中位置？数组长度为什么是2的次幂？
通过计算得到的hash和数组长度n-1进行与操作，得到在数组中的位置。数组长度n为2的m次幂时，n-1转换成二进制各位均为1，如15（1111）。因此与数组长度n-1的与操作，等同于取hash值的低m位，作为数组中的存储位置。
6、HashMap的扩容原理是什么？
- 计算新数组的容量
- 如果老数组容量超过最大容量，无需扩容。否则，新数组容量和新数组的阈值为老数组二倍。
- 如果第一次初始化，并且指定了初始容量，按照thereshold扩容，阈值为容量和加载因子乘积。
- 如果第一次初始化，没有指定容量，默认容量为16，阈值为12。
- 遍历老数组中元素，将其一一映射到新数组
- 如果该节点不存在下一节点，直接根据hash值计算映射到新数组位置。
- 如果该节点为红黑树节点，将红黑树进行拆分。
- 如果该节点为链表节点，将链表进行拆分。
-
7、在扩容过程中，如果节点后为链表，如何进行重新映射？
若旧数组容量为2的m次方，新数组容量为2的m+1次方，则在旧数组中的存储位置为hash值的低m位，在新数组中的存储位置为hash值的低m+1位。不难发现，两个存储位置转化为二进制后，仅有最高位是不同的。因此，在映射到新数组时，可以直接判断hash值第m+1位是否位0，如果为0，则该节点在新旧数组中存储位置不变，如果为1，则该节点在新数组的存储位置为旧数组存储位置+旧数组的容量。
8、HashMap中put操作的工作原理是什么？
- 判断数组是否为空，如果为空的话进行第一次扩容操作。
- 根据hash值，计算Node<key, value>应该存储在数组当中的位置，如果该位置为空，直接存储。
- 如果该位置不为空且和key相同，则直接覆盖。
- 如果该位置节点和key值不相同，判读该节点是否为红黑树中节点，如果是，在红黑树中插入新节点。
- 如果该位置节点和key值不相同，遍历后续链表，如果碰到相同key的节点，直接覆盖。否则，插入链表尾部。
- 链表长度大于8时，链表转换为红黑树。
- 数组长度大于阈值时，数组扩容。
9、HashMap中get操作的工作原理是什么？
- 根据key计算hash值，找到key在数组中的位置。
- 如果该位置为null，直接返回null。
- 通过equals方法判断该节点是否等于key，如果相等直接返回。
- 如果该节点为红黑树中节点，按照红黑树进行查找。
- 如果该节点为链表，按照链表进行查找。
10、HashMap是线程安全的吗？在什么场景下会发生问题？
HashMap是线程不安全的。当两个线程同时进行put操作时，恰好节点的hash值是相同的。其中，线程A判断该数组位置为空，可以直接插入，然后线程因为别的原因被挂起。线程B插入节点前，发现该位置为空，直接插入。紧接着，线程A被唤醒，此时不执行hash值判断，将直接覆盖线程B插入的节点。
文章来源（公众号：八股bro，每天一篇经典面试题，还有大厂内推机会）
#Java开发##Java##学习路径#
投递Momenta等公司7个岗位