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