源码解析 || ArrayList源码解析
前言
这篇文章的ArrayList源码是基于jdk1.8版本的源码，如果与前后版本的实现细节出现不一致的地方请自己多加注意。先上一个它的结构图
ArrayList作为一个集合工具，对于我而言它值得我们注意的地方有：
- 参数的作用细节
- 扩容的细节
- 迭代的细节
- 特殊API的细节
那么我就由这四个细节对ArrayList进行分析。
ArrayList的参数细节
ArrayList参数其实并不是特别多，值得我们拿出来讲的那就更少了。下面我通过一张图的展示，同时列出一些值得我们谈一谈的参数：
- DEFAULT_CAPACITY、MAX_ARRAY_SIZE 两个参数规定了ArrayList的默认长度和最大长度。但是，如果使用默认构造函数，在初始化ArrayList的时候，它的长度是0，只有第一次添加数据时，它才会扩容为10；
- EMPTY_ELEMENTDATA、DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这两个参数的值都是Object空数组，至于为什么作者要写两个同样的变量，那当然是为了区分不同方法当中的语义，使源码更加易读，当然这对于我们来说可以往后再关注。
- size ArrayList中的大小，注意这也可以指已存放的数据的个数，和下面elementData的长度也还有一定的区别。
- elementData Object数组，这个是整个ArrayList最核心的参数之一，ArrayList存放的数据都在这里，对ArrayList的增删改查都基于这个Object数组。同时，它是被transient关键字修饰的，这意味着ArrayList需要进行序列化的时候，会把它忽略。那么我们会有一个问题，elementData 里面的数据难道不用序列化了吗？ 答案当然是需要的，但是它不是直接将一整个数组都序列化，而是通过方法writeObject()，把elementData 中有数据的位置序列化。通俗的话就是，它序列化elementData的前size个，而elementData的真实长度中，size后面的空间都认为是没有数据的，如果也将它序列化会造成一定的流量浪费，影响传输性能。
- modCount 这个参数不是在ArrayList中声明的，它是在父类AbstractList中声明的，它的作用是记录ArrayList的结构（增加或删除）改变次数，以此来配合迭代器进行安全检查，迭代器一旦发现modCount被修改了，则会抛出ConcurrentModificationException。
扩容的细节
首先，为什么不讲增删改查直接谈扩容呢？因为ArrayList的查找和修改的实现细节其实和普通的数组操作一样，并没有什么特别的地方。而添加和删除涉及到数组的动态调整，也就是我现在写的扩容，其它的其实和普通的数组操作差不多。
那么，当ArrayList执行一次add()方法的时候，它会有什么样的操作呢？首先我们先来看一个图。这是一个方法嵌套，执行到最后，就能确保list的空间是安全的。
上面是执行add方法后的一系列调用流程。可以看出方法内在调用完ensureCapacityInternal()后，空间是能确保数据的填充的。而往下调用的方法中，我们只关注grow()方法就行，这是个扩容方法，具体的代码和意图如下所示。
1 /** 2 * Increases the capacity to ensure that it can hold at least the 3 * number of elements specified by the minimum capacity argument. 4 * 5 * @param minCapacity the desired minimum capacity 6 */ 7 private void grow(int minCapacity) { 8 int oldCapacity = elementData.length; 9 //新容量暂时为旧容量的1.5倍 10 int newCapacity = oldCapacity + (oldCapacity >> 1); 11 //这一步是确保扩容的时候，扩容的空间尽量合理，避免频繁扩容 12 if (newCapacity - minCapacity < 0) 13 newCapacity = minCapacity; 14 //假设参数大于MAX_VALUE，设定最大容量为Integer.MAX_VALUE 15 if (newCapacity - MAX_ARRAY_SIZE > 0) 16 newCapacity = hugeCapacity(minCapacity); 17 //调用数组工具把数据覆盖并开辟内存空间 18 elementData = Arrays.copyOf(elementData, newCapacity); 19 }
迭代的细节
ArrayList的迭代器采用的是fast-fail方式，也就是我们的快速失败方式。这是什么意思呢？我们直接贴出源码的注释来解释。
在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
那么 ，iterator通过什么方式判断列表被修改了呢？答案是在ArrayList内部还有一个内部 Iterator的实现类，里面有一个参数expectedModCount，这个值与modCount 比较，若两个值不相等，则抛出异常。
1 //源码方法 2 final void checkForComodification() { 3 if (modCount != expectedModCount) 4 throw new ConcurrentModificationException(); 5 }
注意！我所说的迭代要注意的细节，指的是在循环过程中，伴随着ArrayList结构上的修改，例如添加或删除。如果只是简单的循环遍历输出，其实各种方法没有太大的区别。
下面例举集中常见的错误使用方式：
这种情况通常是迭代用迭代器，而对于修改则是用ArrayList的方法引起的，要解决这个问题只需要利用iterator的remove()方法即可。
1 ArrayList<Integer> list = new ArrayList<>(3); 2 list.add(111); 3 list.add(222); 4 list.add(333); 5 6 Iterator<Integer> iterator = list.iterator(); 7 while(iterator.hasNext()){ 8 Integer next = iterator.next(); 9 if (next.equals(111)){ 10 //错误的使用，在创建迭代器后使用list方法来remove,会抛出ConcurrentModificationException 11 list.remove(new Integer(111)); 12 } 13 System.out.println(next); 14 } 15 }
下面这种情况如果你只是想要找到一个目标值，同时将这个值删除并break退出是可以的。但是，如果你还要继续遍历下去，这种情况则会导致ArrayList集合遍历的不完整。
1 ArrayList<Integer> list = new ArrayList<>(3); 2 list.add(111); 3 list.add(222); 4 list.add(333); 5 for (int i=0;i<list.size();i++){ 6 if (list.get(i).equals(222)){ 7 //执行这一步，size的值为2，导致333这个值没有输出就结束循环。 8 list.remove(i); 9 continue; 10 } 11 System.out.println(list.get(i)); //输出结果：111 12 } 13 14 }
一般来说，当我们迭代有对ArrayList进行remove的需求的时候，可以利用迭代器来遍历ArrayList的结构，这样比较安全规范的且不会产生错误。
1 import java.util.ArrayList; 2 import java.util.Iterator; 3 4 public class ArrayListDemo { 5 public static void main(String[] args) { 6 ArrayList<Integer> list = new ArrayList<>(); 7 list.add(111); 8 list.add(222); 9 list.add(333); 10 Iterator<Integer> iterator = list.iterator(); 11 while (iterator.hasNext()){ 12 Integer next = iterator.next(); 13 if(next.equals(222)){ 14 iterator.remove(); 15 continue; 16 } 17 System.out.println(next); 18 } 19 } 20 }
特殊API的细节
- remove方法参数的不确定性。
就在我刚才的示例代码中就有一种隐藏的危险，当你的ArrayList存放的是Integer类型的时候，有一种场景下你需要移除一个值。你会理所当然的调用list.remove(222);这个方法来移除222这个值。但是，这个时候其实它是指移除索引位置在222上的值。这个时候就会有删除错误或者范围异常的发生。
1 Integer next = iterator.next(); 2 if (next.equals(222)){ 3 4 list.remove(222); 5 }
2. subList方法的实现及返回类型
下面先列出subList方法返回在SubList内部类的继承关系和构造方法。
1 private class SubList extends AbstractList<E> implements RandomAccess { 2 private final AbstractList<E> parent; 3 private final int parentOffset; 4 private final int offset; 5 int size; 6 7 SubList(AbstractList<E> parent, 8 int offset, int fromIndex, int toIndex) { 9 this.parent = parent; 10 this.parentOffset = fromIndex; 11 this.offset = offset + fromIndex; 12 this.size = toIndex - fromIndex; 13 this.modCount = ArrayList.this.modCount; 14 } 15 }
ArrayList中有一个subList方法可以用于对ArrayList的切割。一般我们要用List接口来接收返回的集合，但是其实它返回的具体类型是一个内部类SubList。与ArrayList肯定不是同一个类型，因此，如果你把它强制转换为ArrayList则会发生错误。
1 public static void main(String[] args) { 2 ArrayList<Integer> list = new ArrayList<>(3); 3 list.add(111); 4 list.add(222); 5 list.add(333); 6 List<Integer> subList = list.subList(0, 1); 7 //编译不报错，运行时报错 8 ArrayList worngList = (ArrayList)subList; 9 }
同时，从构造函数可以看出。SubList类中的集合其实是从ArrayList中直接赋值来的，它只是通过修改边界范围和size来构成一个新集合。也就是说，实质上SubList和ArrayList用的是同一个elementData数组。因此，当对SubList进行增删改的时候，也会影响到ArrayList的存放的数据。示例代码如下：
1 public static void main(String[] args) { 2 ArrayList<Integer> list = new ArrayList<>(3); 3 list.add(111); 4 list.add(222); 5 list.add(333); 6 List<Integer> subList = list.subList(0, 1); 7 subList.add(444); 8 subList.add(555); 9 }
我们通过debug可以看到，当添加到444,555的时候，两个对象都出现了这两个数据。
相关文章