Java 高並發與集合框架：JCF 和 JUC 源碼分析與實現

銀文傑
筆名“說好不能打臉”，CSDN專欄作者，CSDN Java特約編輯，《高性能服務系統構建與實戰》一書作者。 16年資深IT“直男”一枚，愛好是敲敲代碼、寫寫博客、研究創業熱點。
參與過多個百萬級用戶系統的設計研發，對系統頂層設計、技術線路規劃、系統性能調優、業務抽像等有較豐富的經驗。也曾有幾年頭腦發熱拍案創業，兼職過市場銷售、電話客服、公司保安及清潔大叔。

第I部分 Java集合框架 1
第1章 JCF中的List集合 3
1．1　List集合概要和重要接口介紹 3
1．1．1 java． lang． Iterable接口 4
1．1．2 java． util． Collection接口 5
1．1．3 java． util． AbstractList抽像類 6
1．1．4 java． util． RandomAccess接口 7
1．2　List集合實現――Vector 14
1．2．1 Vector集合的擴容操作 16
1．2．2 Vector集合的修改方法――set(int， E) 19
1．2．3 Vector集合的刪除方法――removeElementAt(int) 20
1．3　List集合實現――ArrayList 22
1．3．1 ArrayList集合概述 23
1．3．2 ArrayList集合的初始化操作和擴容操作 23
1．3．3 ArrayList集合中的add(E)方法 26
1．3．4 Vector集合與ArrayList集合對比 28
1．4　List集合實現――Stack 29
1．5　List集合實現――LinkedList 32
1．5．1 LinkedList集合的主要結構 33
1．5．2 LinkedList集合的添加操作 35
1．5．3 LinkedList集合的移除操作 40
1．5．4 LinkedList集合的查找操作 44
1．5．5 使用LinkedList集合的棧工作特性 46
1．6 LinkedList集合與ArrayList集合的對比 48
1．6．1 兩種集合寫操作性能的比較 48
1．6．2 兩種集合讀操作性能的比較 49
1．6．3 不同遍歷方式對LinkedList集合的意義 50
1．6．4 在什麼場景中推薦選擇LinkedList集合 54
第2章 JCF中的Queue、Deque集合 55
2．1　Queue集合實現――ArrayDeque 56
2．1．1 ArrayDeque集合的主要結構及相關方法 57
2．1．2 ArrayDeque集合的初始化過程 60
2．1．3 ArrayDeque集合的添加操作 61
2．1．4 ArrayDeque集合的擴容操作 64
2．2　堆和堆排序 67
2．2．1 樹、二叉樹 67
2．2．2 堆、小頂堆、大頂堆 69
2．2．3 堆的降維――使用數組表示堆結構 71
2．2．4 堆排序 72
2．2．5 自行完成一個堆排序 75
2．3　Queue集合實現――PriorityQueue 77
2．3．1 PriorityQueue隊列的基本使用方法 77
2．3．2 PriorityQueue隊列的構造 78
2．3．3 PriorityQueue隊列的核心工作原理 82
2．3．4 PriorityQueue隊列的擴容操作 88
2．3．5 PriorityQueue隊列的添加操作 90
2．3．6 PriorityQueue隊列的移除操作 90
第3章 JCF中的Map集合 94
3．1　Map集合概述 94
3．1．1 K-V鍵值對節點定義――Entry 95
3．1．2 與Map集合有關的重要接口和抽像類 97
3．2　紅黑樹略講 103
3．2．1 二叉查找樹（二叉搜索樹） 104
3．2．2 二叉查找樹的查找操作和添加操作 105
3．2．3 為什麼需要紅黑樹 107
3．2．4 紅黑樹的基本結構 107
3．2．5 紅黑樹的操作規則 108
3．2．6 紅黑樹的節點添加操作 110
3．2．7 紅黑樹的節點刪除操作 120
3．3　Map集合實現――TreeMap 136
3．3．1 TreeMap集合的基本使用方法 136
3．3．2 TreeMap集合的重要屬性和方法 138
3．4　Map集合實現――HashMap 148
3．4．1 HashMap集合的結構 150
3．4．2 HashMap集合的主要工作過程 155
3．4．3 向HashMap集合中添加K-V鍵值對節點（鍊錶方式） 158
3．4．4 向HashMap集合中添加K-V鍵值對節點（紅黑樹方式） 160
3．4．5 HashMap集合紅黑樹、鍊錶互相轉換 165
3．4．6 HashMap集合的擴容操作 172
3．5　Map集合實現――LinkedHashMap 180
3．5．1 LinkedHashMap集合的節點結構 182
3．5．2 LinkedHashMap集合的主要結構 184
3．5．3 LinkedHashMap集合的迭代器 186
第4章 JCF的Set集合 191
4．1　Set集合概述 192
4．1．1 java． util． SortedSet接口 192
4．1．2 java． util． NavigableSet接口 195
4．1．3 java． util． AbstractSet抽像類 199
4．2　Set集合實現――HashSet 200
4．2．1 HashSet集合的主要屬性 201
4．2．2 HashSet集合的構造方法 201
4．2．3 HashSet集合的主要操作方法 202
4．3　Set集合實現――LinkedHashSet、TreeSet 203
4．3．1 LinkedHashSet集合 203
4．3．2 TreeSet集合 204
第II部分 JUC與高並發概述 208
第5章 Object Monitor管程實現 212
5．1　悲觀鎖和樂觀鎖 212
5．2　synchronized修飾符和線程控制 215
5．2．1 線程的基本特點 215
5．2．2 線程狀態切換和操作方法 216
5．3　Object Monitor基本結構概要 227
5．3．1 synchronized修飾符和鎖升級過程 228
5．3．2 管程與synchronized修飾符 233
5．3．3 對線程狀態切換示意圖進行細化 235
5．4　使用jstack命令觀察線程狀態 237
5．4．1 jstack基本命令 237
5．4．2 jstack命令中的線程關鍵信息 238
5．4．3 線程狀態及切換方式（僅限Object Monitor模式） 240
5．5　Object Monitor模式總結 244
5．5．1 as-if-serial語義原則與happens-before規則 244
5．5．2 Object Monitor模式如何保證三性 246
5．5．3 Object Monitor模式如何解決互斥、同步問題 248
第6章 JUC的必要組成部分 250
6．1　Unsafe工具類 252
6．1．1 在源碼中使用Unsafe工具類 252
6．1．2 Unsafe工具類中的典型方法講解 255
6．2　LockSupport工具類 261
6．2．1 park()方法和unpark()方法的使用示例 261
6．2．2 LockSupport工具類的主要屬性和方法 263
6．3　線程狀態 266
6．3．1 使用jstack命令觀察線程狀態 266
6．3．2 更詳細的線程狀態說明 269
6．3．3 其他常用命令 271
6．4　volatile修飾符 275
6．4．1 為什麼需要Java內存模型 275
6．4．2 內存可見性問題和MESI協議 277
6．4．3 存儲緩存和失效隊列 281
6．4．4 內存屏障與數據一致性 283
6．4．5 內存屏障與指令重排 285
6．4．6 volatile修飾符和內存屏障 289
6．5　輕量化的原子性操作方法 300
6．5．1 原子性操作――AtomicInteger類 301
6．5．2 原子性操作――AtomicStampedReference類 301
6．5．3 使用變量句柄完成原子性操作 303
第7章 另一種管程實現――AQS技術 305
7．1　AQS技術的基本原理 306
7．1．1 AQS技術的工作過程概要及使用示例 306
7．1．2 AQS技術中的關鍵定義 308
7．2　AQS實現――ReentrantLock類 325
7．2．1 ReentrantLock類的使用方法 325
7．2．2 AQS技術如何幫助ReentrantLock類工作 327
7．3　AQS實現――Condition控制 332
7．3．1 基本使用方法 332
7．3．2 ReentrantLock類如何進行Condition控制 334
7．4　AQS技術總結 342
第III部分 在高並發場景中工作的集合 345
第8章 高並發場景中的List、Map和Set集合 346
8．1　List集合實現――CopyOnWriteArrayList 346
8．1．1 CopyOnWriteArrayList集合概述 346
8．1．2 CopyOnWriteArrayList集合的主要構造方法 348
8．1．3 CopyOnWriteArrayList集合的主要方法 349
8．1．4 java． util． Collections． synchronizedList()方法的補充作用 352
8．2　Map集合實現――ConcurrentHashMap 355
8．2．1 ConcurrentHashMap集合概述 355
8．2．2 ConcurrentHashMap集合的主要屬性 358
8．2．3 ConcurrentHashMap集合的主要工作過程 359
8．3　高並發場景中的List、Map、Set集合說明 378
第9章 高並發場景中的Queue集合 380
9．1　概述 380
9．1．1 什麼是有界隊列，什麼是無界隊列 381
9．1．2 什麼是阻塞隊列，什麼是非阻塞隊列 382
9．2　Queue集合實現――ArrayBlockingQueue 384
9．2．1 ArrayBlockingQueue隊列的基本使用方法 385
9．2．2 ArrayBlockingQueue隊列的工作原理 388
9．3　Queue集合實現――LinkedBlockingQueue 396
9．3．1 LinkedBlockingQueue隊列的重要屬性 397
9．3．2 LinkedBlockingQueue隊列的構造方法 399
9．3．3 入隊操作和出隊操作 401
9．3．4 LinkedBlockingQueue隊列的主要方法 404
9．4　Queue集合實現――LinkedTransferQueue 413
9．4．1 LinkedTransferQueue隊列的基本使用場景 414
9．4．2 LinkedTransferQueue隊列的主要結構 416
9．4．3 LinkedTransferQueue隊列的主要工作過程 420
9．4．4 LinkedTransferQueue隊列的主要方法 437
9．5　Queue集合實現――PriorityBlockingQueue 438
9．5．1 PriorityBlockingQueue隊列的主要屬性 439
9．5．2 PriorityBlockingQueue隊列的主要構造方法 440
9．5．3 PriorityBlockingQueue隊列的擴容過程 442
9．5．4 PriorityBlockingQueue隊列的典型操作方法 444
9．6　Queue集合實現――DelayQueue 446
9．6．1 java． util． concurrent． Delayed接口與基本使用方法 447
9．6．2 DelayQueue隊列的主要屬性和構造方法 449
9．6．3 DelayQueue隊列的主要工作過程 450
第10章 高並發場景中的集合總結 454
10．1　還有哪些高並發場景中的常用集合沒有被提及 454
10．2　典型集合對應關係對比 455
10．3 高並發場景中的集合可藉鑑的設計思想 455
10．3．1 使用JUC提供的基本要素保證線程安全性 456
10．3．2 通過複合手段保證多場景中的性能平衡性 457
10．3．3 更多提升性能的手段 458