大家好,又见面了,我是你们的朋友全栈君。
本文探讨一下ArrayList的扩容过程
ArrayList底层是数组elementData,用于存放插入的数据。初始大小是0,当有数据插入时,默认大小DEFAULT_CAPACITY = 10。如果在创建ArrayList时指定了initialCapacity,则初始大小是ArrayList
1. 验证扩容的代码示例
从示例中可以看到,当添加元素时,如果元素个数+1> 当前数组长度 【size + 1 > elementData.length】时,进行扩容,扩容后的数组大小是: oldCapacity + (oldCapacity >> 1)
将旧数组内容通过Array.copyOf全部复制到新数组,此时新旧列表的size大小相同,但elementData的长度即容量不同
注意:扩容并不是严格的1.5倍,是扩容前的数组长度右移一位 + 扩容前的数组长度
public class SimpleTest {
public static void main(String[] args) {
ArrayList list = new ArrayList();
int size = 0;
for (int i = 0; i < 100; i++) {
list.add(i);
if(getCapacity(list)>size) {
System.out.println("capacity:"+getCapacity(list) + ",size:"+list.size());
size = getCapacity(list);
}
}
}
public static Integer getCapacity(ArrayList list) {
Integer length = null;
Class clazz = list.getClass();
Field field;
try {
field = clazz.getDeclaredField("elementData");
field.setAccessible(true);
Object[] object = (Object[]) field.get(list);
length = object.length;
return length;
} catch (Exception e) {
e.printStackTrace();
}
return length;
}
}
运行结果如下:
capacity:10,size:1
capacity:15,size:11
capacity:22,size:16
capacity:33,size:23
capacity:49,size:34
capacity:73,size:50
capacity:109,size:74
2. 扩容相关的源代码
public boolean add(E e) {
//调用了一ensureCapacityInternal方法,确保数组下标不越界
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量扩大到原容量的大约1.5倍,右移一位相当于原数值除以2,扩容并不是严格的1.5位
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
3. 为什么按大约1.5倍扩容
扩容因子的大小选择,需要考虑如下情况:
-
扩容容量不能太小,防止频繁扩容,频繁申请内存空间 + 数组频繁复制
-
扩容容量不能太大,需要充分利用空间,避免浪费过多空间;
为了能充分使用之前分配的内存空间,最好把增长因子设为 1<k<2.
k=1.5时,就能充分利用前面已经释放的空间。如果k >= 2,新容量刚刚好永远大于过去所有废弃的数组容量
并且充分利用移位操作(右移一位),减少浮点数或者运算时间和运算次数
详见参见: C++ STL 中 vector 内存用尽后, 为什么每次是 2 倍的增长, 而不是 3 倍或其他值?
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130890.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...