浅谈ArrayList动态扩容

绝地灬酷狼 2021-11-29 23:42 353阅读 0赞

环境：eclipse，jdk1.8  
简介  
ArrayList实现了List接口，继承了AbstractList，底层是数组实现的，一般我们把它认为是可以自增扩容的数组。它是非线程安全的，一般多用于单线程环境下(与Vector最大的区别就是，Vector是线程安全的，所以ArrayList 性能相对Vector 会好些)，它实现了Serializable接口，因此它支持序列化，能够通过序列化传输(实际上java类库中的大部分类都是实现了这个接口的)，实现了RandomAccess接口，支持快速随机访问(只是个标注接口，并没有实际的方法),这里主要表现为可以通过下标直接访问(底层是数组实现的，所以直接用数组下标来索引)，实现了Cloneable接口，能被克隆。  
ArrayList：

RandomAccess：

初始化  
ArrayList一共提供了三个初始化的方法：  
public ArrayList()  
public ArrayList(Collection<? extends E> c)  
public ArrayList(int initialCapacity)；

首先看看源码里无参构造方法的实现：

上面的注释表示他会默认提供容量为10的数组，但是实际并不是在这一步实现。可以看看这里的DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA和elementData：

只是一个空数组。所以这一步实际上只是将elementData指向一个空数组而已。  
再来看看带参数的构造方法：

这个方法是直接将一个集合作为ArrayList的元素，很容易看懂，不多做解释，此时elementData即为集合c转为的数组，size即为elementData的长度。这里size是ArrayList的一个int型私有变量，用于记录该list集合中当前元素的数量，注意不是容量。  
再来看看带初始化容量的构造方法：

从源码里可以看出：首先对传进来的初始化参数initialCapacity进行判断，如果该参数大于0，在elementData进行初始化，初始化为一个容量为initialCapacity的数组，如果传进来的参数initialCapacity等于0，则将elementData指向了EMPTY\_ELEMENTDATA，从这个名字也可以猜出，是个空数组：

add方法的实现  
说了这么多，还没有说到无参构造函数默认是空数组，为什么注释说是容量为10的数组，也还没说到当容量不足时，是如何实现动态扩容的，下面就通过add方法来说明这些问题。(add方法是list接口中声明的通用方法)。ArrayList的add方法实现如下：

size是当前集合拥有的元素个数(未算进准备新增的e元素)，从源码看出，调用了ensureCapacityInternal来保证容量问题，传进去的参数是size+1，来保证新增元素后容量满足要求。  
接下来进入ensureCapacityInternal方法查看其实现：

可以看到代码段：  
        if (elementData == DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA) \{  
            minCapacity = Math.max(DEFAULT\_CAPACITY, minCapacity);  
        \}  
通过这一步来判断，当前elementData是否为空数组(即初始化容量为0或者调用了无参构造函数后的结果)，如果是，则使用  
Math.max(DEFAULT\_CAPACITY, minCapacity)进行选择一个较大的，其中，DEFAULT\_CAPACITY是ArrayList定义的静态常量10：

可以看出，这里如果minCapacity小于10的话(如果elementData为空的话，size+1即minCapacity一般为1)，返回的是10，所以如果没有指定大小的话，默认是初始化一个容量为10的数组。然后在调用ensureExplicitCapacity方法：

可以看到modCount++，这里可以暂时不管它，这个参数主要是用在集合的Fail-Fast机制(即快速失败机制)的判断中使用的。(以后有空再补充这方面的内容)  
在这个方法里进行判断，新增元素后的大小minCapacity是否超过当前集合的容量elementData.length，如果超过，则调用grow方法进行扩容。我们进入该方法进行查看:

在这里可以很清楚的看到扩容容量的计算:int newCapacity = oldCapacity + (oldCapacity >> 1),其中oldCapacity是原来的容量大小，oldCapacity >> 1 为位运算的右移操作，右移一位相当于除以2，所以这句代码就等于int newCapacity = oldCapacity + oldCapacity / 2；即容量扩大为原来的1.5倍(注意我这里使用的是jdk1.8，没记错的话1.7也是一样的)，获取newCapacity后再对newCapacity的大小进行判断，如果仍然小于minCapacity，则直接让newCapacity 等于minCapacity，而不再计算1.5倍的扩容。然后还要再进行一步判断，即判断当前新容量是否超过最大的容量 if (newCapacity - MAX\_ARRAY\_SIZE > 0)，如果超过，则调用hugeCapacity方法，传进去的是minCapacity，即新增元素后需要的最小容量：

如果minCapacity大于MAX\_ARRAY\_SIZE，则返回Integer的最大值。否则返回MAX\_ARRAY\_SIZE。

然后回到grow方法，调用Arrays.copyof方法，即复制原数组内容到一个新容量的大数组里。这里Arrays.copyof方法实际是调用System.arraycopy方法。  
到这里，应该可以很清楚的知道ArrayList底层扩容的原理了。与Vector不同的是，Vector每次扩容容量是翻倍，即为原来的2倍，而ArrayList是1.5倍。看似1.5倍增长的很慢，那经常增加大量元素会不会导致经常扩容，数组重新分配导致效率低下呢？其实不然，每次增长为原来的1.5倍实际增长的量会越来越大的，可以看看网友统计的数据(参考：http://blog.csdn.net/java2000\_net/article/details/5215882)：  
1千需要分配 11次  
1万一级需要分配17次  
10万 需要分配23次  
100万需要分配28次  
当然，如果一开始知道数据量很大的话，可以在初始化时预先指定容量。  
get方法  
很明显是通过数组下标索引来指定返回的数组，这里不多做解释。

验证  
无参构造函数，add三个元素，  
按照理解，此时默认容量应该为10：

可以看出：elementData容量为10，size为3。

无参构造函数，增加12个元素：  
测试代码：  
           List<Integer> list = new ArrayList<>();  
           for (int i = 0 ; i < 12; i ++) \{  
                list.add(i);  
           \}  
   
           System.out.println("ok");

通过debug查看结果：

看到elementData扩容为15(10+10/2 = 15),而集合元素size为12。

无参构造函数，增加原来的1.5倍扩容量的数据：  
测试代码：  
           List<Integer> list = new ArrayList<>();  
           List<Integer> newList = new ArrayList<>();  
           for (int i = 0 ; i < 5; i ++) \{ 初始5个  
                list.add(i);  
           \}  
           for (int i = 5 ; i < 20; i ++) \{  
                newList.add(i);   
           \}  
           list.addAll(newList);  //一次性增加15个  
           System.out.println("ok");

正常情况下，新增5个后，容量为10，再次新增，会变为原来的1.5倍，即15，但是这里新增15个，明显超过，按照上面的理解，应该直接让新容量等于需要的最小容量20，从测试截图可以看到，结果正确。

带集合参数构造函数：  
测试代码：  
           List<Integer> newList = new ArrayList<>();  
           for (int i = 5 ; i < 20; i ++) \{  
                newList.add(i);  
           \}  
           List<Integer> list = new ArrayList<>(newList);  
           System.out.println("ok");

测试结果：

可以看到，结果elementData的容量即为集合参数的大小。  
总结  
总之，ArrayList默认容量是10，如果初始化时一开始指定了容量，或者通过集合作为元素，则容量为指定的大小或参数集合的大小。每次扩容为原来的1.5倍，如果新增后超过这个容量，则容量为新增后所需的最小容量。如果增加0.5倍后的新容量超过限制的容量，则用所需的最小容量与限制的容量进行判断，超过则指定为Integer的最大值，否则指定为限制容量大小。然后通过数组的复制将原数据复制到一个更大(新的容量大小)的数组。  
附：  
size和modCount的区别  
可能看了源码有时候还分不清size和modCount的区别，那么这里就用例子来说明。  
size是ArrayList的变量。modCount是ArrayList的父类AbstractList中的变量，默认值为0。  
size记录了ArrayList中元素的数量，modCount记录的是关于元素的数目被修改的次数。modCount在ArrayList的普通操作里可能并没有看出多大用处，但是在涉及到fail-fast就主要是依靠它了。  
直接用下面这段代码进行测试：  
           List<Integer> list = new ArrayList<>();  
           list.add(1);  
           list.add(2);  
           list.add(3);  
           list.add(4);  
           list.remove(2);  
           list.add(5);  
           list.set(1, 100);  
           list.remove(4);  
           System.out.println(list.size());  
当执行完 list.add(4)时，此时modCount和size都为4：

当执行完list.remove(2)时，此时元素数量发生了修改，所以modCount++即5,而size记录集合中元素的个数，移除了一个后，size=size-1即3：

当执行完list.add(5)时，此时元素数量再次发生了修改，所以modCount++即5,而size记录集合中元素的个数，增加了一个后，size=size-1即4：

当执行完list.set(1, 100)时，元素的数量并没有发生改变，所以modCount和size都不变。