HashMap1.8扩容源码详解
HashMap在1.8版本中的扩容机制相比1.7版本有了一些改进，主要体现在数组的容量扩展以及红黑树的引入。下面对HashMap 1.8版本中的扩容源码进行详细解析。
1. 扩容条件判断
在HashMap的源码中，扩容的条件主要包括两个：元素数量超过阈值（threshold）并且当前桶不为null。以下是HashMap中的判断条件：
int threshold = (int)(capacity * loadFactor);
if (size > threshold && null != table[i = (table.length << 1) - 1]) {
resize();
}
capacity：数组的容量，即table.length。loadFactor：负载因子，用于确定何时进行扩容。size：当前HashMap中元素的数量。threshold：扩容的阈值，当size大于threshold时触发扩容。table[i]：当前桶不为null表示此桶中已经存在元素。
2. 扩容操作
一旦判断需要扩容，就会调用resize()方法进行扩容。resize()方法中的关键操作主要有以下几步：
2.1 计算新的容量
int newCapacity = oldCapacity << 1;
通过将原容量左移一位，即乘以2，得到新的容量。这个操作是为了将数组的容量扩大一倍。
2.2 创建新的数组
Node<K,V>[] newTab = new Node[newCapacity];
根据新的容量创建一个新的Node数组，用于存储扩容后的键值对。
2.3 将元素重新分配到新数组
transfer(newTab, initHashSeedAsNeeded(newCapacity));
transfer()方法将元素重新分配到新数组中。initHashSeedAsNeeded()方法用于初始化哈希种子，以便在计算哈希值时使用。
2.4 将新数组赋值给原数组
table = newTab;
将新创建的数组赋值给table，完成扩容操作。
3. transfer()方法详解
transfer()方法是扩容的核心操作，它负责将原数组中的元素重新分配到新数组中。以下是transfer()方法的主要步骤：
3.1 遍历原数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// ...
}
}
遍历原数组的每个桶，处理每个桶中的链表或红黑树。
3.2 处理链表
if (null == e.next) {
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
// ...
} else {
// ...
}
- 如果链表中只有一个元素，直接将该元素放入新数组的相应位置。
- 如果链表已经转化为红黑树，调用相应的处理方法。
- 如果链表中有多个元素，采用分割链表的方式，将链表中的元素按照新的容量分别放入新数组的不同位置。
3.3 处理红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
如果链表已经转化为红黑树，调用split()方法对红黑树进行分裂，以确保在新数组中仍然保持红黑树结构。
4. 总结
HashMap 1.8版本中的扩容源码通过计算新的容量、创建新数组、重新分配元素等步骤实现了高效的扩容机制。引入红黑树使得在处理链表过长时能够更高效地进行查找操作。这些优化措施在实际应用中为HashMap提供了更好的性能表现。
评论区