ArrayList数组扩容方式（基于jdk1.8）

ArrayList无参构造函数为：

public ArrayList() {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

而DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空数组，即无参ArrayList创建时内部初始容量为0，

当向ArrayList中增加数据时，先检查elementData数组的大小，如果elementData数组已经无法在存放元素，需要进行扩容，具体的扩容方法为grow方法

public boolean add(E e) {

    //检查elementData数组是否可以能够存放下一个元素，

    ensureCapacityInternal(size + 1);  // Increments modCount!!

    elementData[size++] = e;

    return true;

}

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

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        //这种情况是无参构造方法创建的ArrayList，增加数据时elementData扩容为DEFAULT_CAPACITY(该值为10)大小的数组，

        return Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    return minCapacity;

}

private void ensureCapacityInternal(int minCapacity) {

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

        grow(minCapacity);

}

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

}

测试程序如下：

private static void testArrayList() throws Exception {
    List<String> list = new ArrayList<>();
    Field field = ArrayList.class.getDeclaredField("elementData");
    field.setAccessible(true);
    for (int i = 0; i < 100; i++) {
        Object[] data = (Object[]) field.get(list);
        int before = data.length;
        list.add(String.valueOf(i));
        data = (Object[]) field.get(list);
        int after = data.length;
        if (before != after) {
            System.out.println(String.format("增加第%s个元素时进行了扩容，原来内部数组大小为：%s，扩容后为：%s", i + 1, before, after));
        }
    }
}

测试结果如下：

增加第1个元素时进行了扩容，原来内部数组大小为：0，扩容后为：10
增加第11个元素时进行了扩容，原来内部数组大小为：10，扩容后为：15
增加第16个元素时进行了扩容，原来内部数组大小为：15，扩容后为：22
增加第23个元素时进行了扩容，原来内部数组大小为：22，扩容后为：33
增加第34个元素时进行了扩容，原来内部数组大小为：33，扩容后为：49
增加第50个元素时进行了扩容，原来内部数组大小为：49，扩容后为：73
增加第74个元素时进行了扩容，原来内部数组大小为：73，扩容后为：109

如果将ArrayList初始容量设置为5，即List<String> list = new ArrayList<>(5);

测试结果如下：

增加第6个元素时进行了扩容，原来内部数组大小为：5，扩容后为：7
增加第8个元素时进行了扩容，原来内部数组大小为：7，扩容后为：10
增加第11个元素时进行了扩容，原来内部数组大小为：10，扩容后为：15
增加第16个元素时进行了扩容，原来内部数组大小为：15，扩容后为：22
增加第23个元素时进行了扩容，原来内部数组大小为：22，扩容后为：33
增加第34个元素时进行了扩容，原来内部数组大小为：33，扩容后为：49
增加第50个元素时进行了扩容，原来内部数组大小为：49，扩容后为：73
增加第74个元素时进行了扩容，原来内部数组大小为：73，扩容后为：109

巴特西

ArrayList数组扩容方式（基于jdk1.8）

最新文章

热门文章