高清圖解28個高并發(fā)之數(shù)據(jù)結(jié)構(gòu)/數(shù)據(jù)結(jié)構(gòu)場景匹配技巧分析
Java 集合以 ArrayList、LinkedList、HashSet、TreeSet 和 HashMap 等組件為核心，構(gòu)筑了強大而靈活的數(shù)據(jù)結(jié)構(gòu)體系。這些組件精心設計以滿足不同的性能和功能需求，如 ArrayList 的動態(tài)數(shù)組支持快速隨機訪問，而 LinkedList 的雙向鏈表結(jié)構(gòu)則擅長于頻繁的插入和刪除操作。HashSet 基于哈希表提供高效的元素查找，TreeSet 則通過紅黑樹維持元素排序。對于多線程環(huán)境，CopyOnWriteArraySet 和 ConcurrentHashMap 等并發(fā)集合保證了線程安全，同時優(yōu)化了讀寫性能。這些設計精妙的組件，不僅提升了數(shù)據(jù)處理的效率，也簡化了復雜問題的解決方案，了解他的設計就掌握了他的原理，本篇注重設計。
1、JDK集合數(shù)據(jù)結(jié)構(gòu)范圍
1.1. 列表（List）
圖片
- ArrayList: 基于動態(tài)數(shù)組實現(xiàn)，支持快速隨機訪問。
- LinkedList: 基于雙向鏈表實現(xiàn)，適合頻繁的插入和刪除操作。
- CopyOnWriteArrayList: 線程安全的變體，寫操作時復制數(shù)組。
1.2. 集合（Set）
圖片
- HashSet: 基于 HashMap 實現(xiàn)，保證元素唯一性。
- LinkedHashSet: 哈希表和鏈表實現(xiàn)，維護元素插入順序。
- TreeSet: 基于紅黑樹，元素處于排序狀態(tài)。
- CopyOnWriteArraySet: 線程安全的變體，寫操作時復制數(shù)組。
1.3. 隊列（Queue）
圖片
- LinkedListQueue (作為隊列使用時): 支持先進先出（FIFO）。
- ArrayDeque: 雙端隊列，支持快速插入和刪除。
- PriorityQueue: 支持優(yōu)先級排序的隊列。
- ConcurrentLinkedQueue: 線程安全的無界隊列。
- BlockingQueue: 支持阻塞操作的隊列接口，具體實現(xiàn)包括：
ArrayBlockingQueue: 有界阻塞隊列。
LinkedBlockingQueue: 基于鏈表結(jié)構(gòu)的阻塞隊列。
PriorityBlockingQueue: 具有優(yōu)先級的阻塞隊列。
SynchronousQueue: 不存儲元素的阻塞隊列，主要用于任務竊取。
圖片
1.4. 雙端隊列（Deque）
圖片
- ArrayDeque: 基于動態(tài)數(shù)組，實現(xiàn)雙向隊列。
- LinkedList (作為雙端隊列使用時): 基于鏈表，實現(xiàn)雙向隊列。
1.5. 映射（Map）
圖片
- HashMap: 基于哈希表，存儲鍵值對。
- LinkedHashMap: 哈希表加鏈表，維護插入順序。
- TreeMap: 基于紅黑樹，鍵處于排序狀態(tài)。
- Hashtable: 古老的 Map 實現(xiàn)，線程安全。
- ConcurrentHashMap: 線程安全的 HashMap 實現(xiàn)。
- ConcurrentSkipListMap: 線程安全的 TreeMap 實現(xiàn)。
- IdentityHashMap: 使用 == 比較鍵的身份，而不是使用 equals() 方法。
- WeakHashMap: 鍵是弱引用，適合緩存使用。
1.6. 其他
圖片
- Vector: 古老的動態(tài)數(shù)組實現(xiàn)，線程安全。
- Stack: 古老的棧實現(xiàn)，可以使用 Vector 或 Deque 實現(xiàn)。
- Properties: 用于處理配置文件的集合類。
2、集合數(shù)據(jù)結(jié)構(gòu)設計與分析
2.1 ArrayList
ArrayList 是 Java 集合框架中的一個非常核心的類，實現(xiàn)了 List 接口。以下是 ArrayList 的設計：
設計思考：
- 需求場景：
在許多編程任務中，需要一個能夠動態(tài)增長和收縮的數(shù)組。例如，在實現(xiàn)數(shù)據(jù)集合、緩沖區(qū)管理、實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)（如棧、隊列）等場景中，動態(tài)數(shù)組是非常有用的。
- 現(xiàn)有技術(shù)局限性：
傳統(tǒng)的數(shù)組類型在 Java 中是固定長度的，一旦創(chuàng)建，其大小不能改變，這限制了其在需要動態(tài)大小管理時的使用。
技術(shù)融合：
ArrayList 融合了動態(tài)數(shù)組的概念，提供了一個能夠根據(jù)需要自動調(diào)整大小的數(shù)組。
設計理念：
ArrayList 提供了一個能夠根據(jù)添加元素的數(shù)量動態(tài)增長的數(shù)組，同時保持了隨機訪問的能力，使其在執(zhí)行索引位置的查找時非常高效。
實現(xiàn)方式：
ArrayList 內(nèi)部使用一個可變大小的數(shù)組（默認為空，隨著元素添加自動擴容）來存儲元素，當數(shù)組容量不足以容納更多元素時，會自動創(chuàng)建一個更大的新數(shù)組，并將舊數(shù)組中的元素復制到新數(shù)組中。
2.1.1 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說明：
- ArrayList:
Java 集合框架中的一個類，實現(xiàn)了 List 接口。
- Object[] elementData:
ArrayList 內(nèi)部使用一個動態(tài)數(shù)組來存儲元素，這個數(shù)組的類型是 Object[]，可以存儲任何類型的對象。
當數(shù)組容量不足以存儲更多元素時， ArrayList 會自動進行擴容，通常是將數(shù)組大小增加到原來的1.5倍。
int size:
表示 ArrayList 中實際存儲的元素數(shù)量。
size 與 elementData 數(shù)組的 length 屬性不同， length 表示數(shù)組的總?cè)萘浚?nbsp;size 表示當前存儲的元素個數(shù)。
2.1.2 執(zhí)行流程
圖片
圖說明：
- 初始化 ArrayList:
創(chuàng)建一個空的 ArrayList 或指定初始容量的 ArrayList。
- 檢查容量:
在添加元素前，檢查當前數(shù)組容量是否足夠。
添加元素:
嘗試將新元素添加到 ArrayList。
容量不足:
如果當前容量不足以容納新元素，進入擴容流程。
擴容:
創(chuàng)建一個新的數(shù)組，容量通常是原數(shù)組的1.5倍。
復制舊數(shù)組到新數(shù)組:
將舊數(shù)組中的所有元素復制到新數(shù)組中。
增加新元素:
在新數(shù)組中插入新元素。
獲取元素:
根據(jù)索引獲取元素。
索引檢查:
檢查索引是否在有效范圍內(nèi)。
返回元素:
返回指定索引處的元素。
刪除元素:
刪除 ArrayList 中的指定元素。
移除指定索引元素:
將指定索引處的元素移除。
數(shù)組元素向前移動:
將移除元素之后的元素向前移動一位，填補空位。
2.2 LinkedList
LinkedList 在 Java 中是基于雙向鏈表實現(xiàn)的，它包含多個節(jié)點，每個節(jié)點都包含數(shù)據(jù)和兩個引用，分別指向前一個節(jié)點和后一個節(jié)點。以下是 LinkedList 的設計：
設計思考：
- 需求場景：
在許多編程任務中，需要一個可以快速進行插入和刪除操作的動態(tài)數(shù)組。例如，在實現(xiàn)棧、隊列、雙向隊列等數(shù)據(jù)結(jié)構(gòu)時，這些操作非常常見。
- 現(xiàn)有技術(shù)局限性：
ArrayList 提供了快速的隨機訪問能力，但在進行插入和刪除操作時，可能需要移動數(shù)組中的大量元素，導致效率低下。
Vector 類似于 ArrayList，但它是線程安全的，但使用 synchronized 進行同步，導致并發(fā)性能較差。
技術(shù)融合：
LinkedList 結(jié)合了鏈表的插入和刪除效率高的特點，并提供了雙向鏈表的實現(xiàn)，允許從兩端快速地添加或移除元素。
設計理念：
LinkedList 通過使用鏈表結(jié)構(gòu)，可以有效地進行插入和刪除操作，因為這些操作僅需要改變節(jié)點的指針，而不需要移動整個數(shù)組。
它還實現(xiàn)了 List 接口，提供了與 ArrayList 相同的接口，但具有不同的性能特性。
實現(xiàn)方式：
LinkedList 由一系列 Node 對象組成，每個 Node 包含數(shù)據(jù)和兩個引用（ previous 和 next），分別指向前一個和后一個節(jié)點。
2.2.1 數(shù)據(jù)結(jié)構(gòu)
以下是 LinkedList 數(shù)據(jù)結(jié)構(gòu)的主要特點：
- 鏈式存儲：元素在內(nèi)存中不是連續(xù)存儲的，而是通過指針（引用）連接起來的。
- 節(jié)點結(jié)構(gòu)：每個節(jié)點至少包含兩部分信息，一個是存儲數(shù)據(jù)的元素，另一個是指向同鏈表中下一個節(jié)點的引用。在雙向鏈表中，還會有一個指向前一個節(jié)點的引用。
- 動態(tài)大小： LinkedList 的大小是動態(tài)的，可以根據(jù)需要隨時插入或刪除節(jié)點。
- 允許空鏈表：可以創(chuàng)建一個不包含任何節(jié)點的空鏈表。
- 插入和刪除效率高：在鏈表的任意位置插入或刪除節(jié)點的操作時間復雜度為 O(1)，因為這些操作只涉及到節(jié)點的引用的改動。
- 訪問元素效率低：訪問特定索引位置的元素需要從頭節(jié)點開始遍歷鏈表，時間復雜度為 O(n)。
- 沒有空間浪費：與數(shù)組不同，鏈表不需要預先分配固定大小的存儲空間。
- 有序性：鏈表中的節(jié)點按照它們被插入的順序保持有序。
- 可以實現(xiàn)為雙向或循環(huán)鏈表：標準的 LinkedList 實現(xiàn)可以是雙向的，也可以是循環(huán)的（尾節(jié)點指向頭節(jié)點）。
2.2.1 執(zhí)行流程
圖片
圖說明：
- 初始化 LinkedList:
創(chuàng)建一個空的 LinkedList 實例。
- 添加元素:
將新元素添加到 LinkedList。
刪除元素:
從 LinkedList 刪除指定的元素。
訪問元素:
根據(jù)索引訪問 LinkedList 中的元素。
遍歷 LinkedList:
通過節(jié)點間的鏈接順序遍歷整個 LinkedList。
檢查邊界條件:
在執(zhí)行索引相關(guān)操作前，檢查索引是否在有效范圍內(nèi)。
獲取節(jié)點:
獲取指定索引處的節(jié)點。
更新節(jié)點指針:
在添加或刪除元素時，更新節(jié)點間的指針。
返回節(jié)點數(shù)據(jù):
返回指定節(jié)點的數(shù)據(jù)。
LinkedList 節(jié)點:
LinkedList 由一系列節(jié)點組成，每個節(jié)點包含前一個節(jié)點、后一個節(jié)點和節(jié)點數(shù)據(jù)。
Node prev:
節(jié)點中保存的對前一個節(jié)點的引用。
Node next:
節(jié)點中保存的對后一個節(jié)點的引用。
Node data:
節(jié)點中保存的數(shù)據(jù)。
2.3 CopyOnWriteArrayList
CopyOnWriteArrayList 在 Java 中是一個線程安全的變體數(shù)組列表，其特點是在修改（寫操作）時通過復制整個底層數(shù)組來實現(xiàn)，以此保證讀操作的線程安全和高性能。以下是 CopyOnWriteArrayList 的設計：
設計思考：
- 需求場景：
在多線程環(huán)境中，讀操作遠比寫操作頻繁，且對數(shù)據(jù)的實時性要求不是非常高的場景。例如，緩存系統(tǒng)、實時數(shù)據(jù)的訂閱發(fā)布模型等。
- 現(xiàn)有技術(shù)局限性：
傳統(tǒng)的線程安全實現(xiàn)，如 Vector 或通過 synchronized 同步代碼塊或方法，可能會因為寫操作導致的線程阻塞，嚴重影響并發(fā)性能。
技術(shù)融合：
CopyOnWriteArrayList 采用了寫時復制（Copy-On-Write）的策略，當進行寫操作（添加、刪除等）時，先復制整個數(shù)組，然后在新數(shù)組上進行操作，而讀操作則直接作用于原數(shù)組，從而提高了讀操作的性能。
設計理念：
利用了讀操作遠多于寫操作的特性，通過分離讀和寫操作，使得讀操作無需加鎖，從而提高了并發(fā)讀的性能。
實現(xiàn)方式：
內(nèi)部使用一個數(shù)組來存儲元素，所有寫操作都會創(chuàng)建一個新的數(shù)組，并將修改應用于新數(shù)組，然后原子性地將內(nèi)部數(shù)組引用指向新數(shù)組。
2.3.1 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說明：
- CopyOnWriteArrayList:
表示 CopyOnWriteArrayList 的實例。
- Object[] array:
CopyOnWriteArrayList 內(nèi)部使用的一個數(shù)組 array 來存儲元素。這是原始數(shù)組，所有讀操作都訪問這個數(shù)組。
Object[] newArray:
寫操作時創(chuàng)建的新數(shù)組。當寫操作發(fā)生時，這個數(shù)組是原始數(shù)組的一個深拷貝。
寫操作:
包括添加、刪除或修改元素。寫操作不是在原始數(shù)組上進行，而是在新數(shù)組上進行。
工作原理：
- 讀操作:
多個讀線程可以同時訪問和遍歷 array，因為數(shù)組是不可變的。
- 寫操作:
當寫操作發(fā)生時（如添加、刪除或修改元素），寫線程首先會創(chuàng)建原始 array 的一個副本 newArray。
寫線程在 newArray 上進行添加、刪除或修改操作。
寫操作完成后，寫線程會原子性地將 CopyOnWriteArrayList 的內(nèi)部數(shù)組引用指向 newArray。
數(shù)據(jù)一致性:
在寫操作進行時，讀線程仍然可以訪問舊的內(nèi)部數(shù)組 array，從而保證了數(shù)據(jù)的一致性。
2.3.2 執(zhí)行流程
圖片
圖說明：
- 初始化 CopyOnWriteArrayList:
創(chuàng)建一個空的 CopyOnWriteArrayList 實例。
- 內(nèi)部數(shù)組 array:
CopyOnWriteArrayList 內(nèi)部使用一個數(shù)組來存儲元素。
讀操作:
直接讀取內(nèi)部數(shù)組的元素，是線程安全的，因為內(nèi)部數(shù)組不可變。
寫操作:
包括添加、刪除和修改元素，需要創(chuàng)建內(nèi)部數(shù)組的一個新副本。
復制數(shù)組:
在執(zhí)行寫操作前，復制內(nèi)部數(shù)組，以保證新元素的添加不會影響讀操作。
添加元素:
向 CopyOnWriteArrayList 添加新元素。
刪除元素:
從 CopyOnWriteArrayList 刪除元素。
修改元素:
修改 CopyOnWriteArrayList 中的元素。
數(shù)組拷貝:
創(chuàng)建內(nèi)部數(shù)組的一個新副本，并在新副本上執(zhí)行寫操作。
2.4 HashSet
HashSet 是 Java 集合框架中的一個基本成員，它是 java.util 包下的一個非常常用的集合類。以下是 HashSet 的設計：
設計思考：
- 需求場景：
在很多應用場景中，需要存儲不重復的元素，并且需要快速地添加、刪除和查找元素。
例如，在處理配置選項、用戶權(quán)限、郵件地址列表等場景時，確保元素的唯一性是非常重要的。
- 現(xiàn)有技術(shù)局限性：
ArrayList 和 LinkedList 雖然可以存儲元素，但它們需要線性時間來查找元素，且不保證元素的唯一性。
技術(shù)融合：
HashSet 基于 HashMap 實現(xiàn)，它結(jié)合了哈希表的快速查找特性來提供常數(shù)時間復雜度的添加、刪除和查找操作，同時保證了元素的唯一性。
設計理念：
HashSet 提供了一個不允許重復元素的數(shù)據(jù)結(jié)構(gòu)，它使用哈希表的鍵來存儲元素，而不關(guān)心值。
這種設計使得 HashSet 在保證元素唯一性的同時，提供了高效的操作性能。
實現(xiàn)方式：
HashSet 的每個元素都作為 HashMap 的一個鍵存儲，而對應的值是一個固定的對象（通常是一個名為 PRESENT 的私有靜態(tài)對象）。
2.4.1 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說明：
- HashSet:
表示 HashSet 類的實例，用于存儲不重復的元素。
- HashMap:
HashSet 的內(nèi)部實現(xiàn)基于 HashMap。
數(shù)組 (Buckets) :
HashMap 使用一個數(shù)組來存儲桶（Buckets），桶是用于存儲 Entry 對象的容器。
索引1, 索引2, 索引3:
表示數(shù)組中的具體索引位置，每個索引對應一個桶。
Entry (鏈表/紅黑樹) :
每個桶可以包含多個 Entry 對象，它們通過鏈表或紅黑樹形式連接。
鏈表 Entry:
在哈希沖突較少的情況下， Entry 對象通過鏈表連接。
紅黑樹 Entry:
當鏈表長度超過閾值時，鏈表可能會被轉(zhuǎn)換成紅黑樹以提高搜索效率。
2.4.2 執(zhí)行流程
圖片
圖說明：
- 創(chuàng)建 HashSet 實例:
初始化 HashSet 對象。
- 添加元素:
將元素添加到 HashSet。
計算元素的hashCode:
調(diào)用元素的 hashCode() 方法計算其哈希碼。
確定數(shù)組索引位置:
根據(jù)哈希碼和數(shù)組長度確定數(shù)組索引位置。
處理哈希沖突:
如果索引位置已有元素，處理哈希沖突。
元素添加至鏈表/紅黑樹:
將新元素添加至對應索引的鏈表或紅黑樹中。
刪除元素:
從 HashSet 刪除元素。
計算元素的hashCode:
調(diào)用元素的 hashCode() 方法計算其哈希碼。
確定數(shù)組索引位置:
根據(jù)哈希碼和數(shù)組長度確定數(shù)組索引位置。
找到對應的哈希桶:
定位到數(shù)組中對應的哈希桶。
從鏈表/紅黑樹中刪除元素:
從對應索引的鏈表或紅黑樹中刪除元素。
遍歷 HashSet:
遍歷 HashSet 中的所有元素。
獲取數(shù)組:
獲取 HashSet 內(nèi)部的數(shù)組。
遍歷每個桶:
遍歷數(shù)組的每個桶。
遍歷鏈表/紅黑樹:
遍歷桶內(nèi)的鏈表或紅黑樹中的所有元素。
2.5 LinkedHashSet
LinkedHashSet 是 Java 集合框架中的一個成員，它結(jié)合了 HashSet 的快速查找特性和 LinkedList 的插入順序保持功能。以下是 LinkedHashSet 的設計：
設計思考：
- 需求場景：
在很多應用場景中，需要快速地插入、刪除和查找元素，同時也需要保持元素的插入順序。
例如，在處理用戶會話、緩存實現(xiàn)、任務調(diào)度等場景時，保持元素的添加順序是非常重要的。
- 現(xiàn)有技術(shù)局限性：
HashSet 提供了常數(shù)時間的添加、刪除和查找性能，但它不保持元素的插入順序。
TreeSet 保持了元素的排序順序，但不是插入順序，且它的性能不如 HashSet。
ArrayList 和 LinkedList 保持了插入順序，但它們的查找性能為線性時間復雜度。
技術(shù)融合：
為了結(jié)合 HashSet 的快速查找能力和 LinkedList 的插入順序保持能力， LinkedHashSet 應運而生。
設計理念：
LinkedHashSet 底層使用 HashMap 來存儲元素，保證了快速的查找性能。
同時，它在每個 HashMap 的條目上使用一個雙向鏈表來維護元素的插入順序。
實現(xiàn)方式：
LinkedHashSet 繼承自 HashSet，但重寫了 add、 iterator 等方法，以維護插入順序。
它在內(nèi)部維護了與 HashMap 條目關(guān)聯(lián)的雙向鏈表的節(jié)點，這些節(jié)點鏈接了具有相同哈希值但插入順序不同的元素。
2.5.1 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說明：
- LinkedHashSet:
表示 LinkedHashSet 類的實例，它繼承自 HashSet 并維護元素的插入順序。
- HashMap:
LinkedHashSet 的實現(xiàn)基于 HashMap，用來存儲集合中的元素。
數(shù)組 (Buckets) :
HashMap 使用一個數(shù)組來存儲桶（Buckets），桶是用于存儲 Entry 對象的容器。
哈希桶:
每個桶內(nèi)部使用鏈表來解決哈希沖突。
鏈表 Entry:
每個桶包含多個 Entry 對象，它們通過鏈表連接。
紅黑樹 Entry:
當鏈表長度超過閾值時，鏈表可能會被轉(zhuǎn)換成紅黑樹以提高搜索效率。
鏈表 節(jié)點1 和 鏈表 節(jié)點2:
表示鏈表中的節(jié)點，每個節(jié)點存儲著集合中的一個元素，并指向前一個和后一個節(jié)點，形成雙向鏈表。
元素:
存儲在 LinkedHashSet 中的最終數(shù)據(jù)。
2.5.2 執(zhí)行流程
圖片
圖說明：
- 創(chuàng)建 LinkedHashSet 實例:
初始化 LinkedHashSet 對象。
- 添加元素:
將元素添加到 LinkedHashSet。
計算元素的hashCode:
調(diào)用元素的 hashCode() 方法計算其哈希碼。
確定數(shù)組索引位置:
根據(jù)哈希碼和數(shù)組長度確定數(shù)組索引位置。
找到對應的哈希桶:
定位到數(shù)組中對應的哈希桶。
檢查哈希桶中的鏈表/紅黑樹:
檢查哈希桶中是否已有鏈表或紅黑樹結(jié)構(gòu)。
處理哈希沖突:
如果桶中已有元素，處理哈希沖突。
元素添加至鏈表/紅黑樹:
將新元素添加至對應索引的鏈表或紅黑樹中。
刪除元素:
從 LinkedHashSet 刪除元素。
重新計算元素的hashCode:
調(diào)用元素的 hashCode() 方法計算其哈希碼。
確定刪除元素的數(shù)組索引位置:
根據(jù)哈希碼和數(shù)組長度確定數(shù)組索引位置。
找到刪除元素的哈希桶:
定位到數(shù)組中對應的哈希桶。
從鏈表/紅黑樹中刪除元素:
從對應索引的鏈表或紅黑樹中刪除元素。
遍歷 LinkedHashSet:
遍歷 LinkedHashSet 中的所有元素。
獲取數(shù)組:
獲取 LinkedHashSet 內(nèi)部的數(shù)組。
遍歷每個桶:
遍歷數(shù)組的每個桶。
遍歷鏈表/紅黑樹:
遍歷桶內(nèi)的鏈表或紅黑樹中的所有元素。
讀取元素:
讀取鏈表或紅黑樹中的元素。
2.6 TreeSet
TreeSet 是 Java 集合框架中的一個有序集合類，實現(xiàn)了 Set 接口。以下是 TreeSet 的設計：
設計思考：
- 需求場景：
在許多編程任務中，需要存儲不重復的元素，并且這些元素需要保持一定的順序，例如，自然排序或自定義排序順序。
例如，在處理需要排序的配置選項、用戶權(quán)限、需要按順序處理的任務列表等場景時，元素的排序順序是非常重要的。
- 現(xiàn)有技術(shù)局限性：
HashSet 提供了非常快的查找、添加和刪除操作，但它不保證元素的任何特定順序。
ArrayList 和 LinkedList 可以保持插入順序，但查找操作需要線性時間。
技術(shù)融合：
TreeSet 結(jié)合了 HashSet 的快速查找特性和 ArrayList/ LinkedList 的元素順序保持功能，但通過使用紅黑樹（一種自平衡的二叉搜索樹）實現(xiàn)，提供了有序的元素集合。
設計理念：
TreeSet 提供了一個不允許重復元素的數(shù)據(jù)結(jié)構(gòu)，同時保證了元素處于排序狀態(tài)，可以進行有效的范圍查詢和排序操作。
實現(xiàn)方式：
TreeSet 內(nèi)部使用 TreeMap 的實例來存儲元素，其中元素作為鍵，值是一個固定的虛擬對象（如 PRESENT），從而保證了元素的唯一性。
2.6.1 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說明：
- TreeSet:
表示 TreeSet 類的實例，它實現(xiàn)了 Set 接口，并保證元素處于排序狀態(tài)。
- TreeMap:
TreeSet 基于 TreeMap 實現(xiàn)，其中元素作為鍵存儲，而不關(guān)心值。
紅黑樹:
TreeMap 的底層數(shù)據(jù)結(jié)構(gòu)是一個紅黑樹，它是一個自平衡的二叉搜索樹。
根節(jié)點:
紅黑樹的根節(jié)點，是樹的入口。
左子節(jié)點和右子節(jié)點:
表示紅黑樹節(jié)點的子節(jié)點。
元素A, 元素B, 元素C:
實際存儲在 TreeSet 中的數(shù)據(jù)。
2.6.2 執(zhí)行流程
圖片
圖說明：
- 添加元素：
計算元素的自然排序：根據(jù)元素的自然順序或提供的 Comparator 計算排序。
構(gòu)建紅黑樹：TreeSet 基于紅黑樹數(shù)據(jù)結(jié)構(gòu)，確保元素處于排序狀態(tài)。
確定插入位置：在紅黑樹中找到元素的插入位置。
插入元素到紅黑樹：將元素插入到紅黑樹中。
- 刪除元素：
計算元素的自然排序：根據(jù)元素的自然順序或提供的 Comparator 計算排序。
查找紅黑樹：在紅黑樹中查找要刪除的元素。
刪除元素從紅黑樹：從紅黑樹中刪除元素。
遍歷 TreeSet：
獲取紅黑樹根節(jié)點：獲取紅黑樹的根節(jié)點，開始遍歷。
遍歷紅黑樹節(jié)點：遍歷紅黑樹的每個節(jié)點。
讀取元素：從紅黑樹的節(jié)點中讀取元素。
2.7 CopyOnWriteArraySet
CopyOnWriteArraySet 是 Java 并發(fā)包 java.util.concurrent 中的一個集合類，它是 CopyOnWriteArrayList 的一個變體，用于維護一個線程安全的、動態(tài)的元素集合。以下是 CopyOnWriteArraySet 的設計：
設計思考：
- 需求場景：
在多線程環(huán)境中，讀操作頻繁而寫操作相對較少的場景，如緩存、實時數(shù)據(jù)集、事件監(jiān)聽器集合等。
- 現(xiàn)有技術(shù)局限性：
傳統(tǒng)的線程安全集合，如 Collections.synchronizedSet 或 Hashtable，在讀多寫少的場景下可能因為寫操作導致的線程阻塞，影響性能。
技術(shù)融合：
CopyOnWriteArraySet 采用了寫時復制（Copy-On-Write）的策略，在讀操作遠多于寫操作的情況下，提高了讀操作的性能。
設計理念：
CopyOnWriteArraySet 利用了讀操作遠多于寫操作的特點，在讀操作時不需要加鎖，從而提高了并發(fā)讀的性能。
實現(xiàn)方式：
內(nèi)部使用 CopyOnWriteArrayList 存儲元素，所有寫操作（添加、刪除等）都會創(chuàng)建一個新的數(shù)組副本，然后對新數(shù)組進行修改，最后原子性地將內(nèi)部數(shù)組引用指向新數(shù)組。
2.7.1 數(shù)據(jù)結(jié)構(gòu)
圖片
圖說明
- CopyOnWriteArraySet：表示 CopyOnWriteArraySet 類的實例，它提供了線程安全的 Set 集合功能。
- CopyOnWriteArrayList：CopyOnWriteArraySet 基于 CopyOnWriteArrayList 實現(xiàn)，后者是線程安全的 ArrayList 實現(xiàn)。
- 內(nèi)部數(shù)組：CopyOnWriteArrayList 初始的內(nèi)部數(shù)組，用于存儲集合中的元素。
- 內(nèi)部數(shù)組副本：當執(zhí)行寫操作（如添加、刪除）時，CopyOnWriteArrayList 創(chuàng)建內(nèi)部數(shù)組的一個副本。
- 新內(nèi)部數(shù)組：寫操作完成后，CopyOnWriteArrayList 將內(nèi)部數(shù)組引用指向新的數(shù)組副本。
- 元素1、元素2、元素n：表示存儲在 CopyOnWriteArraySet 中的實際數(shù)據(jù)。
2.7.1 執(zhí)行流程
圖片
圖說明
- 創(chuàng)建 CopyOnWriteArraySet 實例：初始化 CopyOnWriteArraySet 對象。
- 添加元素：將元素添加到 CopyOnWriteArraySet。
- 復制舊內(nèi)部數(shù)組：為了添加元素，先復制當前的內(nèi)部數(shù)組。
- 修改新內(nèi)部數(shù)組副本：在數(shù)組的副本上添加元素。
- 將新內(nèi)部數(shù)組副本設置為當前：將修改后的數(shù)組副本設置為當前數(shù)組，完成添加操作。
- 刪除元素：從 CopyOnWriteArraySet 刪除元素。
- 復制舊內(nèi)部數(shù)組：為了刪除元素，先復制當前的內(nèi)部數(shù)組。
- 修改新內(nèi)部數(shù)組副本：在數(shù)組的副本上刪除元素。
- 將新內(nèi)部數(shù)組副本設置為當前：將修改后的數(shù)組副本設置為當前數(shù)組，完成刪除操作。
- 遍歷 CopyOnWriteArraySet：遍歷 CopyOnWriteArraySet 中的所有元素。
- 讀取當前內(nèi)部數(shù)組：讀取當前的內(nèi)部數(shù)組，進行遍歷操作。
