ArrayList是在实际项目中一个非常常用的类,今天我们通过源码来了解一下ArrayList的本质
内部变量说明
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//使用有参构造创建ArrayList的时候,如果size=0那么elementData就会指向这个数组,或者调用trimToSize(0)方法也会指向这个空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//只有使用无参构造的时候才会将elementData指向这个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//内部的元素数组,我们使用get()方法其实就是从其中取出元素
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList的长度,默认为0
private int size;
//ArrayList的临界值,如果下一次扩容的数值大于这个数值,那么将elementData扩容到数组的最大值也就是0x7fffffff,如果最小需要的容量已经大于0x7fffffff那么则抛出OOM异常
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
初始化
ArrayList()
我们要使用ArrayList必定要先new一个出来,现在我们来看看new 到底做了写什么.
ArrayList<Object> arrayList = new ArrayList<>();
在我们调用这样一个空参构造的时候,ArrayList实际上帮我们创建了一个空的数组,口说无凭,可以来看看
/**
* 构造一个空list并且初始化容量为10(如果只是单纯的new实际上并没有初始化容量)
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
而这个 DEFAULTCAPACITY_EMPTY_ELEMENTDATA是什么呢?
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
是的,他就是一个长度为0的Object的对象数组. 这个是一个 默认的静态被final修饰的的空数组实例,每一个array list实例被new出来一开始都共享这个空数组实例.
ArrayList(int initialCapacity)和ArrayList(Collection<? extends E> c)
当我们调用这两个方法中的其中一个方法的时候,如果 initialCapacity==0或者c.size()==0那么内部的element将会指向EMPTY_ELEMENTDATA
问题:不是已经有了一个空数组(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)了为什么还要有一个空数组(EMPTY_ELEMENTDATA)呢?
用一个场景来解释这个问题
在我们创建ArrayList 的时候,如果使用ArrayList<>(int initialCapacity)指定初始化容量的方式来创建,这时候传参是0那么,ArrayList内部的容器指向的就是这个EMPTY_ELEMENTDATA
在执行add方法的时候,如果是使用无参构造的方式创建的ArrayList 那么就会直接初始化其容量为10.
如果是使用有参构造的方式创建的ArrayList那么就会执行正常的扩容方式
说白了就是,DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是一个标记,用来区分ArrayList是不是无参构造创建的ArrayList
添加元素
void add(E e)
当我们添加元素的时候只需要调用add方法就行了,但是你知道其背后到底执行了哪些动作吗?让我们接着往下看吧!
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
我们来看看流程
看了流程之后,你可能会有诸多问题.
到底是怎么计算扩容的容量的?
添加元素是怎么添加的?
扩容容量是怎么计算的?
此处以**void add(E e)**为例
当我们添加一个元素的时候,如果这个元素是通过无参构造创建的(为了不让思路变得更复杂,此处只针对void add(E e)方法添加元素的容量计算),那么就将其容量初始化为 DEFAULT_CAPACITY,也就是10(还记得开始我们介绍了其内部的变量吗,就是那个DEFAULT_CAPACITY)
看起来这样做就足够了,但是java为了避免溢出,又做了一层处理
新容量= 原来的容量+原来的容量/2 这块有两层判断,
newCapacity-minCapacity<0 newCapacity-MAX_ARRAY_SIZE>0 (同newCapacity-Integer.MAX_VALUE - 8>0 )
第二个其实还想得通当超过最大数组长度的时候就将其扩展到Integer.MAX_VALUE
那第一个新的容量为什么会小于最小的容量呢?
实际上是因为Integer超过最大范围再加会溢出直接变为-2^32.
元素是如何添加的?
重新创建一个新的数组,将其靠拷贝
System.arraycopy()
得到元素
E get(int index)
- 此方法会先检查index是否是有效的索引
- 是有效的则会从内部数组elementData中强转并且返回该元素
- 不是有效的则会抛出IndexOutOfBoundsException异常
结语:
- ArrayList是基于数组实现的.
- ArrayList的扩容算法是 oldLength+oldLength>>1,也就是oldLength+oldLength/2
- ArrayList是扩容是重新分配一片空间,将原来的内容拷贝进去.
- ArrayList理论上的最大长度是Integer.MAX_VALUE