ArrayList擴(kuò)容

參考：
https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

一挽绩、初始化

0罗珍、內(nèi)部組成
ArrayList內(nèi)部有一個(gè)數(shù)組elementData來存放數(shù)據(jù)客燕，還有一個(gè)整數(shù)size來記錄實(shí)際的元素個(gè)數(shù)。

private transient Object[] elementData;
private int size;

重要的數(shù)據(jù)：

DEFAULT_CAPACITY 默認(rèn)容器大小
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 默認(rèn)空數(shù)組巡通，調(diào)用空參構(gòu)造函數(shù)時(shí)elementData的默認(rèn)值

/**
     * 默認(rèn)初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;
    

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

1、以無參數(shù)構(gòu)造方法創(chuàng)建 ArrayList 時(shí)，實(shí)際上初始化賦值的是一個(gè)空數(shù)組宅广。
源碼：

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2、使用帶初始容量參數(shù)的構(gòu)造函數(shù)時(shí)（用戶自己指定容量）些举，在參數(shù)合法的情況下（大于等于0）跟狱，分配給指定大小的數(shù)組。
源碼：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //創(chuàng)建initialCapacity大小的數(shù)組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //創(chuàng)建空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0户魏，拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

二驶臊、擴(kuò)容機(jī)制

1. add方法

/**
     * 將指定的元素追加到此列表的末尾。 
     */
    public boolean add(E e) {
   //添加元素之前叼丑，先調(diào)用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //這里看到ArrayList添加元素的實(shí)質(zhì)就相當(dāng)于為數(shù)組賦值
        elementData[size++] = e;
        return true;
    }

當(dāng)我們調(diào)用add方法時(shí)关翎，add方法會(huì)先調(diào)用ensureCapacityInternal(size + 1)

2. ensureCapacityInternal方法(容量最小值為10)

add方法首先調(diào)用了ensureCapacityInternal(size + 1)

//得到最小擴(kuò)容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 獲取默認(rèn)的容量和傳入?yún)?shù)的較大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

當(dāng)ArrayList是無參構(gòu)造且第一次調(diào)用add時(shí)，minCapacity 會(huì)被賦予DEFAULT_CAPACITY的值也就是10鸠信；

3. ensureExplicitCapacity(判斷是否需要擴(kuò)容)

ensureCapacityInternal一定會(huì)調(diào)用ensureExplicitCapacity(minCapacity);

//判斷是否需要擴(kuò)容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //調(diào)用grow方法進(jìn)行擴(kuò)容纵寝，調(diào)用此方法代表已經(jīng)開始擴(kuò)容了
            grow(minCapacity);
    }

最少所需容量minCapacity 大于內(nèi)置數(shù)組elementData的長度時(shí)，調(diào)用grow(minCapacity)擴(kuò)容

4. grow(1.5倍擴(kuò)容)擴(kuò)容核心

ArrayList 每次擴(kuò)容之后容量都會(huì)變?yōu)樵瓉淼?1.5 倍左右（oldCapacity為偶數(shù)就是1.5倍星立，否則是1.5倍左右）爽茴！奇偶不同葬凳，比如：10+10/2 = 15, 33+33/2=49。如果是奇數(shù)的話會(huì)丟掉小數(shù).

/**
     * 要分配的最大數(shù)組大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList擴(kuò)容的核心方法室奏。
     */
    private void grow(int minCapacity) {
        // oldCapacity為舊容量沮明，newCapacity為新容量
        int oldCapacity = elementData.length;
        //將oldCapacity 右移一位，其效果相當(dāng)于oldCapacity /2窍奋，
        //我們知道位運(yùn)算的速度遠(yuǎn)遠(yuǎn)快于整除運(yùn)算荐健，整句運(yùn)算式的結(jié)果就是將新容量更新為舊容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后檢查新容量是否大于最小需要容量琳袄，若還是小于最小需要容量江场，那么就把最小需要容量當(dāng)作數(shù)組的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE窖逗，
       //如果minCapacity大于最大容量址否，則新容量則為`Integer.MAX_VALUE`，否則碎紊，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`乐尊。
        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);
    }

4. hugeCapacity

從上面 grow() 方法源碼我們知道：如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) hugeCapacity() 方法來比較 minCapacity 和 MAX_ARRAY_SIZE缓升，如果minCapacity大于最大容量眠屎，則新容量則為Integer.MAX_VALUE千扶，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 Integer.MAX_VALUE - 8秃嗜。

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //對minCapacity和MAX_ARRAY_SIZE進(jìn)行比較
        //若minCapacity大权均，將Integer.MAX_VALUE作為新數(shù)組的大小
        //若MAX_ARRAY_SIZE大，將MAX_ARRAY_SIZE作為新數(shù)組的大小
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

ArrayList擴(kuò)容機(jī)制總結(jié)

ArrayList的底層是數(shù)組锅锨，有兩個(gè)核心內(nèi)置元素：
1叽赊、 elementData 是其底層數(shù)組，存放數(shù)據(jù)元素的地方必搞。
2必指、 size是當(dāng)前存放元素的個(gè)數(shù)。
初始化時(shí)恕洲，若使用無參構(gòu)造塔橡，elementData 指向一個(gè)空數(shù)組；若使用帶參構(gòu)造研侣，則elementData 數(shù)組的初始容量大小和參數(shù)相同谱邪。
使用add方法
1、無參構(gòu)造并且未進(jìn)行添加操作的elementData 數(shù)組容量變?yōu)?0庶诡；
2、其它情況下咆课，elementData 數(shù)組應(yīng)該有的最小容量為minCapacity =size+1末誓。如果minCapacity 大于Integer.MAX_VALUE扯俱，拋出溢出異常；如果minCapacity 小于等于elementData 當(dāng)前容量喇澡，不用進(jìn)行擴(kuò)容操作迅栅；如果minCapacity 大于elementData 當(dāng)前容量，elementData 的容量擴(kuò)容為原來的1.5倍晴玖。如果擴(kuò)容后的容量不大于minCapacity 读存，則elementData 的容量擴(kuò)容為minCapacity ；如果如果擴(kuò)容后的容量大于MAX_ARRAY_SIZE呕屎，當(dāng)minCapacity > MAX_ARRAY_SIZE時(shí)elementData 的容量擴(kuò)容為Integer.MAX_VALUE让簿，當(dāng)minCapacity <MAX_ARRAY_SIZE時(shí)elementData 的容量擴(kuò)容為MAX_ARRAY_SIZE。