不同的 JDK 版本的扩容机制可能有差异 实验环境: JDK1.8
扩容机制:
当向 ArrayList 中添加元素的时候, ArrayList 如果要满足新元素的存储超过 ArrayList 存储新元素前的存储能力, ArrayList 会增强自身的存储能力, 已达到存储新元素的要求
ArrayList: 本质通过内部维护的数组对象进行数据存储
1: 分析 ArrayList 的 add(E) 方法
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
分析: add 方法首先通过 ensureCapacityInternal() 方法确保当前 ArrayList 维护的数组具有存储新元素的能力, 经过处理之后将元素存储在数组 elementData 的尾部 elementData:ArrayList 真正用于存储元素的数组
2: 分析 ensureCapacityInternal 方法
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
分析: ensureCapacityInternal 判断 ArrayList 默认的元素存储数据是否为空, 为空则设置最小要求的存储能力为必要存储的元素和默认存储元素个数的两个数据之间的最大值, 然后调用 ensureExplicitCapacity 方法实现这种最低要求的存储能力
注意: ArrayList 的存储空间并不是需要一个创建一个, 而是分阶段性的创建, 一般会预留存储空间. 例如, 如果 ArrayList 需要存储 10 个元素, 恰好 ArrayList 只能存储 6 个元素, 剩余 4 个元素无法存储, ArrayList 可能会一次性扩展 10 个元素, 这种 ArrayList 就有 20 个元素的存储能力, 在存储能力范围内, 下次再存放元素, 就不需要再次扩容
3: 分析 ensureExplicitCapacity 方法:
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- grow(minCapacity);
- }
分析: 如果最低要求的存储能力 > ArrayList 已有的存储能力, 这就表示 ArrayList 的存储能力不足, 因此需要调用 grow(); 方法进行扩容 4: 分析 grow() 方法
- 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);
- }
分析: 当 ArrayList 扩容的时候, 首先会设置新的存储能力为原来的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity www.michenggw.com>> 1);
如果扩容之后还是不能满足要求则 MAX_ARRAY_SIZE 比较, 求取最大值, 如果 MAX_ARRAY_SIZE 大小的能力还是不能满足则通过 hugeCapacity() 方法获取 ArrayList 能允许的最大值:
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity <0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity> MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
从 hugeCapacity 方法看出, ArrayList 最大的存储能力: 存储元素的个数为整型的范围. 确定 ArrayList 扩容之后最新的可存储元素个数时, 调用 elementData = Arrays.copyOf(elementData, newCapacity); 实现 elementData 数组的扩容, 整个流程就是 ArrayList 的自动扩容机制工作流程
扩展: ArrayList 的自动扩容机制底层借助于 System 实现
- public static native void arraycopy
- (Object src, int srcPos,
- Object dest, int destPos,
- int length);
arraycopy 标识为 native 意味 JDK 的本地库, 不可避免的会进行 IO 操作, 如果频繁的对 ArrayList 进行扩容, 毫不疑问会降低 ArrayList 的使用性能, 因此当我们确定添加元素的个数的时候, 我们可以事先知道并指定 ArrayList 的可存储元素的个数, 这样当我们向 ArrayList 中加入元素的时候, 就可以避免 ArrayList 的自动扩容, 从而提高 ArrayList 的性能
ArrayList 含参构造函数: 初始化时指定存储元素的能力:
- public ArrayList(int initialCapacity) {
- if (initialCapacity www.dasheng178.com> 0) {
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException(
- "Illegal Capacity:"+initialCapacity);
- }
来源: http://www.bubuko.com/infodetail-2949208.html