声明：我用的Java的版本是Java9版本。版本不同，源代码也有差异。

ArrayList源码中大量使用了一下两个函数，首先搞清楚这两个函数的含义

System.arraycopy()

// 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
/**
*   复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

举例：

1
2
3

int[] array = new int[]{10,23,24,15,12,45,23,56,12};
System.arraycopy(array,5,array,4,4);
System.out.println(Arrays.toString(array));//[10, 23, 24, 15, 45, 23, 56, 12, 12]

含义：将array数组的元素，从下标5为起始，4个元素，赋给array数组从4索引开始的位置上。这个实现的是一个数组删除操作。

Arrays.copyOf()

public static int[] copyOf(int[] original, int newLength) {
	// 申请一个新的数组
    int[] copy = new int[newLength];
	// 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

含义是：传入原始数组，复制出一个newLength长度的数组。

ArrayList底层实现是数组。

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

ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, **java.io.Serializable**。

RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了 Cloneable 接口 ，即覆盖了函数clone()，能被克隆。
ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

ArrayList成员变量

private static final int DEFAULT_CAPACITY = 10;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // non-private to simplify nested class access

private int size;

DEFAULT_CAPACITY定义了ArrayList的默认容量为 10。
MAX_ARRAY_SIZE要分配的数组的最大大小。
EMPTY_ELEMENTDATA和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA都定义了一个空数组。
- EMPTY_ELEMENTDATA = {}：空数组（用于空实例）
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}：
  - 用于默认大小空实例的共享空数组实例
  - 把它从EMPTY_ELEMENTDATA数组中区分出来，用来知道在添加第一个元素时容量需要增加多少。
elementData是ArrayList的底层实现，是一个Object数组。
size表明ArrayList当前存有多少元素。

ArrayList构造方法

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}


public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

ArrayList()

无参构造，将之前已经初始化的默认实例[DEFAULTCAPACITY_EMPTY_ELEMENTDATA]赋值给elementData

初始时容量为0，当添加第一个元素的时候数组容量才变成10
ArrayList(int initialCapacity)
- 带初始容量参数的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小）
  1. 如果initialCapacity大于0，就new一个Object数组。
  2. 如果initialCapacity等于0，将被赋值一个空实例EMPTY_ELEMENTDATA
  3. 如果initialCapacity小于0，抛出IllegalArgumentException异常。
ArrayList(Collection<? extends E> c)
- 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
  1. 首先将传入的集合转化为数组，赋值给elementData
  2. 如果elementData的长度不为0
    - 如果elementData的类型不是Object[]类型。c.toArray可能返回的不是Object类型的数组
      
      将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组
  3. 如果elementData的长度为0
    
    elementData被赋值为一个空实例EMPTY_ELEMENTDATA

ArrayList常用方法

ArrayList的常用方法有：

get()
add()
set()
remove()

`get()`方法

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

首先他会检查这个索引是否合法

然后调用elementData(index)方法，返回元素

1
2
3

E elementData(int index) {
    return (E) elementData[index];//进行了强制转换
}

`add()`方法

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

调用了add(E e, Object[] elementData, int s)方法，这是一个私有方法

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

这个是一个辅助方法，从add(E)中分离出来，以保持方法字节码大小小于35 。

E e：表示要插入的元素

Object[] elementData：表示要插入的数组

int s表示要插入的位置

首先判断，elementData是否已满，如果已经满了，再调用grow()方法进行扩容。
然后就是数组赋值操作了。

`set()`方法

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

首先他会检查这个索引是否合法
然后获取该索引位置原始元素
该索引位置被新元素所取代
返回旧元素

`remove()`方法

public E remove(int index) {
    Objects.checkIndex(index, size);//检查索引

    modCount++;
    E oldValue = elementData(index);//获取原始元素

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

需要将删除点之后的元素向前移动一个位置。

需要注意的是：为了让GC起作用，必须将最后一个元素置为null。

对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

ArrayList的扩容策略

一步一步的看ArrayList的扩容策略，扩容函数是grow()

1
2
3

private Object[] grow() {
    return grow(size + 1);
}

内部又调用了grow(size + 1)。

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

增加容量以确保它至少能容纳最小容量参数指定的元素数量。
参数:
minCapacity—期望的最小容量

返回一个从原始数组elementData，复制一个容量为newCapacity(minCapacity)是数组。从而进行扩容。

这个newCapacity(minCapacity)返回新的容量。newCapacity()是扩容的核心。

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

int newCapacity = oldCapacity + (oldCapacity >> 1)表明新的容量是旧的容量的1.5倍。

如果新的容量小于等于期望的最小容量：
1. 如果此时ArrayList的底层数组elementData是默认的空实例DEFAULTCAPACITY_EMPTY_ELEMENTDATA：
  
  则ArrayList至少扩容为默认容量10。Math.max(10, minCapacity)
2. 如果不是默认的空实例，但期望的最小容量小于0，就抛出异常。
3. 如果以上两种情况都不符合，就返回期望的最小容量。然后ArrayList就会扩容为期望的最小容量。

如果新的容量大于期望的最小容量：

检查这新的容量，是否小于，允许扩容的最大容量【Integer.MAX_VALUE - 8】。

如果小于，则返回新的容量，即ArrayList将扩容为旧容量的1.5倍。

如果大于，则调用hugeCapacity(minCapacity)函数，在对期望的最小容量进行进步判断。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

如果期望的最小容量大于允许扩容的最大容量，则ArrayList扩容为int整数的最大值。
否则ArrayList扩容为允许扩容的最大容量

扩容策略总结：

默认容量：10

最大扩容容量：Integer.MAX_VALUE - 8 = 2147483639

最小期望容量：当前容量+1

当添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组列表将被扩展为DEFAULT_CAPACITY。

即

如果ArrayList使用无参构造初始化，初次添加元素，会扩容为10。

其他情况，当需要扩容时

minCapacity最小期望容量为当前容量+1。

如果minCapacity<10，就会扩容为最小期望容量

如果minCapacity>10，新容量为原始容量的1.5倍。

如果这个新的容量小于允许最大容量，则扩容为原始容量的1.5倍。

如果这个新的容量大于允许最大容量

最小期望容量小于允许最大容量，则扩容为，允许的最大容量

最小期望容量小于允许最大容量，则扩容为，int整型的最大值。

并发修改异常

并发修改异常是发生在ArrayList使用迭代器遍历过程中，对ArrayList进行修改而发生的异常。

比如：

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>(4);
        arrayList.add(10);arrayList.add(23);arrayList.add(17);
        for (Integer integer : arrayList) {
            if(integer%5==0)arrayList.add(21);
        }
        System.out.println(arrayList);
    }
}

引发异常ConcurrentModificationException。

源码分析

我们知道增强式for循环，它本质是使用迭代器。

ArrayList 继承了AbstractList抽象类，它里面定义了一个变量modCount。

1
2
3

public abstract class A  AbstractList<E>{
    protected transient int modCount = 0;//跟进父类  初试为0
}

modCount表示预期修改次数。

public class ArrayList<E> extends AbstractList<E> implements List<E>{
    public Iterator<E> iterator() {
          return new Itr();//获取迭代器。
    }
    
    private class Itr implements Iterator<E> {
        int expectedModCount = modCount;//预期集合修改次数
        /*
            modCount:实际集合修改次数
            expectedModCount:预期集合修改次数
        */    
        public E next() {           
            checkForComodification();           
            int i = cursor;             
            if (i >= size)    
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)    
                throw new ConcurrentModificationException();  
            cursor = i + 1;     
            return (E) elementData[lastRet = i];  
        } 
        final void checkForComodification() {  
            if (modCount != expectedModCount)//不一样了，抛出异常 
                throw new ConcurrentModificationException();
            }
        }
    public boolean add(E e) { 
        modCount++;//实际操作次数++,预期的并没有++ 
        add(e, elementData, size); 
        return true; 
    }
}

当我们通过iterator()方法获取迭代器，expectedModCount = modCount此时预期修改次数和实际修改次数相等。

当调用迭代器的next()方法时，每次调用都会检查预期修改次数和实际修改次数是否相等，如果不相等就会抛出异常。

而，我们调用add()方法时，modCount++，实际修改次数加一，但预期修改次数不变。等下次调用next()的时候，就会引发并发修改异常。

除了add()方法，一下方法，在迭代器遍历过程中调用也会产生并发修改异常，因为它们内部也同样modCount++：

trimToSize()
ensureCapacity()
remove()
clear()
addAll()
removeRange()
batchRemove()

…….

附:查看集合容量的方法

//查看ArrayList集合容量方法 -- 反射
public static int getArrayListLength(ArrayList list) throws Exception{
    //获取Class对象
    Class c = Class.forName("java.util.ArrayList");
    //映射Class对象c所表示类(即Arraylist)的属性
    Field field = c.getDeclaredField("elementData");
    //设置访问状态表示为true
    field.setAccessible(true);
    //返回指定对象上此 Field 表示的字段的值
    Object[] object = (Object[])field.get(list);
    return object.length;
}

__END__

ArrayList源码解析

ArrayList成员变量

ArrayList构造方法

ArrayList常用方法

get()方法

add()方法

set()方法

remove()方法

ArrayList的扩容策略

并发修改异常

源码分析

附:查看集合容量的方法

`get()`方法

`add()`方法

`set()`方法

`remove()`方法