ArrayList的扩容机制
1.是什么
ArrayList 是 Java 中的动态数组类，它的底层实现是一个可以自动扩展的数组。ArrayList 的扩容机制是其最重要的特性之一，因为它使得开发者无需关心数组的大小。以下是 ArrayList 扩容机制的详细解释：
1. 初始容量
当创建 ArrayList 时，默认情况下它会有一个初始容量。这个初始容量可以通过构造函数指定：
ArrayList()：默认容量是10。ArrayList(int initialCapacity)：使用用户指定的初始容量。
2. 添加元素时的扩容
当向 ArrayList 添加元素时，如果当前元素的数量超过了数组的容量，ArrayList 需要进行扩容。扩容的核心逻辑发生在 add() 方法中。扩容的步骤可以概括为：
- 检查当前容量：在添加元素前，
ArrayList会检查当前底层数组的容量是否足够容纳新的元素。 - 扩容逻辑：如果容量不足，则触发扩容机制。
ArrayList的扩容策略是按照 1.5 倍的方式进行扩容。具体来说，新容量 = 旧容量 + (旧容量 >> 1)，即新容量是旧容量的 1.5 倍。 - 复制数组：
ArrayList会创建一个新的数组，将原数组中的所有元素复制到新数组中，释放旧数组的内存。 - 添加元素：完成扩容后，元素被添加到新的数组中。
3. 源码分析
我们通过源码进一步了解 ArrayList 的扩容机制。这里的示例是基于 JDK 8 的 ArrayList 源码。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 添加元素
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果没有初始化数组，则将默认容量与需要的最小容量进行比较
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 扩容条件：当最小容量大于当前数组容量时
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 旧容量
int oldCapacity = elementData.length;
// 新容量 = 旧容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量仍然不足以容纳新元素，使用最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于最大允许的数组大小，使用最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 复制数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
4. 扩容示例
假设我们创建一个默认容量为 10 的 ArrayList，并向其中不断添加元素，扩容过程如下：
- 初始容量为
10。 - 当添加第
11个元素时，触发扩容。此时，旧容量为10，新容量为10 + 10/2 = 15，扩容到15。 - 当添加第
16个元素时，再次触发扩容。旧容量为15，新容量为15 + 15/2 = 22，扩容到22。 - 依次类推，后续每当容量不足时，
ArrayList按照1.5倍的速率扩容。
5. 扩容的性能影响
- 扩容代价：扩容的代价主要来自于数组的复制操作，尤其是在数组较大的情况下，复制操作会占用较多的时间。每次扩容时，
ArrayList需要分配新的数组并将旧数组的数据复制到新数组中。 - 避免频繁扩容：如果能够提前预估
ArrayList的大小，建议在创建时指定合适的初始容量（通过ArrayList(int initialCapacity)构造函数）。这样可以减少扩容次数，提高性能。
6. 总结
ArrayList 的扩容机制通过按 1.5 倍的方式增长容量来处理动态数据的添加，保证了使用的便捷性和一定的性能优化。但扩容过程中由于涉及数组复制，会引入一定的开销。因此，合理设置初始容量可以避免频繁的扩容操作，提升效率。
原文地址：https://blog.csdn.net/2401_83418369/article/details/142424285
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！