簡單複習一下ArrayList的擴容原理

剛剛跟幾個好朋友喝完小酒回家，簡單大概複習一下ArrayList的擴容原理，由於頭有點小暈，就只大概說一下擴容的原理哈；

首先ArrayList實現了List介面，繼承了AbstractList，大家都知道底層是由數組實現的，但是我們都知道數組是不會增的，那麼ArrayList是如何自增擴容的呢？

我們直接看它的add方法源碼

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
 
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        int oldCapacity= this.elementData.length;
        int newCapacity= oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
 
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
 
        this.elementData = Arrays.copyOf(this.elementData, arg2);
    }

size是當前集合擁有的元素個數，從源碼看出，調用了ensureCapacityInternal來保證容量問題，傳進去的參數是size+1，保證集合+1之後能夠存儲下一個數據。

DEFAULT_CAPACITY是ArrayList定義的靜態常量10；

判斷elementData是否是空數組，如果是則取一個較大的值；

接下來modCount++，這個值說過的，在保證fail-fast機制的時候協助使用的，用於判斷集合的結構是否發生了變化；

新增元素後的長度值減去當前的容量值是否大於0，這裡就是判斷是否需要擴容的關鍵方法；

新長度 = 原長度 + 原長度右移以為位運算   ->   新長度 = 原長度 + 0.5倍原長度

如果新長度還是小於集合所需最小長度，則把最小長度賦值給新長度；而不進行擴容了；

如果新長度超過了最大的容量，則調用hugeCapacity方法，這個方法裡面判斷，源碼是一個三元運算：(最小所需長度 > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;

其實說白了就是調用Arrays.copyOf方法，講原數組複製到一個新的大容量數組；