前言

業精于勤荒于嬉，行成于思毀于隨；

在碼農的大道上，唯有自己強才是真正的強者，求人不如求己，靜下心來，開始思考…

今天一起來聊一聊 List集合，看到這里，筆者懂，大家莫慌，先來寶圖鎮樓 ~

我要打十個年輕人，敢偷襲我老同志，耗子尾汁…

咳咳… 相信大家滿腦子的ArrayList已被保國爺爺經典的畫面以及臺詞沖淡了，那么，目的已達到，那我們言歸正傳，對于螢屏前帥氣的猿友們來說，ArrayList，LinkedList，Vector，CopyOnWriteArrayList… 張口就來，閉眼能寫，但是呢，我相信大部分的猿友們并沒有刨根問底真正去看過其原始碼，此時，筆者帥氣的臉龐似有似無洋溢起一抹微笑，畢竟是查看過原始碼的猿，就是那么的不講武德，吃我一記閃電五連鞭，話不多說，來吧，展示…

一、List類圖

二、原始碼剖析

1. ArrayList（此篇詳解）

• 建構式

    // 默認值-空陣列
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // ArrayList底層為陣列 transient關鍵字：當前陣列不能被序列化
    transient Object[] elementData; 

    /**
     * 建構式
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

從原始碼中可以看出，構造只為底層陣列進行初始化，默認值為空陣列；

• add() - 添加元素方法

    // ArrayList元素個數
    private int size;

    // 默認初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 記錄對ArrayList操作次數
    protected transient int modCount = 0;

    // ArrayList最大元素個數
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 添加入口
     */
    public boolean add(E e) {
        // 對陣列進行初始化以及擴容
        ensureCapacityInternal(size + 1);
        // 陣列中添加元素
        elementData[size++] = e;
        return true;
    }

    // 1.對陣列進行初始化以及擴容
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 2.計算最小容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 判斷陣列是否為空，即為第一次添加元素
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // max方法：a >= b ? a : b
            // eg: 10 >= 1 -> 10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    // 3.判斷是否需要擴容
    private void ensureExplicitCapacity(int minCapacity) {
        // modCount(記錄修改次數) -> 在當前執行緒使用迭代器的程序中，如有其他執行緒修改了modCount(會判斷是否修改操作有誤(執行緒安全問題)) -> 拋出ConcurrentModificationException例外
        //      Fail-Fast 機制，快速失敗機制，modCount宣告為volatile，保證執行緒之間修改的可見性
        modCount++;

        // 判斷是否進行擴容
        if (minCapacity - elementData.length > 0)
            // 具體擴容方法
            grow(minCapacity);
    }

    // 4.具體擴容
    private void grow(int minCapacity) {
        // 獲取資料長度
        int oldCapacity = elementData.length;
        // 計算擴容后長度，第一次為例：0 + (0 >> 1) = 0 + 0 = 0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 判斷如果擴容后長度-最小容量<0,擴容后的長度為最小容量，此判斷作用于第一次添加元素時
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 計算擴容后長度最大值，最大值為Integer的最大值(2^31-1)
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
        }

        // 使用 Arrays.copyOf 對我們陣列容量實作擴容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

從原始碼中可以看出，添加元素時且會對陣列進行初始化或者擴容；

知識點：
第一次擴容也就是第一次add時：陣列長度length擴容為10，集合size為1；
第二次擴容也就是第十一次add時：陣列長度length擴容為15，集合size為11；
之后每次擴容遵循以下規則，oldCapacity + (oldCapacity >> 1)；

結論：
每擴容后為之前陣列長度的1.5倍，最大值：Integer最大值(2^31-1)，最小值：10；

• get() - 獲取元素方法

    /**
     * 入口
     */
    public E get(int index) {
        // 校驗是否越界
        rangeCheck(index);

        // so easy：通過下標獲取元素
        return elementData(index);
    }

    // 校驗下標是否越界
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }

從原始碼中可以看出，獲取元素時就是獲取陣列元素，通過下標直接獲取即可；

• remove() - 洗掉元素方法

    /**
     * 入口
     */
    public E remove(int index) {
        // 校驗下標是否越界
        rangeCheck(index);

        // add()方法中已詳情描述
        modCount++;

        // 獲取要洗掉的元素
        E oldValue = elementData(index);

        /**
         * public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
         *  說明此方法引數作用：
         *      src：源陣列
         *      srcPos：源陣列復制的起始位置
         *      dest：目的陣列
         *      destPos：目標陣列放置的起始位置
         *      length：陣列元素被復制的數量
         */
        // 對應引數中length
        int numMoved = size - index - 1;
        // 洗掉元素其實就是一個陣列整體移動的程序，再將最后一個元素置空即可
        if (numMoved > 0)
            // 此每個引數都需各位猿友細品下，慢慢來，只是一個程序... 如此如此，這般這般，暖男的我在下方提供圖，便于猿友們理解
            System.arraycopy(elementData, index+1, elementData, index, numMoved);

        // 將最后一個元素置空，如只有一個元素，置空即可，便于GC作業
        elementData[--size] = null; // clear to let GC do its work

        // 回傳洗掉的元素值
        return oldValue;
    }

從原始碼中可以看出，洗掉元素實則為陣列移動覆寫的程序，已下圖為例，便于大家理解：

• 源陣列：
  
• 目標陣列(洗掉元素后的陣列)：
  
• 洗掉下標為0的元素(不)

結合 arraycopy(Object src, int srcPos, Object dest, int destPos, int length)來講，可得知：

1. src：為上述源陣列；
2. srcPos：源陣列要復制的起始位置為(index+1 = 0+1 = 1)
3. dest：為上述目標陣列
4. destPos：目標陣列放置的起始位置為(index=0)；
5. length：復制的長度為(size-index-1 = 4-0-1 = 3)

• 程序演示：
  
• 劃重點：

相信之前沒仔細研究過的猿友們，對ArrayList洗掉元素大概程序已有一些了解；

但對于有經驗的開發猿來說，筆者大概能猜到兩種，一種是一心追隨本心道心堅固的猿友，另一種呢就是追求大道審視局勢的猿友；

前者：看到這里，不論是從筆者的描述還是圖文結合的理解，貌似有一定的道理，但當時的我看并不是如此，既然是arraycopy，那就不應該是移動覆寫，而是重新復制一個新陣列，

后者：我當時查閱原始碼好像覺得也并不是這樣的，記得也是復制一個新陣列，而不是移動覆寫，但筆者描述確又很在理，難道…遺漏了什么？

邪魅一笑，嘴角微起，來吧，展示…

其實嘛，大家說的都沒錯，實際上確實是復制新的陣列，但ArrayList這里，源陣列和目標陣列是用一個呢.

哎…人生么，如此這般，細節決定成敗，

• ArrayList總結：

1. 底層為陣列；
2. 構造初始化，陣列為空陣列，集合size為0，陣列length為0；
   第一次擴容也就是第一次add時：陣列長度length擴容為10，集合size為1；
   第二次擴容也就是第11次add時：陣列長度length擴容為15，集合size為11；
   之后每次擴容遵循以下規則，oldCapacity + (oldCapacity >> 1)，故每次擴容為之前陣列長度的1.5倍；
   最大值：Integer最大值2147483647(2^31-1)，最小值：10；
3. 通過下標去獲取元素，故查詢效率高，增刪效率低；
4. 執行緒不安全；
5. 有modCount；

2. LinkedList

不講武德，一起聊聊List集合之LinkedList

3. Vector

不講武德，一起聊聊List集合之Vector

4. CopyOnWriteArrayList

不講武德，一起聊聊List集合之CopyOnWriteArrayList

~~ 碼上福利

大家好，我是猿醫生：

在碼農的大道上，唯有自己強才是真正的強者，求人不如求己，靜下心來，掃碼一起學習吧…