【原】精解四大集合框架：List核心知識(shí)總結(jié)

田維常 2020-09-20

展開(kāi)全文

回復(fù)“面試”獲取全套面試資料

Java集合框架早也是個(gè)老話題了，今天主要是總結(jié)一下關(guān)于Java中的集合框架List的核心知識(shí)點(diǎn)。肯定有人會(huì)問(wèn)，這篇寫(xiě)的是List那接下來(lái)就還有三篇？是的，java集合框架一共會(huì)有四篇。希望通過(guò)這個(gè)系列能讓你全面的get到Java集合框架的核心知識(shí)點(diǎn)。

目的

更希望通過(guò)這個(gè)系列的文章有所收獲，不僅可以用于工作中，也可以用于面試中。

Java 集合是一個(gè)存儲(chǔ)相同類型數(shù)據(jù)的容器，類似數(shù)組，集合可以不指定長(zhǎng)度，但是數(shù)組必須指定長(zhǎng)度。集合類主要從 Collection 和 Map 兩個(gè)根接口派生出來(lái)，比如常用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。包目錄：java.util

學(xué)過(guò)Java的都知道Java有四大集合框架，JDK版本1.8

List
Set
Queue
Map

常用集合UML類圖

下面展示常用的集合框架（下面圖中的兩種線：虛線為實(shí)現(xiàn)，實(shí)線為繼承）

ArrayList

ArrayList 是基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，容量能自動(dòng)增長(zhǎng)的集合。隨機(jī)訪問(wèn)效率高，隨機(jī)插入、隨機(jī)刪除效率低。線程不安全，多線程環(huán)境下可以使用 Collections.synchronizedList(list) 函數(shù)返回一個(gè)線程安全的 ArrayList 類，也可以使用 concurrent 并發(fā)包下的 CopyOnWriteArrayList 類。

動(dòng)態(tài)數(shù)組，是指當(dāng)數(shù)組容量不足以存放新的元素時(shí)，會(huì)創(chuàng)建新的數(shù)組，然后把原數(shù)組中的內(nèi)容復(fù)制到新數(shù)組。

主要屬性：

1//存儲(chǔ)實(shí)際數(shù)據(jù)，使用transient修飾，序列化的時(shí)不會(huì)被保存
2transient Object[] elementData;
3//元素的數(shù)量，即容量。
4private int size;

數(shù)據(jù)結(jié)構(gòu)：動(dòng)態(tài)數(shù)組

特征：

允許元素為 null；
查詢效率高、插入、刪除效率低，因?yàn)榇罅?copy 原來(lái)元素；
線程不安全。

使用場(chǎng)景：

需要快速隨機(jī)訪問(wèn)元素
單線程環(huán)境

常用方法介紹

add(element) 流程：添加元素

 1    private static final int DEFAULT_CAPACITY = 10;    
 2    //添加的數(shù)據(jù)e放在list的后面
 3    public boolean add(E e) {
 4        ensureCapacityInternal(size + 1); 
 5        elementData[size++] = e;
 6        return true;
 7    }
 8    private void ensureCapacityInternal(int minCapacity) {
 9        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
10    }
11    private static int calculateCapacity(Object[] elementData, int minCapacity) {
12        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
13            return Math.max(DEFAULT_CAPACITY, minCapacity);
14        }
15        return minCapacity;
16    }

判斷當(dāng)前數(shù)組是否為空，如果是則創(chuàng)建長(zhǎng)度為 10（默認(rèn)）的數(shù)組，因?yàn)?new ArrayList 的時(shí)沒(méi)有初始化；
判斷是否需要擴(kuò)容，如果當(dāng)前數(shù)組的長(zhǎng)度加 1（即 size+1）后是否大于當(dāng)前數(shù)組長(zhǎng)度，則進(jìn)行擴(kuò)容 grow()；
最后在數(shù)組末尾添加元素，并 size+1。

grow() 流程：擴(kuò)容

 1    private void grow(int minCapacity) {
 2        // overflow-conscious code
 3        int oldCapacity = elementData.length;
 4        int newCapacity = oldCapacity + (oldCapacity >> 1);
 5        if (newCapacity - minCapacity < 0)
 6            newCapacity = minCapacity;
 7        if (newCapacity - MAX_ARRAY_SIZE > 0)
 8            newCapacity = hugeCapacity(minCapacity);
 9        // minCapacity is usually close to size, so this is a win:
10        elementData = Arrays.copyOf(elementData, newCapacity);
11    }

創(chuàng)建新數(shù)組，長(zhǎng)度擴(kuò)大為原數(shù)組的 1.5 倍（oldCapacity >> 1就是相當(dāng)于10>>1==10/2=5，二進(jìn)制位運(yùn)算）；
如果擴(kuò)大 1.5 倍還是不夠，則根據(jù)實(shí)際長(zhǎng)度來(lái)擴(kuò)容，比如 addAll() 場(chǎng)景；
將原數(shù)組的數(shù)據(jù)使用 System.arraycopy（native 方法）復(fù)制到新數(shù)組中。

add(index,element) 流程：向指定下標(biāo)添加元素

 1    public void add(int index, E element) {
 2        rangeCheckForAdd(index);
 3
 4        ensureCapacityInternal(size + 1);  // Increments modCount!!
 5        System.arraycopy(elementData, index, elementData, index + 1,
 6                         size - index);
 7        elementData[index] = element;
 8        size++;
 9    }
10    private void rangeCheckForAdd(int index) {
11        if (index > size || index < 0)
12            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
13    }

檢查 index 是否在數(shù)組范圍內(nèi)，假如數(shù)組長(zhǎng)度是 2，則 index 必須 >=0 并且 <=2，否則報(bào) IndexOutOfBoundsException 異常；
擴(kuò)容檢查；
通過(guò)拷貝方式，把數(shù)組位置為 index 至 size-1 的元素都往后移動(dòng)一位，騰出位置之后放入元素，并 size+1。

set(index,element) 流程：設(shè)置新值，返回舊值

 1   public E set(int index, E element) {
 2        rangeCheck(index);
 3
 4        E oldValue = elementData(index);
 5        elementData[index] = element;
 6        return oldValue;
 7    }
 8    private void rangeCheck(int index) {
 9        if (index >= size)
10            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
11    }

檢查 index 是否在數(shù)組范圍內(nèi)，假如數(shù)組長(zhǎng)度是 2，則 index 必須小于<2，下標(biāo)是從0開(kāi)始的，size=2說(shuō)明下標(biāo)只有0和1；
保留被覆蓋的值，因?yàn)樽詈笮枰祷嘏f的值；
新元素覆蓋位置為 index 的舊元素，返回舊值。

get(index) 流程：通過(guò)下標(biāo)獲取list中的數(shù)據(jù)

1    public E get(int index) {
2        rangeCheck(index);
3        return elementData(index);
4    }

判斷下標(biāo)有沒(méi)有越界；
直接通過(guò)數(shù)組下標(biāo)來(lái)獲取數(shù)組中對(duì)應(yīng)的元素，get 的時(shí)間復(fù)雜度是 O(1)。

remove(index) 流程：按照下標(biāo)移除lsit中的數(shù)據(jù)

 1    public E remove(int index) {
 2        rangeCheck(index);
 3        modCount++;
 4        E oldValue = elementData(index);
 5        int numMoved = size - index - 1;
 6        if (numMoved > 0)
 7            System.arraycopy(elementData, index+1, elementData, index,
 8                             numMoved);
 9        elementData[--size] = null; // clear to let GC do its work
10        return oldValue;
11    }

檢查指定位置是否在數(shù)組范圍內(nèi)，假如數(shù)組長(zhǎng)度是 2，則 index 必須 >=0 并且 < 2；
保留要?jiǎng)h除的值，因?yàn)樽詈笮枰祷嘏f的值；
計(jì)算出需要移動(dòng)元素個(gè)數(shù)，再通過(guò)拷貝使數(shù)組內(nèi)位置為 index+1 到 size-1 的元素往前移動(dòng)一位，把數(shù)組最后一個(gè)元素設(shè)置為 null（精辟小技巧），返回舊值。

remove(object) 流程：

 1    public boolean remove(Object o) {
 2        if (o == null) {
 3            for (int index = 0; index < size; index++)
 4                if (elementData[index] == null) {
 5                    fastRemove(index);
 6                    return true;
 7                }
 8        } else {
 9            for (int index = 0; index < size; index++)
10                if (o.equals(elementData[index])) {
11                    fastRemove(index);
12                    return true;
13                }
14        }
15        return false;
16    } 
17    private void fastRemove(int index) {
18        modCount++;
19        int numMoved = size - index - 1;
20        if (numMoved > 0){
21        //數(shù)組拷貝    
22        System.arraycopy(elementData, index+1, elementData, index,
23                             numMoved);
24        }    
25        //方便GC
26        elementData[--size] = null;
27    }

遍歷數(shù)組，比較obejct是否存在于數(shù)組中；
計(jì)算出需要移動(dòng)元素個(gè)數(shù)，再通過(guò)拷貝使數(shù)組內(nèi)位置為 index+1 到 size-1 的元素往前移動(dòng)一位，把數(shù)組最后一個(gè)元素設(shè)置為 null（精辟小技巧）。

總結(jié)：

new ArrayList 創(chuàng)建對(duì)象時(shí)，如果沒(méi)有指定集合容量則初始化為 0；如果有指定，則按照指定的大小初始化；
擴(kuò)容時(shí)，先將集合擴(kuò)大 1.5 倍，如果還是不夠，則根據(jù)實(shí)際長(zhǎng)度來(lái)擴(kuò)容，保證都能存儲(chǔ)所有數(shù)據(jù)，比如 addAll() 場(chǎng)景。
如果新擴(kuò)容后數(shù)組長(zhǎng)度大于（Integer.MAX_VALUE-8），則拋出 OutOfMemoryError。
建議在使用的時(shí)候，先評(píng)估一下要存多少數(shù)據(jù)，然后就可以大致或者準(zhǔn)確的給ArrayList指定大小，這樣就會(huì)避免不斷多次擴(kuò)容對(duì)系統(tǒng)帶來(lái)的開(kāi)銷。

LinkedList

LinkedList 是可以在任何位置進(jìn)行插入和移除操作的有序集合，它是基于雙向鏈表實(shí)現(xiàn)的，線程不安全。LinkedList 功能比較強(qiáng)大，可以實(shí)現(xiàn)棧、隊(duì)列或雙向隊(duì)列。

主要屬性：

 1//鏈表長(zhǎng)度
 2transient int size = 0;
 3//頭部節(jié)點(diǎn)
 4transient Node<E> first;
 5//尾部節(jié)點(diǎn)
 6transient Node<E> last;
 7
 8/**
 9* 靜態(tài)內(nèi)部類，存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)
10* 前驅(qū)結(jié)點(diǎn)、后繼結(jié)點(diǎn)，那證明至少是雙向鏈表
11*/
12private static class Node<E> {
13    //自身結(jié)點(diǎn)
14    E item;
15    //下一個(gè)節(jié)點(diǎn)
16    Node<E> next;
17    //上一個(gè)節(jié)點(diǎn)
18    Node<E> prev;
19}

數(shù)據(jù)結(jié)構(gòu)：雙向鏈表

特征：

允許元素為 null；
插入和刪除效率高，查詢效率低；
順序訪問(wèn)會(huì)非常高效，而隨機(jī)訪問(wèn)效率（比如 get 方法）比較低；
既能實(shí)現(xiàn)棧 Stack（后進(jìn)先出），也能實(shí)現(xiàn)隊(duì)列（先進(jìn)先出）, 也能實(shí)現(xiàn)雙向隊(duì)列，因?yàn)樘峁┝?xxxFirst()、xxxLast() 等方法；
線程不安全。

使用場(chǎng)景：

需要快速插入，刪除元素
按照順序訪問(wèn)其中的元素
單線程環(huán)境

add() 流程：

 1  public boolean add(E e) {
 2        linkLast(e);
 3        return true;
 4    }
 5    void linkLast(E e) {
 6        final Node<E> l = last;
 7        final Node<E> newNode = new Node<>(l, e, null);
 8        last = newNode;
 9        if (l == null)
10            first = newNode;
11        else
12            l.next = newNode;
13        size++;
14        modCount++;
15    }

創(chuàng)建一個(gè)新結(jié)點(diǎn)，結(jié)點(diǎn)元素 e為傳入?yún)?shù)，前繼節(jié)點(diǎn) prev 為“當(dāng)前鏈表 last 結(jié)點(diǎn)”，后繼節(jié)點(diǎn) next 為 null；
判斷當(dāng)前鏈表 last 結(jié)點(diǎn)是否為空，如果是則把新建結(jié)點(diǎn)作為頭結(jié)點(diǎn)，如果不是則把新結(jié)點(diǎn)作為 last 結(jié)點(diǎn)。
最后返回 true。

get(index) 流程：

 1    public E get(int index) {
 2        checkElementIndex(index);
 3        return node(index).item;
 4    }
 5    /**
 6     * Returns the (non-null) Node at the specified element index.
 7     */
 8    Node<E> node(int index) {
 9        if (index < (size >> 1)) {
10            Node<E> x = first;
11            for (int i = 0; i < index; i++)
12                x = x.next;
13            return x;
14        } else {
15            Node<E> x = last;
16            for (int i = size - 1; i > index; i--)
17                x = x.prev;
18            return x;
19        }
20    }
21    private void checkElementIndex(int index) {
22        if (!isElementIndex(index))
23            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
24    }
25    private boolean isElementIndex(int index) {
26        return index >= 0 && index < size;
27    }

檢查 index 是否在數(shù)組范圍內(nèi)，假如數(shù)組長(zhǎng)度是 2，則 index 必須 >=0 并且 < 2；
index 小于“雙向鏈表長(zhǎng)度的 1/2”則從頭開(kāi)始往后遍歷查找，否則從鏈表末尾開(kāi)始向前遍歷查找。

remove() 流程：

1    public E remove(int index) {
2        checkElementIndex(index);
3        return unlink(node(index));
4    }
5    private void checkElementIndex(int index) {
6        if (!isElementIndex(index))
7            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
8    }

判斷 first 結(jié)點(diǎn)是否為空，如果是則報(bào) NoSuchElementException 異常；
如果不為空，則把待刪除結(jié)點(diǎn)的 next 結(jié)點(diǎn)的 prev 屬性賦值為 null，達(dá)到刪除頭結(jié)點(diǎn)的效果。
返回刪除值。

Vector

Vector 是矢量隊(duì)列，也是基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，容量可以自動(dòng)擴(kuò)容。跟 ArrayList 實(shí)現(xiàn)原理一樣，但是 Vector 是線程安全，使用 Synchronized 實(shí)現(xiàn)線程安全，性能非常差，已被淘汰，使用 CopyOnWriteArrayList 替代 Vector。

主要屬性：

1//存儲(chǔ)實(shí)際數(shù)據(jù)
2protected Object[] elementData;
3//動(dòng)態(tài)數(shù)組的實(shí)際大小
4protected int elementCount;
5//動(dòng)態(tài)數(shù)組的擴(kuò)容系數(shù)
6protected int capacityIncrement;

數(shù)據(jù)結(jié)構(gòu)：動(dòng)態(tài)數(shù)組

特征：

允許元素為 null；
查詢效率高、插入、刪除效率低，因?yàn)樾枰苿?dòng)元素；
默認(rèn)的初始化大小為 10，沒(méi)有指定增長(zhǎng)系數(shù)則每次都是擴(kuò)容一倍，如果擴(kuò)容后還不夠，則直接根據(jù)參數(shù)長(zhǎng)度來(lái)擴(kuò)容；
線程安全，性能差（Synchronized），使用 CopyOnWriteArrayList 替代 Vector。

使用場(chǎng)景：多線程環(huán)境

為什么是線程安全的，看看下面的幾個(gè)常用方法就知道了。

 1    public synchronized void addElement(E obj) {
 2        modCount++;
 3        ensureCapacityHelper(elementCount + 1);
 4        elementData[elementCount++] = obj;
 5    }
 6    public boolean remove(Object o) {
 7        return removeElement(o);
 8    }
 9    public synchronized boolean removeElement(Object obj) {
10        modCount++;
11        int i = indexOf(obj);
12        if (i >= 0) {
13            removeElementAt(i);
14            return true;
15        }
16        return false;
17    }
18    public synchronized E get(int index) {
19        if (index >= elementCount)
20            throw new ArrayIndexOutOfBoundsException(index);
21
22        return elementData(index);
23    }
24    public synchronized boolean add(E e) {
25        modCount++;
26        ensureCapacityHelper(elementCount + 1);
27        elementData[elementCount++] = e;
28        return true;
29    }

這幾個(gè)常用方法中，方法都是使用同步鎖synchronized修飾，所以它是線程安全的。

Stack

Stack 是棧，先進(jìn)后出原則，Stack 繼承 Vector，也是通過(guò)數(shù)組實(shí)現(xiàn)，線程安全。因?yàn)樾时容^低，不推薦使用，可以使用 LinkedList（線程不安全）或者 ConcurrentLinkedDeque（線程安全）來(lái)實(shí)現(xiàn)先進(jìn)先出的效果。

數(shù)據(jù)結(jié)構(gòu)：動(dòng)態(tài)數(shù)組

構(gòu)造函數(shù)：只有一個(gè)默認(rèn) Stack()

特征：先進(jìn)后出

實(shí)現(xiàn)原理：

Stack 執(zhí)行 push() 時(shí)，將數(shù)據(jù)推進(jìn)棧，即把數(shù)據(jù)追加到數(shù)組的末尾。
Stack 執(zhí)行 peek 時(shí)，取出棧頂數(shù)據(jù)，不刪除此數(shù)據(jù)，即獲取數(shù)組首個(gè)元素。
Stack 執(zhí)行 pop 時(shí)，取出棧頂數(shù)據(jù)，在棧頂刪除數(shù)據(jù)，即刪除數(shù)組首個(gè)元素。
Stack 繼承于 Vector，所以 Vector 擁有的屬性和功能，Stack 都擁有，比如 add()、set() 等等。

1public class Stack<E> extends Vector<E> {
2//....
3}

CopyOnWriteArrayList

CopyOnWriteArrayList 是線程安全的 ArrayList，寫(xiě)操作（add、set、remove 等等）時(shí)，把原數(shù)組拷貝一份出來(lái)，然后在新數(shù)組進(jìn)行寫(xiě)操作，操作完后，再將原數(shù)組引用指向到新數(shù)組。CopyOnWriteArrayList 可以替代 Collections.synchronizedList(List list)。這個(gè)是在JUC包目錄下的。內(nèi)部使用了AQS實(shí)現(xiàn)的鎖。

java.util.concurrent

數(shù)據(jù)結(jié)構(gòu)：動(dòng)態(tài)數(shù)組

特征：

線程安全；
讀多寫(xiě)少，比如緩存；
不能保證實(shí)時(shí)一致性，只能保證最終一致性。

缺點(diǎn)：

寫(xiě)操作，需要拷貝數(shù)組，比較消耗內(nèi)存，如果原數(shù)組容量大的情況下，可能觸發(fā)頻繁的 Young GC 或者 Full GC；
不能用于實(shí)時(shí)讀的場(chǎng)景，因?yàn)樽x取到數(shù)據(jù)可能是舊的，可以保證最終一致性。

實(shí)現(xiàn)原理：

CopyOnWriteArrayList 寫(xiě)操作加了鎖，不然多線程進(jìn)行寫(xiě)操作時(shí)會(huì)復(fù)制多個(gè)副本；讀操作沒(méi)有加鎖，所以可以實(shí)現(xiàn)并發(fā)讀，但是可能讀到舊的數(shù)據(jù)，比如正在執(zhí)行讀操作時(shí)，同時(shí)有多個(gè)寫(xiě)操作在進(jìn)行，遇到這種場(chǎng)景時(shí)，就會(huì)都到舊數(shù)據(jù)。

 1public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
 2    private static final long serialVersionUID = 8673264195747942595L;
 3
 4    /** The lock protecting all mutators */
 5    final transient ReentrantLock lock = new ReentrantLock();
 6    //添加數(shù)據(jù)
 7    public boolean add(E e) {
 8        //使用到了鎖機(jī)制
 9        final ReentrantLock lock = this.lock;
10        lock.lock();
11        try {
12            Object[] elements = getArray();
13            int len = elements.length;
14            Object[] newElements = Arrays.copyOf(elements, len + 1);
15            newElements[len] = e;
16            setArray(newElements);
17            return true;
18        } finally {
19            //釋放鎖
20            lock.unlock();
21        }
22    }
23    //移除數(shù)據(jù)
24    public E remove(int index) {
25        //鎖機(jī)制
26        final ReentrantLock lock = this.lock;
27        lock.lock();
28        try {
29            Object[] elements = getArray();
30            int len = elements.length;
31            E oldValue = get(elements, index);
32            int numMoved = len - index - 1;
33            if (numMoved == 0)
34                setArray(Arrays.copyOf(elements, len - 1));
35            else {
36                Object[] newElements = new Object[len - 1];
37                System.arraycopy(elements, 0, newElements, 0, index);
38                System.arraycopy(elements, index + 1, newElements, index,
39                                 numMoved);
40                setArray(newElements);
41            }
42            return oldValue;
43        } finally {
44            //釋放鎖
45            lock.unlock();
46        }
47    }