ArrayList源码及扩容机制分析

ArrayList 位于 java.util 包下


ArrayList 基本特点&＃xff1a;

1. 底层动态数组&＃xff0c;有序&＃xff0c;有下标&＃xff0c;可以重复
2. 线程不安全
3. 查询性能较快&＃xff0c;增删性能稍差


类的定义

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable


ArrayList实现List接口&＃xff0c;继承AbstractList抽象类&＃xff0c;另外实现RandomAccess (支持随机访问)、Cloneable(支持拷贝) 两个特殊接口

ArrayList类的变量

// 默认容量大小
private static final int DEFAULT_CAPACITY &＃61; 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA &＃61; {};
// 空数组。&＃xff08;用两个的目的是为了知道添加第一个元素时需要创建多大的空间&＃xff09;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA&＃61;{};
----------
// 真正存储ArrayList中的元素的数组
transient Object[] elementData;
// 存储ArrayList的大小&＃xff0c;注意不是elementData的长度
private int size;
-----------
// 数组的最大长度
private static final int MAX_ARRAY_SIZE &＃61; Integer.MAX_VALUE - 8;
// 修改次数, 每次add、remove它的值都会加1&＃xff08;这个属性是AbstractList中的&＃xff09;
protected transient int modCount &＃61; 0;


类的构造方法&＃xff1a;

// 无参
public ArrayList() {this.elementData &＃61; DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}


// 带初始长度参数的构造函数
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {// 初始长度参数大于0&＃xff0c;用此长度初始化创建元素数组this.elementData &＃61; new Object[initialCapacity];} else if (initialCapacity &＃61;&＃61; 0) {// 初始长度参数为0&＃xff0c;使用空数组this.elementData &＃61; EMPTY_ELEMENTDATA;} else {//传入参数 <0 抛IllegalArgumentException异常throw new IllegalArgumentException("Illegal Capacity: "&＃43;initialCapacity);}
}


// 参数为集合的 构造方法
public ArrayList(Collection<? extends E> c) {// 参数转数组&＃xff0c;并赋值给当前集合数组elementData &＃61; c.toArray();// 设置元素个数if ((size &＃61; elementData.length) !&＃61; 0) {// 不是Object数组就转为Object数组if (elementData.getClass() !&＃61; Object[].class)elementData &＃61; Arrays.copyOf(elementData, size, Object[].class);} else {// 参数中也没有元素时&＃xff0c;用空数组替换this.elementData &＃61; EMPTY_ELEMENTDATA;}
}


ArrayList中的常用方法&＃xff1a;

这些方法看名字大概就应该知道是干什么的了&＃xff0c;不再详细说明。

ArrayList的扩容机制&＃xff1a;

先来看一个方法&＃xff1a;

private void ensureExplicitCapacity(int minCapacity) {//　修改次数 &＃43; 1modCount&＃43;&＃43;;// 判断是否需要扩容if (minCapacity - elementData.length > 0)grow(minCapacity);
}


这个方法的作用是用来保证ArrayList的容量的。 在ArrayList每次添加操作时&＃xff0c;也就是说在每次执行add()、addAll() 方法时&＃xff0c;都会调用这个方法&＃xff0c;判断数组长度是否需要扩容。如果 添加后需要的长度 > 原来数组的长度&＃xff0c;就需要调用grow() 方法进行扩容。

ArrayList 的 grow() 扩容方法&＃xff1a;

private void grow(int minCapacity) {// 先获取 原数组的长度int oldCapacity &＃61; elementData.length;// 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的1.5倍int newCapacity &＃61; oldCapacity &＃43; (oldCapacity >> 1);if (newCapacity - minCapacity < 0)//如果新的数组容量小于需要的最小容量&＃xff0c;即假设新的数组容量是15&＃xff0c;最小需要16的容量&＃xff0c;则会将16赋予newCapacitynewCapacity &＃61; minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)/* * 变量 MAX_ARRAY_SIZE &＃61; 2147483639 [0x7ffffff7]* 如果 扩容后的新容量 大于 MAX_ARRAY_SIZE 则会使用hugeCapacity方法*/newCapacity &＃61; hugeCapacity(minCapacity);// 确定新数组的容量后&＃xff0c;将 原数组数据 copy 到新数组中 去elementData &＃61; Arrays.copyOf(elementData, newCapacity);}


通过上面的源码及注释可以看到&＃xff0c;ArrayList 扩容长度 一般为原数组长度的1.5倍。如果新数组长度 > 数组规定的最大容量时&＃xff0c;会调用 hugeCapacity&＃xff08;minCapacity&＃xff09; 方法。

ArrayList 的 hugeCapacity(minCapacity) 方法&＃xff1a;

// 传入参数为&＃xff1a; 添加操作执行后&＃xff0c;数组所需要的最小长度
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // 如果最小长度 <0&＃xff0c;抛出 内存溢出 错误throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?// 如果 需要的长度 > 最大数组容量 &＃xff0c; 就返回Integer 类型的最大值作为容量Integer.MAX_VALUE :// 否则 就 返回 数组最大容量 作为 新扩容后的 长度。MAX_ARRAY_SIZE;
}


当 grow&＃xff08;&＃xff09;方法中 计算出的新数组长度 >　数组最大长度　时&＃xff0c;调用该方法&＃xff0c;判断　操作后元素所需要的长度　是否　&＃xff1e;　数组最大长度&＃xff0c;如果大于&＃xff0c;就返回Integer 类型的最大值 作为新数组长度&＃xff0c;否则 仍然返回 数组最大长度 作为新数组长度。