解析HashMap resize()源码：数组扩容与元素迁移策略

本文档深入解析了HashMap类中的resize()方法，这是HashMap实现动态扩容的核心机制。resize()方法主要分为两个步骤：创建新数组和数据迁移。 首先，我们来看创建新数组的部分。HashMap使用的是一个大小为2的幂次方的数组，这是因为这样可以利用位操作来快速定位元素。如果旧数组`oldTab`的长度`oldCap`大于0，resize()会判断其是否达到扩容条件。如果旧数组的容量`oldCap`大于或等于`MAXIMUM_CAPACITY`（HashMap的预设最大容量，通常设置为1 << 30），则直接将其扩大一倍。否则，如果`oldCap`小于`MAXIMUM_CAPACITY`，则新数组`newCap`会被设置为`oldCap`的两倍，保证足够的空间以容纳更多的元素。同时，新数组的扩容阈值`newThr`也会相应调整，通常是新数组容量乘以负载因子（默认为0.75）。 接下来是数据迁移的过程。HashMap中的元素存储在一个个桶（Node数组）中，每个桶内部又使用链表或红黑树（从Java 8版本开始）来处理哈希冲突。当resize()方法执行时，需要将旧数组`oldTab`中的所有元素复制到新数组`newTab`。具体来说： 1. 对于旧数组中的每个元素（Node<K, V>），计算新的哈希值`e.hash`。然后使用位与运算`(e.hash & oldCap)`来确定元素在旧数组中的原始索引位置。这个操作符会将`e.hash`的结果与旧数组长度进行按位与，使得结果落在0到`oldCap - 1`的范围内。 2. 根据上述计算结果，元素被分类到两个链表：`lo`（低位区链表，当`(e.hash & oldCap) == 0`时）和`hi`（高位区链表，否则）。`lo`链表中的元素会在新数组中的位置保持不变，而`hi`链表中的元素则会移动到新数组相应偏移位置，即`e.hash`的计算结果加上旧数组长度。 3. 最后，遍历旧数组的每个桶，处理对应的`lo`和`hi`链表，将元素添加到新数组的新位置，并更新指向新位置的引用。 理解resize()方法的源码对于维护和优化HashMap性能至关重要，因为正确的扩容策略能确保在数据量增加时，查找、插入和删除操作的效率。通过掌握这个过程，开发者可以更好地理解和应对不同场景下的HashMap性能优化问题。