個人部落格位址：https://alexaccele.github.io/

集合類實作原理總結

整體認識

這裡貼出一張網上某大神制作的關于集合類的整體結構關系

此圖轉載自 https://blog.csdn.net/u010887744/article/details/50575735

List

ArrayList——非線程安全

内部結構

ArrayList的内部結構其實就是一個數組。

由于是數組結構，故通路時間複雜度為O(1)，插入删除的時間複雜度為O(n)。

擴容機制

ArrayList的預設大小是10個元素，當容量不夠時，則需要擴容，而擴容的大小是原來的1.5倍(JDK1.8)，其實作代碼如下：

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

其決定新數組大小的則是

int newCapacity = oldCapacity + (oldCapacity >> 1);

可以看出采用的是位運算得出原來的一半，再加上原來的大小，則得出了1.5倍。

而擴容的行為則是通過

Arrays.copyOf(elementData, newCapacity);

将原來的數組内容複制到新的數組中。

補充

關于網上部分文章提到的擴容為原來的1.5倍+1，其實是JDK1.6中的實作。擴容值算法如下：

int var4 = var2 * 3 / 2 + 1;

而自從JDK1.7開始則是采用位運算實作，故沒有了後面的+1.

LinkedList——非線程安全

内部結構

采用雙向連結清單實作，故插入的時間複雜度是O(1)，而查詢的時間複雜度是O(n)

由于還實作了Deque接口，故還可以用作雙端隊列

由于是連結清單結構，故隻要是周遊連結清單就需要使用ListIterator

采用了索引優化，可以根據index選擇從first或者last開始周遊。

Vector——線程安全

内部結構

與ArrayList相同，采用數組的形式實作

初始大小10，最大容量Integer.MAX_VALUE - 8。

擴容機制

擴容為原來的兩倍

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
           

線程安全的實作

所有可能發生競争的方法都采用synchronized關鍵字實作，故效率極低，現在已經不再使用。

若要使用線程安全的List則應該使用CopyOnWriteArrayList。

CopyOnWriteArrayList——線程安全

CopyOnWrite容器即寫時複制的容器。通俗的了解是當我們往一個容器添加元素的時候，不直接往目前容器添加，而是先将目前容器進行Copy，複制出一個新的容器，然後新的容器裡添加元素，添加完元素之後，再将原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行并發的讀，而不需要加鎖，因為目前容器不會添加任何元素。是以CopyOnWrite容器也是一種讀寫分離的思想，讀和寫不同的容器。

寫鎖的實作

隻在寫的時候對數組加鎖，采用的是ReentrantLock，加鎖之後再複制原來的數組到新數組中，并添加新的元素。

在這個加鎖的期間，由于其他線程仍然可以進行讀操作，但讀的數組是加鎖前的舊數組，是以可能會讀到原來的舊資料。

适用場景

适合用在讀多寫少的場景，即可以并發的讀而不需要額外的同步操作，隻有少量的寫操作需要依靠鎖來保證線程安全。

Map

HashMap——非線程安全

内部結構

HashMap中主幹是一個Node數組，每個Node包含一個key-value的鍵值對。

transient Node<k,v>[] table;//存儲（位桶）的數組</k,v>
           

Node是HashMap的一個靜态内部類。

//Node是單向連結清單，它實作了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> {
    final int hash;
    final K key;
    V value;
    Node<k,v> next;
    //構造函數Hash值 鍵 值 下一個節點
    Node(int hash, K key, V value, Node<k,v> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + = + value; }
 
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
 
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    //判斷兩個node是否相等,若key和value都相等，傳回true。可以與自身比較為true
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
}
           

沖突解決

在HashMap中是以數組（也稱為位桶）+ 連結清單 + (紅黑樹)的形式存在，當hash值沖突時，則以連結清單的形式解決hash沖突。

新特性

在JDK1.8中則更是增加了紅黑樹的結構，當連結清單的長度超過門檻值8時，則會将這部分hash沖突的連結清單轉為紅黑樹，這樣的目的在于，當HashMap中的hash沖突過多而導緻連結清單過長時，仍能較快速的查找到對應的value值，即從以前的 O(n)變為了O(log(n))。

補充

當連結清單長度超過8時，還要判斷目前的map集合中是否總數量達到了64個，如果沒有達到的話，不是進行紅黑樹的轉換，而是直接進行擴容。

擴容機制

構造hash表時，如果不指明初始大小，預設大小為16（即Node數組大小16）

當連結清單數組的容量超過初始容量的0.75倍（負載因子）時，再散列将連結清單數組擴大2倍，把原連結清單數組的搬移到新的數組中。

為什麼要擴容？為什麼需要使用負載因子

因為如果填充比很大，說明利用的空間很多，如果一直不進行擴容的話，連結清單就會越來越長，這樣查找的效率很低，因為連結清單的長度很大（JDK1.8使用了紅黑樹後會改進很多），擴容之後，将原來連結清單數組的每一個連結清單分成奇偶兩個子連結清單分别挂在新連結清單數組的散列位置，這樣就減少了每個連結清單的長度，增加查找效率。

LinkedHashMap——非線程安全

LinkedHashMap繼承自HashMap，大部分屬性都類似，但HashMap不保證存儲順序，而LinkedHashMap會維護元素的順序，順序可分為通路順序和插入順序，預設是保證插入順序（即疊代周遊的順序是元素插入的順序）

// 第三個參數用于指定accessOrder值
Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
           

通過以上構造函數，可以指定accessOrder的值為true進而使其保證通路順序，通路順序是指，當每次調用get()方法後，對應的key-value鍵值對則被放在了連結清單的尾部。

内部結構

LinkedHashMap是由一個雙向連結清單組成。

LinkedHashMap使用的是LRU算法(最近最少使用) 。當你插入元素時它會将節點插入雙向連結清單的鍊尾，如果key重複，則也會将節點移動至鍊尾，當用get()方法擷取value時也會将節點移動至鍊尾。

TreeMap——非線程安全

内部結構

基于紅黑樹實作

排序方式

其映射根據鍵的自然順序進行排序，或者根據建立映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。其基本操作 containsKey、get、put 和 remove 的時間複雜度是 log(n) 。TreeMap是非同步的。 它的iterator 方法傳回的疊代器是fail-fastl的。

當自定義比較器時，需要自定義類實作java.lang.Comparable接口，并重寫compareTo()方法。

相比較于LinkedHashMap的保證插入順序，TreeMap是在元素的内容上有序（相當于内容排序）

HashTable——線程安全

現在已經不再使用，其線程安全的實作方式是所有的方法都是synchronized方法，故雖然保證了線程安全，但效率很低。若需要使用線程安全的Map則應該使用ConcurrentHashMap。

底層數組+連結清單實作，無論key還是value都不能為null，線程安全，實作線程安全的方式是在修改資料時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關優化

初始size為11，擴容：newsize = olesize*2+1

ConcurrentHashMap——線程安全

内部結構

在JDK1.7中采用的是ReentrantLock+Segment+HashEntry的結構

在JDK1.8中則是采用數組+連結清單+紅黑樹的結構，其線程安全的保證則是通過synchronized+CAS的形式。

線程安全實作機制

在JDK1.7中采用分段鎖技術，将資料分成一段一段的存儲，然後給每一段資料配一把鎖，當一個線程占用鎖通路其中一個段資料的時候，其他段的資料也能被其他線程通路，能夠實作真正的并發通路。

而在JDK1.8中則直接參考了JDK1.8中HashMap的結構，采用數組+連結清單+紅黑樹的結構，而線程安全則是通過CAS來實作。而鎖的細粒度也從JDK1.7中的segment段降低為了JDK1.8中的每個Node，且由于紅黑樹的引入，使得在當連結清單節點過多的情況下能提高查詢效率。

Set

由于Set底層都是采用對應的Map實作，是以不再贅述。

需要注意的是在Set中，Map對應的key則是對應的Set的值，而Map對應的value則是采用同一個Object對象

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();