【java容器的刻意练习】【三】ArrayList动态扩容

2020-01-31 本文已影响0人程序猿修仙传

上一篇我们知道了，ArrayList核心是个数组。那么，心中肯定有个疑问：ArrayList是怎么实现数组的扩容的？

先给出结论。

每添加一个元素，检查数组剩余空间是否足够

如果第一次添加元素，就创建容量为10的数组

如果数组剩余空间不足，触发扩容

每次扩容现有容量的50%

把旧数组内容拷贝到新数组

添加新元素

这一篇我们来看看，怎么得出上面这个结论的。

先对arrayList添加一个元素。

arrayList.add(123);

调用如下方法：

    public boolean add(E e) {
        // 增加数组修改的次数
        modCount++;

        // 调用add私有方法进行元素添加
        add(e, elementData, size);
        return true;
    }

这里的modCount是啥？跳过去看看，原来这个是继承自AbstractList中的字段，表示数组修改的次数，数组每修改一次，就要增加modCount。

还有个size又是啥？跳过去看看，原来是数组包含的元素个数。

size的注释

接着调用了另外一个add私有方法：

    private void add(E e, Object[] elementData, int s) {
        
        // 如果数组已满
        if (s == elementData.length)
            // 当然是扩容啦
            elementData = grow();

        // 还有空间或者扩容完毕，就添加元素
        elementData[s] = e;

        // 增加数组元素个数
        size = s + 1;
    }

终于找到扩容的方法，原来叫 grow 。赶紧跳过去看看。

    private Object[] grow() {
        return grow(size + 1);
    }

呃，又封了一层，传了新增元素后的个数当参数进去。

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

作者的注释说，这个扩容函数保证至少扩容到传进来的最小容量。
所以，minCapacity就是扩容要求的最小容量。那么最大是多少呢？

好像这个最大容量的计算挺复杂，那我们先看这个if-else。

如果数组已经有元素，那么通过ArraysSupport.newLength计算需要扩容的大小，通过Arrays.copyOf创建一个新的大数组，把旧的小数组拷贝过去。如果没有新元素，就创建大小为10的数组。

噢！原来ArrayList自动扩容就这么回事！

知道了原理后，我们就深入想想，如果频繁的扩容，肯定是不行的。但是，一下子创建很大的数组，又非常浪费。那么，应该怎么扩容才合理呢？

我们看看如何计算每次扩容最大容量的。

int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);

oldCapacity 是扩容前的数组大小，这里我们假设是10。
minCapacity - oldCapacity是最小需要扩容的大小。如果只添加一个元素，那么就是1。
oldCapacity >>1右移一位就是除以2，就是原来数组的50%。假设例子中10的一半就是5。

那么，这个ArraysSupport.newLength是什么函数呢？跳过去看看。

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // assert oldLength >= 0
        // assert minGrowth > 0

        // 最小容量与预计增长容量取较大那个，然后加上原来数组大小
        int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
        if (newLength - MAX_ARRAY_LENGTH <= 0) {
            return newLength;
        }
        return hugeLength(oldLength, minGrowth);
    }

原来，扩容后的大小是原来的1.5倍。假设例子中10的1.5倍就是15。

当然，代码中还用hugeLength函数考虑到扩容的上限，是Integer.MAX_VALUE即是0x7fffffff，以及超出上限会抛异常OutOfMemoryError，如下图。

数组大小超出最大上限的处理

到这里，我们终于知道了ArrayList自动扩容的逻辑：

每添加一个元素，检查数组剩余空间是否足够

如果第一次添加元素，就创建容量为10的数组

如果数组剩余空间不足，触发扩容

每次扩容现有容量的50%

把旧数组内容拷贝到新数组

添加新元素

ArrayList扩容示意图

到这里还没完，我们有一个额外的问题：怎么创建ArrayList最合理？

如果少于10个，直接创建个空的就行。
如果确定数组的大概数量，创建时候直接传入最大的量级，或者在合适时机提前调用ensureCapacity扩容。这样可以减少每次只扩容50%多次拷贝问题。
当确认数据已经添加完毕，如有必要，可以调用trimToSize回收多余的空间，这样可以节省内存空间。

【java容器的刻意练习】【三】ArrayList动态扩容

猜你喜欢

热点阅读