前言

說到List我們都會提到它的頂級結構collection，collection也就是我們經常說到的java集合框架之一，通常我們在面試或平常都會說collection下有list和set介面，但是實際代碼是這樣的么，我們來看看真實的collection類圖

collection類下的子類其實不少，只不過我們實際作業中經常用到的就是我標紅的三種，List,Set,Queue，今天我們的主角就是其中之一的List介面，既然今天要看List,首先我們來看一下List的類圖

List中我們常用的子類有ArrayList,Vector，LinkedList，CopyOnWriteArrayList，List是存盤有序的可重復的元素的，且該元素可以是null

接下來我們簡單的看看這四種List，給個簡單的結果定義

/**
 * 普通陣列實作的，執行緒不安全
 */
static List<String> arrayList = new ArrayList<String>();
/**
 * 雙向鏈表實作的，執行緒不安全
 */
static List<String> linkedList = new LinkedList<String>();
/**
 * 普通陣列實作的，執行緒安全，方法級別的synchronized鎖
 */
static List<String> vector = new Vector<String>();
/**
 * 普通陣列實作的，執行緒安全,方法內部ReentrantLock鎖
 */
static List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<String>();

關于執行緒不安全，大家有興趣的可以去看看我的另外一篇博客，執行緒不安全是怎么來的

https://blog.csdn.net/jy317358306/article/details/111598874

ArrayList

ArrayList的類圖

首先我們來看看ArrayList，先上ArrayList的類圖結構

從上圖我們可以看到，ArrayList的初始長度為10，我們要注意下ArrayList真實結構上的這段注釋

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */

這段注釋講了四點：
1.這個Object[] elementData是ArrayList存盤元素的陣列緩沖區
2.ArrayList的長度就是這個陣列緩沖區的長度
3.任何初始的空的ArrayList的初始時默認的Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA 這個空陣列
4.只有當有第一個元素添加的時候才會被擴容至默認的10的長度的陣列

ArrayList的構造方法

接下來我們看看初始化方法

無參構造，直接將默認的空陣列賦值給到了elementData
有參構造，根據傳入的容量大小來創建陣列，有趣的是，這里初始長度為0的時候賦值的不是默認的空陣列，而是另外一個空陣列

ArrayList的執行緒的不安全的問題

首先上測驗代碼：

/**
 * 執行緒個數
 */
private static final int COUNT = 5000;

/**
 * 普通陣列實作的，執行緒不安全
 */
static List<String> arrayList = new ArrayList<String>();

public static void multipleThreadSafetyTest() throws InterruptedException {
    // 讓執行緒提前創建好，同時去爭CPU的執行權
    final CountDownLatch countDownLatch = new CountDownLatch(COUNT);
    for (int i = 0 ; i < COUNT; i++){
        new Thread(new Runnable() {
            public void run() {
                try {
                    countDownLatch.await();
                    arrayList.add("I am arrayList !" );
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
        countDownLatch.countDown();
    }
    // 主執行緒稍微等一會兒，讓子執行緒跑完，以免影響結果的正確性
    Thread.sleep(2000);
    // 輸出結果為5000就是正確的，其他就說明出現了執行緒不安全的問題
    System.out.println("size:"+arrayList.size());
}

public static void main(String[] args) throws InterruptedException {
    multipleThreadSafetyTest();
}

再來看看執行結果，執行緒不安全不是必然出現的哦，但是多執行幾次，一定會出現錯誤的結果的

我執行了兩次就出現了執行緒安全的問題

ArrayList的擴容問題

首先看add方法

第一行ensureCapacityInternal，保證ArrayList長度夠用
第二行就是賦值操作，將當前添加的元素賦值給當前陣列的長度+1的位置上
再來看看ensureCapacityInternal方法

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

先呼叫了計算需求容量的方法calculateCapacity

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果初始時默認ArrayList的空陣列，則初始化長度為默認長度10和添加元素的長度中比較大的那個，實際第一次添加元素就是10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

再來看ensureExplicitCapacity方法

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 如果最小需求容量大于，陣列的長度，則進行擴容grow方法，其實第一次進來陣列的長度為0,所以第一次進來肯定是需要擴容的
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

再來看擴容方法grow

  /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     * 陣列的最大可分配長度位Integer的最大值-8
     * 一些虛擬機保留了一些頭部詞在陣列中
     * 如果嘗試分配超過這個數的長度的陣列一些虛擬機可能會出現記憶體溢位的錯誤
     */
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
 * 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) {
    // 記錄舊的容量
    int oldCapacity = elementData.length;
    // 新的容量為舊的容量+舊的容量的二分之一（移位1位，相當于原來的一半，取整除的結果，奇數相當于-1之后除以2）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新的容量還是不滿足需求容量，則新的容量就是最小需求容量，實際第一次add就是10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果最小容量要求超過ArrayList陣列的最大長度
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 計算新的容量，如果最小需求容量超出ArrayList的最大長度，則新的容量位Integer的最大值
        newCapacity = hugeCapacity(minCapacity);
    // 重新生成一個新的容量的陣列，并將原陣列的元素復制到新的陣列中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    // 如果最小需求容量位負數，則拋出oom例外
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果最小需求容量超出ArrayList的最大長度，則新的容量位Integer的最大值，一些虛擬機可能出現oom
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

ArrayList總結

1.ArrayList的底層存盤結構是陣列
2.ArrayList的初始長度為0，第一次添加元素時，擴容到10
3.ArrayList每次擴容為原來的1.5倍，嚴格來說是原容量+原容量的一半的整除數
4.ArrayList最大長度最好不要超過Integer的最大值減去8，不然可能會出現OOM例外
5.ArrayList是多執行緒不安全的
所以針對以上知識再來個用法總結
1.由于ArrayList底層是陣列，每次擴容是先生成新陣列，然后復制舊陣列的元素到新陣列，所以最好能確定容量的時候給定容量
2.由于ArrayList的陣列有序并且容易發生擴容操作，陣列的元素是連續存盤，并且有序號，所以ArrayList適合讀多寫少的場景
3.由于ArrayList陣列多執行緒不安全，所以多執行緒環境下要考慮執行緒安全問題

Vector

vector實際上跟ArrayList幾乎是一樣的，只是在會產生執行緒安全的方法上加上了synchronized鎖來保證執行緒安全

LinkedList

LinkedList的類圖

LinkedList存盤資料時通過Node來存盤的，Node時LinkedList的一個內部類，LinkedList只記錄了第一個和最后一個節點的資訊，類圖如下：

Node的item屬性存盤每個節點的資料，而next和prev分別指向自己的下一個節點和前一個節點

所以LinkedList的整個的資料結構是這樣的一個雙向鏈表

每次新增一個元素都是將當前元素作為鏈表的最后一個元素存盤，并且將之前的最后一個元素的下一個節點指向添加的節點，將當前添加的節點的上一個節點指向之前的最后一個元素的節點，由于各個Node元素是獨立存在于記憶體中的，所以LinkedList沒有容量這個概念，也沒有擴容的程序，所以LinkedList適合寫多讀少的情況，因為LinkedList查找元素必須從頭部或者尾部逐個去查找到我們需要的那個元素，而ArrayList是直接能定位到讀取的那個元素
linkedList添加元素的程序：

/**
 * Links e as last element.
 */
void linkLast(E e) {
    // l節點為尾部節點
    final Node<E> l = last;
    // new一個新節點
    final Node<E> newNode = new Node<>(l, e, null);
    // 將新節點作為尾部節點
    last = newNode;
    // 如果原LinkedList尾部節點為空，則將新節點當作首節點
    if (l == null)
        first = newNode;
    else
        // 否則修改尾節點的下一個節點指向當前的新節點
        l.next = newNode;
    // 修改LinkedList的長度
    size++;
    modCount++;
}

LinkedList的執行緒不安全

同樣LinkedList的Node和Size是共享變數，所以LinkedList在多執行緒情況下也是不安全的

CopyOnWriteArrayList

CopyOnWriteArrayList的類圖

CopyOnWriteArrayList也是由一個普通陣列來作為實際資料的存盤容器的，每個實體會持有一個ReentrantLock實體，所以CopyOnWriteArrayList也是一樣適合讀多寫少的場景

不同于ArrayList的是CopyOnWriteArrayList沒有指定容量的方法，每一次添加都是一次重新創建新的陣列，復制之前的資料到新的陣列的一個程序

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 鎖住當前代碼塊
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 創建一個新的陣列物件，并拷貝之前的陣列的元素
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 將新添加的節點賦值給新陣列的最后一位
        newElements[len] = e;
        // 將新陣列作為當前CopyOnWriteArrayList物件的基本容器
        setArray(newElements);
        return true;
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

那CopyOnWriteArrayList特殊在哪里呢，它的讀方法沒有加鎖，但是是執行緒安全的，并且它是可以一邊遍歷，一邊操作的資料的，原因就是add和remove的操作物件都不是它本身存盤元素的array這個陣列，而是在方法中新生成的陣列中去操作的，其實這就是一種讀寫分離的想法

/**
 * {@inheritDoc}
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    return get(getArray(), index);
}

CopyOnWriteArrayList的優缺點

優點：

1.執行緒安全

2.可以一邊遍歷，一邊操作資料

3.讀寫分離，只有寫寫有鎖，任何讀讀、讀寫都是沒有鎖的

缺點：

1.新增元素都會冗余一份原陣列，消耗記憶體

2.讀寫之間存在不一致性，寫資料有一定的延遲性