1. 集合 Collection

1.1 Java 集合框架

? ? ? ? ? ? ? ? Java 集合框架位于 java.util 包中，Java 集合框架主要包括兩種型別的容器，一種是集合（Collection），存盤一個元素集合，另一種是圖（Map），存盤鍵/值對映射，Collection 介面又有 3 種子型別，List、Set 和 Queue，再下面是一些抽象類，最后是具體實作類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等，

? ? ? ? ? ? ? ? 集合框架是一個用來代表和操縱集合的統一架構，所有的集合框架都包含如下內容：

• 介面：Collection，List，Set，Map 等，用于以不同的方式操作集合物件
• 實作類：是集合介面的具體實作，如 ArrayList、LinkedList、HashSet、HashMap
• 演算法：是實作集合介面的物件里的方法執行的一些有用的計算，如搜索和排序，這些演算法被稱為多型，那是因為相同的方法可以在相似的介面上有著不同的實作
  ? ? ? ? ? ? ? ?

集合和陣列的區別：

• 集合長度可變，陣列長度固定
• 集合中只能是參考型別，陣列中既可以是基本型別也可以是參考型別
• 集合中可以存盤不同型別的元素（通常只存放同種型別），陣列只能存盤同一種型別
  ? ? ? ? ? ? ? ?

1.2 集合介面

? ? ? ? ? ? ? ?

1.3 Collection 集合的方法

? ? ? ? ? ? ? ?

2. List

? ? ? ? ? ? ? ? List 介面是一個有序的 Collection，可以精確的控制每個元素的插入位置，通過索引訪問元素，可以存盤相同元素，List 介面存盤一組不唯一，有序的物件，

? ? ? ? ? ? ? ? List 共有三個實作類，ArrayList，Vector，LinkedList，

2.1 ArrayList

? ? ? ? ? ? ? ? ArrayList 是最常用的 List 實作類，內部通過陣列實作，允許堆元素進行快速隨機訪問，

? ? ? ? ? ? ? ? 由于陣列存盤需要整塊記憶體空間，中間不能有間隔，當陣列大小不足需要擴張時，需要將已有陣列的資料全部復制到新存盤空間中，當從 ArrayList 中間插入或洗掉元素時，需要對陣列進行復制、移動，代價很高，因此只適合查找遍歷，不適用于頻繁的插入洗掉，

特點：

• 底層資料結構為陣列
• 查詢快，增刪慢
• 執行緒不安全，效率高
• 可以存盤重復元素

? ? ? ? ? ? ? ?

2.1.1 常用方法

? ? ? ? ? ? ? ?

2.2 LinkedList

? ? ? ? ? ? ? ? LinkedList 是一個繼承于 AbstractSequentialList 的雙向鏈表，同時也可以被當做堆疊、佇列或雙端佇列操作，

? ? ? ? ? ? ? ? LinkedList 實作了 List 介面，能對它進行佇列操作，

? ? ? ? ? ? ? ? LinkedList 實作了 Deque 介面，即能將LinkedList當作雙端佇列使用，
? ? ? ? ? ? ? ? LinkedList 實作了 Cloneable 介面，即覆寫了函式clone()，能克隆，
? ? ? ? ? ? ? ? LinkedList 實作 java.io.Serializable 介面，這意味著 LinkedList 支持序列化，能通過序列化去傳輸，

? ? ? ? ? ? ? ? LinkedList 包含兩個重要成員 header 和 size， header 是雙向鏈表的表頭，是雙向鏈表節點對應的類 Entry 的實體，Entry 中包含成員變數：previous，next，element，element 是該節點中存放的資料，

特點：

• 底層資料結構是雙向鏈表

• 查詢慢，增刪快

• 執行緒不安全，效率高

• 可以存盤重復元素

? ? ? ? ? ? ? ?

2.2.1 常用方法

? ? ? ? ? ? ? ?

2.3 Vector

? ? ? ? ? ? ? ? 與 ArrayList 基本相同，通過陣列實作，最大的區別是支持執行緒同步，某一時刻只有一個執行緒能夠修改 Vector，但執行緒同步需要很高的消費，訪問比 ArrayList 慢，

特點：

• 底層資料結構是陣列
• 查詢快，增刪慢
• 執行緒安全，效率低
• 可以存盤重復元素
• 使用 synchronized 方法保證執行緒安全
  ? ? ? ? ? ? ? ?

3. Set

? ? ? ? ? ? ? ? Set 具有與 Collection 完全一樣的介面，Set 中的物件不可重復，除此之外可以把 Set 當做 Collection 使用，該集合用于存盤無序元素，物件是否重復根據 hashCode 判斷，
? ? ? ? ? ? ? ? 如果想讓兩個不同的物件被視為相等，就必須覆寫 Object 的 hashCode 方法和 equals 方法，

? ? ? ? ? ? ? ?

3.1 HashSet

? ? ? ? ? ? ? ? HashSet 底層資料結構采用哈希表實作，元素的唯一性通過該元素型別是否重寫 hashCode() 和 equals() 方法來保證，

? ? ? ? ? ? ? ? HashSet 首先判斷兩個元素的哈希值，如果哈希值相同，會接著通過 equals 方法比較，如果 equals 也為 true，則視為同一個元素，

? ? ? ? ? ? ? ? HashSet 通過 hashCode 的值來確定元素在記憶體中的位置，一個 hashCode 位置上可以存放多個元素（多個元素存放在一個哈希桶中），

特點：

• 底層資料結構為哈希表
• 元素無序且唯一
• 執行緒不安全
• 效率高
• 可存盤 null 元素

? ? ? ? ? ? ? ?

3.2 LinkedHashSet

? ? ? ? ? ? ? ? LinkedHashSet 繼承于 HashSet，底層使用 LinkedHashMap 保存所有元素，方法操作上與 HashSet 相同，

特點：

• 底層使用 LinkedHashMap 保存元素
• 元素順序與存盤順序一致
• 元素唯一
• 執行緒不安全，效率高

? ? ? ? ? ? ? ?

3.3 TreeSet

? ? ? ? ? ? ? ? TreeSet 的底層資料結構為紅黑樹，實作了 SortedSet 介面，可以隨時確保集合中的元素處于有序狀態，

? ? ? ? ? ? ? ? TreeSet 每插入一個物件都會進行排序，將其插入紅黑樹的指定位置，Integer 和 String 物件都可以進行默認的 TreeSet 排序，但自定義物件不可以，自定義類必須實作 Comparable 介面，并重寫 compareTo() 方法才能使用 TreeSet，

? ? ? ? ? ? ? ? 重寫 compareTo() 方法時，比較不同的值，需要根據小于、等于、大于來回傳相應的負整數，零或正整數，

特點：

• 底層資料結構為紅黑樹
• 元素有序且唯一
• 只能添加同種型別物件
• 不支持快速隨機訪問
• 不允許元素為 null

? ? ? ? ? ? ? ?

3.3.1 常用方法

4. Map

? ? ? ? ? ? ? ? List 和 Set 都繼承自 Collection 介面，Map 不是，Map 用于保存具有映射關系的資料 key 和 value，通過鍵 key 查找值 value，它們可以是任何參考型別的資料，但 key 不能重復，

? ? ? ? ? ? ? ?

4.1 Map 的主要方法

? ? ? ? ? ? ? ?

4.2 HashMap

? ? ? ? ? ? ? ? HashMap 的主干是一個 Entry 陣列，Entry 是 HashMap 的基本組成單元，每一個 Entry 包含一個 key-value 鍵值對，為了解決哈希沖突 HashMap 采用了鏈地址法，也就是陣列+鏈表的方式，
? ? ? ? ? ? ? ? 因此大多數情況下 HashMap 可以直接定位到值，訪問速度極快，遍歷順序不確定，HashMap 只允許一個鍵為 null，允許多條值為 null，且 HashMap 非執行緒安全，
? ? ? ? ? ? ? ? JDK 8 對 HashMap 進行了修改，最大的不同是引入了紅黑樹提升 HashMap 的查找效率，在 JDK 8 中，為解決哈希沖突的鏈表中的元素超過 8 個以后，會將鏈表轉換為紅黑樹，在此處查找是可以把時間復雜度降低至 O(logN)，

? ? ? ? ? ? ? ?

HashMap的建構式

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

? initialCapacity 為 HashMap 的初始大小，loadFactor 為負載因子，

? 如果不填入構造引數，默認初始大小為16，負載因子為0.75，

特點：

• 底層資料結構：陣列代表一對映射，鏈表/紅黑樹解決哈希沖突
• 訪問速度快，效率極高
• 遍歷順序不確定
• 非執行緒安全

? ? ? ? ? ? ? ?

4.3 LinkedHashMap

? ? ? ? ? ? ? ? LinkedHashMap 是 HashMap 的一個子類，底層資料結構是用雙向鏈表連接起來的 HashMap，可以保留插入順序，其存取程序基本與 HashMap 相同，
? ? ? ? ? ? ? ? LinkedHashMap 通過維護一個額外的雙向鏈表保證了迭代順序，該迭代順序可以是插入順序，也可以是訪問順序，因此，根據鏈表中元素的順序可以將其分為：保持插入順序的 LinkedHashMap 和 保持訪問順序的 LinkedHashMap，其中 LinkedHashMap 的默認按插入順序排序，
? ? ? ? ? ? ? ? 因此 LinkedHashMap 可以很好的支持 LRU 演算法，

特點：

• 底層資料結構：雙向鏈表連接 HashMap 中的 Entry 陣列
• 可按插入順序或訪問順序存盤
• 可以很好的支持 LRU 演算法
• 非執行緒安全

? ? ? ? ? ? ? ?

4.4 ConcurrentHashMap

? ? ? ? ? ? ? ? ConcurrentHashMap 支持并發操作，是安全高效的 Map 集合，廣泛應用于多執行緒開發，并發控制使? synchronized 和 CAS 來操作，synchronized 只鎖定當前鏈表或紅??叉樹的首節點，這樣只要 hash 不沖突，就不會產?并發，效率極大的提升，
? ? ? ? ? ? ? ? JDK 8 后 ConcurrentHashMap 的資料結構改為 Node 陣列+鏈表/紅黑樹的結構，
? ? ? ? ? ? ? ? 紅黑樹結構略有不同，HashMap 的紅黑樹中的節點叫做 TreeNode，TreeNode 不僅僅有屬性，還維護著紅黑樹的結構，比如說查找，新增等等，ConcurrentHashMap 中紅黑樹被拆分成兩塊，TreeNode 僅僅維護的屬性和查找功能，新增了 TreeBin，來維護紅黑樹結構，并負責根節點的加鎖和解鎖，

• Node：Node 物件是鏈表上的一個節點，內部存盤 key、value，以及下一個節點的參考，節點中的 value 和 next 都用 volatile 修飾，保證并發的可見性

• ForwardingNode：當擴容時，要把鏈表遷移到新的哈希表，在做這個操作時，會在把陣列中的頭節點替換為 ForwardingNode 物件，ForwardingNode 中不保存 key 和 value，只保存擴容后哈希表（nextTable）的參考，此時查找相應 node 時，需要去 nextTable 中查找

• TreeBin：當鏈表轉為紅黑樹后，陣列中保存的參考為 TreeBin，TreeBin 內部不保存 key 或 value，它保存了 TreeNode 的 list 以及紅黑樹 root

  ? ? ? ? ? ? ? ?

ConcurrentHashMap 中添加映射的程序（put 方法）

public V put(K key, V value) {
        return putVal(key, value, false);
    }

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value =https://www.cnblogs.com/wu-Chiyu/archive/2021/10/12/= null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node[] tab = table;;) {
        Node f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node p;
                        binCount = 2;
                        if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

具體流程：

• 給輸入的 key 分配 hashcode，分配好后依次判斷
• 判斷是否需要初始化
• 判斷 key 對應的 Node 陣列是否為空，如果為空則用 CAS 寫入資料
• 判斷是否需要擴容
• 如果都不滿足，則利用 synchronized 鎖寫入資料
• 如果鏈表長度大于 TREEIFY_THRESHOLD，則將鏈表改為紅黑樹
  ? ? ? ? ? ? ? ?

特點：

• 底層資料結構：Node陣列+鏈表/紅黑樹
• 執行緒安全高效，多執行緒使用
• 并發控制使用 synchronized 和 CAS，synchronized 只鎖定當前鏈表或紅??叉樹的首節點

? ? ? ? ? ? ? ?

4.5 HashTable

? ? ? ? ? ? ? ? 執行緒安全的 HashMap，同一時間只有一個執行緒能夠修改 HashTable，并發性遠遠不如 ConcurrentHashMap，效率低下，不建議在代碼中使用，

4.6 TreeMap

? ? ? ? ? ? ? ? TreeMap 實作了 SortedMap 介面，能夠把保存的記錄根據鍵排序，默認為鍵值升序，也可以指定排序的比較器，如果使用排序的映射，建議使用 TreeMap，
? ? ? ? ? ? ? ? TreeMap 底層為紅黑樹，將代表一對對映射的 Entry 陣列作為節點連接成紅黑樹，不需要調優，紅黑樹自動平衡，
? ? ? ? ? ? ? ? 在使用 TreeMap 來保存自定義物件時，與 TreeSet 相同必須讓自定義物件的類實作 Comparable 介面，并重寫 compareTo() 方法，

?

特點：

• 底層資料結構為紅黑樹
• 存入映射按鍵值排序，默認升序
• 非執行緒安全
  ? ? ? ? ? ? ? ?

4.6.1 常用方法

標籤：其他

上一篇：學習Tomcat（七）之Spring內嵌Tomcat

下一篇：Python的串列和元組