引言

• ArrayList，LinkedList，Vector，CopyOnWriteArrayList 底層實(shí)現(xiàn)原理和四個(gè)集合的區(qū)別是什么？
• 為什么工作中會(huì)常用ArrayList和CopyOnWriteArrayList？
• 如果面試官問你ArrayList和LinkedList有什么區(qū)別？

上圖：

image

基礎(chǔ)介紹

ArrayList : 基于數(shù)組實(shí)現(xiàn)的非線程安全的集合。查詢?cè)乜欤迦?，刪除中間元素慢。
LinkedList : 基于鏈表實(shí)現(xiàn)的非線程安全的集合。查詢?cè)芈?，插入，刪除中間元素快。
Vector : 基于數(shù)組實(shí)現(xiàn)的線程安全的集合。線程同步（方法被synchronized修飾），性能比ArrayList差。
CopyOnWriteArrayList: 基于數(shù)組實(shí)現(xiàn)的線程安全的寫時(shí)復(fù)制集合。線程安全（ReentrantLock加鎖），性能比Vector高，適合讀多寫少的場(chǎng)景。

ArrayList 和 LinkedList 讀寫快慢的本質(zhì)

ArrayList : 查詢數(shù)據(jù)快，是因?yàn)閿?shù)組可以通過下標(biāo)直接找到元素。 寫數(shù)據(jù)慢有兩個(gè)原因：一是數(shù)組復(fù)制過程需要時(shí)間，二是擴(kuò)容需要實(shí)例化新數(shù)組也需要時(shí)間。
LinkedList : 查詢數(shù)據(jù)慢，是因?yàn)殒湵硇枰闅v每個(gè)元素直到找到為止。 寫數(shù)據(jù)快有一個(gè)原因：除了實(shí)例化對(duì)象需要時(shí)間外，只需要修改指針即可完成添加和刪除元素。

注：這里的快和慢是相對(duì)的。并不是LinkedList的插入和刪除就一定比ArrayList快。明白其快慢的本質(zhì)：ArrayList快在定位，慢在數(shù)組復(fù)制。LinkedList慢在定位，快在指針修改。

ArrayList

ArrayList 是基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的非線程安全的集合。當(dāng)?shù)讓訑?shù)組滿的情況下還在繼續(xù)添加的元素時(shí)，ArrayList則會(huì)執(zhí)行擴(kuò)容機(jī)制擴(kuò)大其數(shù)組長(zhǎng)度。ArrayList查詢速度非常快，使得它在實(shí)際開發(fā)中被廣泛使用。美中不足的是插入和刪除元素較慢，同時(shí)它并不是線程安全的。

// 查詢?cè)?public E get(int index) {
    rangeCheck(index);                  // 檢查是否越界
    return elementData(index);
}
// 順序添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);   // 擴(kuò)容機(jī)制
    elementData[size++] = e;
    return true;
}
// 從數(shù)組中間添加元素
public void add(int index, E element) {
    rangeCheckForAdd(index);            // 數(shù)組下標(biāo)越界檢查
    ensureCapacityInternal(size + 1);   // 擴(kuò)容機(jī)制
    System.arraycopy(elementData, index, elementData, index + 1, size - index); // 復(fù)制數(shù)組
    elementData[index] = element;       // 替換元素
    size++;
}
// 從數(shù)組中刪除元素
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

從源碼中可以得知，

ArrayList在執(zhí)行查詢操作時(shí)：
第一步：先判斷下標(biāo)是否越界。
第二步：然后在直接通過下標(biāo)從數(shù)組中返回元素。

ArrayList在執(zhí)行順序添加操作時(shí)：
第一步：通過擴(kuò)容機(jī)制判斷原數(shù)組是否還有空間，若沒有則重新實(shí)例化一個(gè)空間更大的新數(shù)組，把舊數(shù)組的數(shù)據(jù)拷貝到新數(shù)組中。
第二步：在新數(shù)組的最后一位元素添加值。

ArrayList在執(zhí)行中間插入操作時(shí)：
第一步：先判斷下標(biāo)是否越界。
第二步：擴(kuò)容。
第三步：若插入的下標(biāo)為i，則通過復(fù)制數(shù)組的方式將i后面的所有元素，往后移一位。
第四步：新數(shù)據(jù)替換下標(biāo)為i的舊元素。
刪除也是一樣：只是數(shù)組往前移了一位，最后一個(gè)元素設(shè)置為null，等待JVM垃圾回收。

從上面的源碼分析，我們可以得到一個(gè)結(jié)論和一個(gè)疑問。
結(jié)論是：ArrayList快在下標(biāo)定位，慢在數(shù)組復(fù)制。
疑問是：能否將每次擴(kuò)容的長(zhǎng)度設(shè)置大點(diǎn)，減少擴(kuò)容的次數(shù)，從而提高效率？其實(shí)每次擴(kuò)容的長(zhǎng)度大小是很有講究的。若擴(kuò)容的長(zhǎng)度太大，會(huì)造成大量的閑置空間；若擴(kuò)容的長(zhǎng)度太小，會(huì)造成頻發(fā)的擴(kuò)容(數(shù)組復(fù)制)，效率更低。

LinkedList

LinkedList 是基于雙向鏈表實(shí)現(xiàn)的非線程安全的集合，它是一個(gè)鏈表結(jié)構(gòu)，不能像數(shù)組一樣隨機(jī)訪問，必須是每個(gè)元素依次遍歷直到找到元素為止。其結(jié)構(gòu)的特殊性導(dǎo)致它查詢數(shù)據(jù)慢。

// 查詢?cè)?public E get(int index) {
    checkElementIndex(index);   // 檢查是否越界
    return node(index).item;
}
Node<E> node(int index) {
    if (index < (size >> 1)) {  // 類似二分法
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
// 插入元素
public void add(int index, E element) {
    checkPositionIndex(index);  // 檢查是否越界
    if (index == size)          // 在鏈表末尾添加
        linkLast(element);
    else                        // 在鏈表中間添加
        linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev; 
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)   
        first = newNode;
    else                
        pred.next = newNode;
    size++;
    modCount++;
}

從源碼中可以得知，

LinkedList在執(zhí)行查詢操作時(shí)：
第一步：先判斷元素是靠近頭部，還是靠近尾部。
第二步：若靠近頭部，則從頭部開始依次查詢判斷。和ArrayList的elementData(index)相比當(dāng)然是慢了很多。

LinkedList在插入元素的思路：
第一步：判斷插入元素的位置是鏈表的尾部，還是中間。
第二步：若在鏈表尾部添加元素，直接將尾節(jié)點(diǎn)的下一個(gè)指針指向新增節(jié)點(diǎn)。
第三步：若在鏈表中間添加元素，先判斷插入的位置是否為首節(jié)點(diǎn)，是則將首節(jié)點(diǎn)的上一個(gè)指針指向新增節(jié)點(diǎn)。否則先獲取當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)（簡(jiǎn)稱A），并將A節(jié)點(diǎn)的下一個(gè)指針指向新增節(jié)點(diǎn)，然后新增節(jié)點(diǎn)的下一個(gè)指針指向當(dāng)前節(jié)點(diǎn)。

Vector

Vector 的數(shù)據(jù)結(jié)構(gòu)和使用方法與ArrayList差不多。最大的不同就是Vector是線程安全的。從下面的源碼可以看出，幾乎所有的對(duì)數(shù)據(jù)操作的方法都被synchronized關(guān)鍵字修飾。synchronized是線程同步的，當(dāng)一個(gè)線程已經(jīng)獲得Vector對(duì)象的鎖時(shí)，其他線程必須等待直到該鎖被釋放。從這里就可以得知Vector的性能要比ArrayList低。

若想要一個(gè)高性能，又是線程安全的ArrayList，可以使用Collections.synchronizedList(list);方法或者使用CopyOnWriteArrayList集合

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

CopyOnWriteArrayList

在這里我們先簡(jiǎn)單了解一下CopyOnWrite容器。它是一個(gè)寫時(shí)復(fù)制的容器。當(dāng)我們往一個(gè)容器添加元素的時(shí)候，不是直接往當(dāng)前容器添加，而是先將當(dāng)前容器進(jìn)行copy一份，復(fù)制出一個(gè)新的容器，然后對(duì)新容器里面操作元素，最后將原容器的引用指向新的容器。所以CopyOnWrite容器是一種讀寫分離的思想，讀和寫不同的容器。

應(yīng)用場(chǎng)景：適合高并發(fā)的讀操作（讀多寫少）。若寫的操作非常多，會(huì)頻繁復(fù)制容器，從而影響性能。

CopyOnWriteArrayList 寫時(shí)復(fù)制的集合，在執(zhí)行寫操作（如：add，set，remove等）時(shí)，都會(huì)將原數(shù)組拷貝一份，然后在新數(shù)組上做修改操作。最后集合的引用指向新數(shù)組。

CopyOnWriteArrayList 和Vector都是線程安全的，不同的是：前者使用ReentrantLock類，后者使用synchronized關(guān)鍵字。ReentrantLock提供了更多的鎖投票機(jī)制，在鎖競(jìng)爭(zhēng)的情況下能表現(xiàn)更佳的性能。就是它讓JVM能更快的調(diào)度線程，才有更多的時(shí)間去執(zhí)行線程。這就是為什么CopyOnWriteArrayList的性能在大并發(fā)量的情況下優(yōu)于Vector的原因。

private E get(Object[] a, int index) {
    return (E) a[index];
}
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;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        ......
        Object[] newElements = new Object[len - 1];
        System.arraycopy(current, 0, newElements, 0, index);
        System.arraycopy(current, index + 1, newElements, index, len - index - 1);
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

更多Java源碼、數(shù)據(jù)庫(kù)、spring boot、內(nèi)功心法等知識(shí)都是需要不斷學(xué)習(xí)、積累、實(shí)踐方能領(lǐng)會(huì)。因此我給大家推薦一個(gè)Java架構(gòu)群：895244712，里面有分布式，微服務(wù)，性能優(yōu)化等技術(shù)點(diǎn)底層原理的視頻，也有眾多想要提升的小伙伴討論技術(shù)，歡迎大家加群一起交流學(xué)習(xí)。

總結(jié)

回到文章的標(biāo)題，如果面試官問你ArrayList和LinkedList有什么區(qū)別？

ArrayList和LinkedList都不是線程安全的，小并發(fā)量的情況下可以使用Vector，若并發(fā)量很多，且讀多寫少可以考慮使用CopyOnWriteArrayList。
因?yàn)镃opyOnWriteArrayList底層使用ReentrantLock鎖，比使用synchronized關(guān)鍵字的Vector能更好的處理鎖競(jìng)爭(zhēng)的問題。

相信這個(gè)回答能夠很好的幫你通過面試：p