一、综述

1.1 简介

ArrayList是支持动态扩容的非线程安全的列表。底层实现采用了数组，支持随机访问，所以查找速度快，但是增删慢（PS：尾部增删速度快）。

ArrayList不是线程安全的列表，并发修改时（add/remove），可能会抛出ConcurrentModificationException异常。可以通过Collections.synchronizedList或者外部操作保证线程安全保证并发修改安全。

1.2 继承关系

Iterable

标记接口，实现该接口即可通过foreach遍历集合。
Serializable

标记接口，实现该接口表明该类可以进行序列化操作。
RandomAccess

标记接口，实现该接口的集合支持快速随机访问。
Cloneable

实现该接口的类通过clone方法可以进行复制新类，否则会抛出CloneNotSupportedException异常。
Collection

java集合体系的根接口，定义通用的方法如size()，isEmpty()，add()，remove()等
AbstractCollection

提供了Collection的基本实现，为Collection的具体实现类减少大量重复工作。
List

有序列表
AbstractList

提供了List的基本实现。

1.3 子类

SubList

为ArrayList提供子列表操作。

剖析

ArrayList深度剖析，包括字段、构造、新增、删除、更新、遍历、序列化、排序、线程安全。

2.1 字段

本类字段

// 默认数组容量
private static final int DEFAULT_CAPACITY = 10;
// 用于ArrayList空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 用于默认大小空实例的共享空数组实例。
 * 我们将DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA区别开来
 * 以便在添加第一个元素时知道要膨胀多少。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存放元素的数组
 * 备注：字段不设置为私有，是为了方便内部类的访问
 * 思考：为什么不是E[]呢？
 */
transient Object[] elementData; 

// 数组实际元素数量
private int size;
复制代码

继承字段（AbstractList）

/**
 * 记录列表结构变化的次数。
 * 作用：提供了快速失败机制。采用迭代器顺序访问元素的情况下，如果modCount和集合的
 * expectedModCount值不相等，就会抛出ConcurrentModificationException异常。
 */
protected transient int modCount = 0;
复制代码

2.2 构造

// 1.创建一个指定数量的集合，如果initialCapacity必须大于等于0
// 等于0的情况下返回空数组实例
// 2.如果可以预估容量，请使用本方法构建实例，避免扩容时数组拷贝带来的性能消耗
public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
				  // 如果容量为0，则都指向同一个共享的空数组
          // 减少内存的占用
          this.elementData = EMPTY_ELEMENTDATA;
      } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }
复制代码

// 默认构造器，创建一个容量为10的ArrayList
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
复制代码

// 使用Collection的实现比如Set,List创建一个ArrayList
// 通常是Collection的实现进行相互转换
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // 使用空数组实现
        elementData = EMPTY_ELEMENTDATA;
    }
}
复制代码

2.3 修改

添加分为两种方式，一种是单个添加，另一种是批量添加

单个添加
- 流程图

- 流程说明
    1. 结尾处添加元素

        ```java
        /**
         * 在ArrayList结尾处添加元素e
         */
        public boolean add(E e) {
            // 添加元素之前根据size预先判断需不需要扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

        private void ensureCapacityInternal(int minCapacity) {
        		// // minCapacity为此时elementData必须的最小长度
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }

        // 如果是默认构造器生成ArrayList,在第一次添加
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            // 如果使用ArrayList()创建，默认容量=DEFAULT_CAPACITY=10
        		if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
        private void ensureExplicitCapacity(int minCapacity) {
            // 修改次数+1，用于fail-fast处理
            modCount++;
        		
        		// 如果minCapacity大于elementData的长度，则进行扩容处理
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
        				// 扩容，可能会引起溢出问题
                grow(minCapacity);
        }
        // ArrayList扩容核心代码
        private void grow(int minCapacity) {
            // overflow-conscious code
        		// 可能存在整型溢出
            int oldCapacity = elementData.length;
        		// 扩容后的大小默认等于扩容之前的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 如果默认扩容大小还小于最小容量，则以最小容量作为本次扩容后的容量大小
            if (newCapacity - minCapacity < 0)
                // 可能1：newCapacity<0整型溢出
                // 可能2：newCapacity<minCapacity
                newCapacity = minCapacity;
        	  // 如果默认扩容大小超过预先定义的数组最大阈值，则进行巨量扩容
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // 数组深拷贝
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

        // 说明ArrayList容量上限是可以达到Integer.MAX_VALUE
        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
        				// 整型已经溢出
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
        ```

    2. 指定位置添加元素

        ```java
        public void add(int index, E element) {
            // 检查位置合法性
            rangeCheckForAdd(index);
            // 跟add(E e)中处理方式类似
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            // 将elementData中位置为index位置及其后面的元素都向后移动一个下标
            //（底层是native方法，使用cpp直接操作内存。）
            // PS：间接验证了如果采用尾插法，那么数组插入操作性能极为可观
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
        private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        ```
复制代码

批量添加

从尾部开始全部插入

public boolean addAll(Collection<? extends E> c) {
    // 集合转化成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 跟add(E e)类似
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将集合内的元素复制到elementData中，覆盖[size, size+numNew)的元素
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
复制代码

从指定位置全部插入（涉及数组元素迁移）

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查位置合法性
    rangeCheckForAdd(index);
		// 集合转化成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 跟add(E e)类似
    ensureCapacityInternal(size + numNew);  // Increments modCount
		// 计算原数组需要往后移动多少个元素
    int numMoved = size - index;
    if (numMoved > 0)
        // 将elementData中位置为index及其以后的元素都向后移动numNew个位置
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 将集合内的元素复制到elementData中，覆盖[index, index+numNew)的元素
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}
复制代码

2.4 删除

单个删除

按索引删除元素

// 根据下标删除元素
// 注意：java5后引入自动装箱、拆箱的机制，因此产生了一个有趣的问题：
// 当类型变量为Integer的ArrayList调用remove时，可能调用remove(Object)，
// 也可能调用remove(Index)
// 一定要注意测试是否符合自己的预期
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
		// 如果被删除元素不是ArrayList的最后一个元素
    // 对应下标之后的元素向前移动一个下标
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 最后一个元素只为null，方便GC
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

E elementData(int index) {
    return (E) elementData[index];
}
复制代码

删除指定元素

// 删除ArrayList中第一次出现的特定元素
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
							// 比较对象时依赖equals方法
              // 因此类型变量E对应的类注意重写equlas方法
              // 重写时注意遵守规范，具体参考effective java第三版的第10、11两条规则
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 根据下标删除元素
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
		// 将elemenData中index+1及其后面的元素都向前移动一个下标
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 根据上一步的操作, size-1位置的对象向前移动了一个下标
    // 如果没有elementData[--size]==null，可能会导致内存泄漏
    // 试想，ArrayList被add了100个对象，然后被remove了100次。
    // 按照GC的机制来说，100个对象应该可以被GC掉（假设没有对象），
    // 但是由于还存在ArrayList的实例引用，对应的100个对象就无法删除
    elementData[--size] = null; // clear to let GC do its work
}
复制代码

批量删除

// 批量删除ArrayList和集合c都存在的元素
public boolean removeAll(Collection<?> c) {
		// 非空校验
    Objects.requireNonNull(c);
		// 批量删除
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
  final Object[] elementData = this.elementData;
  int r = 0, w = 0;
  boolean modified = false;
  try {
      for (; r < size; r++)
          // 把需要保留的元素前置
          if (c.contains(elementData[r]) == complement)
              elementData[w++] = elementData[r];
  } finally {
      // Preserve behavioral compatibility with AbstractCollection,
      // even if c.contains() throws.
     // 即使c.contains抛异常，也要保持跟AbstractCollection行为的兼容性
      // 备注：ArrayList重写了AbstractCollection中的removeAll方法，
      // removeAll调用了batchRemove
      if (r != size) {
				// 备注1：可能是上面的for循环出现了异常
        // 备注2：可能是其它线程添加了元素。
          System.arraycopy(elementData, r,
                           elementData, w,
                           size - r);
          w += size - r;
      }
      if (w != size) {
          // clear to let GC do its work
          for (int i = w; i < size; i++)
					// 跟fastRemove(int index)里面的操作类似，防止内存泄漏
              elementData[i] = null;
					// 思考：为什么addAll的modCount+1，而removeAll的modCoun+size-w
          // 个人以为modCount只是做标记做了结构的修改并且用来做校验。
          // 因此+1，+2 +size-w并没有本质区别
          modCount += size - w;
          size = w;
          modified = true;
      }
  }
  return modified;
}
// 思考：上面是按照元素进行批量删除，如何按照下标区间进行批量删除呢？
复制代码

批量保留

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
复制代码

清空

public void clear() {
    modCount++;

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

    size = 0;
}
复制代码

2.5 更新

更新指定位置的元素

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
复制代码

2.6 查找

查找

第一次出现

// 返回元素第一次出现的下标
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
复制代码

最后一次出现

// 返回最后一次出现的位置
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
复制代码

遍历

for

// for遍历
for (int i = 0; i < strList.size(); i++) {
     System.out.println(strList.get(i));
}
复制代码

foreach

// foreach
// 备注：只要实现Iterable接口，就能使用foreach
for (String s : strList) {
    System.out.println(s);
}
复制代码

foreach-lambda

// foreach-lambda遍历
strList.forEach(System.out::println);
复制代码

iterator

iterator（只能按照index从0到size进行遍历）

Iterator<String> iterator = strList.iterator();
 while (iterator.hasNext()){
      String str = iterator.next();
      System.out.println(str);
      // 下一次出现ConcurrentModificationException
      // 问题是因为list的iterator方法返回的是ArrayList的内部类Itr
      // Itr里面的expectedModCount会与ArrayList的modCount进行比较
      // 剩下的就不言而喻
      strList.remove(str);
      // 进行iterator遍历时，如果进行remove等操作，调用iterator的方法
      // 而不是ArrayList的方法
     //  iterator.remove();
}
复制代码

ListIterator（可以按照index从小到大进行遍历，也可以从大到小进行遍历）

// ListIterator可以进行顺序、逆序遍历，可以指定index位置开始遍历
ListIterator<String> iterator = strList.listIterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}
iterator = strList.listIterator(strList.size());
while (iterator.hasPrevious()){
    System.out.println(iterator.previous());
    iterator.remove();
}
复制代码

Spliterator（并行遍历，充份发挥多核优势）

// 使用并行遍历，可以将元素放在不同的迭代器进行并行遍历
Spliterator<String> spliterator = strList.spliterator();
// split，分而治之，类似算法里面的分治
Spliterator<String> otherSpliterator = spliterator.trySplit();
spliterator.forEachRemaining(System.out::println);
otherSpliterator.forEachRemaining(System.out::println);
复制代码

2.7 序列化

ArrayList的序列化没有直接序列化elementData，而是根据size序列化包含的元素，忽略数组中的其它位置，提高效率并节省空间。

序列化

private void writeObject(java.io.ObjectOutputStream s)
	throws java.io.IOException{
	// fail-fast，后续判断是否有并发处理
	int expectedModCount = modCount;
	// 序列化没有标记为static、transient的字段，包括size等。
	s.defaultWriteObject();
	
	// 没有意义，可以忽略
	s.writeInt(size);
	
	// 序列化元素
	for (int i=0; i<size; i++) {
	    s.writeObject(elementData[i]);
	}
	
	if (modCount != expectedModCount) {
	    // ArrayList被并发处理，发生结构性修改
	    throw new ConcurrentModificationException();
	}
}
复制代码

反序列化

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // 反序列化没有标记为static、transient的字段，包括size等
    s.defaultReadObject();

    // 可以忽略，跟writeObject里面的方法对应
    s.readInt(); 

    if (size > 0) {
        // 数组扩容
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // 反序列化元素并填充到数组中
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}
复制代码

2.8 排序

List<String> strList = new ArrayList<String>(4);
                   strList.add("1");
                   strList.add("2");
                   strList.add("3");

     // 可以使用以下三种排序方式
     Collections.sort(strList);
     Collections.sort(strList, String::compareTo);
     strList.sort(String::compareTo);

     //java8 新增的排序方法
     public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        // 底层使用合并排序算法进行排序
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
复制代码