声明:源码解析基于JDK1.8
ArrayList 继承自 AbstractList 类,并且实现了 List,RandomAccess,Cloneable,java.io.Serializable 接口
使用 ArrayList 的空参构造器实例化对象,会初始化一个长度为 0 空数组。由此可以看出,底层使用的是 Object 类型的数组存储数据
从上面代码中可以看出,初始化的时候,数组的长度为0,那么何时扩容数组的长度呢?其实是在第一次 add 的时候
add 的代码比较多,一步步来分析
复杂内容其实是在 ensureCapacityInternal(size + 1) 这个里面,先抛开这个不说
size 表示当前数组的长度,由于类型是 int,所以默认值为 0
elementData[size++] = e 可以拆分为 elementData[size] = e; size = size + 1
第一次添加数据时,可以表示为:elementData[0] = e; size = 0+1; 即 size = 1
最后返回 true
但是问题来了,初始化时数组的长度为空,即长度为0,是无法往数组中添加数据的,需要将数组扩容
扩容的代码就在 ensureCapacityInternal(size + 1) 方法里
ensureCapacityInternal:翻译过来就是,确保数组内部的容量
首先调用 calculateCapacity 方法计算数组的最小容量
最小容量什么意思呢?用白话说,就是每次添加数据的时候,要确保当前数组的容量要大于计算出来的最小容量。如果当前数组的容量小于计算出来的最小容量,就意味着数组内没有可以存放新数据的位置了,此时就需要扩容数组的容量
从计算最小容量的代码中可以看出:第一次添加数据时,minCapacity = 1
calculateCapacity 方法头上的参数 minCapacity 的实际意义是:每次添加数据的时候,期望的最小容量就是当前数组的容量+1,因为只有当前数组的容量+1 才能新增加一条数据
第一次添加数据时,elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 成立,所以返回的最小容量是 DEFAULT_CAPACITY = 10
只有第一次添加数据时,计算出来的最小容量才为 10,其余时候,计算出来的最小容量都是当前数组的容量+1
由此可见,第一次添加数据时,扩容的容量为 10
接下来是 ensureExplicitCapacity 这个方法
这个方法内部逻辑理解起来比较简单,就是说:如果计算出来的最小容量大于当前数组的容量,就执行扩容的逻辑,反之则不扩容
真正的核心代码在 grow 里,这个才是扩容的真面目
oldCapacity:表示当前数组的容量,即当前数组的长度
newCapacity:表示扩容后数组的容量
>> 1 右移一位,其实就是除以 2 这个操作
以此类推,>> 2 右移两位,表示除以 2 的 2 次方
>> 3 右移三位,表示除以 2 的 3 次方
>> n 右移 n 位,表示除以 2 的 n 次方
oldCapacity + (oldCapacity >> 1) 可以写成 oldCapacity + (oldCapacity / 2) 实际含义是扩容 1.5 倍
如果扩容后数组的容量还比计算出来的最小容量小的话,就把数组容量扩容至计算出来的最小容量
这种情况只会在第一次添加数据,扩容数组容量时发生。
如果扩容后数组的容量大于数组允许的最大容量,就调用 hugeCapacity 方法(这种情况很少发生)
最后使用 Arrays.copyOf 方法进行数组的扩容
最后,白话总结:
首先,ArrayList 底层是一个 Object 类型的数组,实例化 ArrayList 对象时,底层是创建了一个长度为 0 的空数组
当调用 ArrayList 的 add 方法时,如果数组的长度不满足时,就扩容 1.5 倍
第一次 add 的时候,会默认扩容 10 个长度。之后每次 add,如果数组长度不满足时,才扩容 1.5 倍
扩容是使用 Arrays.copyOf 方法