首页 > > 程序设计 > Java技术 >

源码解析 || ArrayList源码解析

2019-08-16 11:35:25来源：博客园阅读 ()

源码解析 || 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方法的实现及返回类型

ArrayList中有一个subList方法可以用于对ArrayList的切割，下面先列出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 }

一般我们要用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     }