经典数据结构之数组&ArrayList源码分析
前言
数组是我们学习数据结构与算法时第一个解除的数据结构，主流的编程语言都提供了数组这一基本数据类型。它是一种线性表，存储了相同类型的数据，在内存中是一块连续的空间
List集合是java编程最常用的集合框架，它继承自Collection，是一个有序集合，也称序列。用户可以精准的控制每个元素的插入、删除，也可以通过整数索引index访问任一元素，并且可以遍历整个集合搜索某一元素。List集合允许插入重复元素和null元素。
关于数组
数组我们肯定不陌生，在初学一门编程语言的时候肯定会先学习数组，主流的编程语言都支持数组。它是一种最基本的线性表数据结构，是一组连续的内存空间，存储了具有相同数据类型的数据。
线性表：顾名思义，就是数据排成像一条线一样的结构。线性表上的数据只有前后两个方向。除了数组，链表、队列、栈等也是一种线性表结构
连续内存空间和相同类型的数据：相同数据类型不必多说。连续内存空间，我觉得这才是数组最大的特性。正是因为这个特性，它才可以支持随机访问，注意是随机访问不是查找哦，随机访问的话我们事先肯定是知道它的下标index的，通过index可以直接定位到某个元素的内存空间地址。它的原理就是：数组下标就是相对于数组起始地址的偏移量，我们只要知道数组对象在内存中的地址，就能通过偏移量计算任一元素的内存地址，即:baseAddress+index*elementSize，baseAddress为数组对象的地址，elementSize为每一个元素的大小，见下图。所以随机访问的时间复杂度为O(1)，如果是查找某个元素的话时间复杂度就是O(n)，因为你事先并不知道这个元素所在的位置，只能遍历一遍逐个比较判断。而且因为它是连续的内存空间，cpu在读取数组的时候可以将整块数组加载到寄存器，性能非常高。
关于ArrayList
ArrayList，顾名思义，是一种基于数组实现的List集合，它封装了对数组的常用基本操作。
下面我们来分析一下List集合最常用的一个实现类——ArrayList。java所有的集合类都是基于两种最基本数据类型来实现——数组、链表(封装类型，通过引用串连起来)。ArrayList是线程不安全的，所以我们一般都是在某一个线程内部(方法内部或ThreadLocal内)创建并使用。它还是可变长的数组集合，当数组容量使用完后，会自动进行扩容。当我们在某一位置进行添加或删除的时候，它会自动搬移后面的元素。那么它究竟是如何实现添加、删除、访问、自动扩容的呢，我们接着往下看
类继承关系图：
数据域
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//当ArrayList为空时使用此空数组对象
private static final Object[] EMPTY_ELEMENTDATA = {};
//当使用无参构造函数的时候指定此数组为elementData的实例对象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正用来存储数据的数组,transient修饰不能参与序列化
//没有用private修饰，方便内部类访问，如内部迭代器Iterator
//内部数组的组件类型为Object，没有用泛型E
transient Object[] elementData;
//容器的大小，即数组中元素的数量
private int size;
构造函数
有三个构造函数，我们分别来分析一下:
1.指定初始容量的构造函数，如果我们事先知道要创建的ArrayList的最大容量可以使用此构造函数，避免后续频繁的扩容操作
//构造一个指定初始容量的ArrayList，初始容量即elementData数组的初始大小
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//创建数组对象，大小为initialCapacity
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果initialCapacity为零的话则使用EMPTY_ELEMENTDATA对象
this.elementData = EMPTY_ELEMENTDATA;
} else {
//initialCapacity小于0则抛异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
2.默认无参构造函数
//默认构造函数只初始化内部元素数组对象，指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，其大小为0，
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个类变量，如果指向它那我们创建的ArrayList对象
//内部元素数组不都指向它了么？！其实，这个数组对象一般是用不到的，在第一次调用add方法添加
//元素的时候会重新创建一个大小为10的数组(扩容)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.传入Collection对象的构造函数
//创建对象的时候传入了一个集合对象，并将集合对象的元素添加到了该ArrayList对象中
public ArrayList(Collection<? extends E> c) {
//集合转化成数组对象，并赋值给内部elementData
elementData = c.toArray();
//如果传入的集合对象不为空，需要判断elementData数组对象的实际类型是否是Object[],
//因为实际的类型也有可能是E1[]或E2[]，
//E1和E2都是E的子类
if ((size = elementData.length) != 0) {
//如果不是Object[]类型，则将元素转成Object类型并拷贝一份新的object数组
//注意传入集合的元素类型也是E，所以强转是没有问题
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果是集合对象是空的话指向EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
}
}
//我们继续看静态方法copyOf
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//先判断newType是否是Object[]类型，是的话直接创建Object[]对象，否则根据newType的
//实际组件类型创建数组对象
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//拷贝original数组的元素到目标数组T[]中，拷贝长度取原数组元素大小和新数组长度的较小者
//防止数组越界异常
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
get方法获取元素
get(int index) 根据elementData数组下标可以直接获取指定元素，时间复杂度为O(1)
//根据index索引获取指定元素，其实索引就是内部数组elementData的下标,elementData[index]
public E get(int index) {
//检查是否下标越界
rangeCheck(index);
return elementData(index);
}
set方法更新元素
set(int index, E element) 方法更新指定下标的元素，其实就是更新elementData数组的元素，因为下标index的位置可以直接定位，所以更新的时间复杂度为O(1）
//更新指定位置的元素
public E set(int index, E element) {
//检查是否下标越界
rangeCheck(index);
//返回原index位置的元素
E oldValue = elementData(index);
//更新index位置元素的值
elementData[index] = element;
return oldValue;
}
add方法添加元素
add(E e)方法就是在列表的最后一个位置添加元素，当内部elementData数组用完后需要创建一个新的数组，大小是原数组的1.5倍，并将原数组元素搬移到新数组。由于是在数组使用完后才会扩容搬移，所以该方法的时间复杂度是O(1)
//添加一个元素，在数组的最后一个位置添加
public boolean add(E e) {
//判断数组容量是否已达上限，是的话触发扩容,size+1是所需的最小容量
ensureCapacityInternal(size + 1); // Increments modCount!!
//在最后一个位置添加元素,size+1
//只在最后一位添加元素所以该方法的时间复杂度为O(1)，这其中会涉及到扩容，搬移n个元素
//但是只有在长度达到n的时候才会搬移，我们可以把搬移操作均摊到每一个元素上，即相当于
//添加一个元素我就假设搬移了一次，所以时间复杂度还是O(1)
elementData[size++] = e;
return true;
}
//该方法会触发扩容操作，继续往下看
private void ensureCapacityInternal(int minCapacity) {
//
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算所需的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组对象的话说明是刚完成了初始化，第一次添加元素触发扩容
//并且第一次扩容的大小是10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
//此方法会在添加元素的时候调用，modCount记录添加删除的次数
modCount++;
//如果数组的长度小于所需的最小容量则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//继续往下看扩容方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容后新数组的大小为原来的大小加上一半,oldCapacity >> 1就是oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的大小还是小于所需的最小容量则取minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//这里，定义了一个ArrayList容量的最大值，即Integer.MAX_VALUE - 8
//当最小的容量大于最大值时，会进行另外的操作，注意这里的newCapacity有可能
//是负数，即最高位是1,超出了了int的最大正整数值(Integer.MAX_VALUE+1就会变成负数)
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//这一步会创建新的数组对象，大小为newCapacity，并将老的elementData里的元素
//搬移到新的数组，扩容结束
elementData = Arrays.copyOf(elementData, newCapacity);
}
//所需最小容量超过了ArrayList最大值MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
//如果是负数则超出了ArrayList的最大容量上限Integer.MAX_VALUE，抛出oom异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//否则超出最大容量MAX_ARRAY_SIZE的话就取Integer.MAX_VALUE，即int类型的最大正整数
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(int index, E element) 方法就是在指定的索引位置添加元素，首先也会判断elementData数组是否够用，如果不够用的话扩容。在指定位置添加元素的时候，先把index及index后面的元素集体往后搬移一个位置，然后在空出来的index位置添加指定元素，这里面会涉及到搬移操作，如果index是size-1的位置，则将最后一个位置的元素向后搬移一位，总共搬移一个，如果index是第一个元素，则需要将全部元素往后搬移一位，总共搬移n个，每次add都会涉及搬移所以我们取平均值n/2，所以该方法的时间复杂度为O(n)
//在指定的位置添加元素
public void add(int index, E element) {
//判断index是否越界
rangeCheckForAdd(index);
//判断是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index位置开始的元素都往后搬移一位,留出index位置，如果index等于size的话不需要搬移直接添加
//这里index是随机的，当他是size-1时只需要搬移一个，当他是第一个时需要搬移所有元素
//取平均数n/2，每添加一次就要搬移n/2个元素，时间复杂度为O(n)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在index位置添加指定元素
elementData[index] = element;
//size扩大1
size++;
}
如下图所示：
remove方法删除元素
remove(int index) 方法删除指定位置的元素，删除该元素后需要把后面的元素往前搬移填补空缺，如果删除的是最后位置的元素，则不需要搬移操作，如果删除的是第一个元素则需要搬移n-1个元素，我们还是取平均数(n-1)/2，即时间复杂度为O(n)
//删除指定位置上的元素
public E remove(int index) {
//判断index是否越界
rangeCheck(index);
//次数加1
modCount++;
//记录该位置原先的元素
E oldValue = elementData(index);
//计算搬移的数量，index位置后所有的元素都要往前搬移一位
int numMoved = size - index - 1;
//说明删除的不是最后一位
if (numMoved > 0)
//将index后面的元素往前搬移一位
//这里的index是随机的，如果是最后一位则不需要搬移操作，如果是第一个，则需要搬移
//n-1个元素，我们还是平均一下，每次删除操作需要搬移(n-1-1)/2个元素，时间复杂度为O(n)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//搬移后需要将最后位置上的元素清空，因为搬移的时候是后一个覆盖前一个，最后一个位置的元素没有被覆盖
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
如下图所示：
remove(Object o) 方法删除指定元素，我们需要先查找o元素所在的位置index，查找操作需要遍历整个数组所以时间复杂度是O(n)，找到index后进行删除，类似与remove(index,object)方法，删除的时间复杂度也是O(n)，所以总的时间复杂度还是O(n)
//删除指定的元素，注意该元素的位置index我们是不知道，所以需要先查找
public boolean remove(Object o) {
//如果删除的是空元素，我们先查找null所在的位置index
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//找到对应的index后对其进行删除
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
//找到指定元素的index后对其进行删除
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//删除指定位置的元素，该方法的操作类似于remove
private void fastRemove(int index) {
//次数加1
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
clear方法清空ArrayList
//清空ArrayList就是把内部数组的所有元素清空
public void clear() {
//等同于做了一次全量删除，次数加1
modCount++;
// clear to let GC do its work
//逐一清空每个元素
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
序列化与反序列化
ArrayList对象的序列化与反序列化与一般的对象稍微有点出入，它的内部每一个元素需要单独进行序列化与反序列
序列化
//该方法在进行序列化的时候会被调用到，即ObjectOutputStream#writeObject(ArrayList)时会
//调用到ArrayList#writeObject
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
//序列化开始的时候先记录修改次数
int expectedModCount = modCount;
//先序列化非static和transient修饰的字段，我们的数组对象elementData就是transient修饰的
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
//再单独序列化size，用于兼容clone方法
s.writeInt(size);
// 最后将每一个元素作为object对象单独序列化
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//以上操作完成后将ArrayList对象相关的数据都写到stream里了，如果这时
//modCount发生了改变，即又操作了删除或添加，则抛异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
反序列化
//该方法在被反序列化时会被调用到 即ObjectOutputStream#readObject()时会
// 调用到ArrayList#readObject
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
//初始化数组对象
elementData = EMPTY_ELEMENTDATA;
//先反序列化非static和transient修饰的字段，包括size字段
s.defaultReadObject();
//对应于writeObject方法里面的s.writeInt(size);
//在这里没有实际意义，忽略
s.readInt();
//原数组容量大于0的话需要反序列化每个元素
if (size > 0) {
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
//这里会触发扩容因为size大于0
ensureCapacityInternal(size);
Object[] a = elementData;
// 按原来的顺序反序列化每个元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
迭代器
ArrayList的迭代器也是我们常用的一个操作对象，用来遍历每一个元素，ArrayList在内部维护了一个迭代器类，可以安全的访问每一个元素，通过iterator()方法获取迭代器实例
//迭代器方法也是比较常用的一个方法
//返回一个Iterator实例
public Iterator<E> iterator() {
return new Itr();
}
来看一下具体的Itr类
//迭代器常常用于ArrayList元素的遍历
//这里内部定义了一个迭代器类并通过iterator()方法返回该实例
private class Itr implements Iterator<E> {
int cursor; // 游标，指向下一个需要返回的元素的位置
int lastRet = -1; // 指向最后一个迭代元素的index位置，没有迭代过元素的话指向-1
int expectedModCount = modCount;//记录修改次数
Itr() {}
//判断是否达到最后一个元素
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
//获取下一个元素，即用来迭代每一个元素
public E next() {
//判断是否修改了ArrayList对象，即modCount发生了变化
checkForComodification();
//记录当前需要返回元素的下标
int i = cursor;
//超出了最后一个元素的下标则抛异常
if (i >= size)
throw new NoSuchElementException();
//通过反射获取ArrayList里的elementData数组对象
Object[] elementData = ArrayList.this.elementData;
//如果i越界了的话抛异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
//游标指向下一个
cursor = i + 1;
//返回当前i位置的元素，并更新lastRet为最后迭代元素的index
return (E) elementData[lastRet = i];
}
public void remove() {
//如果还没有迭代过元素，则抛异常，初始化时lastRet=-1
if (lastRet < 0)
throw new IllegalStateException();
//判断是否修改了ArrayList对象，即modCount发生了变化
//两遍？！
checkForComodification();
checkForComodification();
try {
//删除最后一个迭代的元素，即最后一次next返回的元素
ArrayList.this.remove(lastRet);
//游标指向重新指向下一个元素，被删除元素的后一个
cursor = lastRet;
//重置lastRet
lastRet = -1;
//重置expectedModCount
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//处理剩余的元素，参数是一个函数式接口，用来消费剩余的每一个元素
public void forEachRemaining(Consumer<? super E> consumer) {
//判空
Objects.requireNonNull(consumer);
//下面几行主要判断是否迭代完了全部元素，是的话就直接返回
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
//判断当前位置是否越界
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
//循环条件：i没有到达最后一个位置且ArrayList对象没有发生修改
//依次取出当前游标及后面的元素传给consumer消费处理
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
//更新游标cursor，lastRet
cursor = i;
lastRet = i - 1;
//再次检查ArrayList是否发生了修改
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
后记
ArrayList源码与数组的总结就写到这里，谢谢阅读。相对来说数组是最简单的一种数据结构，理解起来也不难，时间复杂度也很好分析。ArrayList的源码都是基于对数组的操作阅读也不难。下一篇我会总结一下链表、队列以及LinkedList的源码分析。
