前言

时间真是飞快，一转眼2019年四分之三的时间都快要过去了。从工作到现在也有三年时间了，之前一直有个愿望，希望自己能写出一篇从源码层次分析某个知识点的技术文章，但是一直没能抽出足够时间，也可能是一直胆怯怕写不好再被嘲讽，但还是鼓足勇气打算尝试下。
关于Java中的ArrayList集合，在日常的Android开发中是十分常见的，大部分开发者也知道怎么去用，但是其中的原理想必并不是每位开发者都精通的，而ArrayList也正是很多公司面试过程中必问的知识点。因此还是有必要对其原理进行一些了解的(后面的内容采取图文结合的方式进行讲解)。

ArrayList

1.介绍：

ArrayList是一种采用数组结构来保存对象的集合，它实现了List接口，同时也实现了Serializable接口。其优点是便于对集合进行快速随机的访问，适用于经常需要根据索引来访问集合中的对象的场景。缺点是向指定位置插入对象和删除指定索引位置的对象的速度比较慢(并且插入和删除对象的索引越小，效率越低，因为会同时改变后面的对象的索引)。

2.使用：

注：下文说到的当前集合中的数组均指elementData，集合中的对象都是保存在此数组中的。

(1) 构造方法：
首先是一个int类型参数的构造函数，根据值的不同，会出现三种情况

/**
 * 此构造方法传入一个int类型的参数，用于指定内部数组的长度。
 * 当var1值大于0时，内部将会重新创建一个新的数组，并将数组的长度指定为var1的值，最后指向当前集合中的数组；
 * 当var1值小于0时，将抛出非法状态异常；
 * 当var1值等于0时，内部不会重新创建数组，而是直接将当前集合中的数组指向已经创建好的一个空数组EMPTY_ELEMENTDATA；
 */
public ArrayList(int var1) {
        if (var1 > 0) {
            this.elementData = new Object[var1];
        } else {
            if (var1 != 0) {
                throw new IllegalArgumentException("Illegal Capacity: " + var1);
            }
            this.elementData = EMPTY_ELEMENTDATA;
        }
 }

接下来是无参的构造函数，注意这里面指向的空数组和上面的构造函数中的空数组并不是一个数组，这里肯定有人有疑问，既然都是空数组，那么为什么还要创建两个，这个问题后面会给大家提到。

/**
 * 此构造方法不需要传入任何参数，内部不会创建新的数组，而是直接将当前集合中的数组
 * 指向已经创建好的一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA；
 */
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

最后是需要传入一个实现了Collection接口的对象类型的参数的构造函数

/**
 * 此构造方法传入一个实现了Collection接口的对象类型的参数；
 * 首先将传入的对象通过toArray方法转换成一个数组类型的对象，并指向当前集合中的数组对象；
 * 然后判断当前集合中数组的length，如果大于0并且当前数组的类型不是Object[]类型时，会调用
 * Arrays.copyOf(U[] var0, int var1, Class<? extends T[]> var2)方法返回一个Object[]类型的数组并指向当前集合中的数组
 * 如果当前集合中数组的length为0，直接将当前集合中的数组指向已经创建好的一个空数组对象EMPTY_ELEMENTDATA；
 */
public ArrayList(Collection<? extends E> var1) {
        this.elementData = var1.toArray();
        if ((this.size = this.elementData.length) != 0) {
            if (this.elementData.getClass() != Object[].class) {
                this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
            }
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

(2) add(E var1)方法：
此方法是本人认为ArrayList几个常用的方法中包含知识点最多的一个方法了，所以建议仔细阅读，从上到下分别是方法中逐次调用到的方法。

/**
 * 该方法是向当前集合的数组中添加var1对象，是在当前数组的最后一位后面添加，返回的布尔值代表是否添加成功。
 * 方法中首先调用ensureCapacityInternal(this.size + 1)方法来进行扩容操作的处理，即内存空间的重分配；
 * 然后将数组的第size+1个索引指向var1对象。
 */
public boolean add(E var1) {
        this.ensureCapacityInternal(this.size + 1);
        this.elementData[this.size++] = var1;
        return true;
}

/**
 * 此方法用来对当前集合中的数组的容量进行判定，决定是否需要对数组进行扩容操作。
 * 方法中调用ensureExplicitCapacity(calculateCapacity(this.elementData, var1))方法，
 * 接下来先看calculateCapacity(this.elementData, var1)方法。
 */
private void ensureCapacityInternal(int var1) {
        this.ensureExplicitCapacity(calculateCapacity(this.elementData, var1));
}

/**
 * 此方法返回一个int值，上面方法传入进此方法的两个参数分别是当前集合中的数组对象和size+1;
 * 如果当前集合中的数组为DEFAULTCAPACITY_EMPTY_ELEMENTDATA对象，那么返回10和var1中的最大值，否则返回var1；
 * 这里用到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组，回顾上面我们用无参构造创建集合的时候，
 * 集合中的数组是指向该数组对象的，所以我们暂时可以把DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组当做一个区分标记。
 */
private static int calculateCapacity(Object[] var0, int var1) {
        return var0 == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ? Math.max(10, var1) : var1;
}

/**
 * 此方法中有一个判断逻辑，是判断var1值是否大于当前集合中数组的length，先忽略modCound自加逻辑；
 * 上面方法中传入此方法中的参数值有两种可能，一种是10，一种是size+1，
 * 当var1值大于当前集合中数组的length时，调用grow(var1)方法。
 */
private void ensureExplicitCapacity(int var1) {
        ++this.modCount;
        if (var1 - this.elementData.length > 0) {
            this.grow(var1);
        }
}

/**
 * 此方法中，逻辑比较多，我一个步骤一个步骤的解释：
 * 1.首先创建临时变量var2为当前集合中数组的length，
 * 2.然后创建临时变量var3为var2+(var2>>1)的值，这里涉及java的二进制移位运算了，
 * 对于移位运算还请自行科普，这里采用移位运算应该是扩容的一个算法逻辑了，
 * 大概设计者并不想数组每增加一个元素都扩容一次而采取的扩容策略吧；
 * 3.判断var3和var1的大小，如果var3小于var1，那么使var3=var1；
 * 4.当var3大于2147483639时，var3=hugeCapacity(var1);
 * 5.调用Arrays.copyOf(this.elementData, var3)方法返回一个新的数组对象并且赋值指向给当前集合中的数组，
 * 此时当前集合中数组的length变为var3。
 */
private void grow(int var1) {
      1.  int var2 = this.elementData.length;
      2.  int var3 = var2 + (var2 >> 1);
      3.  if (var3 - var1 < 0) {
              var3 = var1;
           }
      4.  if (var3 - 2147483639 > 0) {
              var3 = hugeCapacity(var1);
           }
      5.  this.elementData = Arrays.copyOf(this.elementData, var3);
}

/**
 * 此方法的逻辑很清晰，var0小于0时抛出异常；
 * 当var0大于2147483639时，返回2147483647，否则返回2147483639；
 * 这里其实我们也能知道了当前集合中数组的最大容量，即length的最大值也就是2147483647(Integer.MAX_VALUE)。
 */
private static int hugeCapacity(int var0) {
        if (var0 < 0) {
            throw new OutOfMemoryError();
        } else {
            return var0 > 2147483639 ? 2147483647 : 2147483639;
        }
}

现在，我们回顾下add(E var1)方法中所折射出的关于ArrayList的一些知识点。
首先，当我们采用无参的构造函数创建一个ArrayList时，如果首次调用add方法向集合中添加元素，那么集合首次会默认扩大其数组的容量(即数组的length)到10，当数组中的容量超过10以后，再进行扩容操作，至于每次扩容多少，就通过上面讲到的grow方法中的算法逻辑进行计算(需要掌握二进制移位运算的知识)，感兴趣的同学可以自行尝试计算下具体每次扩容的大小和规律。
其次，如果是通过另外两种构造方法创建的ArrayList集合，那么集合中数组的初始容量即为对应的int类型参数的值或者为传入的集合的size大小，然后首次调用add(E var1)方法便会对集合中的数组的容量进行扩容，扩容逻辑都是同样的。
最后，还要说的是通过grow方法中的逻辑我们可以知道，对于一个ArrayList集合来说，它的size是有范围的，即0-2147483647。
(3) add(int var1, E var2)方法：

/**
 * 此方法接收两个参数，分别为添加进集合的index索引值和插入集合中的元素对象。
 * 1.首先对第一个参数的合法性进行校验，详解见下面；
 * 2.在上面的add(E var1)方法中已经讲解过，这里不再赘述；、
 * 3.调用系统的arrayCopy方法对数组的内容进行复制操作，首先我们要对这个方法中的几个参数的含义有所了解。
     (1)第一个参数为被复制的对象元素；
     (2)第二个参数为从第一个参数(即被复制的对象)的第几个索引开始复制；
     (3)第三个参数为复制到的对象元素；
     (4)第四个参数为从第三个参数(即复制到的对象)的第几个索引开始赋值被复制的内容;
     (5)第五个参数为复制的内容的长度；
     (注：这里第2、4、5个参数的取值都是有范围的，相信根据其代表的意义大多数人能知道该如何取值，避免引起数组越界异常)
     现在应该明白步骤3操作的意义了吧，是将当前集合中的数组从第var1索引开始复制，复制长度为size-var1(即一直到结尾)，
     并且将复制的内容依然赋值到当前集合中的数组中，从第var1+1索引开始赋值，一直赋值到结尾；
     例：一个数组之前元素分别为"0"，"1"，,"2"，"3"，现在要从index=1添加一个元素，那么此步骤操作过后，
        数组的内容就变为"0"，"1"，"1"，,"2"，"3"。
 * 4.此操作对数组var1索引处对应的元素对象进行重新赋值，指向var2对象。
 * 5.当前集合的size增加1。
 */
public void add(int var1, E var2) {
       1. this.rangeCheckForAdd(var1);
       2. this.ensureCapacityInternal(this.size + 1);
       3. System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
       4. this.elementData[var1] = var2;
       5. ++this.size;
}

/**
 * 此方法主要判断传入的index是否合法，当传入的index小于0或者大于当前集合的size时，就会抛出数组越界异常。
 */
private void rangeCheckForAdd(int var1) {
        if (var1 > this.size || var1 < 0) {
            throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
        }
}

两个向集合中添加元素的方法认真读明白以后，剩下的一些常用的方法其实就看上去简单多了。
(4) get(int var1)：

/**
 * 此方法接收一个int类型参数，代表索引值，返回集合中index索引位置的元素对象。
 * rangeCheck方法首先校验传入索引值的合法性，原理类似于上面提到的rangeCheckForAdd方法，这里不再详细解释；
 * 如果index合法，那么返回当前集合中数组的index索引位置上的对象元素。
 */
public E get(int var1) {
        this.rangeCheck(var1);
        return this.elementData(var1);
}

(5) set(int var1, E var2)：

/**
 * 此方法接收两个参数，分别为int类型的index参数和一个元素对象，
 * 方法调用的结果是将集合中var1索引位置上的元素置为var2对象；
 * 首先，同样调用rangeCheck方法校验index的合法性；
 * 如果index合法，那么获取当前集合中数组的var1索引处的对象元素var3，并将该对象指向var2；
 * 最后返回var3。
 */
public E set(int var1, E var2) {
        this.rangeCheck(var1);
        Object var3 = this.elementData(var1);
        this.elementData[var1] = var2;
        return var3;
}

(6) remove(int var1)：

/**
 * 此方法接收一个int类型的参数，该参数的意义为一个index索引值，此方法调用后的结果是移除掉集合中index索引处的元素。
 * 此方法的内部实现和add(int var1, E var2)方法类似，只不过一个是向集合中增加元素，一个是从集合中移除元素。
 * 这个方法就不做过多的解释了，可参考add(int var1, E var2)方法的解析，我们重点看一下另一个从集合中移除元素的方法。
 */
public E remove(int var1) {
        this.rangeCheck(var1);
        ++this.modCount;
        Object var2 = this.elementData(var1);
        int var3 = this.size - var1 - 1;
        if (var3 > 0) {
            System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
        }
        this.elementData[--this.size] = null;
        return var2;
}

(7) remove(Object var1)：

/**
 * 此方法移除集合中和var1相同的对象，这个是否相同还要取决于当前集合中的对象所对应的类中的equals方法是如何定义的；
 * 首先判断传入的var1是否为空，当var1为null时，遍历当前集合中的数组，当发现数组中有null对象时，调用fastRemove(var2)方法
 * 将数组中索引为var2处的元素对象从数组中移除(fastRemove方法和上面讲到的remove(int var1)方法原理类似)；
 * 如果var1不为null，那么遍历当前集合中的数组，通过集合中元素对应的类的equals方法来判定数组中是否有和var1相等的对象，
 * 如果equals方法为true，那么就代表var1对象和当前数组中var2索引处所对应的元素对象相同，接下来就同样调用fastRemove方法，
 * 将数组中索引为var2处的元素对象从数组中移除。
 * 该方法的返回值代表是否移除了集合中和var1对象相同的元素对象。
 */
public boolean remove(Object var1) {
        int var2;
        if (var1 == null) {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (this.elementData[var2] == null) {
                    this.fastRemove(var2);
                    return true;
                }
            }
        } else {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (var1.equals(this.elementData[var2])) {
                    this.fastRemove(var2);
                    return true;
                }
            }
        }
        return false;
}

(8) indexOf(Object var1)：

/**
 * 此方法是用来获取集合中第一个和var1对象相同的对象元素的索引位置，方法内部实现原理和上面的remove(Object var1) 类似(不再赘述)。
 * 当返回-1时，说明当前集合中没有和var1对象“相同”的元素对象。
 */
public int indexOf(Object var1) {
        int var2;
        if (var1 == null) {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (this.elementData[var2] == null) {
                    return var2;
                }
            }
        } else {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (var1.equals(this.elementData[var2])) {
                    return var2;
                }
            }
        }
        return -1;
}

lastIndexOf(Object var1)方法内部基本和indexOf(Object var1)方法一致，只是在遍历集合中的数组时，是从后往前遍历的，因此返回的是最后一个和var1对象“相同”的元素对象的索引值。contains(Object var)方法内部就是调用了indexOf(Object var1)方法。
(9) clear()：

/**
 * 该方法清空集合中的数据，即将集合中数组的每一项元素都置为null，并且将size置为0(集合的容量没有变)。
 */
public void clear() {
        ++this.modCount;
        for(int var1 = 0; var1 < this.size; ++var1) {
            this.elementData[var1] = null;
        }
        this.size = 0;
}

(10) toArray()：

/**
 * 该方法将返回一个新的Object[]类型的数组对象，数组中的数据内容和集合中的数组(elementData)内容一样。
 */
public Object[] toArray() {
        return Arrays.copyOf(this.elementData, this.size);
}

3.总结：

以上详细剖析了ArrayList中十个常用的方法的实现原理，当然还有一些其他的方法也会被经常用到，但是其内部的实现原理基本都差不多，如果将以上我所列的方法中的实现原理都能读懂，那么相信日后你自己浏览ArrayList源码时，其他的方法你也同样能够读懂的。
最后，如果文章对您有帮助，还望点赞支持下。若本章哪里写的不对，也还望指出哈！