Java中的ArrayList容量及扩容方式
短信预约 -IT技能 免费直播动态提醒
查看JDK1.8 ArrayList的源代码
1、默认初始容量为10
private static final int DEFAULT_CAPACITY = 10;2、最大容量为 Integer.MAX_VALUE - 8
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）以新容量拷贝原数据
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 = {};
transient Object[] elementData;
// ArrayList 的大小, 我们平常使用的 list.size() 底层就是记录的这个 size
private int size;
// ArrayList 最大
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;再看构造器，带参构造器
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}参数为 Collection 的构造器
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;
}
}不带参构造器
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) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 不相等的话只有返回当前的 size + 1
return 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 一般不会
newCapacity = hugeCapacity(minCapacity);
// 复制原数组中的元素, 并扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
上看说的是初始化场景，下面看一下其他场景，也是相当简单
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
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 倍！
以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
