数组

• 简单：数组是一种最简单的数据结构
• 占据连续内存：数组空间连续，按照申请的顺序存储，但是必须制定数组大小
• 数组空间效率低：数组中经常有空闲的区域没有得到充分的应用
• 操作麻烦：数组的增加和删除操作很麻烦

ArrayList 应用场景

优点：尾插效率高，支持随机访问。
缺点：中间插入或者删除效率低。

排序不要使用 ArrayList，经常增删改变位置不要用 ArrayList，效率很低。
只存放，随机访问，可以使用 ArrayList。
ArrayList 顺序删除节点要用迭代器从尾部往前删，如果从前往后删的话，会频繁触发 System.arraycopy。
遍历 ArrayList 尽量使用迭代器。

优化ArrayList

如果我们要在集合中添加一百万个数据，它只能是通过每次扩容1.5倍，每次将原数组数据放入新的数组，很明显非常消耗资源。

构造方法

在构造ArrayList时传入一个整型，就会直接构造一个该长度的集合，避免一直扩容造成的资源浪费。

使用普通方法

还可以使用ensureCapacity(int minCapacity)方法。参数为扩容为目标大小。
如果要加入大量的数据，这种方式可以比传统方式快10倍以上，加入数据越多，越明显。

线性表

为了应对数组的缺点，可以使用线性表。
按物理结构划分：顺序存储结构（顺序表）、链式存储结构。

顺序表（ArrayList）

a1 是 a2 的前驱，ai+1 是 ai 的后继，a1 没有前驱，an 没有后继。
n 为线性表的长度 ，若 n==0 时，线性表为空表。
它继承于AbstractList，实现了List、RandomAccess、Cloneable、 Serializable等接口。

ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

ArrayList实现了RandmoAccess接口，即提供了随机访问功能。RandomAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们可以通过元素的序号快速获取元素对象，这就是快速随机访问；实现了Cloneable接口，能被克隆；实现了Serializable接口，因此它支持序列化，能够通过序列化传输。

封装了数组：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    transient Object[] elementData;
    private int size;
}

ArrayList源码详解

ArrayList内部通过一个Object数组来存储数据：

transient Object[] elementData;

ArrayList使用size变量来表示实际存储的元素个数：

private int size;

ArrayList有以下三个构造方法：

// 根据initialCapacity来创建具有指定初始容量的ArrayList
public ArrayList(int initialCapacity)
// 创建一个默认的ArrayList
public ArrayList()
// 根据其他集合来创建ArrayList
public ArrayList(Collection<? extends E> c)

详细看一下这三个构造方法：

public ArrayList(int initialCapacity) {
    // 创建指定初始容量的ArrayList
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    }
    // 初始化容量指定为0，则用EMPTY_ELEMENTDATA数组
    else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    }
    // 否则，抛出IllegalArgumentException异常
    else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    }
}

EMPTY_ELEMENTDATA定义如下（即长度为0的Object数组）：

private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList() {
    // 默认ArrayList的内部数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA声明如下：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA是一样的，都是定义为了长度为0的Object数组，那它们有什么区别呢？它们两个的主要区别在于添加第一个元素时，若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，则程序会将其扩充为容量为DEFAULT_CAPACITY的数组，DEFAULT_CAPACITY定义为10，即通过默认的构造方法创建的ArrayList的初始容量是10。我们后面会详细介绍数组的扩容。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 通过反射获取数组类型，判定c.toArray类型是否为Object[]类型
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 若c为空，则内部数组为EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

ArrayList有两个重载的Add方法：

// 在数组elementData尾部添加一个元素
public boolean add(E e)
// 在数组elementData指定位置index处添加元素
public void add(int index, E element)

add(E e)方法

我们先来看add(E e)方法，源码如下：

// 在数组elementData尾部添加一个元素
public boolean add(E e) {
    // 容量大小判断
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

该方法首先要判断elementData数组的容量是否能够容纳新的元素，若不能，则需要进行扩容操作，然后将元素e放置在数组的size位置。ensureCapacityInternal(int)方法源码如下：

private void ensureCapacityInternal(int minCapacity) {
    // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // minCapacity = max(10, minCapacity)
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 针对数组最小容量，决定是否扩容
    ensureExplicitCapacity(minCapacity);
}

前面讲到的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在这里就起到作用了，若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则会将数组的最小容量设置为10。然后通过ensureExplicitCapacity(int)方法来判断是否要扩容：

private void ensureExplicitCapacity(int minCapacity) {
    // 增加修改次数
    modCount++;
 
    // overflow-conscious code
    // 增加元素后，ArrayList中要存储的元素个数为minCapacity
    // 若此时minCapacity > elementData原始的容量，则要按照minCapacity进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

扩容的最终操作是通过grow(int)方法来实现的：

private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取elementData的原始容量
    int oldCapacity = elementData.length;
    // 计算新的容量
    // 若原数组长度为偶数，那么新数组长度就恰好是原数组长度的1.5倍
    // 若原数组长度为奇数，那么新数组长度就恰好是原数组长度的1.5倍 - 1
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 若按照1.5倍进行扩容后，capacity仍然比实际需要的小，则新容量更改为实际需要的大小，即minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新数组的长度比虚拟机能够提供给数组的最大存储空间大，则将新数组长度更改为最大正数：Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 按照新的容量newCapacity创建一个新数组，然后再将原数组中的内容copy到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容函数整体比较好理解，需要注意的是，若新容量过大，则会通过hugeCapacity(int)方法来进行容量判断：

private static int hugeCapacity(int minCapacity) {
    // minCapacity < 0则表明数组容量已经超过了虚拟机所能表示的最大容量，抛出OutOfMemoryError
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 否则，若minCapacity > MAX_ARRAY_SIZE，则数组容量为Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int index, E element)方法

add(int index, E element)方法源码如下：

public void add(int index, E element) {
    // 判断下标index的合法性
    rangeCheckForAdd(index);
 
    // 数组容量判断
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 数组拷贝，将index到末尾的元素拷贝到index + 1到末尾的位置，将index的位置留出来
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

该方法与add(E e)方法类似，只是元素的插入位置不同，该方法需要调用rangeCheckForAdd(int)方法来对index进行合法检验：

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

若index下标不合法，则抛出IndexOutOfBoundsException异常。

remove方法

remove方法在ArrayList中同样有两种实现方式：

// 根据index下标删除元素
public E remove(int index)
// 根据元素删除
public boolean remove(Object o)

remove(int index)方法

remove(int index)方法源码如下：

public E remove(int index) {
    // 下标合法性检验
    rangeCheck(index);
 
    // 修改次数加1
    modCount++;
    // 获取旧的元素值
    E oldValue = elementData(index);
 
    // 计算需要移动的元素个数
    int numMoved = size - index - 1;
    // 将元素向前移动
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    // 将最后的元素值设置为null
    elementData[--size] = null; // clear to let GC do its work
 
    return oldValue;
}

这里需要注意一点的就是rangeCheck(int)方法：

private void rangeCheck(int index) {
    // 若index下标超出size，则抛出IndexOutOfBoundsException异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

这里只判断了index超出了size，而不需要判断index为负数的情况，这是为什么呢？

因为该方法总是在访问数组之前被调用，在访问数组时，会对下标为负数进行判断，如果index为负数，则会抛出ArrayIndexOutOfBoundsException异常，所以在这里就没有必要判断了，避免冗余。

remove(Object o)方法

remove(Object o)方法源码如下：

public boolean remove(Object o) {
    // 若删除的元素为null
    if (o == null) {
        for (int index = 0; index < size; index++)
            // 若数组元素为null，则调用fastRemove方法快速删除
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } 
    // 若删除的元素不为null
    else {
        for (int index = 0; index < size; index++)
            // 找到要删除的元素，调用fastRemove方法快速删除
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

ArrayList删除元素时，是分为元素为null和不为null两种方式来判断的，这也说明ArrayList允许添加null元素；同时，如果这个元素在ArrayList中存在多个，则只会删除最先出现的那个。

删除元素，采用了fastRemove(int)方法来快速删除：

private void fastRemove(int index) {
    // 修改次数加1
    modCount++;
    // 计算需要移动的元素数目
    int numMoved = size - index - 1;
    // 将index之后的元素向前移动一位
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    // 将数组最后一位置为null
    elementData[--size] = null; // clear to let GC do its work
}

其他相关方法介绍

trimToSize()

trimToSize()源码如下：

public void trimToSize() {
    // 修改次数加1
    modCount++;
    // trim
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

该方法的主要工作就是将数组容量修改为size大小，若size为0，则将数组设置为EMPTY_ELEMENTDATA，否则，通过Arrays.copyOf方法来创建新的数组。

该方法的主要存在意义就是：如果capacity被分配过大，那么可以通过这个方法，将ArrayList实例的capacity的大小修改为数组存储元素的个数，从而缩减ArrayList的存储空间。

contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
 
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;
}

toArray()

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

该方法有可能会抛出java.lang.ClassCastException异常，如果直接用向下转型的方法，将整个ArrayList集合转变为指定类型的Array数组，便会抛出该异常，而如果转化为Array数组时不向下转型，而是将每个元素向下转型，则不会抛出该异常，显然对数组中的元素一个个进行向下转型，效率不高，且不太方便。

toArray(T[] a)

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

该方法可以直接将ArrayList转换得到的Array进行整体向下转型（转型其实是在该方法的源码中实现的），且从该方法的源码中可以看出，参数a的大小不足时，内部会调用Arrays.copyOf方法，该方法内部创建一个新的数组返回，因此对该方法的常用形式如下：

public static Integer[] toArray(ArrayList<Integer> v) {
    Integer[] array = (Integer[])v.toArray(new Integer[0]);
    return array;
}

Arrays.copyOf()、System.arraycopy()

ArrayList的源码中大量地调用了Arrays.copyof()和System.arraycopy()方法，我们下面深入详解一下这两个方法：

ArrayList中用的比较多的Arrays.copyOf()方法定义如下：

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

该方法调用了其重载方法：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
    return copy;
}

该方法实际上是在其内部又创建了一个长度为newlength的数组，调用System.arraycopy()方法，将原来数组中的元素复制到了新的数组中，下面来看System.arraycopy()方法：

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

该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码：

static void pd_conjoint_oops_atomic(oop* from, oop* to, size_t count) {
  // Do better than this: inline memmove body  NEEDS CLEANUP
  if (from > to) {
    while (count-- > 0) {
      // Copy forwards
      *to++ = *from++;
    }
  } else {
    from += count - 1;
    to   += count - 1;
    while (count-- > 0) {
      // Copy backwards
      *to-- = *from--;
    }
  }
}

JVM源码主要思想就是，创建一个新的数组，然后通过上述方法将原数组的数据移动到新数组中。从注释中可以看到，这种实现方式要优于C语言的memmove()方法，因为memmove()方法还需要进行内存清理工作。

该方法可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

fail-fast机制

在ArrayList的源码中，我们经常会看到modCount++这样的代码，其实，modCount是用来实现fail-fast机制的，fail-fast机制是Java集合中的一种错误机制，当多个线程对同一个集合的内容进行操作时，就会发生fail-fast事件，它是一种错误检测机制，只能被用来检测错误，因为JDK并不一定保证fail-fast机制一定会发生。fail-fast机制会尽最大努力来抛出ConcurrentModificationException异常。

fail-fast机制产生的最初原因是在于程序在对Collection进行迭代时，某个线程对该Collection的结构进行了修改。这时迭代器会抛出ConcurrentModificationException异常，从而产生fail-fast事件。如果单线程违法了规则，也同样会抛出此异常。

迭代器在调用next()、remove()等方法时都要调用checkForComodification()方法：

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

该方法主要是检测modCount是否等于expectedModCount，若不等于，则抛出ConcurrentModificationException异常。

在创建迭代器时，会将modCount的值赋给expectedModCount，所以在迭代期间，expectedModCount不会改变，在ArrayList中，无论add、remove还是clear方法，只要改变了ArrayList的元素个数，都会导致modCount改变，从而可能导致fail-fast产生。

fail-fast解决方案

1、在遍历过程中，所有涉及到改变modCount的地方全部加上synchronized或直接使用Collections.SynchronizedList。但不推荐该方案，因为增删产生的同步锁可能会阻塞遍历操作。

2、使用CopyOnWriteArrayList来替换ArrayList，比较推荐该方案。

CopyOnWriteArrayList是 ArrayList的一个线程安全的变体，其中所有可变操作（add、remove等）都是通过对底层数组的一次复制来进行操作的，在以下情况很适用：

• 在不能或不想进行同步遍历，但是又需要从并发中消除冲突时；
• 遍历操作的数量大大超过了可变操作的数量，即读多写少时。
  CopyOnWriteArrayList在copy的数组上进行修改，这样就不会影响原数组中的数据，修改完之后，改变原有数据的引用即可。

对CopyOnWriteArrayList采用了一种读写分离的思想，对CopyOnWriteArrayList进行读取操作不需要加锁。但它存在以下缺点：

• 因为要复制一份底层数组，所以内存占用比较多；
• CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性。

所以，编写程序时，要进行权衡利弊来选择合适的数据结构。

原文链接：Java集合之ArrayList详解_DivineH的博客-CSDN博客
参考：Java 线性表——ArrayList & LinkedList - 少元 - 博客园 (cnblogs.com)