带你读读ArrayList源码，可否？

一直在说ArrayList是非线程安全的，到底是为什么呢？

以ArrayList的add()方法为例，添加操作并不是一步完成，而是分为两步：

1.先在elementData[index]位置上添加一个新的元素

2.接着在为size进行+1操作。

描述：

如果此添加过程是在多线程的环境下，例如线程1已经完成了第一步将元素添加进了elementData[]中，但是此时的size并没有进行+1操作，而现在来了一个线程2，线程1的调度就结束了，size并没有+1,而线程2继续为elementData[]添加值，此时的size状态依然为之前的状态，接着由于线程1需要完成add()全过程，所以就发生了两次size++，此时添加的元素位置索引与size值就不匹配了。

所以这就是非线程安全。

# ArrayList的继承结构

在解读源码之前我们需要对ArrayList的内部继承结构做了解：

AbstractList：实现List接口操作规范，增、删、遍历等操作。

RandomAccess：提供随机访问功能

Cloneable：提供可拷贝功能

Serializable：提供可序列化功能

想将ArrayList烂透与心中，以下几点必须掌握：

（1）扩容机制

（2）浅拷贝

（3）快速报错机制

（4）批量删除算法

（5）遍历方式

在我认为只要明白了以上几点，一千行ArrayList源码的阅读将能顺畅无比。

# 扩容机制

ArrayList源码中能需要扩容的无非就如下几类方法：add()、addAll()、readObject()。

扩容要从一个方法 ensureExplicitCapacity 讲起。

例如从 add(E e) 方法讲起：

方法很简单，先扩容，再维护 size 变量 ，接着往里填元素。而添加方法中的扩容方法如下：

此时可以发现方法中又调用了其他方法：继续跟踪

最后发现，真正的扩容操作在于 grow() 方法里：

前面的几个方法可以说都是在为 grow() 方法寻找合适的接班人而作准备的。找到合适的接班人后，首先以1.5倍原数组的长度进行扩容：方法中用到了 hugeCapacity() 方法。此方法的作用是限制最大的扩容范围。随后将原数组拷贝进我们扩容后的新数组中去。

hugeCapacity() 方法解析：

添加元素，无非就是往后推。而删除元素就是往前推。后面将学习到源码中的删除算法思想。

# 浅拷贝

前面的源码中你可能会对grow中的Arrays.copyOf()方法会产生一个疑问，该复制操作是浅拷贝还是深拷贝呢？

源码中多处出现有关拷贝的情况，例如：

elementData = c.toArray();

elementData = Arrays.copyOf(elementData, size, Object[].class);

ArrayList v = (ArrayList) super.clone();

System.arraycopy(elementData, 0, a, 0, size);

出现这么多的拷贝，你不去搞清楚，内心过得去嘛？过不去嘛！

简单阐述浅拷贝与深拷贝的关系：

（1）浅拷贝：

典型应用：基本数据类型下的值传递

浅拷贝安装索引顺序进行对象的拷贝，顾名思义需要新建一个对象，该新对象有原对象中的所有属性值，位置一一对应，如果属性是基本类型，拷贝的就是基本类型的值；如果属性是内存地址（引用类型），拷贝的就是内存地址 ，所以其中一个对象改变了这个地址，就会影响到另一个对象。过程中修改了原对象不会影响到新对象的拷贝。

（2）深拷贝

深拷贝顾名思义是个狠角色，心狠手辣，连根拔起！殃及他人！和浅拷贝比起来，呵呵，不仅拷贝所有属性，连对象和源对象所引用的对象也能给clone过来。牛！不过需要付出代价，一个字：慢！Java中要实现深拷贝要实现Cloneable接口中的clone()方法，而Object默认的clone方法为浅拷贝，真是庆幸呢！

明白了浅拷贝与深拷贝后，下面就对上面出现的有关拷贝的方法进行解析：

1）

elementData = c.toArray();

这行代码出自如下方法：

老套路，进行跟踪：哇，大有来头，出自Collection接口里：

Object[] toArray();

好家伙，从官方文档可以知道，该方法不会返回集合的引用，只是创建新数组，从迭代器中填充元素，并返回，所以为浅拷贝。

2)

下面代码源码中多处出现：

elementData = Arrays.copyOf(elementData, size, Object[].class);

浅拷贝：文档明确给出，只是复制对象的引用（内存地址），修改源数组值，不会影响新数组。

3）

ArrayList v = (ArrayList) super.clone();

这里调用了Object类的clone()方法，很明显为浅拷贝，文档明确表示。

4）

System.arraycopy(elementData, 0, a, 0, size);

出现频率有些高了，这老兄。很明显他也是浅拷贝，如果是深拷贝，呵呵，估计ArrayList有些不好收拾!

# 快速报错机制

阅读源码的时候，对多次出现的modCount变量表示有些疑惑？这个变量有什么用呢？很重要！能够记录某个线程下的修改或者其他操作次数。

对于快速报错机制必须提的是：ConcurrentModificationException

该异常类在并发环境下可能会产生。即：在不希望修改对象的时候去修改了。

1.例如，通常不允许一个线程修改一个集合当另一个线程在它上面迭代时。总的来说，结果是迭代在这些情况下没有定义。一些迭代器实现(包括所有通用集合实现的实现)由JRE提供)可以选择抛出此异常，如果此行为是检测。

2.如果一个单一的线程发出的方法调用序列违反了对象的约定，同样会抛出该异常。例如，如果一个线程直接修改一个集合使用故障快速迭代器迭代集合，即迭代器将抛出此异常。

而在迭代遍历的过程中都调用了方法 checkForComodification 来判断当前ArrayList是否是同步，以免出现异常。

# 批量删除算法

在阅读ArrayList的时候，相信其他常用方法的处理逻辑，对你来说简直和切豆腐一样简单，不过这里要对方法batchRemove() 进行一下解析，方便各位读者能更加顺畅的去阅读源码。

该方法和扩容一样，一层套一层，最终才能把它套出来。既然是批量删除，那就从removeAll()方法开始说起吧。

正如你所见，我给出的解析实在是太过于详细，以至于我都不怎么想说下去

算法思路：

1.利用双指针对原数组与新数组进行遍历，首先判断给定的集合元素是否包含在数组中，如果存在，就好办了，首先 r 不变，也就是数组位置不变，将元素传给新数组的 w+1 位置，跳出条件后，r才自增，否则r自增，w不自增。

2.下面便是处理一些异常情况了，例如r != size情况，什么！r != size！，那还来干嘛，我来找你，你却说你自己不在，what? 接着讲该异常位置后面的数据赋值到新数组w位置开始的后面所有位置。既然你无情，休教我无义，全部归你管，好自为之！随后维护指针w。什么！w != size ！，难道我是在做梦，一切都不是真实的？赶紧把这段不该的记忆交由GC来清除吧！清除成功！继续下一个。

# 最后一个：遍历方式

终于要结束了！我在阅读源码的时候真要被这家伙给气出命来啊，一推内部类的实现烦不胜烦呀！看得我差点要放弃了都。以后我会对迭代器做一些解析，这里就不做太细的阐述了。文章有些长了，见谅。

ArrayList主要有以下几种遍历方式：for循环、迭代器、随机访问。

这里对ArrayList的迭代器做解释：

由于每个容器类的数据结构不同，齐内部结构逻辑处理也不同，固，每个容器类都可能会有属于自己的一个迭代器的实现。

需要注意的是：迭代器在迭代期间可以从集合中移除元素，不过这样是非线程安全的。

# 文末总结：

ArrayList或多或少都有它的优缺点。

优点：

1.提供随机访问加上自身为数组，所以查找很快。

2.动态扩容，合理利用空间

3.访问，遍历快速

缺点：

1.删除、插入效率低

2.线程不安全

源码中还有很多精彩的细节点，例如writeObject / readObject，中序列化与反序列化的情况。以及Spliterator接口的应用和ArrayListSpliterator中二分法等，有兴趣可以自行研究。