ArrayList源码学习

本文依照构类定义、造函数、成员变量、方法的顺序进行分析。

一、ArrayList数据结构

　　通过翻阅源码和《算法》书籍，我们知道ArrayList的底层数据结构就是数组。在源码中通过object elementData[ ]数组来表示了底层结构。我们对ArrayList类的实例的所有操作底层其实都是基于数组的。

二、ArrayList源码分析

　　2.1 类定义

1 public class ArrayList<E> extends AbstractList<E>
2         implements List<E>, RandomAccess, Cloneable, java.io.Serializable

View Code

　　解释：ArrayList继承AbstractList抽象父类，实现了List接口（规定了List的操作规范）、RandomAccess（可随机访问）、Cloneable（可拷贝，实现该接口，就可以使用Object.clone()方法了）、Serializable（可序列化）。

1）为什么中间要多一个AbastractList抽象父类，是因为这个类中包含了部分通用实现，这样写具体类，比如ArrayList时，只需要专注于本类的具体实现了。

2）在查看了ArrayList的父类AbstractList也实现了List<E>接口，那为什么子类ArrayList还是去实现一遍呢？百度半天结果是因为author在设计的时候的错误而已，因为没啥影响，所以就没管它了，继续保留了。

　　2.2 类的成员变量　　

 1 private static final long serialVersionUID = 8683452581122892189L;//版本号
 2 
 3     /**
 4      * Default initial capacity.
 5      */
 6     private static final int DEFAULT_CAPACITY = 10;  // 缺省容量
 7 
 8     /**
 9      * Shared empty array instance used for empty instances.
10      */
11     private static final Object[] EMPTY_ELEMENTDATA = {}; // 空对象数组
12 
13     /**
14      * Shared empty array instance used for default sized empty instances. We
15      * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
16      * first element is added.
17      */
18     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 缺省空对象数组
19 
20     /**
21      * The array buffer into which the elements of the ArrayList are stored.
22      * The capacity of the ArrayList is the length of this array buffer. Any
23      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
24      * will be expanded to DEFAULT_CAPACITY when the first element is added.
25      */
26     transient Object[] elementData; // non-private to simplify nested class access
27 
28     /**
29      * The size of the ArrayList (the number of elements it contains).
30      *
31      * @serial
32      */
33     private int size;//实际元素大小，默认为0
34 /**
35      * The maximum size of array to allocate.
36      * Some VMs reserve some header words in an array.
37      * Attempts to allocate larger arrays may result in
38      * OutOfMemoryError: Requested array size exceeds VM limit
39      */
40     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//最大数组容量

View Code

解释：该类核心为elementData，它代表了ArrayList的底层数据结构形式，类型为Object[]，实际元素会存放在里面，并且被transient修饰，表明在序列化的时候，此字段是不会被序列化的。

　　2.3 类的构造函数

　　该类总共有三个构造函数，分别如下：

(1) public ArrayList(int initialCapacity)

 1 /**
 2      * Constructs an empty list with the specified initial capacity.
 3      *
 4      * @param  initialCapacity  the initial capacity of the list
 5      * @throws IllegalArgumentException if the specified initial capacity
 6      *         is negative
 7      */
 8     public ArrayList(int initialCapacity) {
 9         if (initialCapacity > 0) {
10             this.elementData = new Object[initialCapacity];
11         } else if (initialCapacity == 0) {
12             this.elementData = EMPTY_ELEMENTDATA;
13         } else {
14             throw new IllegalArgumentException("Illegal Capacity: "+
15                                                initialCapacity);
16         }
17     }

View Code

解释：指定elementData数组的大小，不允许初始化容量小于0，否则抛出异常；

(2) public ArrayList()

1 /**
2      * Constructs an empty list with an initial capacity of ten.
3      */
4     public ArrayList() {
5         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
6     }

View Code

解释：当初始化容量大小没给定时，会将elementData赋值成空集合。

(3) public ArrayList(Collection<? extends E> c)

 1  /**
 2      * Constructs a list containing the elements of the specified
 3      * collection, in the order they are returned by the collection's
 4      * iterator.
 5      *
 6      * @param c the collection whose elements are to be placed into this list
 7      * @throws NullPointerException if the specified collection is null
 8      */
 9     public ArrayList(Collection<? extends E> c) {
10         elementData = c.toArray();
11         if ((size = elementData.length) != 0) {
12             // c.toArray might (incorrectly) not return Object[] (see 6260652)
13             if (elementData.getClass() != Object[].class)
14                 elementData = Arrays.copyOf(elementData, size, Object[].class);
15         } else {
16             // replace with empty array.
17             this.elementData = EMPTY_ELEMENTDATA;
18         }
19     }

View Code

解释：当传递的参数为集合类型时，会把集合类型转化为数组类型，并赋值给elementData。

note:上面代码有提到一个java的bug，即编号6260652。可以查看为什么c.toArray不一定返回Object[ ]. 倘若c.toArray()返回的数组类型不是Object[ ]，则可以利用Arrays.copyOf()来创建一个大小为size的object[]数组。

note:那么为什么会存在不一定返回object[]数组呢？看如下例子：

 1 public static void test()
 2     {
 3         Sub[] subArray = {new Sub(), new Sub()};
 4         System.out.println(subArray.getClass());
 5 
 6         // class [Lcollection.Sub;
 7         Base[] baseArray = subArray;  //向上转型
 8         System.out.println(baseArray.getClass());
 9 
10         // java.lang.ArrayStoreException
11         baseArray[0] = new Base();//会抛出异常，因为baseArray中实际存放的是Sub类型的，虽然Base数组创建成功，但是里面存放的并不是Base，而是Sub
12     }

View Code

这个例子就说明了：假如我们有一个Object[]数组，并不代表着我们可以将Object对象存进去，这取决于数组中元素实际的类型。

2.4 类的成员方法

选取部分进行分析，即增删改查四个。

（1）add

有两个add方法，add(E e)和add(int index,E element)。前者是将指定的元素添加到ArrayList的最后位置，而后者是在指定的位置添加元素。

1     public boolean add(E e) {
2         // note: size + 1，保证资源空间不被浪费，在当前条件下，保证要存多少个元素，就只分配多少个空间资源
3         ensureCapacityInternal(size + 1);  // Increments modCount!!
4         elementData[size++] = e;
5         return true;
6     }

View Code

 1  /**
 2      *在这个ArrayList中的指定位置插入指定的元素，
 3      *  - 在指定位置插入新元素，原先在 index 位置的值往后移动一位,将新的值插入到空缺出来的index地方去
 4      */
 5     public void add(int index, E element) {
 6         rangeCheckForAdd(index);//判断角标是否越界
 7         ensureCapacityInternal(size + 1);  // Increments modCount!!
 8         //第一个是要复制的数组，第二个是从要复制的数组的第几个开始，
 9         // 第三个是复制到哪里去，第四个是复制到的数组从第几个开始存放，最后一个是复制长度
10         System.arraycopy(elementData, index, elementData, index + 1,
11                 size - index);
12         elementData[index] = element;
13         size++;
14     }

View Code

对比上面两个add方法，发现都出现了一个共同的函数ensureCapacityInternal，字面含义就是确保elementData有合适的容量大小。那么它的源码具体实现如下：

1 private void ensureCapacityInternal(int minCapacity) {
2         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
3   }
4 
5 note:这是一个私有方法，只在本类使用。是为了保证空间资源不被浪费，尤其是add方法中更需要特别注意。

View Code

在ensureCapacityInternal方法中我们又发现了ensureExplicitCapacity方法，这个函数也是为了确保elemenData数组有合适的容量大小。ensureExplicitCapacity的源码如下：

1  private void ensureExplicitCapacity(int minCapacity) {
2         // 将“修改统计数”+1，该变量主要是用来实现fail-fast机制的
3         modCount++;
4         // 防止溢出代码：确保指定的最小容量 > 数组缓冲区当前的长度
5         // overflow-conscious code
6         if (minCapacity - elementData.length > 0)
7             grow(minCapacity);
8     }

View Code

fail--fast机制？？？？溢出代码？？？,后面专门补充说明

这个方法中又调用了grow方法，具体实现如下：

 1 /**
 2      * 私有方法：扩容，以确保 ArrayList 至少能存储 minCapacity 个元素
 3      * - 扩容计算：newCapacity = oldCapacity + (oldCapacity >> 1);  扩充当前容量的1.5倍
 4      * @param minCapacity    指定的最小容量
 5      */
 6     private void grow(int minCapacity) {
 7         // overflow-conscious code
 8         int oldCapacity = elementData.length;
 9         int newCapacity = oldCapacity + (oldCapacity >> 1);
10         if (newCapacity - minCapacity < 0)
11             newCapacity = minCapacity;
12         if (newCapacity - MAX_ARRAY_SIZE > 0)
13             newCapacity = hugeCapacity(minCapacity);
14         // minCapacity is usually close to size, so this is a win:
15         elementData = Arrays.copyOf(elementData, newCapacity);
16     }

View Code

Note:真正的扩容操作还是在grow方法中实现的。

因此，当添加一个对象的时候，不一定会进行扩容，比如初始化数组就足够大，用来存放要添加的元素；又或者必须扩容。因此总结成如下图形，来表示当一个add操作发生时，方法调用过程（note:红色箭头表示可能会发生的调用）：

举例：

网上看到很好的两个例子，直接粘贴过来了。（源自：https://www.cnblogs.com/leesf456/p/5308358.html）

1）例一：扩容

      List<Integer> lists = new ArrayList<Integer>();
      lists.add(8);

说明：初始化lists大小为0，调用的ArrayList()型构造函数，那么在调用lists.add(8)方法时，会经过怎样的步骤呢？下图给出了该程序执行过程和最初与最后的elementData的大小

　　说明：我们可以看到，在add方法之前开始elementData = {}；调用add方法时会继续调用，直至grow，最后elementData的大小变为10，之后再返回到add函数，把8放在elementData[0]中。

2）例二：不扩容

   List<Integer> lists = new ArrayList<Integer>(6);
   lists.add(8);

说明：调用的ArrayList(int)型构造函数，那么elementData被初始化为大小为6的Object数组，在调用add(8)方法时，具体的步骤如下：

　　说明：我们可以知道，在调用add方法之前，elementData的大小已经为6，之后再进行传递，不会进行扩容处理。

（2）remove

 1 public E remove(int index) {
 2         rangeCheck(index);
 3 
 4         modCount++;
 5         E oldValue = elementData(index);
 6 
 7         int numMoved = size - index - 1;
 8         if (numMoved > 0)
 9             System.arraycopy(elementData, index+1, elementData, index,
10                              numMoved);
11         elementData[--size] = null; // clear to let GC do its work
12 
13         return oldValue;
14     }

View Code

 1 public boolean remove(Object o) {
 2         if (o == null) {
 3             for (int index = 0; index < size; index++)
 4                 if (elementData[index] == null) {
 5                     fastRemove(index);
 6                     return true;
 7                 }
 8         } else {
 9             for (int index = 0; index < size; index++)
10                 if (o.equals(elementData[index])) {
11                     fastRemove(index);
12                     return true;
13                 }
14         }
15         return false;
16     }

View Code

解释：该类中存在两个remove。前者是移除指定索引处的元素，此时会把指定索引到数组末尾的元素向前移动一个单位，并且会把数组最后一个元素设置为null，这样是为了GC回收。后者是移除指定的元素。

（3）set

1 public E set(int index, E element) {
2         rangeCheck(index);
3 
4         E oldValue = elementData(index);
5         elementData[index] = element;
6         return oldValue;
7     }

View Code

解释：修改了指定索引处的值。

（4）get

 1 public E get(int index) {
 2         rangeCheck(index);
 3 
 4         return elementData(index);
 5 }
 6 
 7 
 8 @SuppressWarnings("unchecked")
 9     E elementData(int index) {
10         return (E) elementData[index];
11     }
12 
13 
14 elementData经过了由object向下转型成为了E

View Code

三. ArrayList的性能分析

ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。

3.1 为什么随机访问效率高

通过get(int index)获取ArrayList第index个元素时。直接返回数组中index位置的元素，而不需要像LinkedList一样进行查找

3.2 为什么随机插入、删除效率低

通过上面的源码分析我们知道，add一个元素，将会调用ensureCapacity(size+1)，它的作用是“确认ArrayList的容量，如果容量不够，就增加容量”。继续追究原来是System.arraycopy(elementData, index, elementData, index + 1, size - index)这一句存在真正的耗时操作，这会导致index之后的元素移动，会造成index止呕的所有元素的改变。同理，remove方法也是如此。因此效率低。

3.3 当有大量数据需要添加时，怎么做提高效率

如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以减少增加重分配的次数提高性能。

3.4 ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性

Note:本文的部分内容来自：https://www.cnblogs.com/leesf456/p/5308358.html