ArrayList继承关系分析

ArrayList创建

使用com.google.common.collect包中Lists类，通过Lists的静态方法创建ArrayList，该类还可以创建其他的list，如LinkedList、CopyOnWriteArrayList等。

List<T> result = Lists.newArrayList();

ArrayList注释

ArrayList属于java.util包下。
进入到ArrayList.java，作者的注释如下：

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 *
 * ArrayList是list接口的可调整大小的数组实现类。实现了所有list的操作，并且允许元素是null。
 * 除了实现list接口， 该类提供了手动操作数组size的方法。该类大致与vector一致，但它是线程不安全的。
 * 
 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.
 *
 * size，isEmpty，get，set，iterator和listIterator操作都是常量复杂度。add操作平均复杂度是常量，也就是说添加n个元素需要O(n)。
 * 所有其他操作大致是线性复杂度。常量因子比LinkedList实现类低。
 * 
 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.
 *
 * 每个ArrayList实例都有一个容量。容量是用于存储数组中元素的数组大小。容量保证至少大于数组的size。
 * 当添加元素到ArrayList时，它的容量会自动增长。扩容策略不确定，因为添加元素时消耗O(n)的时间。
 * 
 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 *
 * 程序在向ArrayList实例添加大量元素前，可以先调用ensureCapacity方法扩容。这样会减少重分配空间的次数。
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 *
 * 注意该类是线程不安全的，即非同步的。如果多个线程同时访问一个ArrayList实例，方法外一定要保证同步，才能至少有一个线程可以修改list结构。
 * 修改list结构是指添加或删除一个或几个元素，或是显示调整数组大小，仅仅set一个元素值不算修改结构。
 * 这通常是在使用ArrayList的某个对象上完成同步操作。
 * 
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 *
 * 如果不存在这样的对象（指上述在外部能保证同步的对象），list应该使用
 * Collections#synchronizedList Collections.synchronizedList此对象的包装类。最好在创建是使用此方法，以防访问时不同步。
 * List list = Collections.synchronizedList(new ArrayList(...));
 * 
 * <p><a name="fail-fast">
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 * 
 * 通过类的#iterator() iterator方法和通过#listIterator(int) listIterator方法返回的迭代器是快速失败的。
 * 如果在迭代器生成之后的任何时间使用除了ListIterator#remove() remove或者ListIterator#add(Object) add的方法来修改list结构，
 * 将会抛出ConcurrentModificationException异常。因此，面对并发修改时，迭代器会迅速干净的失败。
 * 而不是在未来不确定的时间里冒着武断、不确定性行为的风险。
 * 
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 
 * 请注意，无法保证迭代器的快速失效行为，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬保证。
 * 快速失败迭代器会尽可能抛出ConcurrentModificationException异常。
 * 因此编写依赖于此异常的正确性的程序是错误的，迭代器的Fail fast行为应仅用于检测错误。
 * 
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
 */
 public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承关系

ArrayList继承了AbstractList抽象类，实现了List，RandomAccess，Cloneable，Serializable四个接口

Serializable接口：用来序列化和反序列化类。

Cloneable接口：可以使用Object.clone()方法，该方法实现对类实例进行按字段复制，没有实现该接口调用clone方法时会抛CloneNotSupporteddException异常。

RandomAccess接口：这只是一个内部没有方法的接口，仅作为一个标记接口存在，表示List集合下的实现支持快速随机访问功能。

List接口：包含很多方法，如size、isEmpty、contains、iterator等。

AbstractList抽象类：此类提供了List接口的基本实现，以最小化实现由“随机访问”数据存储（例如数组）支持的该接口所需的工作量。实现不可变List集合时，继承该类，并实现其中的get()、size()方法。实现可变List集合时，还需要实现其中的set()方法，如果集合是可变长度集合，需要override其add()和remove()方法。
modCount值保证快速失败机制。

其中ArrayList还有一些内部类，如Itr、ListItr、SubList、ArrayListSpliterator。
Itr实现了Iterator方法hasNext和next方法，重写remove和forEachRemaining方法。其中expectedModCount会初始化为modCount值，迭代时会判断expectedModCount和modCount是否相等，不相等则快速失败。
ListItr继承Itr，实现ListIterator。它实现了向前向后遍历，以及添加修改等方法。
SubList继承AbstractList，实现RandomAccess，是一个对ArrayList局部操作的集合。
ArrayListSpliterator实现Spliterator类，主要有三个方法：

//通过"二分法"分隔List集合
public ArrayListSpliterator<E> trySplit() 
//消费其中单个元素，此时index会相应+1
public boolean tryAdvance(Consumer<? super E> action)
//遍历所有未消费的集合元素
public void forEachRemaining(Consumer<? super E> action)            

代码如下：

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    list1.add("hij");
    list1.add("klm");
    Spliterator spliterator = list1.spliterator();
    Spliterator trySplit = spliterator.trySplit();
    spliterator.forEachRemaining(str-> System.out.println(str));
    trySplit.forEachRemaining(str-> System.out.println(str));
}

输出结果：

hij
klm
abc
def

ArrayList的spliterator()方法返回的元素分隔符与ArrayList相同，但创建的分隔符为late-binding和fail-fast。 late-binding拆分器绑定到元素源，即Arraylist在第一次遍历/拆分/查询估计大小时，而不是在创建Spliterator时。
此外，它还可以单独和批量遍历元素。
分隔后，可以多线程地取遍历数组。

ArrayList常用方法

构造

ArrayList();//默认构造函数，提供初始容量为10的空数组
ArrayList(int initialCapacity);//构造指定初始容量的空数组
ArrayList(Collection<? extends E> c);//构造一个包含指定 collection 的元素的列表，元素顺序是该 collection 的迭代器返回顺序

代码如下：

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    

	//通过反射获取实际容量，即elementData的长度
    public static int getCapacity(ArrayList<?> arrayList) {
    
        Class<ArrayList> arrayListClass = ArrayList.class;
        try {
    
            Field field = arrayListClass.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] objects = (Object[])field.get(arrayList);
            return objects.length;
        } catch (Exception e) {
    
            e.printStackTrace();
            return -1;
        }
    }

    public static void main(String[] args) throws InterruptedException {
    
    	//空构造函数
        ArrayList<String> list1 = new ArrayList<>();
        //指定容量的构造函数
        ArrayList<String> list2 = new ArrayList<>(30);
        list1.add("abc");
        list1.add("def");
        list1.add("hij");
        //用其他collection初始化
        ArrayList<String> list3 = new ArrayList<>(list1);
        System.out.println("list1 = " + list1 + ",size = " + list1.size() + ", capacity = " +getCapacity(list1));
        System.out.println("list2 = " + list2+ ",size = " + list2.size() + ", capacity = " +getCapacity(list2));
        System.out.println("list3 = " + list3+ ",size = " + list3.size() + ", capacity = " +getCapacity(list3));
    }
}

输出如下：

list1 = [abc, def, hij],size = 3, capacity = 10
list2 = [],size = 0, capacity = 30
list3 = [abc, def, hij],size = 3, capacity = 3

从输出中也可以看到capacity的值的原则，空数组是默认10，指定容量即是指定的值。

添加

boolean add(E e);
void add(int index, E element);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);

代码如下：

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    //尾部追加元素
    list1.add("hij");
    System.out.println("list1 = " + list1);
    //在指定index增加元素
    list1.add(2, "xyz");
    System.out.println("list1 = " + list1);
    ArrayList<String> list2 = new ArrayList<>();
    list2.add("Willow");
    //批量增加元素
    list1.addAll(list2);
    System.out.println("list1 = " + list1);
    //在指定index批量增加元素
    list1.addAll(1,list2);
    System.out.println("list1 = " + list1);
}

输出如下：

list1 = [abc, def, hij]
list1 = [abc, def, xyz, hij]
list1 = [abc, def, xyz, hij, Willow]
list1 = [abc, Willow, def, xyz, hij, Willow]

遍历

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    list1.add("hij");
    //通过for循环索引值取元素值
    for (int i = 0; i < list1.size(); i++) {
    
        System.out.print(list1.get(i));
    }
    System.out.println();
    //通过foreach遍历
    for (String str:list1
         ) {
    
        System.out.print(str);
    }
    System.out.println();
    //通过迭代器遍历
    Iterator iter = list1.iterator();
    while (iter.hasNext()){
    
        System.out.print(iter.next());
    }
}

输出如下：

abcdefhij
abcdefhij
abcdefhij

注意：遍历ArrayList时，通过索引序号访问效率最高，而使用迭代器的效率最低。

修改元素值

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    list1.add("hij");
    System.out.println("list1 = " + list1);
    //设置指定index的值为某个新值
    list1.set(2, "Willow");
    System.out.println("list1 = " + list1);
}

输出如下：

list1 = [abc, def, hij]
list1 = [abc, def, Willow]

删除

E remove(int index);
boolean remove(Object o);
void clear();
boolean removeAll(Collection<?> c);
boolean removeIf(Predicate<? super E> filter);
//通过迭代器删除

代码如下：

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    list1.add("hij");
    list1.add("klm");
    list1.add("opq");
    list1.add("rst");
    System.out.println("list1 = " + list1);
    //删除指定index
    list1.remove(0);
    System.out.println("list1 = " + list1);
    //删除指定index
    list1.remove(0);
    System.out.println("list1 = " + list1);
    //删除指定元素
    list1.remove("rst");
    System.out.println("list1 = " + list1);
    //删除指定条件的元素
    list1.removeIf(str->str == "opq");
    System.out.println("list1 = " + list1);
    //情况
    list1.clear();
    System.out.println("list1 = " + list1);
}

输出如下：

list1 = [abc, def, hij, klm, opq, rst]
list1 = [def, hij, klm, opq, rst]
list1 = [hij, klm, opq, rst]
list1 = [hij, klm, opq]
list1 = [hij, klm]
list1 = []

注意：遍历删除时，一定要使用迭代器删除。代码如下：

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    list1.add("hij");
    list1.add("klm");
    list1.add("opq");
    list1.add("rst");
    System.out.println("list1 = " + list1);
    //遍历删除时使用迭代器
    Iterator iterator = list1.iterator();
    while (iterator.hasNext()){
    
        if ("klm".equals(iterator.next())){
    
            iterator.remove();
        }
    }
    System.out.println("list1 = " + list1);
}

输出如下：

list1 = [abc, def, hij, klm, opq, rst]
list1 = [abc, def, hij, opq, rst]

其他方法

public static void main(String[] args) throws InterruptedException {
    
    ArrayList<String> list1 = new ArrayList<>();
    list1.add("abc");
    list1.add("def");
    list1.add("hij");
    list1.add("klm");
    //是否包含某元素
    System.out.println("是否包含abc " + list1.contains("abc"));
    //某元素的index
    System.out.println("abc的位置 " + list1.indexOf("abc"));
    //获得某个index的元素值
    System.out.println("1位置元素值是 " + list1.get(1));
}

输出如下：

是否包含abc true
abc的位置 0
1位置元素值是 def

ArrayList其他

扩容机制
空ArrayList对象是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当第一个元素被添加时，数组容量会变成DEFAULT_CAPACITY。

    /**
     * Default initial capacity.默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     * 被用于空实例的共享空数组实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {
    };

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     * 被用于默认大小的空实例的共享数组实例。
     * 其与EMPTY_ELEMENTDATA的区别是，当我们添加第一个元素时，知道数组该扩充多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    };

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     * 存放ArrayList元素的数组缓冲区。ArrayList的容量就是这个数组缓冲区的长度。 
     * 添加第一个元素时，任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY。
     */
    // non-private to simplify nested class access
    // 非private是为了方便嵌套类的访问
    transient Object[] elementData; 
    /**
     * Constructs an empty list with an initial capacity of ten.
     * 构造空集合时初始容量是10
     */
    public ArrayList() {
    
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

注意容量（capacity ）和size不是一个值的。size是具体存了几个元素，而容量是可以存多少元素。
扩容函数如下：

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
    
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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;
    }

先将容量扩容1.5倍，与保证放下所有元素的最小容量比较，如果够，就扩容1.5，否则判断是否达到集合存储最大值，如果到达了按照hugeCapacity方法返回值扩充。

扩容使用Arrays.copyOf方法，底层是System.arraycopy方法，它是一个JVM提供的高效数组拷贝实现。

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

快速失败机制
ArrayList中通过modCoun来实现"Fail-Fast"的错误检测机制，当多个线程对同一集合的内容进行操作时，可能就会产生异常。
迭代器初始化是，会将modCoun赋值给expectedModCount，当进行一些修改结构的操作时，比如remove相关的，扩容，清空等操作时，modCount++，而迭代过程中判断expectedModCount和modCount是否一致，如果不相等，意味着有其他线程修改了结构，此时就会抛出ConcurrentModificationException异常。
比如清除方法中：

    public void clear() {
    
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

而Itr迭代器中有方法来判断值是否相等，是否抛异常：

        final void checkForComodification() {
    
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }