Java源码分析（三）ArrayList

    ArrayList是我们经常用到的一个集合类。数组在创建时就要给一个明确的大小，而ArrayList的长度是可以动态调整的，因此，也叫动态数组。那么本篇我们一起学习下ArrayList的源码。

一、创建ArrayList

    首先，我们从创建ArrayList开始。上面也提到过，ArrayList的长度是可以动态调整的，我们通常创建一个不指定容量的数组。例如如下代码，创建一个空的ArrayList：

List<String> list = new ArrayList<>();

    看下构造方法的源码：

    代码注释说：构建一个容量为10的空List。List是基于数组来实现的，可以看到，构造方法这里创建了一个空的数组。咦？没看到容量为10啊，这个后面我们会介绍到。

二、添加元素

1、add

    创建好一个空的ArrayList后，我们调用add方法往里面添加元素，如下：

list.add("a");
list.add("b");
list.add("c");

    看下add方法的源码：

    核心是调用了红框中的add方法，看下其实现：

    可以看到，判断size是否达到了数组的长度，如果达到了长度，调用grow()方法扩容，然后把元素赋值给size的位置，对size加1。 简单总结：

   1扩容2赋值3加一。

2、扩容原理

    接下来，看下grow函数是怎么扩容的：

    基于当前的数组和新的容量（size + 1）复制新的容量的数组 ，看下newCapacity函数是如何去确定新的数组的容量的：

    代码注释机翻一下：返回至少与给定最小容量一样大的容量。如果足够的话，返回增加50%的当前容量。除非给定的最小容量大于MAX_ARRAY_SIZE，否则不会返回大于MAX_ARRAY_SIZE的容量。 在扩容的操作里面，用到了几个常量：

private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
@Native public static final int   MAX_VALUE = 0x7fffffff;

    所以，扩容是这样的过程：

1、new = old + old *（old / 2）: 扩容50%得到newCapacity

2、如果newCapacity - 最小容量（即size + 1）<=0，返回给定最小容量。需要注意，如果空的数组，那么返回的容量是10。

这里再详细解释下：

    往一个空的list去add元素，size = 0，minCapacity = size + 1，计算出的newCapacity = 0 + 0 = 0，这时候newCapacity - minCapacity = -1，满足了条件。然后这时候判断数组是空的，所以返回了max(10,1)，也就是10。

    那么接下来继续add元素，容量为10，因此在添加到10个元素之前，都不会扩容。直到添加第11个元素的时候，触发扩容，这时候就是扩容50%了。

return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);

    绝大多数情况下返回newCapacity，也就是扩容50%的容量，当新的容量超过MAX_ARRAY_SIZE，会走到hugeCapacity的逻辑：

总结下，ArrayList添加元素时的扩容流程：

1、新建的ArrayList容量10其实不准确，为0。

2、当首次添加元素时，容量扩展为默认容量10。

3、一直到添加满10个元素之前，都不会再次扩容，维持10的容量。

4、添加第11个元素时，会触发扩容50%；直到用完容量前，不会继续扩容，以此类推。

3、扩容demo验证 

    接下来，我们写一个小的demo验证下扩容的流程：

public class ArrayListTest {public static void main(String[] args) {// 创建一个空的ArrayListArrayList<Integer> list = new ArrayList<>();System.out.println("初始容量：" + getArrayListCapacity(list));for (int i = 0; i < 11; i++) {list.add(i);System.out.println("add第" + (i + 1) + "个元素，容量：" + getArrayListCapacity(list));}}/*** 反射获取Arraylist的容量* @param list* @return*/private static int getArrayListCapacity(ArrayList<?> list) {try {java.lang.reflect.Field capacityField = ArrayList.class.getDeclaredField("elementData");capacityField.setAccessible(true);return ((Object[]) capacityField.get(list)).length;} catch (NoSuchFieldException | IllegalAccessException e) {e.printStackTrace();return -1;}}

三、移除元素 

    移除元素使用remove方法，如下：

 （1）检验index，index非法则会抛出异常：IndexOutOfBoundsException

（2）把index的元素赋值给oldValue，并在程序最后返回该element

（3）调用fastRemove方法移除第index个元素

     看下fastRemove方法：

 

    基于当前的数组去把指定范围的数据copy到另一个数组，并把