ArrayList源码深度解析
站长
· 阅读数 87
概述
ArrayList是一个顺序的容器，底层实际上是一个数组，可以动态扩容，所以使用起来非常方便，也是程序员非常爱用的一个容器，那它底层的扩容机制是怎么样的呢？是如何添加元素的呢？那我们基于jdk8来一探究竟。
ArrayList的基本使用可以参考ArrayList使用详解
类结构
以下是ArrayList的类结构图：
- RandomAccess 是一个标记接口，用于标记实现该接口的集合支持快速随机访问。
- Serializable 是一个标记接口，用于标记实现该接口的类可以序列化。
- Cloneable 是一个标记接口，用于标记实现该接口的类可以调用 clone 方法，否则会抛异常。
- Iterable 是一个遍历接口，内部提供了支持不同遍历方式的方法，比如顺序遍历迭代器、函数式的 foreach 遍历、并行遍历迭代器。
- Collection 是 java 集合体系的根接口，包含了通用的遍历、修改方法，例如 addAll、removeAll。
- AbstractCollection 是一个抽象类，重写了 Collection 中最基础的方法，减少具体集合类的实现成本，比如 contains、isEmpty、toArray，iterator，但是 add 等需要具体集合类自我实现。
- List 是 java 有序集合的基础接口，除了 Collection 的方法，还有支持倒序遍历的 listIterator 方法、子列表 subList 方法，另外重写 spliterator 方法的实现。
- AbstractList 是一个抽象类，重写了 List 的大部分方法，作用跟 AbstractCollection 类似。
核心机制
我们先了解下ArrayList的一些核心机制，然后通过源码的角度来学生和验证这些核心机制，加强了解。
扩容机制
- ArrayList的底层实现就是一个数组，但我们知道创建数组的时候长度是固定的，所以必须要进行自动扩容。
- 每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。
- 数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。
FailFast机制
FailFast机制也叫做快速失败机制，它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
通过记录ArrayList容器的modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
源码解析
关键成员变量
/**
* 默认的容量为10，也就是一开始创建数组的长度
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 有参构造缺省空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 无参构造缺省空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 数组的元素，不是private类型，主要是为了方便内部类的访问
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 数组元素的个数
*
* @serial
*/
private int size;
/**
* 数组的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
这里面关键的是elmentData属性，是一个数组，存储Arraylist增改删的元素，印证了ArrayList底层就是一个数组。
- 为什么数组最大容量是Integer.MAX_VALUE - 8，而不是Integer.MAX_VALUE？
可以查看源码的注释，有些虚拟机在数组中保留了一些头信息。避免内存溢出。
- 为什么定义了两个空数组？
主要是为了优化处理，我们可以看到他们是static类型，是被类共享的。如果一个应用中有很多这样ArrayList空实例的话，就会有很多的空数组，无疑是为了优化性能，所有ArrayList空实例都指向同一个空数组。两者都是用来减少空数组的创建，所有空ArrayList都共享空数组。两者的区别主要是用来起区分作用，针对有参无参的构造在扩容时做区分走不同的扩容逻辑，优化性能。
- elementData为什么定义成transient？这样能序列化吗？
Java中transient关键字的作用，简单地说，就是让某些被修饰的成员属性变量不被序列化。有了transient关键字声明，则这个变量不会参与序列化操作，即使所在类实现了Serializable接口，反序列化后该变量为空值。
实际上ArrayList在序列化的时候会调用writeObject()方法，将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。
而不是通过elementData来序列化，主要原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。
构造方法
- 无参构造方法ArrayList()
// 创建一个容量为10的ArrayList
public ArrayList() {
// 将elementData元素数组初始化为空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 有参构造方法 ArrayList(int)
/**
* 构造一个具有指定初始容量的列表
*
* @param initialCapacity: 初始化数组的值
*/
public ArrayList(int initialCapacity) {
//如果初始化的值大于0，则给定elementData一个长度为initialCapacity的数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { // 如果初始化的值等于0，则初始化为空数组
this.elementData = EMPTY_ELEMENTDATA;
} else { //否则（小于0的情况）抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
- 有参构造方法 ArrayList(Collection<? extends E> c)
//构造一个指定元素的集合
public ArrayList(Collection<? extends E> c) {
// 将集合转换为数组并赋值给elementData
elementData = c.toArray();
// 如果集合的大小不为0
if ((size = elementData.length) != 0) {
// 如果转换后的数组不是泛型(object)，则需要用Arrays的工具转换一下为object数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else { // 否则初始化elementData为一个空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
关键方法
- add(E e) 方法
非常重要的一个方法，深入学习这个方法基本就了解ArrayList的一些核心机制。
// 往数组中添加一个元素
public boolean add(E e) {
// 确定内部数组容量是否够用,如果不够用需要进行扩容处理，就是在这个方法中
//size是元素数组中数据的个数，因为要添加一个元素，所以size+1
//先判断size+1的这个个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将数组size++索引的位置设置为元素e
elementData[size++] = e;
return true;
}
// 容量处理的中间方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算ArrayList的容量大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断数组是不是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 如果是空数组(此时minCapacity = 0 + 1 = 1)，和默认的DEFAULT_CAPACITY=10比较，返回大的那个数
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 返回容量
return minCapacity;
}
// 用于检查容量以及扩容操作
private void ensureExplicitCapacity(int minCapacity) {
// 修改次数记录+1 在父类AbstractList中定义了一个int型的属性：modCount，记录了ArrayList修改的次数
// 主要是用来在并发修改的时候快速失败，提高性能
modCount++;
// 判断数组是否够用，如果不够用，则自动扩容
// 1、当初始化的集合为空数组时，此时minCapacity是10，而elementData的长度为0，所以需要扩容
// 2、当初始化的集合不为空时，也就是给定了大小，或已经初始化了元素，此时的minCapacity = 实际数组个数+1，此时判断集合不够用，也需要进行扩容，否则元素会溢出
if (minCapacity - elementData.length > 0)
// 扩容处理
grow(minCapacity);
}
// 扩容逻辑
private void grow(int minCapacity) {
//元素数组的实际长度(即扩充前的数组大小)
int oldCapacity = elementData.length;
//新的容量，扩容1.5倍赋值给newCapacity( >>为右移运算符，相当于除以2 即oldCapacity/2 )
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果初始化为空的情况，则将数组扩容为10，此时才是真正初始化元素数组elementData大小为10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果1.5倍的数组大小超过了集合的最大长度，则调用hugeCapacity方法，重新计算，也就是给定最大的集合长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 已经确定了大小，就将元素copy到elementData元素数组中~~
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 内存溢出判断
if (minCapacity < 0)
throw new OutOfMemoryError();
// 这里的逻辑为：如果需要扩容的大小比数组的最大值都大，就返回Integer,MAX_VALUE(int最大值),否则返回集合的最大值(int最大值-8)
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- 新增时，如果ArrayList容器的size+1 大于数组的长度，则需要进行扩容
- 扩容底层相当于数组的拷贝操作，将老的数组拷贝到新的数组中，这个过程其实比较消耗性能，所以一开始设置一个合理的数量显得非常重要，尽量避免出现扩容的情况。
2.add(E e) 方法
需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
/**
* 增加元素到指定下标
*
* @param index 下标
* @param element 元素
*/
public void add(int index, E element) {
// 参数校验，判断是不是存在越界
rangeCheckForAdd(index);
// 此方法不再赘述
ensureCapacityInternal(size + 1);
// 拷贝数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将指定元素覆盖到指定下标
elementData[index] = element;
// 长度size + 1
size++;
}
/**
* 适用于add 和 addAll的校验方法
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- boolean remove(Object o)
根据指定元素删除列表中的元素
// 根据元素o进行删除
public boolean remove(Object o) {
// 如果o等于空
if (o == null) {
for (int index = 0; index < size; index++)
// 如果遇到的第一个是null的元素，快速进行删除，因为arraylist可以存储null
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 比较对象的equals方法
// 因此类型变量E对应的类注意重写equlas方法
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 根据下标删除元素
private void fastRemove(int index) {
// 容器修改次数++
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
// 将elemenData中index+1及其后面的元素都向前移动一个下标
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 根据上一步的操作, size-1位置的对象向前移动了一个下标
// 如果没有elementData[--size]==null，可能会导致内存泄漏
// 试想，ArrayList被add了100个对象，然后被remove了100次。按照GC的机制来说，100个对象应该可以被GC掉（假设没有对象对象），但是由于还存在ArrayList的实例引用，对应的100个对象就无法删除
elementData[--size] = null;
}
- E get(int index)
获取指定位置的元素。
/**
* 检查给定的索引是否在范围内。 如果没有，则抛出一个适当的运行时异常。
* @param index : 下标
*/
public E get(int index) {
// 校验下标有效性
rangeCheck(index);
// 返回元素数组中指定index位置的数据
return elementData(index);
}
private void rangeCheck(int index) {
// 如果下标大于实际数组长度（元素数组最后一个数据下标为size-1）
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 迭代器遍历
// 创建迭代器
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// 设置期望的修改次数，也就是创建迭代器那一时刻ArrayList的修改次数
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
// 所有操作前，都检查容器是否发生变化，也就是被修改了
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
// 如果此刻的修改次数和一开始的不一致，抛出ConcurrentModificationException并发修改的异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
- subList方法
subList方法返回的是SubList对象，不是原来的ArrayList类型。相当于一个子视图，他们本质还是共用底层的数据。
public List<E> subList(int fromIndex, int toIndex) {
// 范围验证
subListRangeCheck(fromIndex, toIndex, size);
// 创建SubList的对象
return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
// 添加元素
public void add(int index, E e) {
rangeCheckForAdd(index);
// 校验原来的容器是否发生变化，如果发生变化抛出异常
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
........
}
在 subList 场景中，高度注意对父集合元素的增加或删除，均会导致子列表的遍历、增加、删除产生 ConcurrentModificationException 异常。
总结
- 增删改查中， 增导致扩容，则会修改modCount, 删除也会修改modCount。 改和查一定不会修改modCount。
- 扩容操作会导致数组复制，批量删除会导致找出两个集合的交集，以及数组复制操作，因此，增、删都相对低效。 而 改、查都是很高效的操作。
- ArrayList是一个线程不安全的容器，如果要使用线程安全的话可以考虑
Vector，Collections.synchronizedList或者CopyOnWriteArrayList。
参考
转载自:https://juejin.cn/post/7134142019722543111