面试题分享之Java集合篇（二）

注意：文章若有错误的地方，欢迎评论区里面指正 🍭

系列文章目录

面试题分享之Java基础篇（一）
面试题分享之Java基础篇（二）
面试题分享之Java基础篇（三）

面试题分享之Java集合篇（一）

文章目录

系列文章目录

前言

一、说一下HashMap的底层实现原理

二、HashMap 的长度为什么是 2 的幂次方？

三、说说HashMap的put方法执行流程

四、说说HashMap的get方法执行过程？

五、说说HashMap的resize方法执行过程？

总结

前言

哈喽，小伙伴们，昨天我们见识了一些集合常见的面试题，如：List为什么实现RandomAccess接口、HashSet实现原理等等，废话不多说，今天继续来给大家分享几道Java集合的高频面试题。🌈

一、说一下HashMap的底层实现原理

JDK1.7：数组 + 链表
JDK1.8：数组 + （链表 | 红黑树）

HashMap底层主要基于数组和链表实现，采用Entry数组来存储key-value对（数组默认大小为16），每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，依次来解决Hash冲突的问题，因为HashMap是按照Key的hash值来计算Entry在HashMap中存储的位置的，如果hash值相同，而key内容不相等，那么就用链表来解决这种hash冲突。

不清楚什么是hash冲突或者不知道如何解决hash冲突的小伙伴可以参考：

面试题分享之Java基础篇（二）-CSDN博客

二、HashMap 的长度为什么是 2 的幂次方？

1、计算索引时效率更高：哈希函数通常将键的哈希码转换为一个整数。当这个整数对数组长度取模时，如果数组长度是 2 的幂次方，那么取模操作可以通过位运算来实现，具体是通过与操作（&）来完成。这种位运算通常比取模运算更快。如果数组长度是 2 的幂次方，那么取模运算可以简化为：index = hash & (length - 1);

2、扩容时重新计算索引效率更高：当 HashMap 需要扩容时（即创建一个新的、更大的数组），如果原始数组的长度是 2 的幂次方，那么新的数组长度通常是原始长度的两倍（也是 2 的幂次方）。这种翻倍的特性可以简化扩容过程中的重新哈希计算。

在扩容时，只需要简单地检查原始哈希码的某一位（通常是最高位），就可以确定键应该放到新数组的哪个位置。这种简单的位操作再次提高了性能。

3、减少哈希冲突：均匀的分布有助于减少哈希冲突，即减少多个键映射到同一个数组索引位置的情况。当哈希冲突减少时，查找、插入和删除操作的性能都会得到提高。

三、说说HashMap的put方法执行流程

计算key的hash值
如果桶（数组）数量为0，则初始化桶
如果key所在的桶没有元素，则直接插入
如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
如果找到了对应key的元素，则转后续流程（9）处理
如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
如果插入了元素，则数量加1并判断是否需要扩容

详细的HashMap方法执行过程可以参考：【JDK源码】HashMap源码分析（附常见面试题）

结合源码便于大家理解

java">public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*hash:键的hash值key：要插入的键value：要插入键的值onlyIfAbsent：如果为 true，则仅在映射中不存在指定键时才插入值。evit:用于后续操作（如可能的节点访问和插入后的操作）。*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//检查表是否为null，并且长度是否为0if ((tab = table) == null || (n = tab.length) == 0)//调用resize（）方法进行初始化，并获取新的表长度n = (tab = resize()).length;//使用 (n - 1) & hash 计算键在数组中的索引，这是位操作，用于替代模运算，以提高性能。if ((p = tab[i = (n - 1) & hash]) == null)//若索引为null，则在该位置创建新的结点tab[i] = newNode(hash, key, value, null);else {//否则，索引不为null，则出现hash冲突Node<K,V> e; K k;//检查当前节点的哈希值和键是否与要插入的相同if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//相同，则更新该节点的值（除非 onlyIfAbsent 为 true 并且旧值不为 null）。e = p;else if (p instanceof TreeNode)//如果当前节点是树节点（即已经树化），则调用 putTreeVal 方法在树中插入值。e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//否则（当前节点的哈希值和键是否与要插入的不同），遍历链表以查找是否存在具有相同哈希值和键的节点for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//如果没有找到，则在链表末尾添加新节点。p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//如果链表长度达到或超过 TREEIFY_THRESHOLD（默认为8），则调用 treeifyBin 方法将该链表转换为红黑树。treeifyBin(tab, hash);break;}//如果找到，则更新其值if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果找到了具有相同键的现有节点，则返回其旧值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//增加 modCount（用于 fail-fast 机制）++modCount;//如果 size 大于 threshold（加载因子与当前容量的乘积），则调用 resize() 方法重新调整 HashMap 的大小。if (++size > threshold)resize();//调用 afterNodeInsertion 方法执行可能的后续操作（如清理）。afterNodeInsertion(evict);//如果成功插入了新节点，则返回 null。return null;}

🧑‍💼面试官追问：你刚才提到了树化，能说一下什么时候树化吗？

必须满足两个条件：

链表长度超过树化阈值>8
数组容量>=64

🧑‍💼面试官继续追问：既然会树化，那什么时候会退化？

在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表
移除之前，remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

四、说说HashMap的get方法执行过程？

计算key的hash值
找到key所在的桶及其第一个元素
如果第一个元素的key等于待查找的key，直接返回
如果第一个元素是树节点就按树的方式来查找
否则就按链表方式查找
如果都没有，返回null

贴出源码，方便大家理解

java"> public V get(Object key) {Node<K,V> e;
//调用getNode（）方法，若果返回值为null，则get（）方法返回值也为null，否则为该key的值return (e = getNode(key)) == null ? null : e.value;}
//核心方法
final Node<K,V> getNode(Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;//检查哈希表是否为空或长度为0，计算索引并获取第一个节点，并存储在 first 中if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & (hash = hash(key))]) != null) {//如果第一个节点的哈希值和键与给定的哈希值和键相匹配，则返回该节点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;
//如果第一个节点不匹配，并且它有一个下一个节点（即链表不为空），则继续遍历链表if ((e = first.next) != null) {
//如果第一个节点是树节点（即已经树化），则调用 getTreeNode 方法在树中查找节点if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果不是树节点，则使用 do-while 循环遍历链表中的每个节点do {//如果某个节点的哈希值和键与给定的哈希值和键相匹配，则返回该节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

五、说说HashMap的resize方法执行过程？

直接上源代码：代码解释我就写在下方了

java">final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

1、定义和获取旧表信息:

Node<K,V>[] oldTab = table;：获取当前哈希表的引用。
int oldCap = (oldTab == null) ? 0 : oldTab.length;：计算旧表的容量（长度）。
int oldThr = threshold;：获取旧的阈值。当哈希表的大小达到这个阈值时，就会触发重新调整大小。

2、确定新的容量和阈值:

如果旧表的大小大于0，则：
如果旧表的大小已经达到最大容量（MAXIMUM_CAPACITY），则将阈值设置为Integer.MAX_VALUE并返回旧表（不再进行扩容）。
否则，如果新的容量（旧容量的两倍）小于最大容量且旧容量大于或等于默认初始容量（DEFAULT_INITIAL_CAPACITY），则新的阈值也设置为旧阈值的两倍。
如果旧表的阈值大于0，则新的容量设置为旧阈值（这可能是用于初始化HashMap时直接设置初始容量的情况）。
否则，使用默认的初始容量和加载因子来计算新的容量和阈值。

3、创建新的哈希表:

使用新的容量创建一个新的哈希表。
将新表的引用赋值给table。

4、迁移旧表中的数据:

遍历旧表的每一个位置。
如果该位置上有元素（即节点），则：
将该位置的引用设置为null（表示旧表中该位置不再有数据）。
如果该节点没有下一个节点（即它是一个链表中的单独节点），则直接将其放置在新表的适当位置。
如果该节点是一个TreeNode（即它是红黑树的一个节点），则调用其split方法来重新分配该树中的节点。
否则，这是一个链表，我们需要遍历它并重新分配其节点。这是通过维护两个链表（loHead和hiHead）来实现的，它们分别包含应放置在新表的低索引和高索引位置的节点。