ArrayList扩容源码解析(JDK1.8)

╰半夏微凉° 2022-02-25 02:40 318阅读 0赞

环境：JDK1.8

![2019033115033452.png][]

先看看几个ArrayList内部成员变量：

![20190331150416341.png][]

ArrayList的容量大小

![20190331150438342.png][]

默认的初始容量为10：DEFAULT\_CAPACITY = 10。

![20190331150515182.png][]

对于所有的空实例可共享的空阵列实例EMPTY\_ELEMENTDATA。

![20190331150554891.png][]

对于所有的空实例可共享的空阵列实例DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，不同于EMPTY\_ELEMENTDATA在于该数组可记录第一个元素被添加的时候，容器至少需要多大的空间

![20190331150643851.png][]

存储ArrayList元素的数组缓冲区，ArrayList的容量即为该阵列数据缓冲区的长度。当添加第一个元素时，任意刚开始容量为DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA的空ArrayList的容量都会扩充到DEFAULT\_CAPACITY，也就是10。

![20190331150710922.png][]

内部数组可以分配的最大容量MAX\_ARRAY\_SIZE=Integer.MAX\_VALUE(为整型数最大值)-8，为何要减8呢？因为这个8的空间用于存储数组\_length字段。

查看add(E e)方法：

/**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return <tt>true</tt> (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

查看ensureCapacityInternal(int minCapacity)方法、ensureExplicitCapacity(int minCapacity)方法以及calculateCapacity(Object\[\] elementData, int 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);
        }

ensureExplicitCapacity方法实现：

1. modCount++。

2. 如果需扩充的容量大小minCapacity大于原内部数组大小，则调用grow方法。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }

calculateCapacity方法实现：

1. 传入原内部数组elementData和需扩充的容量大小minCapacity。

2. 如果elementData为空数组则比较默认初始容量DEFAULT\_CAPACITY=10与参数minCapacity的大小，取大返回。

3. 如果elementData不为空，则返回minCapacity。

查看grow(int minCapacity)方法：

增加容量以确保ArrayList能保留指定的最小容量参数下的元素数量

/**
         * 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
         */
        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);
        }

grow方法实现：

a. 取得elementData的长度为原容量oldCapacity。

b. oldCapacity >> 1表示位运算，为oldCapacity转换成二进制后向右移动1位，当前可理解为java中**oldCapacity / 2**的结果，以后会专门写一篇帖子来说明位运算。故可以理解为**新容量newCapacity为oldCapacity+1/2的oldCapacity**，此时再比较newCapacity和参数要求容量(至少得需要到参数要求的容量大小，不然无法将元素存放到ArrayList)，如果小于则newCapacity设置为minCapacity，否则再比较newCapacity和MAX\_ARRAY\_SIZE，如果前者大于后者，则查看hugeCapacity(int minCapacity)方法

![20190331151303682.png][]

当容量参数小于0，抛出异常OutOfMemoryError()。如果参数大于MAX\_ARRAY\_SIZE，则返回Integer.MAX\_VALUE(为整型数最大值)，否则返回MAX\_ARRAY\_SIZE。最后将返回值赋给newCapacity

c. 将原内部数组和新的容量长度融合为新的内部数组对象(内容不变，容量扩充)。

结论：

1. ArrayList对象群初始化时可不传参，共享内部数组对象，大小为空。

2. 当添加第一个元素时，内部扩容为**默认大小10**。

3. 当添加到大于10个元素时，则以后每次需扩容时，规则为**newCapacity(新容量) = oldCapacity(原容量) +oldCapacity/2****。**

4. 将最新添加的元素放入当前ArrayList内部数组的size++位，即elementData\[size++\] = e;

额外说明：**ArrayList从字面上看，底层是用数组实现的，增删查等操作也和数组的这类操作特性一致**。

打个比方：

1. 添加第1个元素则内部数组扩充为默认大小10即elementData的大小为10。

2. 添加第11个元素时，则一直执行到grow方法，传参为11，oldCapacity为10，newCapacity变为15，elementData的大小为15，size当下为15，elementData\[size++\] = e，设置第11个数组元素。

3. 添加第16个元素时，则一直执行到grow方法，传参为16，oldCapacity为15，newCapacity变为22，elementData的大小为22，size当下为15，elementData\[size++\] = e，设置第16个数组元素。

以此类推...

解决具体面试题：

public static ArrayList<Integer> getIntegerList(int capacity) {
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		if (capacity <= 0) {
    			return list;
    		}
    		for (int i = 0; i < capacity; i++) {
    			list.add(i);
    		}
    		return list;
    	}
    	public static void main(String[] args) {
    		getIntegerList(64);
    	}

问题：以上程序中的list扩容了几次？

结合上述内容，则可以继续推倒：

4. 当添加第23个元素时，则newCapacity变为33，elementData的大小为33，设置第23个数组元素。

5. 当添加第34个元素时，则newCapacity变为51，elementData的大小为51，设置第34个数组元素。

6. 当添加第52个元素时，则newCapacity变为78，elementData的大小为78，设置第52个数组元素。

64在第78个元素之前，则经过6次扩容即可满足list.add(63)的需求。

答案为：6次

[2019033115033452.png]: /images/20220225/a02ced3abe1c49fb98369bf1a42ac220.png
[20190331150416341.png]: /images/20220225/f75dec59596c4e758ba5697cb62158be.png
[20190331150438342.png]: /images/20220225/399b495262074e3bb19d29eef6f265ed.png
[20190331150515182.png]: /images/20220225/2375c9dc97bf4a1bb29134fcbbc6f5b0.png
[20190331150554891.png]: /images/20220225/060dd3ae066d44e29e8c19f908d5e340.png
[20190331150643851.png]: /images/20220225/dc5995308d4f435e889a553f77fe0d9d.png
[20190331150710922.png]: /images/20220225/6bbbec01f0a74a57ade2aece63db9594.png
[20190331151303682.png]: /images/20220225/4aea877adf934d9793205824c4796412.png