2018年1月

本文采用知识共享 署名-相同方式共享 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

  1. 默认newCapacity(新容量)为原来elementData长度1.5倍(二进制右移一位为原来的1/2,加上本身1)
  2. 默认容量和需求容量取最大值
  3. 如果newCapacity超过MAX_ARRAY_SIZE(最大数组大小,默认为Integer.MAX_VALUE-8,为什么要减8呢,这篇文章有讲引用类型的开销-From Java code to Java heap),则用hugeCapacity函数尝试获取Integer.MAX_VALUE。
  4. 最后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的函数扩容机制。

Title - Artist
0:00