[toc]

前言

主要通过源码分析，讲解几个ArrayList的常见方法

定义

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提供了随机访问功能，也就是通过下标获取元素对象的功能。
  • RandomAccess接口，标记接口，表明List提供了随机访问的功能，也就是通过下标获取对象功能，之所以是标记接口，是该类本来具备某项能力，使用接口进行标签化，便于其他的类别对其进行识别(instanceOf)
  • ArrayList数组实现，本身就有通过下标随机访问任意元素的功能，那么需要细节上注意的就是随机访问和顺序下标访问(LinkedList)的区别，也就是为什么LinkedList最好不要用循环遍历(因为LinkedList本身使用for循环进行查找元素)，而使用迭代器的原因
  • 实现RandomAccess同时意味着一些算法可以通过类型判断进行一些针对性的优化，例子有Collections的shuffle(洗牌将List打乱顺序)
  • 简单说就是如果实现RandomAccess接口就下标遍历，反之迭代器遍历(RandomAccess标注的使用下标遍历效率要优于迭代器遍历)
• 实现了Cloneable,java.io.Seriaalizable意味着可以被克隆和序列化。

常量和属性

//ArraysList的最大容量，但是有可能达到Integer.MAX_VALUE，扩容时候如果扩容之后的容量大于MAX_ARRAY_SIZE，那么需要进行判断，判断当前size+1与MAX_ARRAY_SIZE的关系，如果size+1>MAX_ARRAY_SIZE那么就会放弃-8的设定容量就会变为Integer.MAX_VALUE
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//这是一个共享的空的数组实例，当使用 ArrayList(0) 或者 
//ArrayList(Collection<? extends E> c)  并且 c.size() = 0 的时候讲 elementData 数组讲指向这个实例对象。
//他的第一次add时候的数组容量不会是默认的10
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小空实例的共享空数组实例。我们将（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）
//和EMPTY_ELEMENTDATA区别开来，以便在添加第一个元素时使用它来判断数组大小设置为DEFAULT_CAPACITY
//第一次add时候默认容量是10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/*属性*/

//存储ArrayList元素的数组缓冲区。 
//ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，
//任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空ArrayList都将扩展为DEFAULT_CAPACITY。
//elementData的初始默认容量为10，大小会根据ArrayList容量的增长而动态的增长
transient Object[] elementDate;
//ArrayList的大小（它包含的元素数）。
private int size;

注：DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次add时候容量默认值是10，而EMPTY_ELEMENTDATA不是
注： elementData.length不一定等于size，因为size是元素个数的统计，elementData.length是存储数据的数组的长度

构造方法

无参的构造方法

//构造一个初始容量为10的空列表。
public ArrayList() {
    //这里并没有初始化
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

无参的构造方法器，是我们经常使用的，其内部只是将elementData指向了DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个空数组，这个空数组容量是0，但是源码注释却说这是一个初始容量为10的空列表，这是为什么，其实在集合调用add方法添加元素的时候，将会调用ensureCapacityInternal确保内部容量的放到，过程如下(具体代码下面会说)：

• 初始时：this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};size=0
• 往数组中添加第一个元素的时候，add(E e)方法中调用了ensureCapacityInternal(size + 1);方法，即ensureCapacityInternal(1)
• 在ensureCapacityInternal(int minCapacity)方法中，minCapacity=DEFAULT_CAPACIITY=10，然后在调用ensureExplicitCapacity(minCapacity)，即ensureExplicitCapacity(10)
• 在ensureExplicitCapacity(int minCapacity)方法中调用grow(minCapacity)方法即grow(10)此处为真正具体的数组扩容算法，在此方法中，通过elementData = Arrays.copyOf(elementData, 10;具体实现了elementData数组初始容量为10的构造

指定初始化容量的构造方法

public ArrayList(int initialCapacity){
    if (initialCapacity > 0) {
        //如果初始化容量大于0创建对应大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0){
        //如果初始化容量大小为0,创建一个空的数组
        this.elementData = EMPTY_ELENENTDATA;
    } else {
        //初始化容量小于0抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity)
    }
}

如果我们预先知道一个集合元素的容纳个数，推荐使用呢这个构造函数，有人认为ArrayList自身具备了扩容机制，无需这么麻烦，但是每一次扩容有一定的内存开销，而这个开销在预先知道容量的时候可以避免的。

源代码中指定初始化容量的构造方法实现，判断了如果我们指定了容量大于0，将直接new一个数组赋值给elementData引用作为集合，的真正存储数组，而指定容量等于0时候将使用EMPTY_ELEMENTDATA这个空数组

使用另一个集合的Collection的构造方法：

//将构造一个包含指定集合元素的列表，其顺序由集合迭代器返回
public ArrayList(Collection<? extends E> c) {
        //将集合转为数组赋值到elementData
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                //进行拷贝
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.没有元素那么将elementData替换成空数组EMPTY_ELEMENTDATA
            //如果传入集合
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

添加元素add()

在集合末尾添加一个元素

//成员变量size标志集合当前元素个数初始化为0
int size;

public boolean add(E e) {
    //检查当前底层数组容量,如果容量不够则进行扩容
    ensureCapacityInternal(size + 1);  // 增加modConunt
    //将数组添加一个元素,size加一
    elementData[size++] = e;
    return true;
}

调用add方法时候总会调用ensureCapacityInternal来判断进行数组扩容(扩容代码稍后说)，ensureCapacityInternal参数为当前集合长度size+1，这个很好理解，是否需要扩充长度，需要看当前底层数组是否够放size+1个元素。

在指定角标位置添加元素方法

//将指定的元素插入该列表中的指定位置.将当前位置元素(如果有),和任何后续元素移到右边(将一个元素添加到他们的索引中)
public void add(int index, E element) {
    //检查角标是否越界
    rangeCheckForAdd(index);
    //扩容检查
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //调用native方法新型数组拷贝
    //第一个参数是拷贝的源数组,第二个参数是从index位置开始拷贝,第三参数:拷贝到目标数组,
    //第四个参数:拷贝到目标数组的起始位置 第五个参数:要复制的数组元素的数量。
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //添加新的元素                 
    elementData[index] = element;
    //size+1
    size++;
}

我们知道一个数组是不能在角标位置直接插入元素的，ArrayList通过数组拷贝的方法指定了角标位置，以及其后续元素整体向后移动一个位置空出index角标位置，来赋值新的值。

批量添加元素

由于批量添加和填一个元素逻辑大概相同，不详细说，代码注释可以了解整个添加过程

public boolean addAll(Collection<? extends E> c) {
    //转换为数组
    Object[] a = c.toArray();
    //数组的长度
    int numNew = a.length;
    //检查是否需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将参数集合中的元素添加到原来数组[size,size+numNew-1]的角标位置上
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    //与单一添加的add方法不同的是批量添加有返回值,如果numNew==0,表示没有添加的元素需要返回false
    return numNew != 0;
}

在数组指定角标位置批量添加元素

public boolean addAll(int index, Collection<? extends E> c) {
    //检查是否越界
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    //检查是否扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //这里做了判断,如果numMoved>0代表出任的位置在集合中间位置
    //和在 numMoved == 0最后位置 则表示要在数组末尾添加
    // 如果 numMoved< 0  rangeCheckForAdd 就跑出了角标越界
    int numMoved = size - index;
    if (numMoved > 0)
        //说明index在中间位置需要将中间位置空开
        //先将元素数组从指定角标位置开始移动numNew个长度
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //将需要添加数组拷贝到对应位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

int numMoved = size - index;中numMoved，如果numMoved>0说明是在数组中间位置批量插入，需要移动数组空出中间位置，如果如果numMoved=0说明是在数组尾部插入，如果numMoved<0那么rangeCheckForAdd()就会抛出异常。

扩容

相关代码如下：

//检查当前底层数组容量,如果容量不够进行扩容
private void ensureCapacityInternal(int minCapacity) {
    //将size+1或者10传入ensureExplicitCapacity进行扩容判断
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果是无参构造方法的集合,第一次添加元素的时候满足这个条件minCapacity将会赋值为10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    //操作数加1,用于保证并发访问
    modCount++;

    // 如果当前数组长度比添加元素的长度要小则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

上面代码主要是做了扩容机制的判断操作，注意参数为当前集合个数加1，第一次添加元素的时候size+1=1，而elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA长度为0，需要进行扩容就是调用grow函数

扩容函数grow()

private void grow(int minCapacity) {
    // 获取当前elementData的大小,也就是list中当前的容量
    int oldCapacity = elementData.length;
    //oldCapacity >> 1 等价于oldCapacity/2,所以新容量是当前容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩容1.5倍仍旧比minCapacity小,那么直接等于minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
     //如果新数组大小比MAX_ARRAY_SIZE大需要进一步比较minCapacity和MAX_ARRAY_SIZE的大小   
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity通常接近size大小
    //使用Arrays.copyOf构建一个长度为newCapacity新数组,并将elementData指向新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//比较 minCapacity 与 Integer.MAX_VALUE - 8 的大小如果大则放弃-8的设定，设置为 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;
}

由此看来ArrayList的扩容机制知识点包含两个：

• 每次扩容大小是原来的1.5倍(当然不包括1.5倍之后大于MAX_ARRAY_SIZE的情况)
• 扩容你过程其实是一个将原来元素拷贝到一个扩容后数组大小的长度新数组中，所以ArrayList的扩容其实相对来说比较耗时的

删除元素

其实删除元素和移除指定角标的元素最终都是通过System.arraycopy贾昂index之后的元素前移以为，并释放原来size位置的元素方便GC，整个过程还是数组拷贝

根据角标移除元素

//将任何后续元素移到左边(从他们索引中减去1)
public E remove(int index) {
    //检查是否会数组越界
    rangeCheck(index);

    modCount++;
    //index位置的元素
    E oldValue = elementData(index);
    //需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //采用拷贝赋值的方法将index之后的所有元素向前移动一个元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //将element末尾元素设置为null                     
    elementData[--size] = null; // 让GC开始工作
    //返回index的元素
    return oldValue;
}

删除指定元素

删除指定元素其实是删除第一个出现的，如果重复，那么删除的是一个出现的

//删除指定元素,如果存在返回true,如果不存在返回false
//更准确的说是删除集合中第一个出现o的元素位置的元素
//也就是说只会删除一个,并且如果有重复的话,只会删除第一个出现的
public boolean remove(Object o) {
    //如果元素为空则只需要判断==也就是内存地址
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //得到第一个等于null的元素角标移除该元素返回false
                fastRemove(index);
                return true;
            }
    } else {
        //如果元素不为空则需要使用equals判断
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                //得到第一个等于o的元素角标并移除该元素,返回true
                fastRemove(index);
                return true;
            }
    }
    return false;
}
//移除元素的逻辑和remove(index)一样
private void fastRemove(int index) {
    modCount++;
    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
}

批量移除/保留 removeAll/retainAll

ArrayList还提供了removeAll/ratainsAll操作，这两个操作分别是批量删除与参数集合共享有元素和批量删除与参数集合不共享的有元素，保留共享元素

//删除与参数集合共享数据
public boolean removeAll(Collection<?> c) {
    //判断是否为空
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
//保留与参数集合相同元素(删除与参数集合所有不同元素)
public boolean retainAll(Collection<?> c) {
     //判断是否为空
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
//批量删除
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    //r为elementData中元素的索引,w为删除元素后集合的长度
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //判断c集合中是否包含elementData[r]元素,然后根据complement是true还是false,进行判断
            //判断是否保留元素
            if (c.contains(elementData[r]) == complement)
                //进入里面的条件是,c不包含elementData[r],并且complement为false说明是调用方法是removeAll
                //c包含elementData[r],并且complement为true,说明调用方法是retainAll
                //保留元素
                elementData[w++] = elementData[r];
    } finally {
        // 如果c.contains(elementData[r])可能会抛出异常，
        //如果抛出异常后 r!=size 则将 r 之后的元素不在比较直接放入数组
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            //w加上剩余元素长度                 
            w += size - r;
        }
        //如果集合移除过的元素,则需要w之后的元素设置为null,方便gc释放内存
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    //返回是否修改成功,哪怕移除一个
    return modified;
}

可以看出移除指定集合包含的元素方式代码逻辑如下：

• 从0开始遍历elementData判断r位置元素是否在指定集合c中，在由complement进行判断，判断该元素是删除还是保留
• 由于c.contains(o)可能会抛出异常ClassCastException/NullPointerException如果因为异常终止，那么我们会将产生异常操作的错误，所以finally中执行了判断操作，如果r!=size那么肯定发生了异常，那么直接将r之后的元素不在比较直接放入数组中，最终得到结构不一定是删除了所有与c相关的元素

ArrayList的get与set方法

public E get(int index) {
    //检查数组越界
    rangeCheck(index);
    //返回对应的值
    return elementData(index);
}
public E set(int index, E element) {
    //检查数组越界
    rangeCheck(index);
    //获取旧的值
    E oldValue = elementData(index);
    //赋予新的值
    elementData[index] = element;
    //返回旧值
    return oldValue;
}
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

判断是否包含元素和获取元素的下标

//集合中是否包含元素,indexOf返回-1表示不包含 return false 否则返回true包含
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
//返回集合中第一个与o相同的元素角标,返回-1表示不存在这个元素
//这里还做了空元素直接判断==
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;
}
//获取最后出现o位置的索引,从 elementData 末尾开始遍历遍历数组，所以返回的是集合中最后一个与 o 相等的元素的角标
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;
}

toArray方法

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
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;
    }

第一种直接进行数组拷贝，变成Object[]类型数组，第二种是转成指定数据类似的数组
但是都是数组拷贝

ArrayList与Vector的共同点和区别

共同点

两者底层都是数组

区别

• ArrayList线程不安全Vector线程安全
• ArrayList每次扩容是1.5倍，而Vector可以通过capacityIncrement设置每次扩容的增量，如果没有设置那么每次扩容是原数组的2倍

总结

• ArrayList底层是一个动态扩容的数组结构，每次扩容需要增量是1.5倍容量
• ArrayList扩容底层通过Arrays.copyOf和System.arraycopy来实现的，每次会产生新的数组和数组中的内容拷贝，所以会耗费性能，所以在多增删操作情况下游戏考虑LinkedList而不是ArrayList
• 运行存放(不止一个)null元素
  允许存放重复数据，存放顺序按照元素的添加顺序
• ArrayList并不是一个线程安全的集合，如果考虑线程安全推荐使用CopyOnWriteArrayList