ArrayList
在Java的集合框架中，ArrayList是一个非常常用的动态数组实现。了解其内部扩容机制对于我们编写的代码十分有益。
1. 介绍
ArrayList是java.util包下的一个类，它实现了动态数组的数据结构。相比于传统数组，ArrayList具有自动扩容的特性，可以根据需要动态地调整数组的大小。
2. 扩容机制
当ArrayList的元素数量接近或超过其当前容量时，就会触发扩容操作。ArrayList的扩容机制主要涉及以下几个关键参数：
- elementData： 用于存储实际元素的数组。
- size： 当前
ArrayList中元素的个数。 - DEFAULT_CAPACITY： 默认初始容量，一般为10。
- MAX_ARRAY_SIZE： 数组的最大容量，一般为
Integer.MAX_VALUE - 8。
2.1 扩容触发条件
扩容会在以下两种情况下触发：
-
添加元素时，size超过elementData的长度
-
使用带有指定初始容量的构造方法，并且该初始容量大于默认容量，也会触发扩容。
2.2 扩容操作过程
扩容的核心方法是 grow(int minCapacity)。下面是扩容的大致过程：
-
计算新容量：
新容量一般为原容量的 1.5 倍，即oldCapacity + (oldCapacity >> 1)。如果这个值仍然不足以容纳minCapacity个元素，那么新容量将被设置为minCapacity。 -
检查是否超过最大容量：
如果新容量超过了
MAX_ARRAY_SIZE，则新容量将被设置为Integer.MAX_VALUE。这是由于数组的最大长度是Integer.MAX_VALUE。 -
创建新数组并复制元素：
利用
Arrays.copyOf创建一个新的数组，并将原数组中的元素复制到新数组中。 -
替换原数组：
将
elementData指向新的数组。
2.3 扩容示例代码
以下是 ArrayList 扩容机制的示例代码：
private void grow(int minCapacity) {
// 获取原容量
int oldCapacity = elementData.length;
// 计算新容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 检查是否足够容纳minCapacity个元素
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) // 溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
总结
了解ArrayList的扩容机制是编写高性能Java代码的重要一环。通过深入了解其内部实现，我们能够更好地利用这一数据结构，避免不必要的扩容操作，提高程序的效率。
希望通过本文的介绍，大家能够对ArrayList的扩容机制有一个清晰而深入的理解～
