阅读提醒：将本文结合源码一起使用味道更佳哦！~
前言
ArrayList 是我们最常用的一个集合类之一。了解它的实现，有助于我们理解自己写下的代码背后更深层次的逻辑。同时也能从其中学习到JDK的设计思想。
类定义
1 | public class ArrayList<E> extends AbstractList<E> |
AbstractList：实现了List，其内部通过cursor实现迭代器逻辑
RandomAccess：标记接口，声明ArrayList支持快速随机访问
Cloneable：标记接口，声明ArrayList重写clone方法。这里ArrayList实现的是浅拷贝，即复制内部数组
Serializable：标记接口，可被默认的序列化机制序列化与反序列化
主要内容
数据结构
ArrayList采用的数据结构为：数组。数组在内存中会开辟一组连续的、大小相同的空间。
ArrayList在内存上的分布类似于以下的图
也是基于此特性,数组的查询能实现O(1)的时间复杂度；
在代码中1
2
3
4
transient Object[] elementData; //内部数组
private int size; //数组的长度
可以看到 elementData 是被 transient 修饰的所以在序列化的时候不会被保存，后面会讲到ArrayList为什么要这么处理。
数据操作
1. 插入
因为篇幅有限，这里只截取了最简单的 add(E e) 方法，其他插入方法的流程于此类似1
2
3
4
5
6
7
8public boolean add(E e) {
//1. 判断是否要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//2. 插入数据
//3. size+1
elementData[size++] = e;
return true;
}
插入这部分代码主要做了两件事
- 是否需要扩容
- 插入数据
以上要深入的的部分（1）ensureCapacityInternal方法。在这部分会涉及扩容，这个我们稍后再去分析。
可以看到在插入的时候，时间复杂度可能会变化，如果要扩容的话，必定会设计数组的转移，所以时间复杂度是O(n),如果不扩容的情况下时间复杂度是O(1).
2. 删除
同上面一样，也以 remove(int index) 方法为例1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public E remove(int index) {
//1. 判断是否超过数据最大长度
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//2. modifyCount +1
modCount++;
//3. 获取旧值
E oldValue = (E) elementData[index];
//4. 计算index位置向后偏移量
int numMoved = size - index - 1;
//5. 将index后的元素前移一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//6. size--
elementData[--size] = null;
return oldValue;
}
删除这部分代码主要做了两件事
- 获取旧的值
- 用后位覆盖的方式，替换原位置的值
以上内容中（2）中的 modCount++的作用是实现迭代器中的多线程操作校验也就是 fast-fail机制；（5）其中调用了System.arraycopy方法，底层是用C实现，能快速的实现数组之间的复制。
我们会发现当ArrayList要remove一个元素的时候，是直接将后面的元素前移顶替，而不是仅仅将其置空。在日常开发中，我们经常会对ArrayList进行遍历操作。如果在正向遍历的情况下，删除数组的某个元素，会导致异常，因为数据索引已经不准确。
同时，我们会发现当删除一个元素的时候，尽管是调用了C层来实现，可是一样是需要O(n)的时间复杂度。
3. 查询
1 | public E get(int index) { |
查询的部分没有太多值得深入的部分。就是通过索引获取值。也看明显的可以看出，ArrayList的查询速度很快，只需要O(1)的时间复杂度。
扩容机制
对于容器来说，扩容的重要性不言而喻。我们在上面的插入中发现调用到了ensureCapacityInternal方法，接下来我们好好了解一下其内部的实现机制；1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private void ensureCapacityInternal(int minCapacity) {
//1. 判断当前的elementData是否为空
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//2. 得到数组需要的最小的容量大小
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// modifyCount +1
modCount++;
//3. 如果所需最小容量大于当前数组容量，则执行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//4. 新数组的容量= 旧数组容量*1.5 (>>1 等效于除以2）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 校验新的容量是否满足最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 判断新的容量是否已经为最大容量了（ MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
扩容部分做的判断很多，总结起来就是以下三个部分
- 是否需要扩容
- 计算出扩容值
- 进行扩容
里面有几点个点值得我们去分析：
（3）不是每次都会去扩容，只有当前容量不满足最低要求容量时候才会去扩容
（4）一般情况下扩容大小会是是1.5倍，了解这个有助于我们了解使用容器时候的内存情况
现在将上面插入部分与扩容整合在一起，整理出流程图：
以上的图省略了一些边界情况，如果当数组为空，或者当数组已经最大等情况
序列化
正常情况下，我们使用序列化，都不需要重写以下方法(writeObject/readObject)，这两个方法的作用是用来指定序列化过程中，如何写入与读取值的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34private void writeObject(ObjectOutputStream s) throws IOException{
//记录期望值
int expectedModCount = modCount;
s.defaultWriteObject();
//写入size
s.writeInt(size);
//1.循环写入数组元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//期望值对比，防止在此方法执行过程中elementData被修改
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
//读取写入的对象
s.defaultReadObject();
s.readInt();
if (size > 0) {
ensureCapacityInternal(size);
Object[] a = elementData;
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
这段代码很简单。就是重写了wirteObject与readObject。但是我这里有一个疑问
为什么不使用默认的wirteObject与readObject，而重写他们呢？
这里以我的观点来看，是为了节省内存的使用。正常情况下ArrayList中的elementData数组是不会被放满的，存在一定的剩余空间（这部分没有看明白的可以回头再看看扩容）。而在序列化过程中，只序列化元素而非数组，能省去很多无用的内存。
浅拷贝
ArrayList实现了clone方法，从拷贝的维度上区分，ArrayList为浅拷贝，为什么Arraylist是浅拷贝呢？我们贴出以下源码1
2
3
4
5
6
7
8
9
10
11
12
13public Object clone() {
try {
//1 生成ArrayList
ArrayList<?> v = (ArrayList<?>) super.clone();
//2 复制其内所有元素
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
以上代码做了两件事情
- 通过clone方法生成新的ArrayList，复制了其中的基础类型
- 复制了原数组中的元素引用
区分浅拷贝和深拷贝的一个很重要的标准是：拷贝对象的元素和原对象的元素是否相同。如果相同则为浅拷贝，不相同为深拷贝
因此虽然生成了新的ArrayList，可是其内的数组对象引用还是与原对象相同。因此是浅拷贝无疑了。
fast-fail
fast-fail 的主要作用是用来校验在某些操作（常为多线程操作）的过程中，元素是否被修改，如果被修改就报ConcurrentModificationException的错误。在ArrayList或其他容器中 一般实现是由expectedModCount 与 modCount 进行对比，来保证元素没有被操作过。
就这部分的内容，是具有通用性的，在java.util中被广泛使用，如HashMap等。我将另开章节fast-fail机制来绍
总结
ArrayList的实现很简单。只需要花上半小时的时间大致就可以看完。而关于ArrayList，我们必须要掌握的要点如下：
- 扩容机制，什么时候扩容，扩容后的大小
- 查询快、删除慢的原因
- 为什么是线程不安全，modCount
了解了这些，会有助于你避免一些日常开发过程中的坑。 Best wish！~