視頻地址：https://www.yuque.com/linxun-bpyj0/linxun/vy91es9lyg7kbfnr

大綱

基礎篇

基礎篇要點：算法、數據結構、基礎設計模式

1. 二分查找

要求

能夠用自己語言描述二分查找算法
能夠手寫二分查找代碼
能夠解答一些變化后的考法

算法描述

前提：有已排序數組 A（假設已經做好）
定義左邊界 L、右邊界 R，確定搜索范圍，循環執行二分查找（3、4兩步）
獲取中間索引 M = Floor((L+R) /2)
中間索引的值 ?A[M] 與待搜索的值 T 進行比較
① A[M] == T 表示找到，返回中間索引
② A[M] > T，中間值右側的其它元素都大于 T，無需比較，中間索引左邊去找，M - 1 設置為右邊界，重新查找
③ A[M] < T，中間值左側的其它元素都小于 T，無需比較，中間索引右邊去找， M + 1 設置為左邊界，重新查找
當 L > R 時，表示沒有找到，應結束循環

更形象的描述請參考：binary_search.html

算法實現

public static int binarySearch(int[] a, int t) {int l = 0, r = a.length - 1, m;while (l <= r) {m = (l + r) / 2;if (a[m] == t) {return m;} else if (a[m] > t) {r = m - 1;} else {l = m + 1;}}return -1;
}

測試代碼

public static void main(String[] args) {int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};int target = 47;int idx = binarySearch(array, target);System.out.println(idx);
}

解決整數溢出問題

當 l 和 r 都較大時，l + r 有可能超過整數范圍，造成運算錯誤，解決方法有兩種：

int m = l + (r - l) / 2;

還有一種是：

int m = (l + r) >>> 1;

其它考法

有一個有序表為 1,5,8,11,19,22,31,35,40,45,48,49,50 當二分查找值為 48 的結點時，查找成功需要比較的次數
使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 中查找元素 81 時，需要經過（ ? ）次比較
在擁有128個元素的數組中二分查找一個數，需要比較的次數最多不超過多少次

對于前兩個題目，記得一個簡要判斷口訣：奇數二分取中間，偶數二分取中間靠左。對于后一道題目，需要知道公式：

其中 n 為查找次數，N 為元素個數

2. 冒泡排序

要求

能夠用自己語言描述冒泡排序算法
能夠手寫冒泡排序代碼
了解一些冒泡排序的優化手段

算法描述

依次比較數組中相鄰兩個元素大小，若 a[j] > a[j+1]，則交換兩個元素，兩兩都比較一遍稱為一輪冒泡，結果是讓最大的元素排至最后
重復以上步驟，直到整個數組有序

更形象的描述請參考：bubble_sort.html

算法實現

public static void bubble(int[] a) {for (int j = 0; j < a.length - 1; j++) {// 一輪冒泡boolean swapped = false; // 是否發生了交換for (int i = 0; i < a.length - 1 - j; i++) {System.out.println("比較次數" + i);if (a[i] > a[i + 1]) {Utils.swap(a, i, i + 1);swapped = true;}}System.out.println("第" + j + "輪冒泡"+ Arrays.toString(a));if (!swapped) {break;}}
}

優化點1：每經過一輪冒泡，內層循環就可以減少一次
優化點2：如果某一輪冒泡沒有發生交換，則表示所有數據有序，可以結束外層循環

進一步優化

public static void bubble_v2(int[] a) {int n = a.length - 1;while (true) {int last = 0; // 表示最后一次交換索引位置for (int i = 0; i < n; i++) {System.out.println("比較次數" + i);if (a[i] > a[i + 1]) {Utils.swap(a, i, i + 1);last = i;}}n = last;System.out.println("第輪冒泡"+ Arrays.toString(a));if (n == 0) {break;}}
}

每輪冒泡時，最后一次交換索引可以作為下一輪冒泡的比較次數，如果這個值為零，表示整個數組有序，直接退出外層循環即可

3. 選擇排序

要求

能夠用自己語言描述選擇排序算法
能夠比較選擇排序與冒泡排序
理解非穩定排序與穩定排序

算法描述

將數組分為兩個子集，排序的和未排序的，每一輪從未排序的子集中選出最小的元素，放入排序子集
重復以上步驟，直到整個數組有序

更形象的描述請參考：selection_sort.html

算法實現

public static void selection(int[] a) {for (int i = 0; i < a.length - 1; i++) {// i 代表每輪選擇最小元素要交換到的目標索引int s = i; // 代表最小元素的索引for (int j = s + 1; j < a.length; j++) {if (a[s] > a[j]) { // j 元素比 s 元素還要小, 更新 ss = j;}}if (s != i) {swap(a, s, i);}System.out.println(Arrays.toString(a));}
}

優化點：為減少交換次數，每一輪可以先找最小的索引，在每輪最后再交換元素

與冒泡排序比較

二者平均時間復雜度都是
選擇排序一般要快于冒泡，因為其交換次數少
但如果集合有序度高，冒泡優于選擇
冒泡屬于穩定排序算法，而選擇屬于不穩定排序

- 穩定排序指，按對象中不同字段進行多次排序，不會打亂同值元素的順序
- 不穩定排序則反之

穩定排序與不穩定排序

System.out.println("=================不穩定================");
Card[] cards = getStaticCards();
System.out.println(Arrays.toString(cards));
selection(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
System.out.println(Arrays.toString(cards));
selection(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
System.out.println(Arrays.toString(cards));System.out.println("=================穩定=================");
cards = getStaticCards();
System.out.println(Arrays.toString(cards));
bubble(cards, Comparator.comparingInt((Card a) -> a.sharpOrder).reversed());
System.out.println(Arrays.toString(cards));
bubble(cards, Comparator.comparingInt((Card a) -> a.numberOrder).reversed());
System.out.println(Arrays.toString(cards));

都是先按照花色排序（????），再按照數字排序（AKQJ…）

不穩定排序算法按數字排序時，會打亂原本同值的花色順序

[[?7], [?2], [?4], [?5], [?2], [?5]]
[[?7], [?5], [?5], [?4], [?2], [?2]]

原來 ?2 在前 ?2 在后，按數字再排后，他倆的位置變了

穩定排序算法按數字排序時，會保留原本同值的花色順序，如下所示 ?2 與 ?2 的相對位置不變

[[?7], [?2], [?4], [?5], [?2], [?5]]
[[?7], [?5], [?5], [?4], [?2], [?2]]

4. 插入排序

要求

能夠用自己語言描述插入排序算法
能夠比較插入排序與選擇排序

算法描述

將數組分為兩個區域，排序區域和未排序區域，每一輪從未排序區域中取出第一個元素，插入到排序區域（需保證順序）
重復以上步驟，直到整個數組有序

更形象的描述請參考：insertion_sort.html

算法實現

// 修改了代碼與希爾排序一致
public static void insert(int[] a) {// i 代表待插入元素的索引for (int i = 1; i < a.length; i++) {int t = a[i]; // 代表待插入的元素值int j = i;System.out.println(j);while (j >= 1) {if (t < a[j - 1]) { // j-1 是上一個元素索引，如果 > t，后移a[j] = a[j - 1];j--;} else { // 如果 j-1 已經 <= t, 則 j 就是插入位置break;}}a[j] = t;System.out.println(Arrays.toString(a) + " " + j);}
}

與選擇排序比較

二者平均時間復雜度都是
大部分情況下，插入都略優于選擇
有序集合插入的時間復雜度為
插入屬于穩定排序算法，而選擇屬于不穩定排序

提示

插入排序通常被同學們所輕視，其實它的地位非常重要。小數據量排序，都會優先選擇插入排序

5. 希爾排序

要求

能夠用自己語言描述希爾排序算法

算法描述

首先選取一個間隙序列，如 (n/2，n/4 … 1)，n 為數組長度
每一輪將間隙相等的元素視為一組，對組內元素進行插入排序，目的有二
① 少量元素插入排序速度很快
② 讓組內值較大的元素更快地移動到后方
當間隙逐漸減少，直至為 1 時，即可完成排序

更形象的描述請參考：shell_sort.html

算法實現

private static void shell(int[] a) {int n = a.length;for (int gap = n / 2; gap > 0; gap /= 2) {// i 代表待插入元素的索引for (int i = gap; i < n; i++) {int t = a[i]; // 代表待插入的元素值int j = i;while (j >= gap) {// 每次與上一個間隙為 gap 的元素進行插入排序if (t < a[j - gap]) { // j-gap 是上一個元素索引，如果 > t，后移a[j] = a[j - gap];j -= gap;} else { // 如果 j-1 已經 <= t, 則 j 就是插入位置break;}}a[j] = t;System.out.println(Arrays.toString(a) + " gap:" + gap);}}
}

參考資料

https://en.wikipedia.org/wiki/Shellsort

6. 快速排序

要求

能夠用自己語言描述快速排序算法
掌握手寫單邊循環、雙邊循環代碼之一
能夠說明快排特點
了解洛穆托與霍爾兩種分區方案的性能比較

算法描述

每一輪排序選擇一個基準點（pivot）進行分區

1. 讓小于基準點的元素的進入一個分區，大于基準點的元素的進入另一個分區
2. 當分區完成時，基準點元素的位置就是其最終位置

在子分區內重復以上過程，直至子分區元素個數少于等于 1，這體現的是分而治之的思想（divide-and-conquer）
從以上描述可以看出，一個關鍵在于分區算法，常見的有洛穆托分區方案、雙邊循環分區方案、霍爾分區方案

更形象的描述請參考：quick_sort.html

單邊循環快排（lomuto 洛穆托分區方案）

選擇最右元素作為基準點元素
j 指針負責找到比基準點小的元素，一旦找到則與 i 進行交換
i 指針維護小于基準點元素的邊界，也是每次交換的目標索引
最后基準點與 i 交換，i 即為分區位置

public static void quick(int[] a, int l, int h) {if (l >= h) {return;}int p = partition(a, l, h); // p 索引值quick(a, l, p - 1); // 左邊分區的范圍確定quick(a, p + 1, h); // 左邊分區的范圍確定
}private static int partition(int[] a, int l, int h) {int pv = a[h]; // 基準點元素int i = l;for (int j = l; j < h; j++) {if (a[j] < pv) {if (i != j) {swap(a, i, j);}i++;}}if (i != h) {swap(a, h, i);}System.out.println(Arrays.toString(a) + " i=" + i);// 返回值代表了基準點元素所在的正確索引，用它確定下一輪分區的邊界return i;
}

雙邊循環快排（不完全等價于 hoare 霍爾分區方案）

選擇最左元素作為基準點元素
j 指針負責從右向左找比基準點小的元素，i 指針負責從左向右找比基準點大的元素，一旦找到二者交換，直至 i，j 相交
最后基準點與 i（此時 i 與 j 相等）交換，i 即為分區位置

要點

基準點在左邊，并且要先 j 后 i
while( i < j && a[j] > pv ) j–
while ( i < j && a[i] <= pv ) i++

private static void quick(int[] a, int l, int h) {if (l >= h) {return;}int p = partition(a, l, h);quick(a, l, p - 1);quick(a, p + 1, h);
}private static int partition(int[] a, int l, int h) {int pv = a[l];int i = l;int j = h;while (i < j) {// j 從右找小的while (i < j && a[j] > pv) {j--;}// i 從左找大的while (i < j && a[i] <= pv) {i++;}swap(a, i, j);}swap(a, l, j);System.out.println(Arrays.toString(a) + " j=" + j);return j;
}

快排特點

平均時間復雜度是，最壞時間復雜度
數據量較大時，優勢非常明顯
屬于不穩定排序

洛穆托分區方案 vs 霍爾分區方案

霍爾的移動次數平均來講比洛穆托少3倍
https://qastack.cn/cs/11458/quicksort-partitioning-hoare-vs-lomuto

補充代碼說明

day01.sort.QuickSort3 演示了空穴法改進的雙邊快排，比較次數更少
day01.sort.QuickSortHoare 演示了霍爾分區的實現
day01.sort.LomutoVsHoare 對四種分區實現的移動次數比較

7. ArrayList

要求

掌握 ArrayList 擴容規則

擴容規則

ArrayList() 會使用長度為零的數組
ArrayList(int initialCapacity) 會使用指定容量的數組
public ArrayList(Collection<? extends E> c) 會使用 c 的大小作為數組容量
add(Object o) 首次擴容為 10，再次擴容為上次容量的 1.5 倍
addAll(Collection c) 沒有元素時，擴容為 Math.max(10, 實際元素個數)，有元素時為 Math.max(原容量 1.5 倍, 實際元素個數)

其中第 4 點必須知道，其它幾點視個人情況而定

提示

測試代碼見 day01.list.TestArrayList ，這里不再列出
要注意的是，示例中用反射方式來更直觀地反映 ArrayList 的擴容特征，但從 JDK 9 由于模塊化的影響，對反射做了較多限制，需要在運行測試代碼時添加 VM 參數 --add-opens java.base/java.util=ALL-UNNAMED 方能運行通過，后面的例子都有相同問題

代碼說明

day01.list.TestArrayList#arrayListGrowRule 演示了 add(Object) 方法的擴容規則，輸入參數 n 代表打印多少次擴容后的數組長度

8. Iterator

要求

掌握什么是 Fail-Fast、什么是 Fail-Safe

Fail-Fast 與 Fail-Safe

ArrayList 是 fail-fast 的典型代表，遍歷的同時不能修改，盡快失敗
CopyOnWriteArrayList 是 fail-safe 的典型代表，遍歷的同時可以修改，原理是讀寫分離

提示

測試代碼見 day01.list.FailFastVsFailSafe，這里不再列出

9. LinkedList

要求

能夠說清楚 LinkedList 對比 ArrayList 的區別，并重視糾正部分錯誤的認知

LinkedList

基于雙向鏈表，無需連續內存
隨機訪問慢（要沿著鏈表遍歷）
頭尾插入刪除性能高
占用內存多

ArrayList

基于數組，需要連續內存
隨機訪問快（指根據下標訪問）
尾部插入、刪除性能可以，其它部分插入、刪除都會移動數據，因此性能會低
可以利用 cpu 緩存，局部性原理

代碼說明

day01.list.ArrayListVsLinkedList#randomAccess 對比隨機訪問性能
day01.list.ArrayListVsLinkedList#addMiddle 對比向中間插入性能
day01.list.ArrayListVsLinkedList#addFirst 對比頭部插入性能
day01.list.ArrayListVsLinkedList#addLast 對比尾部插入性能
day01.list.ArrayListVsLinkedList#linkedListSize 打印一個 LinkedList 占用內存
day01.list.ArrayListVsLinkedList#arrayListSize 打印一個 ArrayList 占用內存

10. HashMap

要求

掌握 HashMap 的基本數據結構
掌握樹化
理解索引計算方法、二次 hash 的意義、容量對索引計算的影響
掌握 put 流程、擴容、擴容因子
理解并發使用 HashMap 可能導致的問題
理解 key 的設計

1）基本數據結構

1.7 數組 + 鏈表
1.8 數組 + （鏈表 | 紅黑樹）

更形象的演示，見資料中的 hash-demo.jar，運行需要 jdk14 以上環境，進入 jar 包目錄，執行下面命令

java -jar --add-exports java.base/jdk.internal.misc=ALL-UNNAMED hash-demo.jar

2）樹化與退化

樹化意義

紅黑樹用來避免 DoS 攻擊，防止鏈表超長時性能下降，樹化應當是偶然情況，是保底策略
hash 表的查找，更新的時間復雜度是，而紅黑樹的查找，更新的時間復雜度是，TreeNode 占用空間也比普通 Node 的大，如非必要，盡量還是使用鏈表
hash 值如果足夠隨機，則在 hash 表內按泊松分布，在負載因子 0.75 的情況下，長度超過 8 的鏈表出現概率是 0.00000006，樹化閾值選擇 8 就是為了讓樹化幾率足夠小

樹化規則

當鏈表長度超過樹化閾值 8 時，先嘗試擴容來減少鏈表長度，如果數組容量已經 >=64，才會進行樹化

退化規則

情況1：在擴容時如果拆分樹時，樹元素個數 <= 6 則會退化鏈表
情況2：remove 樹節點時，若 root、root.left、root.right、root.left.left 有一個為 null ，也會退化為鏈表

3）索引計算

索引計算方法

首先，計算對象的 hashCode()
再進行調用 HashMap 的 hash() 方法進行二次哈希

- 二次 hash() 是為了綜合高位數據，讓哈希分布更為均勻

最后 & (capacity – 1) 得到索引

數組容量為何是 2 的 n 次冪

計算索引時效率更高：如果是 2 的 n 次冪可以使用位與運算代替取模
擴容時重新計算索引效率更高： hash & oldCap == 0 的元素留在原來位置，否則新位置 = 舊位置 + oldCap

注意

二次 hash 是為了配合 容量是 2 的 n 次冪 這一設計前提，如果 hash 表的容量不是 2 的 n 次冪，則不必二次 hash
容量是 2 的 n 次冪 這一設計計算索引效率更好，但 hash 的分散性就不好，需要二次 hash 來作為補償，沒有采用這一設計的典型例子是 Hashtable

4）put 與擴容

put 流程

HashMap 是懶惰創建數組的，首次使用才創建數組
計算索引（桶下標）
如果桶下標還沒人占用，創建 Node 占位返回
如果桶下標已經有人占用

1. 已經是 TreeNode 走紅黑樹的添加或更新邏輯
2. 是普通 Node，走鏈表的添加或更新邏輯，如果鏈表長度超過樹化閾值，走樹化邏輯

返回前檢查容量是否超過閾值，一旦超過進行擴容

1.7 與 1.8 的區別

鏈表插入節點時，1.7 是頭插法，1.8 是尾插法
1.7 是大于等于閾值且沒有空位時才擴容，而 1.8 是大于閾值就擴容
1.8 在擴容計算 Node 索引時，會優化

擴容（加載）因子為何默認是 0.75f

在空間占用與查詢時間之間取得較好的權衡
大于這個值，空間節省了，但鏈表就會比較長影響性能
小于這個值，沖突減少了，但擴容就會更頻繁，空間占用也更多

5）并發問題

擴容死鏈（1.7 會存在）

1.7 源碼如下：

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}
}

e 和 next 都是局部變量，用來指向當前節點和下一個節點
線程1（綠色）的臨時變量 e 和 next 剛引用了這倆節點，還未來得及移動節點，發生了線程切換，由線程2（藍色）完成擴容和遷移

線程2 擴容完成，由于頭插法，鏈表順序顛倒。但線程1 的臨時變量 e 和 next 還引用了這倆節點，還要再來一遍遷移

第一次循環

- 循環接著線程切換前運行，注意此時 e 指向的是節點 a，next 指向的是節點 b
- e 頭插 a 節點，注意圖中畫了兩份 a 節點，但事實上只有一個（為了不讓箭頭特別亂畫了兩份）
- 當循環結束是 e 會指向 next 也就是 b 節點

第二次循環

- next 指向了節點 a
- e 頭插節點 b
- 當循環結束時，e 指向 next 也就是節點 a

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-A3enIgab-1691920287269)()]

第三次循環

- next 指向了 null
- e 頭插節點 a，a 的 next 指向了 b（之前 a.next 一直是 null），b 的 next 指向 a，死鏈已成
- 當循環結束時，e 指向 next 也就是 null，因此第四次循環時會正常退出

數據錯亂（1.7，1.8 都會存在）

代碼參考 day01.map.HashMapMissData，具體調試步驟參考視頻

補充代碼說明

day01.map.HashMapDistribution 演示 map 中鏈表長度符合泊松分布
day01.map.DistributionAffectedByCapacity 演示容量及 hashCode 取值對分布的影響

- day01.map.DistributionAffectedByCapacity#hashtableGrowRule 演示了 Hashtable 的擴容規律
- day01.sort.Utils#randomArray 如果 hashCode 足夠隨機，容量是否是 2 的 n 次冪影響不大
- day01.sort.Utils#lowSameArray 如果 hashCode 低位一樣的多，容量是 2 的 n 次冪會導致分布不均勻
- day01.sort.Utils#evenArray 如果 hashCode 偶數的多，容量是 2 的 n 次冪會導致分布不均勻
- 由此得出對于容量是 2 的 n 次冪的設計來講，二次 hash 非常重要

day01.map.HashMapVsHashtable 演示了對于同樣數量的單詞字符串放入 HashMap 和 Hashtable 分布上的區別

6）key 的設計

key 的設計要求

HashMap 的 key 可以為 null，但 Map 的其他實現則不然
作為 key 的對象，必須實現 hashCode 和 equals，并且 key 的內容不能修改（不可變）
key 的 hashCode 應該有良好的散列性

如果 key 可變，例如修改了 age 會導致再次查詢時查詢不到

public class HashMapMutableKey {public static void main(String[] args) {HashMap<Student, Object> map = new HashMap<>();Student stu = new Student("張三", 18);map.put(stu, new Object());System.out.println(map.get(stu));stu.age = 19;System.out.println(map.get(stu));}static class Student {String name;int age;public Student(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return age == student.age && Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}}
}

String 對象的 hashCode() 設計

目標是達到較為均勻的散列效果，每個字符串的 hashCode 足夠獨特
字符串中的每個字符都可以表現為一個數字，稱為，其中 i 的范圍是 0 ~ n - 1
散列公式為：
31 代入公式有較好的散列特性，并且 31 * h 可以被優化為

- 即 $32 ?h -h $
- 即
- 即

11. 單例模式

要求

掌握五種單例模式的實現方式
理解為何 DCL 實現時要使用 volatile 修飾靜態變量
了解 jdk 中用到單例的場景

餓漢式

public class Singleton1 implements Serializable {private Singleton1() {if (INSTANCE != null) {throw new RuntimeException("單例對象不能重復創建");}System.out.println("private Singleton1()");}private static final Singleton1 INSTANCE = new Singleton1();public static Singleton1 getInstance() {return INSTANCE;}public static void otherMethod() {System.out.println("otherMethod()");}public Object readResolve() {return INSTANCE;}
}

構造方法拋出異常是防止反射破壞單例
readResolve() 是防止反序列化破壞單例

枚舉餓漢式

public enum Singleton2 {INSTANCE;private Singleton2() {System.out.println("private Singleton2()");}@Overridepublic String toString() {return getClass().getName() + "@" + Integer.toHexString(hashCode());}public static Singleton2 getInstance() {return INSTANCE;}public static void otherMethod() {System.out.println("otherMethod()");}
}

枚舉餓漢式能天然防止反射、反序列化破壞單例

懶漢式

public class Singleton3 implements Serializable {private Singleton3() {System.out.println("private Singleton3()");}private static Singleton3 INSTANCE = null;// Singleton3.classpublic static synchronized Singleton3 getInstance() {if (INSTANCE == null) {INSTANCE = new Singleton3();}return INSTANCE;}public static void otherMethod() {System.out.println("otherMethod()");}}

其實只有首次創建單例對象時才需要同步，但該代碼實際上每次調用都會同步
因此有了下面的雙檢鎖改進

雙檢鎖懶漢式

public class Singleton4 implements Serializable {private Singleton4() {System.out.println("private Singleton4()");}private static volatile Singleton4 INSTANCE = null; // 可見性，有序性public static Singleton4 getInstance() {if (INSTANCE == null) {synchronized (Singleton4.class) {if (INSTANCE == null) {INSTANCE = new Singleton4();}}}return INSTANCE;}public static void otherMethod() {System.out.println("otherMethod()");}
}

為何必須加 volatile：

INSTANCE = new Singleton4() 不是原子的，分成 3 步：創建對象、調用構造、給靜態變量賦值，其中后兩步可能被指令重排序優化，變成先賦值、再調用構造
如果線程1 先執行了賦值，線程2 執行到第一個 INSTANCE == null 時發現 INSTANCE 已經不為 null，此時就會返回一個未完全構造的對象

內部類懶漢式

public class Singleton5 implements Serializable {private Singleton5() {System.out.println("private Singleton5()");}private static class Holder {static Singleton5 INSTANCE = new Singleton5();}public static Singleton5 getInstance() {return Holder.INSTANCE;}public static void otherMethod() {System.out.println("otherMethod()");}
}

避免了雙檢鎖的缺點

JDK 中單例的體現

Runtime 體現了餓漢式單例
Console 體現了雙檢鎖懶漢式單例
Collections 中的 EmptyNavigableSet 內部類懶漢式單例
ReverseComparator.REVERSE_ORDER 內部類懶漢式單例
Comparators.NaturalOrderComparator.INSTANCE 枚舉餓漢式單例

并發篇

1. 線程狀態

要求

掌握 Java 線程六種狀態
掌握 Java 線程狀態轉換
能理解五種狀態與六種狀態兩種說法的區別

六種狀態及轉換

分別是

新建

- 當一個線程對象被創建，但還未調用 start 方法時處于新建狀態
- 此時未與操作系統底層線程關聯

可運行

- 調用了 start 方法，就會由新建進入可運行
- 此時與底層線程關聯，由操作系統調度執行

終結

- 線程內代碼已經執行完畢，由可運行進入終結
- 此時會取消與底層線程關聯

阻塞

- 當獲取鎖失敗后，由可運行進入 Monitor 的阻塞隊列阻塞，此時不占用 cpu 時間
- 當持鎖線程釋放鎖時，會按照一定規則喚醒阻塞隊列中的阻塞線程，喚醒后的線程進入可運行狀態

等待

- 當獲取鎖成功后，但由于條件不滿足，調用了 wait() 方法，此時從可運行狀態釋放鎖進入 Monitor 等待集合等待，同樣不占用 cpu 時間
- 當其它持鎖線程調用 notify() 或 notifyAll() 方法，會按照一定規則喚醒等待集合中的等待線程，恢復為可運行狀態

有時限等待

- 當獲取鎖成功后，但由于條件不滿足，調用了 wait(long) 方法，此時從可運行狀態釋放鎖進入 Monitor 等待集合進行有時限等待，同樣不占用 cpu 時間
- 當其它持鎖線程調用 notify() 或 notifyAll() 方法，會按照一定規則喚醒等待集合中的有時限等待線程，恢復為可運行狀態，并重新去競爭鎖
- 如果等待超時，也會從有時限等待狀態恢復為可運行狀態，并重新去競爭鎖
- 還有一種情況是調用 sleep(long) 方法也會從可運行狀態進入有時限等待狀態，但與 Monitor 無關，不需要主動喚醒，超時時間到自然恢復為可運行狀態

其它情況（只需了解）

可以用 interrupt() 方法打斷等待、有時限等待的線程，讓它們恢復為可運行狀態
park，unpark 等方法也可以讓線程等待和喚醒

五種狀態

五種狀態的說法來自于操作系統層面的劃分

運行態：分到 cpu 時間，能真正執行線程內代碼的
就緒態：有資格分到 cpu 時間，但還未輪到它的
阻塞態：沒資格分到 cpu 時間的

- 涵蓋了 java 狀態中提到的阻塞、等待、有時限等待
- 多出了阻塞 I/O，指線程在調用阻塞 I/O 時，實際活由 I/O 設備完成，此時線程無事可做，只能干等

新建與終結態：與 java 中同名狀態類似，不再啰嗦

2. 線程池

要求

掌握線程池的 7 大核心參數

七大參數

corePoolSize 核心線程數目 - 池中會保留的最多線程數
maximumPoolSize 最大線程數目 - 核心線程+救急線程的最大數目
keepAliveTime 生存時間 - 救急線程的生存時間，生存時間內沒有新任務，此線程資源會釋放
unit 時間單位 - 救急線程的生存時間單位，如秒、毫秒等
workQueue - 當沒有空閑核心線程時，新來任務會加入到此隊列排隊，隊列滿會創建救急線程執行任務
threadFactory 線程工廠 - 可以定制線程對象的創建，例如設置線程名字、是否是守護線程等
handler 拒絕策略 - 當所有線程都在繁忙，workQueue 也放滿時，會觸發拒絕策略

1. 拋異常 java.util.concurrent.ThreadPoolExecutor.AbortPolicy
2. 由調用者執行任務 java.util.concurrent.ThreadPoolExecutor.CallerRunsPolicy
3. 丟棄任務 java.util.concurrent.ThreadPoolExecutor.DiscardPolicy
4. 丟棄最早排隊任務 java.util.concurrent.ThreadPoolExecutor.DiscardOldestPolicy

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-U9e6Mevj-1691920287271)()]

代碼說明

day02.TestThreadPoolExecutor 以較為形象的方式演示了線程池的核心組成

3. wait vs sleep

要求

能夠說出二者區別

一個共同點，三個不同點

共同點

wait() ，wait(long) 和 sleep(long) 的效果都是讓當前線程暫時放棄 CPU 的使用權，進入阻塞狀態

不同點

方法歸屬不同

- sleep(long) 是 Thread 的靜態方法
- 而 wait()，wait(long) 都是 Object 的成員方法，每個對象都有

醒來時機不同

- 執行 sleep(long) 和 wait(long) 的線程都會在等待相應毫秒后醒來
- wait(long) 和 wait() 還可以被 notify 喚醒，wait() 如果不喚醒就一直等下去
- 它們都可以被打斷喚醒

鎖特性不同（重點）

- wait 方法的調用必須先獲取 wait 對象的鎖，而 sleep 則無此限制
- wait 方法執行后會釋放對象鎖，允許其它線程獲得該對象鎖（我放棄 cpu，但你們還可以用）
- 而 sleep 如果在 synchronized 代碼塊中執行，并不會釋放對象鎖（我放棄 cpu，你們也用不了）

4. lock vs synchronized

要求

掌握 lock 與 synchronized 的區別
理解 ReentrantLock 的公平、非公平鎖
理解 ReentrantLock 中的條件變量

三個層面

不同點

語法層面

- synchronized 是關鍵字，源碼在 jvm 中，用 c++ 語言實現
- Lock 是接口，源碼由 jdk 提供，用 java 語言實現
- 使用 synchronized 時，退出同步代碼塊鎖會自動釋放，而使用 Lock 時，需要手動調用 unlock 方法釋放鎖

功能層面

- 二者均屬于悲觀鎖、都具備基本的互斥、同步、鎖重入功能
- Lock 提供了許多 synchronized 不具備的功能，例如獲取等待狀態、公平鎖、可打斷、可超時、多條件變量
- Lock 有適合不同場景的實現，如 ReentrantLock， ReentrantReadWriteLock

性能層面

- 在沒有競爭時，synchronized 做了很多優化，如偏向鎖、輕量級鎖，性能不賴
- 在競爭激烈時，Lock 的實現通常會提供更好的性能

公平鎖

公平鎖的公平體現

- 已經處在阻塞隊列中的線程（不考慮超時）始終都是公平的，先進先出
- 公平鎖是指未處于阻塞隊列中的線程來爭搶鎖，如果隊列不為空，則老實到隊尾等待
- 非公平鎖是指未處于阻塞隊列中的線程來爭搶鎖，與隊列頭喚醒的線程去競爭，誰搶到算誰的

公平鎖會降低吞吐量，一般不用

條件變量

ReentrantLock 中的條件變量功能類似于普通 synchronized 的 wait，notify，用在當線程獲得鎖后，發現條件不滿足時，臨時等待的鏈表結構
與 synchronized 的等待集合不同之處在于，ReentrantLock 中的條件變量可以有多個，可以實現更精細的等待、喚醒控制

代碼說明

day02.TestReentrantLock 用較為形象的方式演示 ReentrantLock 的內部結構

5. volatile

要求

掌握線程安全要考慮的三個問題
掌握 volatile 能解決哪些問題

原子性

起因：多線程下，不同線程的指令發生了交錯導致的共享變量的讀寫混亂
解決：用悲觀鎖或樂觀鎖解決，volatile 并不能解決原子性

可見性

起因：由于編譯器優化、或緩存優化、或 CPU 指令重排序優化導致的對共享變量所做的修改另外的線程看不到
解決：用 volatile 修飾共享變量，能夠防止編譯器等優化發生，讓一個線程對共享變量的修改對另一個線程可見

有序性

起因：由于編譯器優化、或緩存優化、或 CPU 指令重排序優化導致指令的實際執行順序與編寫順序不一致
解決：用 volatile 修飾共享變量會在讀、寫共享變量時加入不同的屏障，阻止其他讀寫操作越過屏障，從而達到阻止重排序的效果
注意：

- volatile 變量寫加的屏障是阻止上方其它寫操作越過屏障排到 volatile 變量寫之下
- volatile 變量讀加的屏障是阻止下方其它讀操作越過屏障排到 volatile 變量讀之上
- volatile 讀寫加入的屏障只能防止同一線程內的指令重排

代碼說明

day02.threadsafe.AddAndSubtract 演示原子性
day02.threadsafe.ForeverLoop 演示可見性

- 注意：本例經實踐檢驗是編譯器優化導致的可見性問題

day02.threadsafe.Reordering 演示有序性

- 需要打成 jar 包后測試

請同時參考視頻講解

6. 悲觀鎖 vs 樂觀鎖

要求

掌握悲觀鎖和樂觀鎖的區別

對比悲觀鎖與樂觀鎖

悲觀鎖的代表是 synchronized 和 Lock 鎖

- 其核心思想是【線程只有占有了鎖，才能去操作共享變量，每次只有一個線程占鎖成功，獲取鎖失敗的線程，都得停下來等待】
- 線程從運行到阻塞、再從阻塞到喚醒，涉及線程上下文切換，如果頻繁發生，影響性能
- 實際上，線程在獲取 synchronized 和 Lock 鎖時，如果鎖已被占用，都會做幾次重試操作，減少阻塞的機會

樂觀鎖的代表是 AtomicInteger，使用 cas 來保證原子性

- 其核心思想是【無需加鎖，每次只有一個線程能成功修改共享變量，其它失敗的線程不需要停止，不斷重試直至成功】
- 由于線程一直運行，不需要阻塞，因此不涉及線程上下文切換
- 它需要多核 cpu 支持，且線程數不應超過 cpu 核數

代碼說明

day02.SyncVsCas 演示了分別使用樂觀鎖和悲觀鎖解決原子賦值
請同時參考視頻講解

7. Hashtable vs ConcurrentHashMap

要求

掌握 Hashtable 與 ConcurrentHashMap 的區別
掌握 ConcurrentHashMap 在不同版本的實現區別

更形象的演示，見資料中的 hash-demo.jar，運行需要 jdk14 以上環境，進入 jar 包目錄，執行下面命令

java -jar --add-exports java.base/jdk.internal.misc=ALL-UNNAMED hash-demo.jar

Hashtable 對比 ConcurrentHashMap

Hashtable 與 ConcurrentHashMap 都是線程安全的 Map 集合
Hashtable 并發度低，整個 Hashtable 對應一把鎖，同一時刻，只能有一個線程操作它
ConcurrentHashMap 并發度高，整個 ConcurrentHashMap 對應多把鎖，只要線程訪問的是不同鎖，那么不會沖突

ConcurrentHashMap 1.7

數據結構：Segment(大數組) + HashEntry(小數組) + 鏈表，每個 Segment 對應一把鎖，如果多個線程訪問不同的 Segment，則不會沖突
并發度：Segment 數組大小即并發度，決定了同一時刻最多能有多少個線程并發訪問。Segment 數組不能擴容，意味著并發度在 ConcurrentHashMap 創建時就固定了
索引計算

- 假設大數組長度是，key 在大數組內的索引是 key 的二次 hash 值的高 m 位
- 假設小數組長度是，key 在小數組內的索引是 key 的二次 hash 值的低 n 位

擴容：每個小數組的擴容相對獨立，小數組在超過擴容因子時會觸發擴容，每次擴容翻倍
Segment[0] 原型：首次創建其它小數組時，會以此原型為依據，數組長度，擴容因子都會以原型為準

ConcurrentHashMap 1.8

數據結構：Node 數組 + 鏈表或紅黑樹，數組的每個頭節點作為鎖，如果多個線程訪問的頭節點不同，則不會沖突。首次生成頭節點時如果發生競爭，利用 cas 而非 syncronized，進一步提升性能
并發度：Node 數組有多大，并發度就有多大，與 1.7 不同，Node 數組可以擴容
擴容條件：Node 數組滿 3/4 時就會擴容
擴容單位：以鏈表為單位從后向前遷移鏈表，遷移完成的將舊數組頭節點替換為 ForwardingNode
擴容時并發 get