Java中的ArrayList容量及扩容方式

Java中的ArrayList容量及扩容方式

目录查看JDK1.8 ArrayList的源代码1、默认初始容量为102、最大容量为 Integer.MAX_VALUE - 83、扩容方式：java ArrayList() 扩容原理先看下 ArrayList 的属性以及构造方法，这个比较重要上看说的是初始化场景，下面看一下其他场景，也是相当简单结论

查看JDK1.8 ArrayList的源代码

1、默认初始容量为10

/**

* Default initial capacity.

*/

private static final int DEFAULT_CAPACITY = 10;

2、最大容量为 Integer.MAX_VALUE - 8

/**

* The maximum size of array to allocate.

* Some VMs reserve some header words in an array.

* Attempts to allocate larger arrays may result in

* OutOfMemoryError: Requested array size exceeds VM limit

*/

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

原因：之前参考别人的，有待求证：

数组对象有一个额外的元数据，用于表示数组的大小；

数组长度size为int类型，共32位，有一位符号位，所以最大长度为Integer.MAX_VALUE=2^31= 2,147,483,648；

8bytes用来存储size；

3、扩容方式：

（1）首先传递进来一个希望的最小容量minCapacity；

（2）新容量newCapacity = oldCapacity + (oldCapacity >> 1)，即新容量等于原容量的1.5倍；

（3）如果minCapacity > newCapacity ，newCapacity = minCapacity ;

（4）如果 newCapacity > 最大容量 MAX_ARRAY_SIZE ，newCapacity = hugeCapacity(minCapacity);

（5）以新容量拷贝原数据

/**

* Increases the capacity to ensure that it can hold at least the

* number of elements specified by the minimum capacity argument.

*

* @param minCapacity the desired minimum capacity

*/

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

}

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

Java ArrayList() 扩容原理

平常都是直接使用 ArrayList()，今天特地看一下 ArrayList() 的扩容原理。

先看下 ArrayList 的属性以及构造方法，这个比较重要

先看下属性

// ArrayList 默认容量大小

private static final int DEFAULT_CAPACITY = 10;

// 一个共享的空数组, 在空实例时使用

private static final Object[] EMPTY_ELEMENTDATA = {};

// 一个共享的空数组, 在使用默认 size 的空实例时使用

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/*

存储 ArrayList 元素的数组缓冲区

重点1: ArrayList 的容量是数组缓冲区的长度

重点2: 从这个元素也可以看的出来 ArrayList() 的底层就是一个 Object[]

add 第一个元素时, 任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将被扩展为 DEFAULT_CAPACITY

*/

transient Object[] elementData;

// ArrayList 的大小, 我们平常使用的 list.size() 底层就是记录的这个 size

private int size;

// ArrayList 最大

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

再看构造器，带参构造器

/*

带参构造器, 参数为容量大小, 例如: 初始化一个容器为 20 类型为 Integer 的 ArrayList

ArrayList list = new ArrayList<>(20);

*/

public ArrayList(int initialCapacity) {

/*

初始化容量 > 0, elementData 初始化为初始化容量大小的数组

初始化容量 = 0, elementData = EMPTY_ELEMENTDATA (空数组)

初始化容量 < 0, 直接抛出异常

*/

if (initialCapacity > 0) {

this.elementData = new Object[initialCapacity];

} else if (initialCapacity == 0) {

this.elementData = EMPTY_ELEMENTDATA;

} else {

throw new IllegalArgumentException("Illegal Capacity: "+

initialCapacity);

}

}

参数为 Collection 的构造器

/*

将一个参数为 Collection 的集合转换为 ArrayList

*/

public ArrayList(Collection extends E> c) {

// Collection 转换为数组 Object[] 类型

elementData = c.toArray();

// 判断当前对象大小是否和 Collection 长度相等并且不等于 0, false 的话 elementData 等于空数组了

if ((size = elementData.length) != 0) {

// c.toArray() 可能不会正确地返回一个 Object[] 数组，所以使用 Arrays.copyOf()

if (elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class);

} else {

this.elementData = EMPTY_ELEMENTDATA;

}

}

不带参构造器

/*

不带参构造器就像我们平时使用一样, 直接 new 一个 ArrayList 不需要传递任何参数

构造方法中直接将 elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA (空数组)

*/

public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

看到这里就发现，带参的构造器我们可以直接传递参数，而默认的构造器怎么怎么样初始化容量大小的呢？

add() 方法可以直接得到答案。

public boolean add(E e) {

// 这一行是关键, 看下面

ensureCapacityInternal(size + 1);

// 将元素追加到集合的末尾 假如当前 size = 10 size++ 追加到第 11 位

elementData[size++] = e;

return true;

}

ensureCapacityInternal() 方法调用

private void ensureCapacityInternal(int minCapacity) {

/*

calculateCapacity() 方法, 刚初始化时会返回 10, 其他情况返回当前 size + 1

ensureExplicitCapacity() 方法, 调用扩容

*/

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

private static int calculateCapacity(Object[] elementData, int minCapacity) {

/*

使用无参构造器创建创建 ArrayList 的集合, 此时一定是相等的

*/

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

/*

两数相比返回最大值, 此时 Math.max(10, 1);

默认容量, 由此而来

*/

return Math.max(DEFAULT_CAPACITY, minCapacity);

}

// 不相等的话只有返回当前的 size + 1

returnMxvxEhS minCapacity;

}

private void ensureExplicitCapacity(int minCapacity) {

// 增量, 记录修改/更新次数

modCount++;

// 初始化: 10 - 0 > 0

// 其他: size + 1 > 0

if (minCapacity - elementData.length > 0)

// 扩容操作

grow(minCapacity);

}

private void grow(int minCapacity) {

// 老的长度, 初始化时为 0,

int oldCapacity = elementData.length;

// 新的长度此时 0 + (0 >> 1), newCapacity = 0

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

// 初始化场景: 0 - 10 < 0 ? true newCapacity = 10

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

// 初始化场景: 10 - 2147483639 > 0 返回 false

if (newCapacity - MAX_ARRAY_SIZE > 0)

// 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会

MxvxEhS newCapacity = hugeCapacity(minCapacity);

// 复制原数组中的元素, 并扩容

elementData = Arrays.copyOf(elementData, newCapacity);

}

上看说的是初始化场景，下面看一下其他场景，也是相当简单

private void ensureCapacityInternal(int minCapacity) {

/*

calculateCapacity() 方法, 正常扩容返回 size + 1, 比如 10 + 1, 因为默认长度为 10 当再次新增数据时就会出发扩容

ensureExplicitCapacity() 方法, 调用扩容

*/

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

private static int calculateCapacity(Object[] elementData, int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(DEFAULT_CAPACITY, minCapacity);

}

/*

elementData 不等于空数组

返回当前的 size + 1, 即 10 + 1 返回 11

*/

return minCapacity;

}

private void ensureExplicitCapacity(int minCapacity) {

// 增量, 记录修改/更新次数

modCount++;

// 其他: 11 - 10 > 0 true, 触发扩容, 如果当前下表是 5 的话 5 + 1 =6, 6 < 10 是, 此时不会出发扩容

if (minCapacity - elementData.length > 0)

// 扩容操作

grow(minCapacity);

}

private void grow(int minCapacity) {

// 老的长度 10

int oldCapacity = elementData.length;

// 新的长度此时 10 + (10 >> 1), newCapacity = 15

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

// 15 - 11 < 0 ? false

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

// 15 - 2147483639 > 0 返回 false

if (newCapacity - MAX_ARRAY_SIZE > 0)

// 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会

newCapacity = hugeCapacity(minCapacity);

// 复制原数组中的元素, 并扩容 newCapacity = 15

elementData = Arrays.copyOf(elementData, newCapacity);

}

结论

1、 触发扩容的关键是

当前 size + 1 是否大于当前容量，如果大于容量则证明，集合不够用了，需要扩容。如果小与当前容量则证明集合还有容量不需要扩容！

2、 每次扩容的大小是

oldCapacity + (oldCapacity >> 1) 即: 10 + (10 >> 1)

即：当前容量的 1.5 倍！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。