探秘ArrayList源码:Java动态数组的背后实现
- 一、成员变量
- 二、构造器
- 1、默认构造器
- 2、带初始容量参数构造器
- 3、指定collection元素参数构造器
- 三、add()方法扩容机制
- 四、场景分析
- 1、对于ensureExplicitCapacity()方法
- 1.1 add 进第 1 个元素到 ArrayList 时
- 1.2 当 add 第 2 个元素时
- 1.3 直到添加第 11 个元素
- 2、对于grow() 方法:
- 2.1 当 add 第 1 个元素时
- 2.2 当 add 第 11 个元素进入 grow 方法时
- 五、心得体会
- 六、源码简易流程图
一、成员变量
读者需先对源码的成员变量阅览一遍,看个眼熟,有助于后面源码的理解
private static final long serialVersionUID = 8683452581122892189L;/** * 默认初始容量大小 */private static final int DEFAULT_CAPACITY = 10;/** * 空数组(用于空实例)。 */private static final Object[] EMPTY_ELEMENTDATA = {}; //用于默认大小空实例的共享空数组实例。//我们把它从EMPTY_ELEMENTDATA数组中区分出来,以知道在添加第一个元素时容量需要增加多少。private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/** * 存储ArrayList元素的数组缓冲区 */transient Object[] elementData; /** * ArrayList 所包含的元素个数 */private int size;
二、构造器
1、默认构造器
/** *默认构造函数,使用初始容量10构造一个空列表(无参数构造) */public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
以无参数构造方法创建 ArrayList时,实际上初始化赋值的是一个空数组。此时并没有为它创建对象,当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为 10。
2、带初始容量参数构造器
/** * 带初始容量参数的构造函数。(用户自己指定容量) */public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//初始容量大于0//创建initialCapacity大小的数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//初始容量等于0//创建空数组this.elementData = EMPTY_ELEMENTDATA;} else {//初始容量小于0,抛出异常throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);}}
3、指定collection元素参数构造器
/***构造包含指定collection元素的列表,这些元素利用该集合的迭代器按顺序返回*如果指定的集合为null,throws NullPointerException。*/ public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}
三、add()方法扩容机制
在进入ArrayList的核心源码扩容机制前,我们首先需要对源码中涉及到的一些变量进行一个初步的了解,这将有助于你对源码的深入了解
minCapacity
:数组所需的最小容量elementData
:存储ArrayList元素的数组缓冲区
public boolean add(E e) { ensureCapacityInternal(size + 1);// size = 0 elementData[size++] = e; return true;}
private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//elementData = {}}
private static int calculateCapacity(Object[] elementData, int minCapacity) {//判断elementData是否为空数组if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//DEFAULTCAPACITY_EMPTY_ELEMENTDATA ={}return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10;minCapacity = 1}return minCapacity;}
private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//ensureExplicitCapacity(10)}
private void ensureExplicitCapacity(int minCapacity) {//minCapacity = 10modCount++;if (minCapacity - elementData.length > 0)//elementData.length = 0grow(minCapacity);}
private void grow(int minCapacity) {//minCapacity = 10int oldCapacity = elementData.length;//oldCapacity = 0int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity= 1.5*oldCapacity = 0if (newCapacity - minCapacity < 0)//minCapacity = 10newCapacity = minCapacity;//newCapacity = 10if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//利用Arrays.copyOf()方法进行扩容elementData = Arrays.copyOf(elementData, newCapacity);}
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) " />Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
- 增加一个新元素,此时所需的最小容量是
minCapacity = size+1
- 首先判断底层数组
elementData
是否是空数组- 如果是空数组,则更新
minCapacity
为默认容量10, - 如果不是空数组,则对
minCapacity
不做变更
- 如果是空数组,则更新
- 判断所需最小容量
minCapacity
是否大于缓冲数组elementData
的长度:- 如果大于,则进行扩容
grow()
, - 否则不做处理
- 如果大于,则进行扩容
- 扩容
grow()
中,首先一上来就将elementData
的长度扩长为原来长度的1.5倍,再对扩容后的elementData
的长度和所需最小的容量minCapacity
进行判断- 如果扩容后的
elementData
的长度还小于minCapacity
的长度,说明还是不够,此时就直接将minCapacity
的长度赋值给elementData
- 否则的话直接进行下一步即可
- 如果扩容后的
- 最后需要对
elementData
的长度进行一个是否超过最大限度值MAX_ARRAY_SIZE
判断- 如果超过最大限度值,就看看所需的最小容量
minCapacity
是否大于最大限度值Integer.MAX_VALUE
- 如果不是,就将数组的长度扩容为数组的最大限度值
MAX_ARRAY_SIZE
,如果是,则返回Integer.MAX_VALUE
- 如果超过最大限度值,就看看所需的最小容量
四、场景分析
1、对于ensureExplicitCapacity()方法
1.1 add 进第 1 个元素到 ArrayList 时
当我们要 add
进第 1 个元素到 ArrayList
时,elementData.length
为 0 (因为还是一个空的 list),因为执行了 ensureCapacityInternal()
方法 ,所以 minCapacity
此时为 10。此时,minCapacity - elementData.length > 0
成立,所以会进入 grow(minCapacity)
方法。
1.2 当 add 第 2 个元素时
当 add 第 2 个元素时,minCapacity
为 2,此时 elementData.length(容量)
在添加第一个元素后扩容成 10 了。此时,minCapacity - elementData.length > 0
不成立,所以不会进入 (执行)grow(minCapacity)
方法。
添加第 3、4···到第 10 个元素时,依然不会执行 grow
方法,数组容量都为 10。
1.3 直到添加第 11 个元素
minCapacity(为 11)
比 elementData.length
(为 10)要大。进入 grow
方法进行扩容。
2、对于grow() 方法:
2.1 当 add 第 1 个元素时
oldCapacity
为 0,经比较后第一个 if 判断成立,newCapacity = minCapacity(为 10)
。但是第二个 if 判断不会成立,即 newCapacity
不比 MAX_ARRAY_SIZE
大,则不会进入 hugeCapacity
方法。数组容量为 10,add 方法中 return true,size 增为 1。
2.2 当 add 第 11 个元素进入 grow 方法时
newCapacity
为 15,比 minCapacity(为 11)
大,第一个 if 判断不成立。新容量没有大于数组最大 size,不会进入 hugeCapacity
方法。数组容量扩为 15,add 方法中 return true,size 增为 11。以此类推······
五、心得体会
- 变量
minCapacity
理解为我们添加元素进ArrayList集合中,底层数组所需的最小容量 - 变量
elementData.length
理解为我们添加元素进ArrayList集合中,底层数组的最大限度容量 - 当最小容量
minCapacity
> 最大限度容量elementData.length
,必定会触发扩容机制。 - 我们总是频繁地向ArrayList集合添加元素,开发人员也想到了这点,所以在ArrayList集合的扩容机制中,当我们添加第一个元素时,直接就把
minCapacity
设置为10,此处可以理解为,因为我们后续要频繁添加元素,为了不总是触发该集合的扩容机制,便“谎称”所需的最小容量是10,所以系统就直接把elementData.length
设置为10