美文网首页Java集合类源码探究
【java容器的刻意练习】【三】ArrayList动态扩容

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

作者: 程序猿修仙传 | 来源:发表于2020-01-31 12:48 被阅读0次

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

    先给出结论。

    1. 每添加一个元素,检查数组剩余空间是否足够
    2. 如果第一次添加元素,就创建容量为10的数组
    3. 如果数组剩余空间不足,触发扩容
    4. 每次扩容现有容量的50%
    5. 把旧数组内容拷贝到新数组
    6. 添加新元素

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

    先对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自动扩容的逻辑:

    1. 每添加一个元素,检查数组剩余空间是否足够
    2. 如果第一次添加元素,就创建容量为10的数组
    3. 如果数组剩余空间不足,触发扩容
    4. 每次扩容现有容量的50%
    5. 把旧数组内容拷贝到新数组
    6. 添加新元素
    ArrayList扩容示意图

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

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

    相关文章

      网友评论

        本文标题:【java容器的刻意练习】【三】ArrayList动态扩容

        本文链接:https://www.haomeiwen.com/subject/ktmwthtx.html