本文采用知识共享 署名-相同方式共享 4.0 国际 许可协议进行许可。
访问 https://creativecommons.org/licenses/by-sa/4.0/ 查看该许可协议。
通过查看ArrayList源码发现:
private static final int DEFAULT_CAPACITY = 10;
默认容量为10,我们用的最多的add函数
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add函数第一行调用了ensureCapacityInternal(确保在容量内)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
先来看calculateCapacity(计算容量),传入了ArrayList内部保存数据的数组、需要确保的容量。
1.如果elementData为空,拿需要确保的容量 和 默认的容量(10)中大的那个返回
,反之返回需要确保容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
ensureCapacityInternal还没完,紧接着来到ensureExplicitCapacity(确保明确的容量)
1.操作数+1,迭代时通过modCount确定有没产生并发修改,迭代是改变则抛ConcurrentModificationException
2.需要确保容量如果大于elementData长度,则调用grow(扩容),反之不扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow
- 默认newCapacity(新容量)为原来elementData长度1.5倍(二进制右移一位为原来的1/2,加上本身1)
- 默认容量和需求容量取最大值
- 如果newCapacity超过MAX_ARRAY_SIZE(最大数组大小,默认为Integer.MAX_VALUE-8,为什么要减8呢,这篇文章有讲引用类型的开销-From Java code to Java heap),则用hugeCapacity函数尝试获取Integer.MAX_VALUE。
- 最后copy一个以newCapacity为容量创建一个新elementData
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); }
以上就是Java的函数扩容机制。