系列文章目录
- 面试题分享之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源码分析（附常见面试题）
结合源码便于大家理解
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，并且长度是否为0
if ((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 key
V 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
贴出源码，方便大家理解
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方法执行过程？
直接上源代码：代码解释我就写在下方了
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 threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = 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 order
Node<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;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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）来实现的，它们分别包含应放置在新表的低索引和高索引位置的节点。
内容比较多，大家在面试回答的时候不用回答的特别详细，简述大概流程就可以啦，一定要理解！！！
总结
好了，今天的分享就到这里，明天见🥳
