ArrayList初始化与扩容原理

ArrayList初始化

来看如下代码：

public static void main(String[] args) {
    List<Person> list1 = new ArrayList<>();
    List<Person> list2 = new ArrayList<>();

    Person person1 = new Person("张三");
    list1.add(person1);

    System.out.println("list1.size()" + list1.size());
    System.out.println("list2.size()" + list2.size());
}

首先：执行List list1 = new ArrayList<>();当看到new这个关键字的时候，可知代码在堆内存开辟了一块空间，如下图。

ArrayList初始化1

1	常量池位于方法区，方法区位于堆内存

无参构造函数如下：

1
2
3

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

很简单，就一行代码，继续看一下this.elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA分别是什么，下面是ArrayList中的一些属性：

private static final int DEFAULT_CAPACITY = 10;// 默认初始化的容量
private static final Object[] EMPTY_ELEMENTDATA = {};// 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 空数组
transient Object[] elementData; // 存放元素的数组
private int size;// 数组中元素的个数

和String一样，底层是数组，唯一的区别是String底层是char[]数组，而这儿是Object[]数组，也就是说该数组可以放任何对象（所有对象都继承自父类Object），执行完构造函数后，如下图。

ArrayList初始化2

static修饰的变量，常驻于方法区，我们不需要new，JVM会提前给我们初始化好，这个特性在实际开发过程中，经常拿来做缓存。static变量又叫类变量，不管该类有多少个对象，static的变量只有一份，独一无二。fianl修饰的变量，JVM也会提前给我们初始化好。transient这个关键字告诉我们该对象在序列化的时候请忽略这个元素。

继续执行：List list2 = new ArrayList<>()：

ArrayList初始化3

new的时候考虑到了缓存，为了避免反复的创建无用数组，所有新new出来的ArrayList底层数组都指向缓存在方法区里的Object[]数组。

继续执行Person person1 = new Person(“张三”)

创建Person对象

继续执行list1.add(person1)，看源码ArrayList是怎么处理add的：

public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       elementData[size++] = e;
       return true;
}

调用add方法的时候，首先是调用了ensureCapacityInternal方法。这个方法接收一个int类型的参数，表示的是当前数组中的元素个数加1。现在是空数组，所以size就是0，也就说传入的是1。

我们在图里的ArrayList对象里补上它，成员变量初始化的size为0。

ArrayList初始化5

接下来看看ensureCapacityInternal里面做了什么事。

1
2
3

private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

接下来看看ensureCapacityInternal里面做了什么事。

1
2
3

private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

这个方法里面又调用了两个方法，一个calculateCapacity方法，然后将calculateCapacity方法的返回值作为参数再调用ensureExplicitCapacity方法。先看看calculateCapacity方法做了什么。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       return minCapacity;
}

它首先看看当前数组是否为空，如果为空，那么就返回DEFAULT_CAPACITY和minCapacity当中较大的一个。DEFAULT_CAPACITY就是10，minCapacity就是刚才传入的size + 1，也就是1，所以就返回10。然后将10作为参数传给ensureExplicitCapacity：

private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       if (minCapacity - elementData.length > 0)
           grow(minCapacity);
}

这里有个变量自增了，看看下面的判断。现在这个minCapacity是刚才传入的10，底层数组的length是0，所以调用了grow方法。再去看看grow方法：

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
}

直接看最后一句，进入代码：

1
2
3

public static <T> T[] copyOf(T[] original, int newLength) {
    return (Object[])copyOf(original, newLength, original.getClass());
}

再看copyOf()方法：

public static <T, U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    Object[] copy = newType == Object[].class ? (Object[])(new Object[newLength]) : (Object[])((Object[])Array.newInstance(newType.getComponentType(), newLength));
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

System.arraycopy()方法是native修饰的本地方法。

由于数组内容目前为空，相当于没有拷贝。原来只是创建了一个默认长度为10的Object[]数组，如下图：

ArrayList初始化6

再看add()的代码，其中：

1	elementData[size++] = e;

相当于：

1 2	elementData[size] = e; size++

很简单，size现在是0，把传进来的这个e(这里是person1)，放到list1的elementData[]下标为0的数组里面，同时size加1，如下图：

往ArrayList添加元素

注意看红框里，虽然我们list1里的elementData数组的长度是10，但是size是1，size是逻辑长度，并不是数组长度。

现在debug一下，验证我们图里的内容：

debug验证数组长度

本节最开始代码执行结果如下：

1 2	list1.size()1 list2.size()0

看一下size()方法的源码：

1
2
3

public int size() {
    return size;
}

就是返回size的值，而不是数组的长度，所以String里叫length()而List里面叫size()。

ArrayList底层数组扩容原理

看如下代码与图（去掉了一些无用的细节如方法区、常量池等）：

public static void main(String[] args) {
    Person[] perArr = new Person[5];
    perArr[0] = new Person("张三");
    perArr[1] = new Person("李四");
    perArr[2] = new Person("王五");
    perArr[3] = new Person("赵六");
    perArr[4] = new Person("孙七");

    System.out.println("perArr.length:" + perArr.length);
}

数组在堆内存中的展现1

debug可以看到与上图一致：

debug数组展示

执行结果也在我们期望中：

1	perArr.length:5

再往数组里加添加一个叫“周八”的person对象：

1	perArr[5] = new Person("周八");

执行会报数组下标越界异常。在Java中，数组一但在堆内存中创建，长度是固定的。

那要往数组里加一个“周八”用户，只能重新new长一点的新的数组，把原来数组的元素复制过去：

Person[] newPerArr = new Person[10];//数组扩大一倍，防止后面出现更多用户
for (int i = 0;i<perArr.length;i++){
    newPerArr[i] = perArr[i];
}
newPerArr[5] = new Person("周八");

把老数组的元素循环一下，赋值给新的数组，debug看一下：

debug数组展示2

“周八”已经有了。以上代码虽然简单，但还不是最优雅的，有经验的程序员一般会这么写，该段代码执行结果和上面那段代码一样：

1
2
3

Person[] newPerArr = new Person[10];
System.arraycopy(perArr, 0, newPerArr, 0, perArr.length);//数组拷贝
newPerArr[5] = new Person("周八");

数组在堆内存中的展现2

到此，便可知道ArrayList里的底层数组扩容是怎么实现的了。ArrayList初始化一节中我们知道当ArrayList如果不指定构造个数的话，第一次往里面添加元素时底层数组会初始化一个长度为10的数组，我们再回顾一下昨天的源码，再来看一下ArrayList里的源码，当添加第11个元素时：

private void ensureExplicitCapacity(int minCapacity) {
       modCount++;
       if (minCapacity - elementData.length > 0)
       //minCapacity值11，大于数组长度，执行grow方法
           grow(minCapacity);
}

再看grow()方法：

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
}

使用无参构造方法，这里oldCapacity是0，newCapacity的初始值是1.5倍的oldCapacity，所以也是0。接下来因为newCapacity减minCapacity是0减10，所以小于0，那么newCapacity就是10。最后调用Arrays.copyOf方法，初始化数组，将一个旧数组中的数据拷贝到新数组中。

这既是初始化的过程，其实也是扩容的过程。add的时候，先将数组中的元素个数size加1传给ensureCapacityInternal方法，如果当前elementData为空，就是初始化，返回10，初始化一个大小为10的数组。如果elementData不为空，就返回size + 1的值，将其传入ensureExplicitCapacity方法，判断size + 1的值减去当前数组的长度是否大于0。比如我现在elementData的length为10，现在已经存了9个元素，即size + 1等于10，此时10减10是不大于的0，不执行grow方法。当存了10个元素的时候，10加1等于11，才会执行grow方法。也就是说，当数组满了才会执行扩容操作。扩容的时候，是扩容为当前数组容量的1.5倍，然后底层调用一个本地方法将旧数组数据转移到新数组。

下面代码：

1	int newCapacity = oldCapacity + (oldCapacity >> 1);

相当于：

1	int newCapacity = oldCapacity + (oldCapacity / 2);

但前者性能更好。

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);
        }
}

以传进来的个数作为元素个数创建底层数组，首先判断传入的 initialCapacity 是否大于0，大于0就new一个长度为 initialCapacity 的数组；如果等于0，那么 elementData 还是空数组；如果小于0，直接抛异常。

所以当我们在写代码过程中，如果我们大概知道元素的个数，比如一个班级大概有40-50人，我们优先考虑List list2 = new ArrayList<>(50)以指定个数的方式去构造，这样可以避免底层数组的多次拷贝，进而提高程序性能。

总结

初始化：调用无参构造初始化时只是创建了一个空数组，等调用add方法的时候才会调用扩容方法，初始化一个长度为10的数组。
扩容：当数组中存满了元素时，创建一个容量为原先的1.5倍的新数组，将元素copy到新数组的方法底层调用的是System类的一个本地方法。

元素的删除与插入

ArrayList中的删除

如下代码添加10个用户：

Person[] group = new Person[10];
group[0] = new Person("张三", 21);
group[1] = new Person("李四", 19);
group[2] = new Person("王五", 25);
group[3] = new Person("赵六", 24);
group[4] = new Person("孙七", 32);
group[5] = new Person("周八", 17);
group[6] = new Person("钱九", 24);
group[7] = new Person("吴十", 23);
group[8] = new Person("冯十一", 18);
group[9] = new Person("朱十二", 36);

比如我们要把“周八”这个人从数组中删除，如图：

删除数组元素1

我们只能循环数组，找到“周八“的下标5，由于数组没有提供删除方法，我们只能把下标为5的位置赋值为null(造成了数组空洞)，“周八”这个Person对象已经没有引用指向它了，JVM的垃圾回收机制会在适当的时候回收它。但数组的长度还是10。下次当我们再循环查找某人时，稍不注意就会报空指针异常，虽然我们可以写非空去判断，但还是不太友好，我们把null后面的所有元素引用复制一下，往前拷贝一份，把null这个空给填上，如下图：

删除数组元素2

复制后：

删除数组元素3

null之后的ref引用都按顺序复制了一份到原来的null的位置，原有的引用被覆盖，但perArr[9]里的引用的指向还是不变（注意，是复制不是挪动）。此时perArr[8]、perArr[9]指向的是同一个对象，这显然不是我们所要的结果，再处理一下，我们把perArr[9]的引用赋值为null。如下图：

删除数组元素4

问题似乎解决了，但数组长度还是10，还需要自行维护一个size来记录长度，以上数组复制的代码，我们都要自己去写，好在ArrayList这个类已经实现了，数组拷贝工作交给它就好，我们只需要调用ArrayList这个类提供的remove删除元素就行，至于底层数组怎么拷贝，元素怎么删除由ArrayList对象本身去处理。我们来看一看ArrayList的两种元素删除方式，首先是按照下标删除：

List<Person> perList = new ArrayList<>();
perList.add(new Person("张三", 21));
perList.add(new Person("李四", 19));
perList.add(new Person("王五", 25));
perList.add(new Person("赵六", 24));
perList.add(new Person("孙七", 32));
perList.add(new Person("周八", 17));
perList.add(new Person("钱九", 24));
perList.add(new Person("吴十", 23));
perList.add(new Person("冯十一", 18));
perList.add(new Person("朱十二", 36));

perList.remove(5);//删除ArrayList里下标为5的元素
perList.remove(new Person("孙七", 32));//删除孙七
System.out.println("perList.size()" + perList.size());

先看看删除前的元素，debug如下：

debug删除数组元素1

perList里面已经有了10个元素，执行一下这两句remove操作，再看一下debug的情况：

debug删除数组元素2

下标为5的“周八”已经删除掉了，下标为5以后的元素也按照我们之前的猜想往前移了一位，数组最后一个位置也置为null了。但“孙七”没有删掉，打印出来的个数也是9。

看一下两种删除方式的源码：

public E remove(int index) {//删除指定位置的元素
    rangeCheck(index);// 检测指定的索引是否越界

    modCount++;//记录修改次数
    E oldValue = elementData(index);//根据数组下标拿到底层数组里的元素

    int numMoved = size - index - 1;//计算数组需要拷贝元素的个数
    if (numMoved > 0)//拷贝删除位置（index）+1后面的numMoved个元素并从删除位置（index）开始复制
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //这行代码相当于size=size-1;elementData[size] = null; size减少1,数组最后一个位置赋值为null
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;//返回事先拿到的删除元素
}

基本上和我们图中的分析一致，并采用size来记录元素的真实个数，这段代码里还调了一个方法rangeCheck()方法：

private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

就是检查底层数组下标是否越界。再看另外一种删除方式：

public boolean remove(Object o) {  
    if(o == null) {//如果要删除的元素为null
        for(int index = 0; index < size; index++)  
        if(elementData[index] == null) {  
            fastRemove(index);//循环查找null，找到后执行fastRemove()方法
            return true;//删除成功
        }  
    }else{//如果要删除的元素不为null
        for(int index = 0; index < size; index++)  
        if(o.equals(elementData[index])) {  
            fastRemove(index);//equals循环比对，比对成功执行fastRemove()方法
            return true;//删除成功
        }  
    }  
    return false;//删除失败
}

再看一下fastRemove()方法：

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;
}

和上面用下标删除方式一致。

如果写了一个类（Person），需要这个类完美的支持List，必需按照List的规范来写代码，上面代码中的孙七是我们新neW出来的，不是我们数组里的孙七。由于我们没有重写equals，默认继承Person父类Objecte的equals方法，判断是否指向同一个引用，而不是比较值。

重写完equals和hashCode方法，执行一下再debug看一下：

debug删除数组元素3

孙七已经删除掉了，孙七后面的所有人也向前复制了一格，末位置为null，size也是8了，如下图：

删除数组元素5

图中的“孙七”、“周八”已经没有引用指向它们，JVM虚拟机会在适当的时候进行回收。

在ArrayLIst中，如果底层数组长度为n，当我们用下标方式去删除元素时，如果删除的是最后一个元素，不会触发数组底层的复制，时间复杂度为O(1)。如果删除第i的元素，会触发底层数组复制n-i次，根据最坏情况，时间复杂度为O(n)。

由此看来，在ArrayList中删除指定元素的效率似乎不是太高，删除元素会造成底层数组复制。

ArrayList中的插入

还有一个add方法，public void add(int index, E element) ，从指定位置添加元素：

public void add(int index, E element) {
   rangeCheckForAdd(index);//检查index是否越界

   //判断数组要不要扩容
   ensureCapacity(size + 1);  // Increments modCount!!
   System.arraycopy(elementData, index, elementData, index + 1,
            size - index);//取出插入位置后面的元素，往后依次复制一格
   elementData[index] = element;//给数组元素下标为index的元素赋值
   size++;
  }

执行如下代码：

List<Person> perList = new ArrayList<>();
perList.add(new Person("张三", 21));
perList.add(new Person("李四", 19));
perList.add(new Person("王五", 25));
perList.add(new Person("赵六", 24));
perList.add(new Person("孙七", 32));
perList.add(new Person("周八", 17));
perList.add(new Person("钱九", 24));
perList.add(new Person("吴十", 23));

perList.add(2, new Person("李莫愁", 29));//把李莫愁放到下标为2的位置

当执行到System.arraycopy()这个方法时，如下图：

ArrayList添加元素1

注意，此处并不是依次移动元素到下一格，是依次复制插入位置及后面的数组元素，到后面一格，不是移动，因此，复制完后，arr[2]、arr[3]指向对一个对象：

ArrayList添加元素2

在代码执行完System.arraycopy()方法，debug验证如下：

debugArrayList添加元素1

最后，在堆内存中创建李莫愁这个对象，把arr[2]的引用指向它：

ArrayList添加元素3

再debug一下：

debugArrayList添加元素2

最后我们来说说ArrayLIst这个对象里添加的时间复杂度，如果我们不指定位置直接添加元素时(add(E element))，元素会默认会添加在最后，不会触发底层数组的复制，不考虑底层数组自动扩容的话，时间复杂度为O(1) ，在指定位置添加元素(add(int index, E element))，需要复制底层数组，根据最坏打算，时间复杂度是O(n)。

再来看读取元素，下面代码是获取List中下标为2的元素:

1 2	Person person = perList.get(2); System.out.println(person.getName());

源码如下:

public E get(int index) {
    rangeCheck(index);//检查index这个下标是否越界

    return elementData(index);//直接从底层数组里拿数据
}

读取元素和数组长度无关，直接从底层数组里去拿元素。

下面将李莫愁替换：

1	perList.set(2, new Person("小龙女", 22));

源码如下：

public E set(int index, E element) {
    rangeCheck(index);//检查数组越界

    E oldValue = elementData(index);
    elementData[index] = element;//在底层数组的指定位置放入元素
    return oldValue;//取到原来的元素并返回
}

很简单，就是往指定位置放入元素，并返回原来的元素，如下图：

ArrayList添加元素4

图中“李莫愁”已经没有引用指向它了，JVM会在合适的时候回收它，底层数组第2个位置已经换成了“小龙女”，debug验证一下：

debugArrayList添加元素3

总结

在ArrayList中，底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)。

当ArrayList里有大量数据时，这时候去频繁插入/删除元素会触发底层数组频繁拷贝，效率不高，还会造成内存空间的浪费，这个问题在另一个类：LinkedList里有解决方案。而查找元素效率不高，在HashMap里有解决方案。

参考资料：
清浅池塘 ArrayList初始化、ArrayList底层数组扩容原理、三顾ArrayList、ArrayList的时间复杂度
贪挽懒月 Java源码解读 — ArrayList