前言

前面一篇文章我们梳理了Kotlin集合接口相关的内容，本篇开始我们来梳理常用的具体集合。

本系列文章：

Kotlin集和1 — 集合类的父接口 – 掘金 (juejin.cn)

正文

首先来看一下List大家庭有哪些内容，直接看下面图即可：

从上面可知，我们经常用的大概就上面5个集合：

上面简单梳理了各种List的特性，本篇文章我们来梳理一下ArrayList的原理。

注释总结

看源码先看注释，ArrayList大概有100行的注释，其中介绍的还是比较全面的，这里就简单介绍几点，然后在后面源码分析中再做详细讲解。

可变数组实现List接口的集合，保存的元素可以为null。
size、isEmpty、get、set、iterator、listIterator这些方法调用是一个常量时间，和元素个数无关；add方法调用的时间复杂度是O(n)。
每个ArrayList实例都有一个容量，而这个容量大小就是用来保存元素的数组的大小，容量大小至少要大于或者等于元素的个数；每当有新元素加入到ArrayList中时这个容量就要判断是否需要增长，而增长的策略也是有考虑，是有时间成本的。
ArrayList是非同步的，当有多个线程访问一个ArrayList实例，并且至少有一个线程修改列表结构，就必须要从外部进行同步操作；这里的修改列表结构操作指的是增加、删除元素或者底层数组大小变化，仅仅是设置元素的值不是修改列表结构。
如果没有对应的线程安全的对象，可以使用Collections中的synchronizedList来让一个普通的ArrayList实例成为线程同步的对象。
由ArrayList返回的iterator是具有”快速失败”机制的，当ArrayList的iterator被创建后，凡是不是通过iterator进行的修改结构的操作都会直接报出 ConcurrentModificationException 异常；因此在面对并发修改问题上，迭代器直接干净、快速的返回失败，而不是在未来一段时间内在不确定的问题上冒险地做出不确定地行为。
同时，iterator地”快速失败”机制也不能完全保证，因为可以存在不同步的并发修改。

好了，上面就是ArrayList的注释总结，大概介绍了ArrayList的特点以及”快速失败”机制，那下面就从源码层面细节分析。

源码解析

源码代码不多，我们来看看。

保存的数组和构造函数

//默认数组容量
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//也是一个空数组，我们之所以分开是为了看第一个元素被添加进来时膨胀了多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存数据的数组，这个数组的大小就是容量
transient Object[] elementData; 
//ArrayList里元素的个数，注意这里和上面的容量指的是不一样的
private int size;
复制代码

这里使用了2个空数组，而且保存数据的数组类型都是Object，这也就证明了泛型在运行时会被擦除的实时。

还有一点就是保存数据的数组是通过 transient 修饰的，这说明当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;
}

//传入Collection
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;
    }
}
复制代码

注意Collection的toArray()是Collection中定义的方法，所以每种集合具体实现不一样。

扩容过程

说完初始化，来说一下扩容过程，扩容也是有讲究的，比如一次性扩容多少，一下子要添加很多元素该怎么办，是逐步扩容还是一次性扩容，我们就来分析分析。

会调用扩容的方法：

//增加一个元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
复制代码

//增加多个元素
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
复制代码

这里都会调用 ensureCapacityInternal 方法：

private void ensureCapacityInternal(int minCapacity) {
    //当原来是个空集合时，需要扩容的量小于10时，最小是默认容量10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
复制代码

//确定明确的容量
private void ensureExplicitCapacity(int minCapacity) {
    //结构改变
    modCount++;
    //期望的容量，比目前保存的容量大
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
复制代码

//扩容
private void grow(int minCapacity) {
    //原来的容量
    int oldCapacity = elementData.length;
    //新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //假如1.5倍后还满足不了，就采用期望值，以免再次扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //复制到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码

扩容会发现每次先建议为原来的1.5倍，假如期望的大小大于1.5倍，则直接采用期望值，以免二次扩容，因为扩容完需要进行数组复制，比较浪费资源。

增删改查

说完扩容的过程，也就到了每个集合喜闻乐见的操作即增删改查。

//直接add默认是加入到数组最后
public boolean add(E e) {
    //modCount会增加，即数据结构改变操作会增加
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}
复制代码

//某个位置插入一个元素
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    ensureCapacityInternal(size + 1); 
    //这里就比较费劲了，把从index开始包括index后面所有元素都进行复制到后面一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    //ArrayList大小++
    size++;
}
复制代码

//删除index位置的元素
public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //数据结构发生变化
    modCount++;
    //返回删除的元素
    E oldValue = (E) elementData[index];
    //同样费劲，index位置元素删除后，index位置后面所有元素都要向前移动一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //注意数组虽然赋值了新值，但是最后一个值还是之前保存的值
    //这里给赋值为null，可以加快GC
    elementData[--size] = null; 
    return oldValue;
}
复制代码

//删除ArrayList中的某个元素，会删除遍历到的第一个元素
public boolean remove(Object o) {
    //由于ArrayList可以保存null，所以先判空
    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++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
复制代码

//修改index位置的元素
public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //注意这个方法是不修改modCount值得
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}
复制代码

//没啥说得，这里可以直接通过数组下标得到
public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

ArrayList的增删改查还是蛮简单的，可以注意下面几点：

增和删都会修改结构，即modCount会变化。
增和删一般都会复制数组，耗时久，这也就是ArrayList的缺点，其中数组复制是使用System.arrayCopy方法，这个方法很常用。
查操作由于index和数组的index是对应的，所以查询时间是一个常量时间返回，这也就是ArrayList的优点。

遍历ArrayList

说起遍历ArrayList，我们一般有下面4种方式，我们来看一下：

使用迭代器进行遍历

//使用迭代器进行遍历
val list = arrayListOf(1,2,3,7,8,9)
val iterator = list.iterator()
while (iterator.hasNext()){
    println("value = ${iterator.next()}")
}
复制代码

这种遍历方式肯定没问题，我们来看看这里获取的迭代器：

//会发现每次获取迭代器时，都会创建一个新实例，而且迭代器实例不会
//提前获取，这个知识点后面有用到
public Iterator<E> iterator() {
    return new Itr();
}
复制代码

关于迭代器的实现，我们等会再说。

直接根据ArrayList长度来进行遍历

//index的值是0  ~ size-1
for (index in 0 until list.size){
    println("element = ${list[index]}")
}
复制代码

这种遍历方式不使用迭代器，直接进行get方法便可以获取所有的值。

快速遍历的方法，还有一种for循环是我们经常用的方式：

//for循环快速遍历
for (element in list){
    println("element = $element")
}
复制代码

对于这种方式，或许用的多，但是这里面调用的是什么原理或许不太了解，其实这个也是调用的是迭代器，但是它为什么可以写的这么简洁呢，其实就是Kotlin的约定。

我们来看一下Iterator的代码：

//接口
public interface Iterator<out T> {
    //运算符重载
    public operator fun next(): T

    public operator fun hasNext(): Boolean
}
复制代码

会发现这里的next和hasNext方法是通过operator修饰的，这里就涉及了一种约定，至于什么是约定我之前文章也说过，简单来说就是简化调用函数，比如这里的next函数和hasNext函数的简化调用就是我们前面所说的快速for循环了。

使用forEach来进行遍历：

list.forEach { it -> println("$it") }
复制代码

在KT代码中会发现这个forEach方法是个扩展函数，我们来看一下其实现：

//forEach源码
public inline fun <T> Iterable<T>.forEach(action: (T) -> Unit): Unit {
    for (element in this) action(element)
}
复制代码

会发现这里使用的是for循环，和上面串起来了，底层也是迭代器实现。

既然我们最常用的快速遍历都是使用的是迭代器，所以我们看一下迭代器的实现。

ArrayList的迭代器Itr

前面代码我们知道默认调用getIterator方法返回的是Itr实例，所以直接看一下Itr的源码：

//默认迭代器源码
private class Itr implements Iterator<E> {
    //即ArrayList元素个数
    protected int limit = ArrayList.this.size;
    //下一个即将返回的元素的下标，注意是即将返回
    int cursor;       
    //已经返回的元素的下标，即刚刚遍历过的元素的下标
    int lastRet = -1; 
    //期望的结构变化次数
    int expectedModCount = modCount;

    //还有没有下一个元素
    public boolean hasNext() {
        return cursor < limit;
    }

    //取出遍历的元素
    public E next() {
        //内外部结构变化次数不一样，直接抛异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        if (i >= limit)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        //cursor加1，注意这是下次要取出的元素的下标
        cursor = i + 1;
        //lastRet表示已经返回的元素下标
        return (E) elementData[lastRet = i];
    }

    //删除当前返回的元素
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        try {
            //调用ArrayList的删除方法
            ArrayList.this.remove(lastRet);
            //下一个遍历的下标，将是刚刚删除的下标
            cursor = lastRet;
            //已经返回的元素被删除了，所以置为-1
            lastRet = -1;
            //终于又赋值了
            expectedModCount = modCount;
            //保持正确的元素个数
            limit--;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}
复制代码

上面迭代器的代码非常简单，不过在取出元素和删除元素时都会可能会抛出 ConcurrentModificationException 异常，而这个异常就是迭代器的”快速失败“机制，我们就来好好看看这个异常的产生原因

ConcurrentModificationException异常

这个异常触发的条件非常简单，首先它只会在迭代器中抛出，其次当expectedModCount不等于modCount时即会抛出异常。

而这个expectedModCount会在迭代器实例创建时赋值为modCount，并且只会在调用迭代器的remove方法时，这2个值才会又设置为一样，所以当迭代器创建后，在迭代器遍历时modCount发生变化时就会抛出该异常。

而外部modCount变化即结构变化的操作也就是add和remove，所以记住一句话：在通过迭代器遍历时，想删除某个元素就使用迭代器的删除方法。

我们来看个例子：

val list = arrayListOf("hello", "android", "kotlin", "java", "arrayList")
for (element in list) {
    //在遍历时，发现某个值符合条件需要删除
    if (element == "android") {
        //调用ArrayList的删除方法
        list.remove("android")
    }
}
复制代码

果不其然，会抛出下面异常：

那正确的写法就是使用迭代器，而且删除使用迭代器里面的方法：

val list = arrayListOf("hello", "android", "kotlin", "java", "arrayList")
//调用迭代器
val iterator = list.iterator()
while (iterator.hasNext()){
    if (iterator.next() == "android"){
        //调用迭代器的方法
        iterator.remove()
    }
}
复制代码