Java ArrayList扩容机制原理深入分析
在 Java 中,ArrayList 是一种动态数组,它可以自动扩容以适应数据的增长。了解 ArrayList 扩容机制的原理,有助于我们更好地理解和使用 ArrayList,提高代码效率。
ArrayList 扩容机制
ArrayList 内部使用数组来存储元素,当向 ArrayList 中添加元素时,如果当前数组已满,就需要扩容。下面是 ArrayList 扩容的基本流程:
- 获取当前 ArrayList 的容量 capacity 和当前 ArrayList 已存储的元素个数 size;
- 判断当前数组是否已满,即
size == capacity
; - 如果数组已满,创建一个新的容量是原来容量 1.5 倍的数组,并将原数组中的元素复制到新数组中;
- 新数组成为 ArrayList 的内部数组。
下面是一个简单的示例:
import java.util.ArrayList;
public class Demo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(3);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
}
}
在上面的例子中,我们创建了一个容量为 3 的 ArrayList,并往里面添加了 6 个元素。在添加第 4 个元素时,由于数组已满,系统调用了 grow()
方法进行扩容。下面是 grow()
方法的源码:
private void grow(int minCapacity) {
// 获取当前 ArrayList 容量
int oldCapacity = elementData.length;
// 计算新容量大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量不足以满足最小容量需求,就使用最小容量作为新容量
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// 创建新的数组,并将原数组的元素复制到新数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
可以看到,在扩容时,系统会计算出新的容量大小,并将原数组的元素复制到新数组中,从而保证数据的顺序不变。需要注意的是,在计算新容量大小时,采用了位运算 >>
来代替除法,以提高代码效率。
另外,在调用 grow()
方法扩容时,如果我们向 ArrayList 中添加大量元素,扩容的次数可能很多,从而导致效率降低。因此,我们在使用 ArrayList 时,尽量预留一定的容量,避免频繁扩容。
下面是一个添加 100 000 个元素的例子,可以看到,在初始容量为 100 000 的情况下,并不会出现扩容的情况:
import java.util.ArrayList;
public class Demo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
list.add(i);
}
}
}
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java ArrayList扩容机制原理深入分析 - Python技术站