排序算法 9

P1：分類

排序算法可以分為內部排序和外部排序，在內存中進行的排序稱為內部排序，當要排序的數據量很大時無法全部拷貝到內存，這時需要使用外存進行排序，這種排序稱為外部排序。

內部排序包括比較排序和非比較排序，比較排序包括插入排序、選擇排序、交換排序和歸并排序，非比較排序包括計數排序、基數排序和桶排序。

其中插入排序又包括直接插入排序和希爾排序，選擇排序包括直接選擇排序和堆排序，交換排序包括冒泡排序和快速排序。

---

P2：直接插入排序

直接插入排序屬于插入排序，是一種穩定的排序，平均/最差時間復雜度均為 O(n2)，當元素基本有序時最好時間復雜度為 O(n)，空間復雜度為 O(1)。

基本原理：每一趟將一個待排序記錄按其關鍵字的大小插入到已排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。

適用場景：待排序記錄較少或基本有序的情況。

public void insertionSort(int[] nums) {for (int i = 1; i < nums.length; i++) {int insertNum = nums[i];int insertIndex;for (insertIndex = i - 1; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex--) {nums[insertIndex + 1] = nums[insertIndex];}nums[insertIndex + 1] = insertNum;}}

優化：直接插入沒有利用到要插入的序列已有序的特點，插入第 i 個元素時可以通過二分查找找到插入位置 insertIndex，再把 i~insertIndex 之間的所有元素后移一位，把第 i 個元素放在插入位置上。

public void binaryInsertionSort(int[] nums) {for (int i = 1; i < nums.length; i++) {int insertNum = nums[i];int insertIndex = -1;int start = 0;int end = i - 1;while (start <= end) {int mid = start + (end - start) / 2;if (insertNum > nums[mid])start = mid + 1;else if (insertNum < nums[mid])end = mid - 1;else {insertIndex = mid + 1;break;}}if (insertIndex == -1)insertIndex = start;if (i - insertIndex >= 0)System.arraycopy(nums, insertIndex, nums, insertIndex + 1, i - insertIndex);nums[insertIndex] = insertNum;}}

---

P3：希爾排序

希爾排序屬于插入排序，又稱縮小增量排序，是對直接插入排序的一種改進，并且是一種不穩定的排序，平均時間復雜度為O(n^1.3)，最差時間復雜度為 O(n2)，最好時間復雜度為 O(n)，空間復雜度為 O(1)。

基本原理：把記錄按下標的一定增量分組，對每組進行直接插入排序，每次排序后減小增量，當增量減至 1 時排序完畢。

適用場景：中等規模的數據量，對規模很大的數據量不是最佳選擇。

public void shellSort(int[] nums) {for (int d = nums.length / 2; d > 0 ; d /= 2) {for (int i = d; i < nums.length; i++) {int insertNum = nums[i];int insertIndex;for (insertIndex = i - d; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex -= d) {nums[insertIndex + d] = nums[insertIndex];}nums[insertIndex + d] = insertNum;}}}

---

P4：直接選擇排序

直接選擇排序屬于選擇排序，是一種不穩定的排序，任何情況下時間復雜度都是 O(n2)，空間復雜度為 O(1)。

基本原理：每次在未排序序列中找到最小元素，和未排序序列的第一個元素交換位置，再在剩余未排序序列中重復該操作直到所有元素排序完畢。

適用場景：數據量較小的情況，比直接插入排序稍快。

public void selectSort(int[] nums) {int minIndex;for (int index = 0; index < nums.length - 1; index++){minIndex = index;for (int i = index + 1;i < nums.length; i++){if(nums[i] < nums[minIndex]) minIndex = i;}if (index != minIndex){swap(nums, index, minIndex);}}}

---

P5：堆排序

堆排序屬于選擇排序，是對直接選擇排序的改進，并且是一種不穩定的排序，任何情況時間復雜度都為 O(nlogn)，空間復雜度為 O(1)。

基本原理：將待排序記錄看作完全二叉樹，可以建立大根堆或小根堆，大根堆中每個節點的值都不小于它的子節點值，小根堆中每個節點的值都不大于它的子節點值。

以大根堆為例，在建堆時首先將最后一個節點作為當前節點，如果當前節點存在父節點且值大于父節點，就將當前節點和父節點交換。在移除時首先暫存根節點的值，然后用最后一個節點代替根節點并作為當前節點，如果當前節點存在子節點且值小于子節點，就將其與值較大的子節點進行交換，調整完堆后返回暫存的值。

適用場景：數據量較大的情況。

public void add(int[] nums, int i, int num){nums[i] = num;int curIndex = i;while (curIndex > 0) {int parentIndex = (curIndex - 1) / 2;if (nums[parentIndex] < nums[curIndex]) swap(nums, parentIndex, curIndex);else break;curIndex = parentIndex;}}public int remove(int[] nums, int size){int result = nums[0];nums[0] = nums[size - 1];int curIndex = 0;while (true) {int leftIndex = curIndex * 2 + 1;int rightIndex = curIndex * 2 + 2;if (leftIndex >= size) break;int maxIndex = leftIndex;if (rightIndex < size && nums[maxIndex] < nums[rightIndex])maxIndex = rightIndex;if (nums[curIndex] < nums[maxIndex])swap(nums, curIndex, maxIndex);else break;curIndex = maxIndex;}return result;}

---

P6：冒泡排序

冒泡排序屬于交換排序，是一種穩定的排序，平均/最壞時間復雜度均為 O(n2)，當元素基本有序時最好時間復雜度為O(n)，空間復雜度為 O(1)。

基本原理：是比較相鄰的元素，如果第一個比第二個大就進行交換，對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對，每一輪排序后末尾元素都是有序的，針對 n 個元素重復以上步驟 n -1 次排序完畢。

public void bubbleSort(int[] nums) {for (int i = 0; i < nums.length - 1; i++) {for (int index = 0; index < nums.length - 1 - i; index++) {if (nums[index] > nums[index + 1]) swap(nums, index, index + 1)}}}

優化：當序列已經有序時仍會進行不必要的比較，可以設置一個標志記錄是否有元素交換，如果沒有直接結束比較。

public void betterBubbleSort(int[] nums) {boolean swap;for (int i = 0; i < nums.length - 1; i++) {swap = true;for (int index = 0; index < nums.length - 1 - i; index++) {if (nums[index] > nums[index + 1]) {swap(nums, index ,index + 1);swap = false;}}if (swap) break;}}

---

P7：快速排序

快速排序屬于交換排序，是對冒泡排序的一種改進，并且是一種不穩定的排序，平均/最好時間復雜度均為 O(nlogn)，當元素基本有序時最壞時間復雜度為O(n2)，空間復雜度為 O(logn)。

基本原理：首先選擇一個基準元素，通過一趟排序將要排序的數據分割成獨立的兩部分，一部分全部小于等于基準元素，一部分全部大于等于基準元素，再按此方法遞歸對這兩部分數據進行快速排序。

快速排序的一次劃分從兩頭交替搜索，直到 low 和 high 指針重合，因此一趟時間復雜度是 O(n)，而整個算法的時間復雜度與劃分趟數有關。最好情況是每次劃分選擇的中間數恰好將當前序列等分，經過 log(n) 趟劃分便可得到長度為 1 的子表，這樣算法的時間復雜度為O(nlogn)。最壞情況是每次所選中間數是當前序列中的最大或最小元素，這使每次劃分所得子表其中一個為空表，另一個子表的長度為原表的長度 - 1。這樣長度為 n 的數據表的需要經過 n 趟劃分，整個排序算法的時間復雜度為O(n2)。

適用場景：數據量較大且元素基本無序的情況。

public void quickSort(int[] nums, int start, int end) {if (start < end) {int pivotIndex = getPivotIndex(nums, start, end);quickSort(nums, start, pivotIndex - 1);quickSort(nums, pivotIndex + 1, end);}}public int getPivotIndex(int[] nums, int start, int end) {int pivot = nums[start];int low = start;int high = end;while (low < high) {while (low <= high && nums[low] <= pivot) low++;while (low <= high && nums[high] > pivot) high--;if (low < high) swap(nums, low, high);}swap(nums, start, high);return high;}

優化：當規模足夠小時，例如 end - start < 10 時，采用直接插入排序。

---

P8：歸并排序

歸并排序基于歸并操作，是一種穩定的排序算法，任何情況時間復雜度都為 O(nlogn)，空間復雜度為 O(n)。

基本原理：應用分治法將待排序序列分成兩部分，然后對兩部分分別遞歸排序，最后進行合并，使用一個輔助空間并設定兩個指針分別指向兩個有序序列的起始元素，將指針對應的較小元素添加到輔助空間，重復該步驟到某一序列到達末尾，然后將另一序列剩余元素合并到輔助空間末尾。

適用場景：數據量大且對穩定性有要求的情況。

int[] help;public void mergeSort(int[] arr) {int[] help = new int[arr.length];sort(arr, 0, arr.length - 1);}public void sort(int[] arr, int start, int end) {if (start == end) return;int mid = start + (end - start) / 2;sort(arr, start, mid);sort(arr, mid + 1, end);merge(arr, start, mid, end);}public void merge(int[] arr, int start, int mid, int end) {if (end + 1 - start >= 0) System.arraycopy(arr, start, help, start, end + 1 - start);int p = start;int q = mid + 1;int index = start;while (p <= mid && q <= end) {if (help[p] < help[q]) arr[index++] = help[p++];else arr[index++] = help[q++];}while (p <= mid) arr[index++] = help[p++];while (q <= end) arr[index++] = help[q++];}

---

P9：排序算法的選擇原則

當數據量規模較小時，考慮直接插入排序或直接選擇排序，當元素分布有序時直接插入排序將大大減少比較次數和移動記錄的次數，如果不要求穩定性，可以使用直接選擇排序，效率略高于直接插入排序。

當數據量規模中等時，選擇希爾排序。

當數據量規模較大時考慮堆排序、快速排序和歸并排序。如果對穩定性有要求可以采用歸并排序，如果元素分布隨機可以采用快速排序，如果元素分布接近正序或逆序可以采用堆排序。

一般不使用冒泡排序。

---

設計模式 12

P1：原則

開閉原則：面向對象設計中最基礎的設計原則，指一個軟件實體（類、模塊、方法等）應該對擴展開放，對修改關閉。它強調用抽象構建框架，用實現擴展細節，提高代碼的可復用性和可維護性。例如在版本更新時盡量不修改源代碼，但可以增加新功能。

單一職責原則：一個類、接口或方法只負責一個職責，提高代碼可讀性和可維護性，降低代碼復雜度以及變更引起的風險。

依賴倒置原則：程序應該依賴于抽象類或接口，而不是具體的實現類。可以降低代碼的耦合度，提高系統的穩定性。

接口隔離原則：將不同功能定義在不同接口中實現接口隔離，避免了類依賴它不需要的接口，減少了接口之間依賴的冗余性和復雜性。

里氏替換原則：對開閉原則的補充，規定了任何父類可以出現的地方子類都一定可以出現，可以約束繼承泛濫，加強程序健壯性。

迪米特原則：也叫最少知道原則，每個模塊對其他模塊都要盡可能少地了解和依賴，降低代碼耦合度。

合成/聚合原則：盡量使用組合(has-a)/聚合(contains-a)而不是繼承(is-a)達到軟件復用的目的，避免濫用繼承帶來的方法污染和方法爆炸，方法污染指父類的行為通過繼承傳遞給子類，但子類并不具備執行此行為的能力；方法爆炸指繼承樹不斷擴大，底層類擁有的方法過于繁雜，導致很容易選擇錯誤。

---

P2：分類

創建型模式：提供了一種在創建對象的同時隱藏創建邏輯的方式，而不是使用 new 運算符直接實例化對象，使程序在判斷需要創建哪些對象時更加靈活。包括工廠模式、抽象工廠模式、單例模式、建造者模式、原型模式。

結構型模式：通過類和接口之間的繼承和引用實現創建復雜結構的對象。包括適配器模式、橋接模式、過濾器模式、組合模式、裝飾器模式、外觀模式、享元模式、代理模式。

行為型模式：通過類之間不同的通信方式實現不同的行為。包括責任鏈模式、命名模式、解釋器模式、迭代器模式、中介者模式、備忘錄模式、觀察者模式、狀態模式、策略模式、模板模式、訪問者模式。

---

###P3：簡單工廠模式

工廠模式屬于創建型模式，分為簡單工廠模式，工廠方法模式和抽象工廠模式。

簡單工廠模式指由一個工廠對象來創建實例，客戶端不需要關注創建的邏輯，只需要提供傳入工廠對象的參數。適用于工廠類負責創建對象較少的情況，缺點是如果要增加新產品，就需要修改工廠類的判斷邏輯，違背開閉原則，且產品多的話會使工廠類比較復雜。

應用舉例

Calendar 抽象類的 getInstance 方法，該方法調用了 createCalendar 方法，根據不同的地區參數創建不同的日歷對象。

Spring 中的 BeanFactory 使用簡單工廠模式，根據傳入一個唯一的標識來獲得 Bean 對象。

舉例

一個工廠和一種抽象產品。例如一個麥當勞店可以生產漢堡。

public class MacDonaldFactory {public Hamburger eatHamburger(String name) {if ("beef".equals(name))return new BeefHamburger();else if ("pig".equals(name))return new PigHamburger();return null;}}interface Hamburger {void eat();}class BeefHamburger implements Hamburger {@Overridepublic void eat() {System.out.println("吃牛肉漢堡");}}class PigHamburger implements Hamburger {@Overridepublic void eat() {System.out.println("吃豬肉漢堡");}}

---

P4：工廠方法模式

工廠方法模式指定義一個創建對象的接口，讓接口的實現類來決定創建哪一種對象，讓類的實例化推遲到子類中進行。客戶端只需關心對應的工廠而無需關心創建細節，主要解決了產品擴展的問題，在簡單工廠模式中如果產品種類變多，工廠的職責會越來越多，不便于維護。

應用舉例

Collection 接口這個抽象工廠中定義了一個抽象的 iterator 工廠方法，返回一個 Iterator 類的抽象產品。該方法通過 ArrayList 、HashMap 等具體工廠實現，返回 Itr、KeyIterator 等具體產品。

Spring 的 FactoryBean 接口的 getObject 方法也是一個工廠方法。

舉例

多個工廠和一種抽象產品。例如一個麥當勞店可以生產漢堡，一個肯德基店也可以生產漢堡。

public interface HamburgerFactory {Hamburger build();}class MCFactory implements HamburgerFactory {@Overridepublic Hamburger build() {return new MCHamburger();}}class KFCFactory implements HamburgerFactory {@Overridepublic Hamburger build() {return new KFCHamburger();}}interface Hamburger {void eat();}class MCHamburger implements Hamburger {@Overridepublic void eat() {System.out.println("吃麥當勞漢堡");}}class KFCHamburger implements Hamburger {@Overridepublic void eat() {System.out.println("吃肯德基漢堡");}}

---

P5：抽象工廠模式

抽象工廠模式指提供一個創建一系列相關或相互依賴對象的接口，無需指定它們的具體類。客戶端不依賴于產品類實例如何被創建和實現的細節，主要用于系統的產品有多于一個的產品族，而系統只消費其中某一個產品族產品的情況。抽象工廠模式的缺點是不方便擴展產品族，并且增加了系統的抽象性和理解難度。

應用舉例

java.sql.Connection 接口就是一個抽象工廠，其中包括很多抽象產品如 Statement、Blob、Savepoint 等。

舉例

多個工廠和多種抽象產品。例如一個麥當勞店和一個肯德基店都可以生產漢堡和可樂。

public interface FoodFactory {Hamburger buildHamburger();Drink buildDrink();}class MCFactory implements FoodFactory {@Overridepublic Hamburger buildHamburger() {return new MCHamburger();}@Overridepublic Drink buildDrink() {return new MCDrink();}}class KFCFactory implements FoodFactory {@Overridepublic Hamburger buildHamburger() {return new KFCHamburger();}@Overridepublic Drink buildDrink() {return new KFCDrink();}}interface Hamburger {void eat();}class MCHamburger implements Hamburger {@Overridepublic void eat() {System.out.println("吃麥當勞漢堡");}}class KFCHamburger implements Hamburger {@Overridepublic void eat() {System.out.println("吃肯德基漢堡");}}interface Drink {void drink();}class MCDrink implements Drink {@Overridepublic void drink() {System.out.println("喝麥當勞飲料");}}class KFCDrink implements Drink {@Overridepublic void drink() {System.out.println("喝肯德基飲料");}}

---

P6：單例模式

單例模式屬于創建型模式，指一個單例類在任何情況下都只存在一個實例，構造方法必須是私有的、由自己創建一個靜態實例對象存儲該實例，并對外提供一個靜態公有方法獲取實例。優點是內存中只有一個實例，減少了開銷，尤其是頻繁創建和銷毀實例的情況下，并且可以避免對資源的多重占用。缺點是沒有抽象層，難以擴展，與單一職責原則沖突。

應用舉例

Spring 的 ApplicationContext 創建的 Bean 實例都是單例對象，還有 ServletContext、數據庫連接池等也都是單例模式。

餓漢式：在類加載時就初始化創建單例對象，線程安全，但不管是否使用都創建對象可能會浪費內存。

public class HungrySingleton {private HungrySingleton(){}private static HungrySingleton instance = new HungrySingleton();public static HungrySingleton getInstance() {return instance;}}

懶漢式：在外部調用時才會加載，線程不安全，可以加鎖保證線程安全但效率低。

public class LazySingleton {private LazySingleton(){}private static LazySingleton instance;public static LazySingleton getInstance() {if(instance == null) {instance = new LazySingleton();}return instance;}}

雙重檢查鎖：使用 volatile 以及多重檢查來減小鎖范圍，提升效率。

public class DoubleCheckSingleton {private DoubleCheckSingleton(){}private volatile static DoubleCheckSingleton instance;public static DoubleCheckSingleton getInstance() {if(instance == null) {synchronized (DoubleCheckSingleton.class) {if (instance == null) {instance = new DoubleCheckSingleton();}}}return instance;}}

靜態內部類：同時解決餓漢式的內存浪費問題和懶漢式的線程安全問題。

public class StaticSingleton {private StaticSingleton(){}public static StaticSingleton getInstance() {return StaticClass.instance;}private static class StaticClass {private static final StaticSingleton instance = new StaticSingleton();}}

枚舉：Effective Java 作者提倡的方式，不僅能避免線程安全問題，還能防止反序列化重新創建新的對象，絕對防止多次實例化，也能防止反射破解單例的問題。

public enum EnumSingleton {INSTANCE;}

---

P7：代理模式

代理模式屬于結構型模式，為其他對象提供一種代理以控制對這個對象的訪問。優點是可以增強目標對象的功能，降低代碼耦合度，擴展性好。缺點是在客戶端和目標對象之間增加代理對象會導致請求處理速度變慢，增加系統復雜度。

應用舉例

Spring 利用動態代理實現 AOP，如果 Bean 實現了接口就使用 JDK 代理，否則使用 CGLib 代理。

靜態代理：代理對象持有被代理對象的引用，調用代理對象方法時也會調用被代理對象的方法，但是會在被代理對象方法的前后增加其他邏輯。需要手動完成，在程序運行前就已經存在代理類的字節碼文件，代理類和被代理類的關系在運行前就已經確定了。 缺點是一個代理類只能為一個目標服務，如果要服務多種類型會增加工作量。

public interface Company {void findWorker();}public class Hr implements Company {@Overridepublic void findWorker() {System.out.println("需要找招聘一個員工");}}public class Proxy implements Company {private Hr hr;public Proxy(){this.hr = new Hr();}@Overridepublic void findWorker() {hr.findWorker();System.out.println("找到了員工");}}

動態代理：動態代理在程序運行時通過反射創建具體的代理類，代理類和被代理類的關系在運行前是不確定的。動態代理的適用性更強，主要分為 JDK 動態代理和 CGLib 動態代理。

• JDK 動態代理：通過 Proxy 類的 newInstance 方法獲取一個動態代理對象，需要傳入三個參數，被代理對象的類加載器、被代理對象實現的接口，以及一個 InvocationHandler 調用處理器來指明具體的邏輯，相比靜態代理的優勢是接口中聲明的所有方法都被轉移到 InvocationHandler 的 invoke 方法集中處理。 public static void main(String[] args) {Hr hr = new Hr();Company proxyHr = (Company) Proxy.newProxyInstance(hr.getClass().getClassLoader(), hr.getClass().getInterfaces(), (proxy, method, args1) -> {System.out.println("接收代理請求");Object obj = method.invoke(hr, args1);System.out.println("找到了員工，完成請求");return obj;});proxyHr.findWorker();}```
• CGLib 動態代理：JDK 動態代理要求實現被代理對象的接口，而 CGLib 要求繼承被代理對象，如果一個類是 final 類則不能使用 CGLib 代理。兩種代理都在運行期生成字節碼，JDK 動態代理直接寫字節碼，而 CGLib 動態代理使用 ASM 框架寫字節碼，ASM 的目的是生成、轉換和分析以字節數組表示的已編譯 Java 類。 JDK 動態代理調用代理方法通過反射機制實現，而 GCLib 動態代理通過 FastClass 機制直接調用方法，它為代理類和被代理類各生成一個類，該類為代理類和被代理類的方法分配一個 int 參數，調用方法時可以直接定位，因此調用效率更高。

---

P8：裝飾器模式

裝飾器模式屬于結構型模式，在不改變原有對象的基礎上將功能附加到對象，相比繼承可以更加靈活地擴展原有對象的功能。這種模式創建了一個裝飾類用來包裝原有的類，并在保持類方法簽名完整性的前提下提供了額外的功能。裝飾器模式適合的場景：在不想增加很多子類的前提下擴展一個類的功能。

應用舉例

java.io 包中，InputStream 字節輸入流通過裝飾器 BufferedInputStream 增強為緩沖字節輸入流。

和代理模式的區別：裝飾器模式的關注點在于給對象動態添加方法，而動態代理更注重對象的訪問控制。動態代理通常會在代理類中創建被代理對象的實例，而裝飾器模式會將裝飾者作為構造方法的參數。

---

P9：適配器模式

適配器模式屬于結構型模式，它作為兩個不兼容接口之間的橋梁，結合了兩個獨立接口的功能，將一個類的接口轉換成另外一個接口，這種模式涉及到一個單一的類，該類負責加入獨立或不兼容的接口功能。優點是使得原本由于接口不兼容而不能一起工作的類可以一起工作。 缺點是過多使用適配器會讓系統非常混亂，不易整體把握。

應用舉例

• java.io 包中，InputStream 字節輸入流通過適配器 InputStreamReader 轉換為 Reader 字符輸入流。
• Spring MVC 中的 HandlerAdapter，由于 handler 有很多種形式，包括 Controller、HttpRequestHandler、Servlet 等，但調用方式又是確定的，因此需要適配器來進行處理，根據適配規則調用 handle 方法。
• Arrays.asList 方法，將數組轉換為對應的集合（注意不能使用修改集合的方法，因為返回的 ArrayList 是 Arrays 的一個內部類）。

和裝飾器模式的區別：適配器模式沒有層級關系，適配器和被適配者沒有必然連續，滿足 has-a 的關系，主要用于解決不兼容的問題，注重兼容和轉換，是一種后置考慮。裝飾器模式具有層級關系，裝飾器與被裝飾者實現同一個接口，滿足 is-a 的關系，注重覆蓋和擴展，是一種前置考慮。

和代理模式的區別：適配器模式主要改變所考慮對象的接口，而代理模式不能改變所代理類的接口。

---

P10：策略模式

策略模式屬于行為型模式，定義了一系列算法并把它們封裝起來，讓它們之間可以互相替換。策略模式的應用場景主要包括：① 在一個系統里面有許多類，它們之間的區別僅在于它們的行為，使用策略模式可以動態地讓一個對象在許多行為中選擇一種行為。 ② 一個系統需要動態地在幾種算法中選擇一種。策略模式主要解決在有多種算法相似的情況下，使用 if/else 所帶來的復雜和難以維護。策略模式的優點是算法可以自由切換，可以避免使用多重條件判斷并且擴展性良好，缺點是策略類會增多并且所有策略類都需要對外暴露。

應用舉例

• 比較器 Comparator：在集合框架中，經常需要通過構造方法傳入一個比較器 Comparator 進行比較排序。Comparator 就是一個抽象策略，一個類通過實現該接口并重寫 compare 方法成為具體策略類。
• ThreadPoolExecutor 中的四種拒絕策略：在創建線程池時，需要傳入拒絕策略，當創建新線程使當前運行的線程數超過maximumPoolSize 時會使用相應的拒絕策略進行處理。

---

P11：模板模式

模板模式屬于行為型模式，指定義一個算法的骨架，并允許子類為一個或多個步驟提供實現。模板模式使子類可以在不改變算法結構的情況下重新定義算法的某些步驟，適用于抽取子類的重復代碼到一個公共父類中。優點是可以封裝固定不變的部分，擴展可變的部分。缺點是每一個不同實現都需要一個子類維護，會增加類的數量。為防止惡意操作，一般模板方法都以 final 修飾。

應用舉例

每一個 Servlet 都必須實現 Servlet 接口，GenericServlet 是實現了該接口的通用抽象類，而 HttpServlet 繼承了 GenericServlet，提供了處理 HTTP 協議的通用實現，所以一般定義 Servlet 只需要繼承 HttpServlet 即可。

HttpServlet 定義了一套處理 HTTP 請求的模板，service 方法為模板方法，定義了處理HTTP請求的基本流程，doXXX 等方法為基本方法，根據請求方法的類型做相應的處理，子類可重寫這些方法。

---

P12：觀察者模式

觀察者模式屬于行為型模式，也叫發布訂閱模式，定義對象間的一種一對多的依賴關系，當一個對象的狀態發生改變時，所有依賴于它的對象都得到通知并被自動更新。主要解決一個對象狀態改變給其他對象通知的問題，缺點是如果一個被觀察者對象有很多的直接和間接觀察者的話，通知很耗時， 并且如果存在循環依賴的話可能導致系統崩潰，另外觀察者無法知道目標對象具體是怎么發生變化的。

應用舉例

ServletContextListener 能夠監聽 ServletContext 對象的生命周期，實際上就是監聽 Web 應用。在 ServletContextListener 中定義了處理對應事件的兩個方法，當 Servlet 容器啟動 Web 應用時調用 contextInitialized 方法，終止 Web 應用時調用 contextDestroyed 方法。

---

Java 基礎 22

P1：基本概念

優點

① 具有平臺無關性，擺脫了硬件平臺的束縛，實現了"一次編寫，到處運行"。

② 提供了一種相對安全的內存管理和訪問機制，避免了大部分內存泄漏和指針越界問題。

③ 實現了熱點代碼檢測和運行時編譯及優化，使得程序隨運行時間增長可以獲得更高的性能。

④ 有一套完善的應用程序接口，還支持很多第三方類庫。

Java 平臺無關性原理

主要通過 JVM 和語言規范實現。

• 編譯器生成一個體系結構中立的目標文件格式，這是一種編譯后的代碼，只要有 Java 運行時系統，這些編譯后的代碼就可以在很多處理器上運行。Java 編譯器通過生成與特定計算機體系結構無關的字節碼指令來實現這一特性，字節碼文件不僅可以很容易地在任何機器上解釋執行，還可以動態地轉換成本地機器代碼，轉換是由 JVM 實現的，JVM 是平臺相關的，屏蔽了不同操作系統的差異。
• Java 中基本數據類型的大小以及有關運算的行為都有明確的說明，例如 int 類型永遠為 32 位整數，而在 C/C++ 中可能是 16 位整數、32 位整數，也可能是編譯器開發商指定的其他任何大小。在 Java 中數值類型有固定的字節數，二進制數據以固定的格式進行存儲和傳輸，字符串則采用標準的 Unicode 格式存儲。

JDK 和 JRE 的區別

JDK：Java Development Kit，Java 開發工具包。它提供了編譯、運行 Java 程序所需的各種工具和資源，包括 Java 編譯器、JRE 以及常用的基礎類庫等，是 JAVA 的核心。

JRE：Java Runtime Environment，Java 運行時環境，是運行基于 Java 語言編寫的程序所不可缺少的運行環境，包括 JVM、核心類庫、核心配置工具等。

---

P2：數據類型

基本數據類型

JVM 并沒有針對 boolean 數據類型進行賦值的專用字節碼指令，boolean f = false 就是使用 ICONST_0，即常數 0 來進行賦值。單個boolean 變量用 int 代替，而 boolean 數組會編碼成 byte 數組。

每個基本數據類型都對應一個自己的包裝類，除了 int 和 char 對應 Integer 和 Character 之外，其余基本數據類型的包裝類都是首字母大寫即可。自動裝箱指的是將基本數據類型包裝為一個包裝類對象，例如向一個泛型為 Integer 類型的集合添加 int 類型的元素。自動拆箱指的是將一個包裝類對象轉換為一個基本數據類型，例如將一個包裝類對象賦值給一個基本數據類型的變量。要比較兩個包裝類的數值需要使用 equals 方法，而不能使用 == 比較運算符。

所有的 POJO 類屬性必須使用包裝數據類型，RPC 方法的返回值和參數必須使用包裝數據類型，所有局部變量推薦使用基本數據類型。

引用數據類型

引用數據類型分為引用變量本身和引用指向的對象，引用變量稱為 refvar，引用指向的實際對象稱為 refobj。

refvar 是基本的數據類型，它的默認值是 null，存儲 refobj 的首地址，可以直接使用雙等號 == 進行等值判斷。作為一個引用變量，不管它指向包裝類、集合類、字符串還是自定義類，均占 4B 空間。無論 refobj 是多么小的對象，最小的占用空間是 12B（用于存儲基本信息，稱為對象頭），但由于存儲空間分配必須是 8B 的倍數，所以初始分配空間至少是 16B。

一個 refvar 至多存儲一個 refobj 的首地址，一個 refobj 可以被多個 refvar 存儲下它的首地址，即一個堆內對象可以被多個 refvar 引用指向。如果 refobj 沒有被任何 refvar 指向，那么遲早會被垃圾回收。

---

P3：String

String 是 final 修飾的不可變只讀字符串類，存儲數據的 value 字符數組也是 final 修飾的不可變數組。String 對象是不可變對象，對它的任何修改實際上都是創建一個新對象，再把引用指向該對象。String 對象賦值操作后，會在常量池中進行緩沖，如果下次申請創建對象時，緩存中已經存在就直接返回相應引用給創建者。

直接使用 + 進行字符串拼接，如果是字面量會自動拼接為一個新的常量，但如果在循環體內拼接效率就很低。要提升拼接效率可以使用 StringBuilder 或 StringBuffer 可變字符串，可以直接在原對象上進行修改，區別是 StringBuffer 使用了 synchronized 保證線程安全性，但一般字符串拼接都是單線程操作，所以使用 StringBuilder 較多。常量和常量的拼接，結果也在常量池中，且不存在兩個相同的常量。只要參與拼接的字符串里有變量，結果就在堆中。

如果是通過字符串常量賦值的形式，例如 String s = “s”，字符串常量內容存于常量池，變量存于棧中并直接引用常量池中的字符串。如果是通過new 的形式，例如 String s = new String(“s”)，會先在堆中創建實例對象，然后再去常量池尋找需要的字符串常量，如果找到了則直接使用，沒找到則開辟新的空間并存儲內容，最后棧中變量引用堆中對象，對象再引用常量池中的字符串。

---

P4：值調用和引用調用

按值調用指的是方法接收的是調用者提供的值，而按引用調用指的是方法接收的是調用者提供的變量地址。Java 總是采用按值調用，也就是說方法得到的是所有參數值的一個副本，當傳遞對象時實際上方法接收的是這個對象引用的副本。方法不能修改基本數據類型的參數，可以改變對象參數的狀態，但不能讓對象參數引用一個新的對象。

舉例來說，如果傳遞了一個 int 類型的值 ，改變該值不會影響實參，因為改變的是該值的一個副本。如果傳遞了一個 int[] 類型的數組，改變數組的內容會影響實參，而如果改變這個參數的引用，并不會讓實參引用新的數組對象。

---

P5：面向對象

概念

面向過程讓計算機有步驟地順序做一件事，是一種過程化思維，在使用面向過程語言開發大型項目時，軟件復用和維護存在很大問題，模塊之間耦合嚴重。面向對象相對于面向過程而言更適合解決規模較大的問題，可以拆解問題復雜度，對現實事物進行抽象并映射為開發對象，更接近人的思維。

例如開門這個動作，面向過程是"open(Door door)"，是一種動賓結構，“door"是被作為操作對象的參數傳入方法的，方法內定義開門的具體步驟實現。而使用面向對象的方式，首先會定義一個類"Door”，然后抽象出門的屬性（如尺寸、顏色）和行為（如 open 和 close），屬于主謂結構。面向過程的代碼結構松散，強調如何流程化地解決問題。面向對象的代碼強調高內聚、低耦合，先抽象模型，定義共性行為，再解決實際問題。

封裝

封裝是一種對象功能內聚的表現形式，在抽象基礎上決定信息是否公開，以及公開等級，核心問題是以什么樣的方式暴漏哪些信息。封裝的主要任務是對屬性、數據、部分內部敏感行為實現隱藏，對熟悉的訪問和修改必須通過公共接口來實現，某些敏感方法或外部不需要感知的復雜邏輯一般也會進行封裝。封裝使對象之間的關系變得簡單，降低了代碼耦合度，有利維護。

設計模式原則的迪米特原則就是對封裝的具體要求，即 A 模塊使用 B 模塊的某個接口行為，對 B 模塊中除此行為之外的其他信息知道的應該盡可能少。之所以不直接對 public 的屬性進行讀取和修改，而是使用對應的 getter/setter 方法，是因為假設想在修改屬性時進行權限控制、日志記錄等操作，在直接訪問屬性的情況下是無法做到的。如果將公開的屬性和行為修改為 private 則依賴模塊都會報錯，因此在不知道使用哪種訪問控制權限時應當優先使用 private。

繼承

可以通過繼承來擴展一個類，子類可以繼承父類的部分屬性和行為，使模塊具有復用性。繼承是一種"is-a"的關系，可以使用里氏替換原則判斷是否滿足"is-a"關系，即任何父類出現的地方子類都可以出現。如果父類引用直接使用子類引用來代替，可以正確編譯并執行，輸出結果符合子類場景的預期，那么說明兩個類符合里氏替換原則，可以使用繼承關系。

多態

多態是以封裝和繼承為基礎，根據運行時的實際對象類型，同一個方法產生不同的運行結果，使同一個行為具有不同的表現形式。多態是指在編譯層面無法確定最終調用的方法體，以重寫為基礎來實現面向對象特性，在運行期由 JVM 進行動態綁定，調用合適的重寫方法體來執行。由于重載是編譯期確定方法調用，屬于靜態綁定，本質上重載的結果是完全不同的方法，因此一般多態專指重寫。

• 重載
  重載是指方法名稱相同，但是參數類型或參數個數不相同，是水平方向上行為的不同實現。對于編譯器來說，方法名稱和參數列表組成了一個唯一鍵，稱為方法簽名，JVM 通過這個唯一鍵決定調用哪種重載的方法。
  JVM 在重載方法中，選擇合適的目標方法的順序：① 精確匹配。② 如果是基本數據類型，自動轉換成更大表示范圍的基本類型。③ 通過自動拆箱與裝箱。④ 通過子類向上轉型繼承路線依次匹配。⑤ 通過可變參數匹配。
  不管繼承關系如何復雜，重載在編譯時可以根據規則知道調用哪種目標方法，因此重載屬于靜態綁定。

• 重寫
  重寫是指子類實現接口或者繼承父類時，保持方法簽名完全相同，實現不同的方法體，是垂直方向上行為的不同實現。
  元空間有一個方法表保存著每個可以實例化類的方法信息，JVM 可以通過方法表快速激活實例方法。如果某個類重寫了父類的某個方法，則方法表中的方法指向引用會指向子類的實現處。需要注意父類引用執行子類方法時無法調用子類存在而父類不存在的方法。
  重寫的子類方法訪問權限不能變小，返回類型和拋出的異常類型不能變大，且必須加 @Override 注解。

---

P6：訪問權限控制符

---

P7：Object 類

Object 的類是所有類的父類，Object 類的方法：

• equals：用于檢測一個對象是否等于另一個對象，默認使用 == 比較兩個對象的引用，可以重寫 equals 方法自定義比較規則。equals 方法需要滿足以下規范：自反性、對稱性、傳遞性、一致性并對于任何非空引用 x，x.equals(null) 返回 false。
• hashCode：散列碼是由對象導出的一個整型值，是沒有規律的，每個對象都有一個默認的散列碼，值由對象的存儲地址得出。字符串可能有相同的散列碼，因為字符串的散列碼是由內容導出的。為了在集合中正確使用對象，一般需要同時重寫 equals 和 hashCode 方法，要求是 equals 相同是 hashCode 必須相同，但 hashCode 相同時 equals 未必相同，因此 hashCode 是兩個對象相同的必要不充分條件。
• toString：打印對象時默認會調用它的 toString 方法，如果沒有重寫該方法默認打印的是表示對象值的一個字符串，一般需要重寫該方法。打印數組時可以使用 Arrays.toString() 方法。
• clone：clone 方法聲明為 protected，類只能通過該方法克隆它自己的對象，如果希望其他類也能調用該方法必須定義該方法為 public。如果一個對象的類沒有實現 Cloneable 接口，該對象調用 clone 方法會拋出一個 CloneNotSupport 異常。默認的 clone 方法是淺拷貝，一般重寫 clone 方法需要實現 Cloneable 接口并指定訪問修飾符為 public。
  • 淺拷貝：只復制當前對象的基本數據類型以及相應的引用變量，但沒有復制引用變量指向的實際對象。對克隆對象的修改可能會影響原對象，是不安全的。
  • 深拷貝：會完全拷貝基本數據類型和引用數據類型，深拷貝是安全的。
• finalize：要確定一個對象死亡至少要經過兩次標記，如果對象在進行可達性分析后發現沒有與 GC Roots 連接的引用鏈，會被第一次標記，隨后進行一次篩選，篩選條件是此對象是否有必要執行 finalize 方法。假如對象沒有重寫 finalize 方法或者該方法已經被虛擬機調用過，這兩種情況視為沒有必要執行。如果判斷為有必要執行，對象就會被放置在一個叫做 F-Queue 的隊列中，由一條虛擬機自動建立的低調度優先級的 Finalizer 線程去執行其 finalize 方法。虛擬機會觸發該方法但不保證它會運行結束，這是為了防止某個對象的 finalize 方法執行緩慢或發生死循環。只要對象在 finalize 方法中重新與引用鏈上的任何一個對象建立關聯就會在第二次標記時被移出即將回收集合。由于運行代價高昂，不確定性大，無法保證各個對象的調用順序，在 JDK 9 已經被標記為過時方法，因此它并不適合釋放資源，釋放資源可以使用 try-finally 代碼塊。
• getClass：返回包含對象信息的類對象。
• wait / notify / notifyAll：阻塞或喚醒持有該對象鎖的線程。

---

P8：內部類

使用內部類主要有兩個原因：內部類可以對同一個包中的其他類隱藏。內部類方法可以訪問定義這個內部類的作用域中的數據，包括原本私有的數據。內部類是一個編譯器現象，與虛擬機無關。編譯器會把內部類轉換成常規的類文件，用美元符號 $ 分隔外部類名與內部類名，其中匿名內部類使用數字進行編號，虛擬機對此一無所知。

靜態內部類：由 static 修飾，屬于外部類本身，只加載一次。靜態內部類的好處是作用域僅在包內，可以通過 外部類.內部類 直接訪問，并且靜態內部類可以訪問外部類中所有靜態屬性和方法。例如 HashMap 中的 Node 節點，ReentrantLock 中繼承自 AQS 的 Sync 類，ArrayList 中的 SubList 都是靜態內部類。內部類中還可以定義內部類，例如 ThreadLoacl 靜態內部類 ThreadLoaclMap 中還定義了一個內部類 Entry。

成員內部類：屬于外部類的每個對象，隨對象一起加載。不可以定義靜態成員和方法，可以訪問外部類的所有內容。

局部內部類：定義在方法或者表達式內部。不能聲明訪問修飾符，只能定義實例成員變量和實例方法，作用范圍僅在聲明這個局部類的代碼塊中。

匿名內部類：沒有名字的局部內部類，可以簡化代碼，匿名內部類會立即創建一個匿名內部類的對象返回，對象類型相當于當前 new 的類的子類類型。匿名內部類一般用于實現事件監聽器和其他回調。

class OuterClass{static class StaticInnerClass {}class NormalInnerClass {}public void test() {class LocalClass {}// 靜態內部類創建對象new OuterClass.StaticInnerClass();// 成員內部類創建對象new OuterClass().new NormalInnerClass();// 局部內部類創建對象new LocalClass();// 匿名內部類創建對象Runnable runnable = () -> {};}}

---

P9：接口和抽象類

定義類的過程就是抽象和封裝的過程，而接口和抽象類則是對實體類進行更高層次的抽象，僅定義公共行為和特征。

抽象類在被繼承時體現的是 is-a 關系，接口在被實現時體現的是 can-do 關系。與接口相比，抽象類通常是對同類事物相對具體的抽象，通常包含抽象方法、實體方法、屬性變量。is-a 關系需要符合里氏替換原則，can-do 關系要符合接口隔離原則，實現類要有能力去實現并執行接口定義的行為。例如 Plane 和 Bird 都具有 fly 方法，應該把 fly 定義為一個接口，而不是作為某個抽象類的方法，再利用 is-a 關系去繼承抽象類，因為除了 fly 這個行為外，Plane 和 Bird 之間很難找到其他共同特征。

抽象類是模板式設計，包含一組具體的特征，例如某品牌特定型號的汽車，底盤、控制電路、剎車系統等是抽象出來的共同特征，但根據不同級別的配置，內飾，顯示屏，座椅材質可以存在不同版本的實現。

接口是契約式設計，是開放的，就像一份合同，定義了方法名、參數、返回值甚至拋出的異常類型，誰都可以實現它，但必須要遵守這個接口的約定。例如所有車輛都必須實現剎車這個強制行為規范。

接口是頂級的類，雖然關鍵詞是 interface，但編譯之后的字節碼擴展名還是 .class，抽象類在接口下面的第二層，對各個接口進行了組合，然后實現部分接口。當糾結定義接口和抽象類時，推薦定義為接口，遵循接口隔離原則，按某個維度劃分成多個接口，然后再利用抽象類去實現這些接口，這樣做有利于后續的擴展和重構。

---

P10：static 關鍵字

static 關鍵字主要有兩個作用：（1）為某特定數據類型或對象分配單一的存儲空間，而與創建對象的個數無關。（2）讓某個屬性或方法與類而不是對象關聯在一起，可以在不創建對象的情況下通過類名來訪問。

作用范圍

static 修飾的變量稱為靜態變量，也叫類變量，可以直接通過類名訪問，靜態變量存儲在 JVM 的方法區中。

static 修飾的方法稱為靜態方法，也叫類方法，可以直接通過類名訪問，靜態方法只能訪問靜態變量或靜態方法，不能訪問實例成員變量和實例方法，也不能使用 this 和 super 關鍵字，通常用于定義工具類方法。

static 修飾的代碼塊稱為靜態代碼塊，只能定義在類下，在類加載時執行且只會執行一次，通常用于初始化屬性和環境配置等。

static 修飾的類稱為靜態內部類，可以訪問外部類的靜態變量和方法。

static 也可以用來導入包下的靜態變量。

類初始化的順序

（1）父類靜態代碼塊和靜態變量

（2）子類靜態代碼塊和靜態變量

（3）父類普通代碼塊和普通變量

（4）父類構造方法

（5）子類普通代碼塊和普通變量

（6）子類構造方法

其中代碼塊和變量的初始化順序按照類中聲明的順序執行。

---

P11：序列化和反序列化

Java 對象在 JVM 運行時被創建，當 JVM 退出時存活對象都會銷毀，如果需要將對象及其狀態持久化，就需要通過序列化來實現，將內存中的對象保存在二進制流中，在需要時再將二進制流反序列化為對象。對象序列化保存的是對象的狀態，因此類中的靜態變量不會被序列化，因為靜態變量是類屬性。除了靜態變量外，transient 修飾的變量也不會被序列化。transient 的作用就是把這字段的生命周期僅限于內存中而不會寫到磁盤里持久化，被 transient 修飾的變量會被設為對應數據類型的默認初始值。

序列化的常用常見是 RPC 框架的數據傳輸，常見的序列化有三種：

• Java 原生序列化
  實現 Serializabale 標記接口，Java 序列化保留了對象類的元數據（如類、成員變量、繼承類信息等），以及對象數據等，兼容性最好，但不支持跨語言，性能一般。序列化和反序列化必須保持序列化 ID 的一致，一般使用 private static final long serialVersionUID 定義序列化 ID，如果不設置編譯器會根據類的內部實現自動生成該值。如果是兼容升級不應該修改序列化 ID，如果是不兼容升級則需要修改。使用 Java 原生序列化不會調用類的無參構造方法，而是調用本地方法將成員變量賦值為對應類型的初始值，基于性能一般不推薦使用。
• Hessian 序列化
  Hessian 序列化是一種支持動態類型、跨語言、基于對象傳輸的網絡協議。Java 對象序列化的二進制流可以被其它語言反序列化。Hessian 協議的特性：① 自描述序列化類型，不依賴外部描述文件或接口定義，用一個字節表示常用基礎類型，極大縮短二進制流。② 語言無關，支持腳本語言。③ 協議簡單，比 Java 原生序列化高效。Hessian 會把復雜對象所有屬性存儲在一個 Map 中進行序列化，當父類和子類存在同名成員變量時會先序列化子類，再序列化父類，因此子類值會被父類覆蓋。
• JSON 序列化
  JSON 是一種輕量級的數據格式，JSON 序列化就是將數據對象轉換為 JSON 字符串，在序列化過程中拋棄了類型信息，所以反序列化時只有提供類型信息才能準確進行。相比前兩種方式可讀性更好，方便調試。

序列化通常會使用網絡傳輸對象，而對象中往往有敏感數據，容易遭受攻擊，Jackson 和 fastjson 等都出現過反序列化漏洞，因此有些對象的敏感屬性不需要進行序列化傳輸時應該加上 transient 關鍵字。如果一定要傳遞敏感屬性可以使用對稱與非對稱加密方式獨立傳輸，再使用某個方法把屬性還原到對象中。

---

P12：反射

在運行狀態中，對于任意一個類，都能夠知道這個類的所有屬性和方法，對于任意一個對象，都能夠調用它的任意一個方法和屬性；這種動態獲取的信息以及動態調用對象的方法的功能稱為Java的反射機制。優點是運行時動態獲取類的全部信息，缺點是破壞了類的封裝性，泛型的約束性。反射是框架的核心靈魂，動態代理設計模式采用了反射機制，還有 Spring、Hibernate 等框架也大量使用到了反射機制。

在程序運行期間，Java 運行時系統始終為所有對象維護一個運行時類型標識，這個信息會跟蹤每個對象所屬的類，虛擬機利用運行時類型信息選擇要執行的正確方法，保存這些信息的類名為 Class。

獲取 Class 實例的方法有三種：① 直接通過 類名.class 。②通過對象的 getClass()方法。③通過 Class.forName(類的全限定名)。Class 類中的 getFields、getMethods 和 getConstructors 方法分別返回這個類支持的公共字段、方法和構造方法的數組，其中包括父類的公共成員。Class 類中的 getDeclaredFields、getDeclaredMethods 和 getDeclaredConstructors方法分別返回這個類聲明的全部字段、方法和構造方法的數組，其中包括私有成員、包成員和受保護成員，但不包括父類的成員。

Field、Method、Constructor 分別用于描述類的字段、方法和構造方法。這三個類都有一個 getName 方法返回字段、方法或構造方法的名稱。Field 類有一個 getType 方法用來返回描述字段類型的一個對象，這個對象的類型也是 Class。Method 和 Constructor 類有報告參數類型的方法，Method 類還有一個報告返回類型的方法。這三個類都有一個 getModifiers 方法，它返回一個整數，用不同的 0/1 位描述所使用的修飾符。

---

P13：注解

注解是一種標記，可以使類或接口附加額外的信息，是幫助編譯器和 JVM 完成一些特定功能的，例如常用注解 @Override 標識一個方法是重寫方法。

元注解就是自定義注解的注解，包括：

• @Target：用來約束注解作用的位置，值是枚舉類 ElementType 的枚舉實例，包括 METHOD 方法、VARIABLE 變量、TYPE 類/接口、PARAMETER 方法參數、CONSTRUCTORS 構造方法和 LOACL_VARIABLE 局部變量等。
• @Rentention：用來約束注解的生命周期，值是 RetentionPolicy 枚舉類實例，包括：SOURCE 源碼、CLASS 字節碼和 RUNTIME 運行時。
• @Documented：表明這個注解應該被 javadoc 工具記錄。
• @Inherited：表面某個被標注的類型是被繼承的。

---

P14：異常

所有的異常都是 Throwable 的子類，分為 Error 和 Exception。Error 描述了 Java 運行時系統的內部錯誤和資源耗盡錯誤，例如 StackOverFlowException 和 OutOfMemoryException，這種異常程序無法處理。Exception 又分為受檢異常和非受檢異常，受檢異常是需要在代碼中顯式處理的異常，否則會編譯出錯，非受檢異常是運行時異常，繼承自 RuntimeException。

受檢異常又可以分為：① 無能為力型，程序無法處理，例如字段超長導致的 SQLException。一般處理的方法是完整保存異常現場，供開發人員解決。② 力所能及型，如發生未授權異常 UnAuthorizedException，程序可跳轉至權限申請頁面。常見的受檢異常還有FileNotFoundException、ClassNotFoundException、IOException等。

非受檢異常又可以分為：① 可預測的異常，例如 IndexOutOfBoundsException、NullPointerException 等，這類異常應該提前做好處理。② 需捕捉異常，例如進行 RPC 調用時產生的遠程服務超時異常，這類異常是客戶端必須顯式處理的。③ 可透出異常，主要指框架或系統產生的且會自行處理的異常，而程序無需關心，例如 Spring 中拋出的 NoSuchRequestHandingMethodException，Spring 會自動完成異常處理，默認將拋出的異常自動映射到合適的狀態碼。

以坐飛機為例，機場地震屬于不可抗力，對應了 Error。飛機延誤屬于受檢異常，應對這種異常無能為力，堵車也屬于受檢異常，應對這種異常可以提前除非或改簽。沒有帶身份證屬于可預測的異常，汽車突然拋錨屬于需捕捉異常，雖然難以預料但必須處理，檢票機器故障屬于可透出異常，由機場處理而無需我們關心。

異常處理

拋出異常：遇到異常不進行具體處理，而是將異常拋出給調用者，由調用者根據情況處理。拋出異常有2種形式，一種是 throws 關鍵字聲明拋出的異常，作用在方法上，一種是使用throw 語句直接拋出異常，作用在方法內。

捕獲異常：使用 try/catch 進行異常的捕獲，try 中發生的異常會被 catch 代碼塊捕獲，根據情況進行處理，如果有 finally 代碼塊無論是否發生異常都會執行，一般用于釋放資源，Java 7 開始可以將資源定義在 try 代碼塊中自動釋放資源。

---

P15：泛型

泛型的本質是參數化類型，解決不確定具體對象類型的問題。泛型在定義處只具備執行 Object 方法的能力。泛型的好處：① 類型安全，放置的是說明取出來就是什么，不存在 ClassCastException 異常。② 提升可讀性，從編碼階段就顯式地知道泛型集合、泛型方法等處理的對象類型是什么。③ 代碼重用，泛型合并了同類型的處理代碼。

類型擦除

虛擬機沒有泛型類型對象，所有對象都屬于普通類。無論何時定義一個泛型類型，都會自動提供一個相應的原始類型，原始類型的名字就是去掉類型參數后的泛型類型名。類型變量會被擦除，如果沒有限定類型就會替換為 Object，如果有限定類型就會替換為第一個限定類型，例如 <T extends A & B> 會使用 A 類型替換 T。

泛型主要用于編譯階段，在編譯后生成的 Java 字節代碼文件中不包含泛型中的類型信息。

泛型規范

泛型限定

對泛型上限的限定使用<? extends T>，它表示該通配符所代表的類型是 T 類的子類型或 T 接口的子接口。

對泛型下限的限定使用<? super T>，它表示該通配符所代表的類型是 T 類的父類型或 T 接口的父接口。

---

P16：Java 8 新特性

lambda 表達式：lambda 表達式允許把函數作為一個方法的參數傳遞到方法中，主要用來簡化匿名內部類的代碼。

函數式接口：使用 @FunctionalInterface 注解標識，有且僅有一個抽象方法，可以被隱式轉換為 lambda 表達式。

方法引用：可以直接引用已有類或對象的方法或構造方法，進一步簡化 lambda 表達式。方法引用有四種形式：引用構造方法、引用類的靜態方法、引用特定類的任意對象方法、引用某個對象的方法。

接口中的方法：接口中可以定義 default 修飾的默認方法，降低了接口升級的復雜性，還可以定義靜態方法。

注解：Java 8 引入了重復注解機制，相同的注解在同一個地方可以聲明多次。注解的作用范圍也進行了擴展，可以作用于局部變量、泛型、方法異常等。

類型推測：加強了類型推測機制，可以使代碼更加簡潔，例如在定義泛型集合時可以省略對象中的泛型參數。

Optional 類：用來處理空指針異常，提高代碼可讀性。

Stream 類：把函數式編程風格引入 Java 語言，提供了很多功能，可以使代碼更加簡潔。方法包括 forEach 遍歷、count 統計個數、filter 按條件過濾、limit 取前 n 個元素、skip 跳過前 n 個元素、map 映射加工、concat 合并stream流等。

日期：增強了日期和時間的 API，新的 java.time 包主要包含了處理日期、時間、日期/時間、時區、時刻和時鐘等操作。

JavaScript：Java 8 提供了一個新的 JavaScript 引擎，它允許在 JVM上運行特定的 JavaScript 應用。

---

P17：Java IO

同步和異步是通信機制，阻塞和非阻塞是調用狀態。

同步 IO 是用戶線程發起 I/O 請求后需要等待或者輪詢內核 I/O 操作完成后才能繼續執行。

異步 IO 是用戶線程發起 I/O 請求后仍可以繼續執行，當內核 I/O 操作完成后會通知用戶線程，或者調用用戶線程注冊的回調函數。

阻塞 IO 是指 I/O 操作需要徹底完成后才能返回用戶空間 。

非阻塞 IO 是指 I/O 操作被調用后立即返回一個狀態值，無需等 I/O 操作徹底完成。

BIO

同步阻塞式 IO，服務器實現模式為一個連接請求對應一個線程，即客戶端有連接請求時服務器端就需要啟動一個線程進行處理，如果這個連接不做任何事情會造成不必要的線程開銷。可以通過線程池機制改善，這種 IO 稱為偽異步 IO。

主要分為字符流和字節流，字符流包括字符輸入流 Reader 和字符輸出流 Writer，字節流包括字節輸入流 InputStream 和 字節輸出流 OutputStream，字節流和字符流都有對應的緩沖流和過濾流，也可以將字節流包裝為字符流。

適用場景：連接數目少、服務器資源多、開發難度低。

---

NIO

同步非阻塞 IO，服務器實現模式為多個連接請求對應一個線程，客戶端發送的連接請求都會注冊到一個多路復用器 Selector 上，多路復用器輪詢到連接有I/O請求時才啟動一個線程進行處理，有數據才會開啟線程處理，性能比較好。

同步是指線程還是要不斷接收客戶端連接并處理數據，非阻塞是指如果一個管道沒有數據，不需要等待，可以輪詢下一個管道。

有三個核心組件：

Selector

選擇器或多路復用器，主要作用是輪詢檢查多個 Channel 的狀態，判斷 Channel 注冊的事件是否發生，即判斷 Channel 是否處于可讀或可寫狀態。在使用之前需要將 Channel 注冊到 Selector 上，注冊之后會得到一個 SelectionKey，通過 SelectionKey 可以獲取 Channel 和 Selector 的相關信息。

Channel

雙向通道，替換了 IO 中的 Stream，不能直接訪問數據，要通過 Buffer 來讀寫數據，也可以和其他 Channel 交互。

FileChannel 處理文件、DatagramChannel 處理 UDP 數據、SocketChannel 處理 TCP 數據，用作客戶端、ServerSocketChannel 處理 TCP 數據，用作服務器端。

Buffer

緩沖區，本質是一塊可讀寫數據的內存，這塊內存被包裝成 NIO 的 Buffer 對象，用來簡化數據的讀寫。Buffer 的三個重要屬性：position 表示下一次讀寫數據的位置，limit 表示本次讀寫的極限位置，capacity 表示最大容量。

• flip() 將寫轉為讀，底層實現原理是把 position 置 0，并把 limit 設為當前的 position 值。
• 通過 clear() 將讀轉為寫模式（用于讀完全部數據的情況，把 position 置 0，limit 設為 capacity）。
• 通過 compact() 將讀轉為寫模式（用于沒有讀完全部數據，存在未讀數據的情況，讓 position 指向未讀數據的下一個）。
• 通道的方向和 Buffer 的方向是相反的，讀取數據相當于向 Buffer 寫入，寫出數據相當于從 Buffer 讀取。

使用步驟：向 Buffer 寫入數據，調用 flip 方法將 Buffer 從寫模式切換為讀模式，從 Buffer 中讀取數據，調用 clear 或 compact 方法來清空 Buffer。

適應場景：連接數目多、連接時間短、開發難度高。

---

AIO

異步非阻塞 IO，服務器實現模式為一個有效請求對應一個線程,客戶端的 I/O 請求都是由操作系統先完成 IO 操作后再通知服務器應用來啟動線程直接使用數據。

異步是指服務端線程接收到客戶端管道后就交給底層處理IO通信，自己可以做其他事情，非阻塞是指客戶端有數據才會處理，處理好再通知服務器。

AsynchronousServerSocketChannel 異步服務器端通道，通過靜態方法 open() 獲取實例，通過 accept 方法獲取客戶端連接通道。

AsynchronousSocketChannel 異步客戶端通道，通過靜態方法 open() 獲取實例，過 connect 方法連接服務器通道。

AsynchronousChannelGroup 異步通道分組管理器，它可以實現資源共享。創建時需要傳入一個ExecutorService，也就是綁定一個線程池，該線程池負責兩個任務：處理 IO 事件和觸發 CompletionHandler 回調接口。

實現方式：

通過 Future 的 get 方法進行阻塞式調用。

通過實現 CompletionHandler 接口，重寫請求成功的回調方法 completed() 和 請求失敗回調方法 failed()。

適用場景：連接數目多、連接時間長、開發難度高。

---

P18：List

List 集合是線性數據結構的主要實現，集合元素通常存在明確的前驅和后繼元素以及首尾元素。List 集合的遍歷結果是穩定的，最常用的是 ArrayList 和 LinkedList。

ArrayList

ArrayList 是容量可以改變的非線程安全集合，內部使用數組進行存儲，集合擴容時會創建更大的數組空間，把原有數組復制到新數組中。ArrayList 支持對元素的快速隨機訪問，但是插入與刪除時速度通常很慢。ArrayList 實現了 RandomAcess 標記接口，如果一個類實現了該接口，那么表示這個類使用索引遍歷比迭代器更快。

三個重要的成員變量：

• elementData：ArrayList 的數據域，被 transient 修飾，表示在類的序列化時被忽視，集合序列化時會調用 writeObject 寫入流中，在網絡客戶端反序列化的 readObject 中會重新賦值到新對象的 elementData 中。之所以這樣做的原因是 elementData 容量通常會大于實際存儲元素的數量，所以只需發送真正有實際值的數組元素即可。
• size：表示當前實際大小，elementData 的大小是大于等于 size 的。
• modCount：繼承自 AbstractList，記錄了結構性變化的次數，所有涉及結構變化的方法都會增加該值。expectedModCount 是在迭代器初始化時記錄的 modCount 值，每次訪問新元素時都會檢查 modCount 和 expectedModCount 是否相等，如果不相等就會拋出異常。這種機制叫做 fail-fast，所有集合類都有這種機制。

可以使用線程安全的 CopyOnWriteArrayList 代替 ArrayList，它實現了讀寫分離。如果是寫操作則復制一個新的集合，在新集合內添加或刪除元素，待修改完成之后再將原集合的引用指向新集合。這樣做的好處是可以高并發地進行讀寫操作而不需要加鎖，因為當前集合不會添加任何元素。使用時注意盡量設置容量初始值，避免多次擴容，并且可以使用批量添加或刪除，比如只增加一個元素卻復制整個集合。CopyOnWriteArrayList 適合讀多寫少的場景，單個添加時效率極低。CopyOnWriteArrayList 是 fail-safe 的，并發包的集合都是這種機制，fail-safe 是在安全的副本上進行遍歷，集合修改與副本的遍歷沒有任何關系，但缺點就是無法讀取到最新的數據。這也是 CAP 理論中 C 和 A 的矛盾，即一致性與可用性的矛盾。

LinkedList

LinkedList 本質是雙向鏈表，與 ArrayList 相比插入和刪除速度更快，但是隨機訪問元素則很慢。除了繼承自 AbstractList 外，它還實現了 Deque 接口，這個接口同時具有隊列和棧的性質。成員變量被 transient 修飾，序列化原理和 ArrayList 類似。

LinkedList 包含三個重要的成員：size、first 和 last。size 是雙向鏈表中節點的個數。first 和 last 分別指向首尾節點的引用。

LinkedList 的優點在于可以將零散的內存單元通過附加引用的方式關聯起來，形成按鏈路順序查找的線性結構，內存利用率較高。

Vector 和 Stack

Vector 的實現和 ArrayList 基本一致，底層使用的也是數組，它和 ArrayList 的區別主要在于：① Vector 的所有公有方法都使用了 synchronized 修飾保證線程安全性。② 增長策略不同，Vector 多了一個成員變量 capacityIncrement 用于標明擴容的增量。

Stack 是 Vector 的子類，實現和 Vector基本一致，與之相比多提供了一些方法表達棧的含義。

---

P19：Set

Set 是不允許出現重復元素的集合類型，常用的是 HashSet、TreeSet 和 LinkedHashSet。

HashSet 的是通過 HashMap 實現的，HashMap 的 Key 值即 HashSet 存儲的元素，所有 Key 都使用相同的 Value ，一個 static final 修飾的變量名為 PRESENT 的 Object 類型的對象。使用 Key 保證集合元素的唯一性，但它不保證集合元素的有序性。由于 HashSet 的底層是 HashMap 實現的，HashMap 是線程不安全的，因此 HashSet 也是線程不安全的。

HashSet 判斷元素是否相同時，對于基本類型的包裝類，直接按值進行比較。對于引用數據類型，會先比較 hashCode 返回值是否相同，如果不同則代表不是同一個對象，如果相同則繼續比較 equals 方法返回值是否相同，都相同說明是同一個對象。

TreeSet 的是使用 TreeMap 實現的，底層為樹結構，在添加新元素到集合中時，按照某種比較規則將其插入合適的位置，保證插入后的集合仍然是有序的。LinkedHashSet 繼承自 HashSet，內部使用鏈表維護了元素插入的順序。

---

P20：紅黑樹

AVL 樹是一種平衡二叉查找樹，增加和刪除節點后通過樹形旋轉重新達到平衡。右旋是以某個節點為中心，將它沉入當前右子節點的位置，而讓當前的左子節點作為新樹的根節點，也稱為順時針旋轉。同理左旋是以某個節點為中心，將它沉入當前左子節點的位置，而讓當前的右子節點作為新樹的根節點，也稱為逆時針旋轉。

紅黑樹是 1972 年發明的，當時稱為對稱二叉 B 樹，1978 年正式命名為紅黑樹，它的主要特征是在每個節點上增加一個屬性來表示節點的顏色，可以是紅色也可以是黑色。紅黑樹和 AVL 樹類似，都是在進行插入和刪除元素時，通過特定的旋轉來保持自身平衡的，從而獲得較高的查找性能。與 AVL 樹相比，紅黑樹不追求所有遞歸子樹的高度差不超過 1，而是保證從根節點到葉尾的最長路徑不超過最短路徑的 2 倍，所以它的最差時間復雜度也是 O(log_n)。紅黑樹通過重新著色和左右旋轉，更加高效地完成了插入和刪除之后的自平衡調整。

紅黑樹在本質上還是二叉查找樹，它額外引入了 5 個約束條件：① 節點只能是紅色或黑色。② 根節點必須是黑色。③ 所有 NIL 節點都是黑色的。④ 一條路徑上不能出現相鄰的兩個紅色節點。⑤ 在任何遞歸子樹中，根節點到葉子節點的所有路徑上包含相同數目的黑色節點。這五個約束條件保證了紅黑樹的新增、刪除、查找的最壞時間復雜度均為 O(log_n)。如果一個樹的左子節點或右子節點不存在，則均認定為黑色。紅黑樹的任何旋轉在 3 次之內均可完成。

紅黑樹的平衡性不如 AVL 樹，它維持的只是一種大致的平衡，并不嚴格保證左右子樹的高度差不超過 1。這導致節點數相同的情況下，紅黑樹的高度可能更高，也就是說平均查找次數會高于相同情況的 AVL 樹。在插入時，紅黑樹和 AVL 樹都能在至多兩次旋轉內恢復平衡，在刪除時由于紅黑樹只追求大致平衡，因此紅黑樹至多三次旋轉可以恢復平衡，而 AVL 樹最多需要 O(log_n) 次。AVL 樹在插入和刪除時，將向上回溯確定是否需要旋轉，這個回溯的時間成本最差為 O(log_n)，而紅黑樹每次向上回溯的步長為 2，回溯成本低。因此面對頻繁地插入與刪除紅黑樹更加合適。

---

P21：TreeMap

基于紅黑樹實現的 TreeMap 提供了平均和最差時間復雜度均為 O(log_n) 的增刪改查操作，該集合最大的特點就是 Key 的有序性。TreeMap 繼承了 SortedMap 和 NavigableMap，SortedMap 表示 Key 是有序不可重復的，支持獲取頭尾 Key-Value 元素，或者根據 Key 指定范圍獲取子集合等。插入的 Key 必須實現 Comparable 接口或提供額外的 Comparator 比較器，所以 Key 不允許為 null。NavigableMap 繼承了 SortedMap，根據指定的搜索條件返回最匹配的 Key-Value 元素。

不同于 HashMap 的是 TreeMap 并非一定要重寫 hashCode 和 equals 方法來達到 Key 去重的目的。HashMap 是依靠 hashCode 和 equals 來去重的，而 TreeMap 依靠 Comparable 或 Comparator 來實現去重。 TreeMap 對 Key 進行排序時，如果比較器不為空就會優先使用比較器的 compare 方法，如果比較器為空就會使用 Key 實現的自然排序 Comparable 接口的 compareTo 方法，如果兩者都不滿足就會拋出異常。

TreeMap 通過 put 和 deleteEntry 實現紅黑樹增加和刪除節點的操作。插入新節點的規則有三個：① 需要調整的新節點總是紅色的。② 如果插入新節點的父節點是黑色的，不需要調整。③ 如果插入新節點的父節點是紅色的，由于紅黑樹中不能出現相鄰的紅色，則進入循環判斷，通過重新著色或左右旋轉來調整。TreeMap 的插入操作就是按照 Key 的對比往下遍歷，大于比較節點值的向右查找，小于的向左查找，先按照二叉查找樹的特性操作，無需關心節點顏色與樹的平衡，后續會重新著色和旋轉，保持紅黑樹的特性。

TreeMap 是線程不安全的集合，在多線程操作時需要添加互斥機制，或者把對象放在 Collections.synchronizedMap() 中實現同步。在 JDK 7 之后的 HashMap、TreeSet、ConcurrentHashMap 也都是使用紅黑樹的方式管理節點。如果只是對單個元素進行排序，使用 TreeSet 即可。TreeSet 的底層就是 TreeMap，Value 共享一個靜態的 Object 對象。

---

P22：HashMap

JDK 8 之前

底層實現是數組 + 鏈表，主要成員變量包括：存儲數據的 table 數組、鍵值對數量 size、加載因子 loadFactor。

table 數組用于記錄 HashMap 的所有數據，它的每一個下標都對應一條鏈表，所有哈希沖突的數據都會被存放到同一條鏈表中，Entry 是鏈表的節點元素，包含四個成員變量：鍵 key、值 value、指向下一個節點的指針 next 和元素的散列值 hash。

在 HashMap 中數據都是以鍵值對的形式存在的，鍵對應的 hash 值將會作為其在數組里的下標，如果兩個元素 key 的 hash 值一樣，就會發送哈希沖突，被放到同一個下標中的鏈表上，為了使 HashMap 的查詢效率盡可能高，應該使鍵的 hash 值盡可能分散。

HashMap 默認初始化容量為 16，擴容容量必須是 2 的冪次方、最大容量為 1<< 30 、默認加載因子為 0.75。

1.put 方法：添加元素

① 如果 key 為 null 值，直接存入 table[0]。② 如果 key 不為 null 值，先計算 key 對應的散列值。③ 調用 indexFor 方法根據 key 的散列值和數組的長度計算元素存放的下標 i。④ 遍歷 table[i] 對應的鏈表，如果 key 已經存在，就更新其 value 值然后返回舊的 value 值。⑤ 如果 key 不存在，就將 modCount 的值加 1，使用 addEntry 方法增加一個節點，并返回 null 值。

2.hash 方法：計算元素 key 對應的散列值

① 處理 String 類型的數據時，直接調用對應方法來獲取最終的hash值。② 處理其他類型數據時，提供一個相對于 HashMap 實例唯一不變的隨機值 hashSeed 作為計算的初始量。③ 執行異或和無符號右移操作使 hash 值更加離散，減小哈希沖突的概率。

3.indexFor 方法：計算元素下標

直接將 hash 值和數組長度 - 1 進行與操作并返回，保證計算后的結果不會超過 table 數組的長度范圍。

4.resize 方法：根據 newCapacity 來確定新的擴容閾值 threshold

① 如果當前容量已經達到了最大容量，就將閾值設置為 Integer 的最大值，之后擴容就不會再觸發。② 創建一個新的容量為 newCapacity 的 Entry 數組，并調用 transfer 方法將舊數組的元素轉移到新數組.③ 將閾值設為 newCapacity x loadFactor 和 最大容量 + 1 的較小值。

5.transfer：轉移舊數組到新數組

① 遍歷舊數組的所有元素，調用 rehash 方法判斷是否需要哈希重構，如果需要就重新計算元素 key 的散列值。② 調用 indexFor 方法根據 key 的散列值和數組的長度計算元素存放的下標 i，利用頭插法將舊數組的元素轉移到新的數組。

6.get 方法：根據 key 獲取元素的 value 值

① 如果 key 為 null 值，調用 getForNullKey 方法，如果 size 為 0 表示鏈表為空，返回 null 值。如果 size 不為 0，說明存在鏈表，遍歷 table[0] 的鏈表，如果找到了 key 為 null 的節點則返回其 value 值，否則返回 null 值。

② 調用 getEntry 方法，如果 size 為 0 表示鏈表為空，返回 null 值。如果 size 不為 0，首先計算 key 的散列值，然后遍歷該鏈表的所有節點，如果節點的 key 值和 hash 值都和要查找的元素相同則返回其 Entry 節點。

③ 如果找到了對應的 Entry 節點，調用 getValue 方法獲取其 value 值并返回，否則返回 null 值。

---

JDK 8 開始

使用的是數組 + 鏈表/紅黑樹的形式，table 數組的元素數據類型換成了 Entry 的靜態實現類 Node。

1.put 方法：添加元素

① 調用 putVal 方法添加元素。

② 如果 table 為空或沒有元素時就進行擴容，否則計算元素下標位置，如果不存在就新創建一個節點存入。

③ 如果首節點和待插入元素的 hash值和 key 值都一樣，直接更新 value 值。

④ 如果首節點是 TreeNode 類型，調用 putTreeVal 方法增加一個樹節點，每一次都比較插入節點和當前節點的大小，待插入節點小就往左子樹查找，否則往右子樹查找，找到空位后執行兩個方法：balanceInsert 方法，把節點插入紅黑樹并對紅黑樹進行調整使之平衡; moveRootToFront 方法，由于調整平衡后根節點可能變化，table 里記錄的節點不再是根節點，需要重置根節點。

⑤ 如果是鏈表節點，就遍歷鏈表，根據 hash 值和 key 值判斷是否重復，決定更新值還是新增節點。如果遍歷到了鏈表末尾，添加鏈表元素，如果達到了建樹閾值，還需要調用 treeifyBin 方法把鏈表重構為紅黑樹。

⑥ 存放元素后，將 modCount 值加 1，如果 節點數 + 1 大于擴容閾值，還需要進行擴容。

2.get 方法：根據 key 獲取元素的 value 值

① 調用 getNode 方法獲取 Node 節點，如果不是 null 值就返回 Node 節點的 value 值，否則返回 null。

② 如果數組不為空，先比較第一個節點和要查找元素的 hash 值和 key 值，如果都相同則直接返回。

③ 如果第二個節點是 TreeNode 節點則調用 getTreeNode 方法進行查找，否則遍歷鏈表根據 hash 值和 key 值進行查找，如果沒有找到就返回 null。

3.hash 方法：計算元素 key 對應的散列值

Java 8 的計算過程簡單了許多，如果 key 非空就將 key 的 hashCode() 返回值的高低16位進行異或操作，這主要是為了讓盡可能多的位參與運算，讓結果中的 0 和 1 分布得更加均勻，從而降低哈希沖突的概率。

4.resize 方法：擴容數組

重新規劃長度和閾值，如果長度發生了變化，部分數據節點也要重新排列。

重新規劃長度

① 如果 size 超出擴容閾值，把 table 容量增加為之前的2倍。

② 如果新的 table 容量小于默認的初始化容量16，那么將 table 容量重置為16。

③ 如果新的 table 容量大于等于最大容量，那么將閾值設為 Integer 的最大值，并且 return 終止擴容，由于 size 不可能超過該值因此之后不會再發生擴容。

重新排列數據節點

① 如果節點為 null 值則不進行處理。

② 如果節點不為 null 值且沒有next節點，那么重新計算其散列值然后存入新的 table 數組中。

③ 如果節點為 TreeNode 節點，那么調用 split 方法進行處理，該方法用于對紅黑樹調整，如果太小會退化回鏈表。

④ 如果節點是鏈表節點，需要將鏈表拆分為 hashCode() 返回值超出舊容量的鏈表和未超出容量的鏈表。對于hash & oldCap == 0 的部分不需要做處理，反之需要放到新的下標位置上，新下標 = 舊下標 + 舊容量。

---

線程安全

Java 7 的 HashMap 存在死循環和數據丟失問題。

并發賦值被覆蓋：在 createEntry 方法中，新添加的元素直接放在頭部，使得新添加的元素在下次提取時可以更快被訪問到，但是如果兩個線程如果同時執行到此處，就會導致其中一個線程的賦值被覆蓋，這是數據丟失的原因之一。

已遍歷區間新增元素丟失：當某個線程在 transfer 方法遷移時，其他線程新增的元素可能落在已經遍歷過的哈希槽上。在遍歷完成后，table 數組引用指向了 newTable，這時新增元素就會丟失，被垃圾收集器回收。

新表被覆蓋：如果擴容完成，執行了 table = newTable，則后續的元素就可以在新表上進行插入操作。但是如果多線程同時擴容，每個線程又都會 new 一個數組對象，這是線程內的局部數組對象，線程之間不可見。遷移完成后，resize 線程會賦值給 table，從而覆蓋其他線程的操作，因此在新表中進行插入操作的對象都會被丟棄。

擴容時 resize 方法調用的 transfer 方法中使用頭插法遷移元素，雖然 newTable 是局部變量，但是原先 table 中的 Entry 鏈表是共享的，產生問題的根源是 Entry 的 next 指針被并發修改，這可能導致數據丟失、兩個對象互鏈或者對象自己互鏈，形成環路的原因是兩個線程都執行完第一個節點的遍歷操作后，到第二個節點時產生互鏈。

JDK 8 的 HashMap 在 resize 方法中完成擴容，并且改用了尾插法，不會產生死循環的問題，但是在多線程的情況下還是可能會導致數據覆蓋的問題，因此依舊線程不安全。可以使用 ConcurrentHashMap 代替或者 Collections.synchronizedMap 包裝成同步集合。

---

JVM 15

P1：運行時數據區

程序計數器

程序計數器是一塊較小的內存空間，可以看作當前線程所執行字節碼的行號指示器。字節碼解釋器工作時通過改變這個計數器的值來選取下一條需要執行的字節碼指令，它是程序控制流的指示器，分支、循環、跳轉、線程恢復等功能都需要依賴計數器完成。程序計數器是線程私有的，各條線程之間互不影響。

如果線程正在執行的是一個 Java 方法，計數器記錄的是正在執行的虛擬機字節碼指令的地址。如果正在執行的是本地（Native）方法，計數器值則應為空（Undefined）。

此區域是唯一在虛擬機規范中沒有規定任何內存溢出情況的區域。

Java 虛擬機棧

Java 虛擬機棧是線程私有的，用來描述 Java 方法的內存模型。每當有新的線程創建時就會給它分配一個棧空間，當線程結束后棧空間就被回收，因此棧與線程擁有相同的生命周期。棧中的元素用于支持虛擬機進行方法調用，每個方法在執行的時候都會創建一個棧幀用來存儲這個方法的局部變量表、操作棧、動態鏈接和方法出口等信息。每個方法從開始調用到執行完成的過程，就是棧幀從入棧到出棧的過程。在活動線程中，只有位于棧頂的幀才是有效的，稱為當前棧幀。

該區域有兩類異常情況：如果線程請求的棧深度大于虛擬機所允許的深度，將拋出 StackOverflowError 異常。如果 JVM 棧容量可以動態擴展，當棧擴展時無法申請到足夠的內存會拋出 OutOfMemoryError 異常（HotSpot 不可以動態擴展，不存在此問題）。

本地方法棧

本地方法棧與虛擬機棧的作用相似，不同的是虛擬機棧為虛擬機執行 Java 方法（字節碼）服務，而本地方法棧是為虛擬機棧用到的本地（Native）方法服務。調用本地方法時虛擬機棧保持不變，動態鏈接并直接調用指定的本地方法。

虛擬機規范對本地方法棧中方法所用語言、使用方式與數據結構無強制規定，具體的虛擬機可根據需要自由實現，例如 HotSpot 直接將虛擬機棧和本地方法棧合二為一。

與虛擬機棧一樣，本地方法棧也會在棧深度異常和棧擴展失敗時分別拋出 StackOverflowError 和 OutOfMemoryError 異常。

Java 堆

堆是虛擬機所管理的內存中最大的一塊，是被所有線程共享的，在虛擬機啟動時創建。堆用來存放對象實例，Java 里幾乎所有的對象實例都在這里分配內存。堆可以處于物理上不連續的內存空間中，但在邏輯上它應該被視為連續的。但對于大對象（例如數組），多數虛擬機實現出于簡單、存儲高效的考慮會要求連續的內存空間。

堆既可以被實現成固定大小的，也可以是可擴展的，可以通過 -Xms 和 -Xmx 設置堆的最小和最大容量，當前主流的 JVM 都是按照可擴展來實現的。如果在堆中沒有內存完成實例分配，并且堆也無法再擴展時，虛擬機將拋出 OutOfMemoryError 異常。

方法區

方法區和 Java 堆一樣是各個線程共享的內存區域，它用于存儲被虛擬機加載的類型信息、常量、靜態變量、即時編譯器編譯后的代碼緩存等數據。

JDK 8 之前使用永久代來實現方法區，這種設計導致了容易發生內存溢出，因為永久代有 -XX:MaxPermSize的上限，即使不設置也有默認大小。JDK 7 時把原本放在永久代的字符串常量池、靜態變量等移出，到了 JDK8 時永久代被完全廢棄，改用在本地內存中實現的元空間代替，把 JDK 7 中永久代剩余內容（主要是類型信息）全部移到元空間。

虛擬機規范對方法區的約束很寬松，除了和堆一樣不需要連續內存和可以選擇固定大小/可擴展外，還可以不實現垃圾回收。垃圾回收在該區域出現較少，主要目標針對常量池和類型卸載。如果方法區無法滿足新的內存分配需求，將拋出 OutOfMemoryError 異常。

運行時常量池

運行時常量池是方法區的一部分，Class 文件中除了有類的版本、字段、方法、接口等描述信息外，還有一項信息是常量池表，用于存放編譯器生成的各種字面量與符號引用，這部分內容將在類加載后存放到運行時常量池。一般來說，除了保存 Class 文件中描述的符號引用外，還會把符號引用翻譯出來的直接引用也存儲在運行時常量池中。

運行時常量池相對于 Class 文件常量池的一個重要特征是具備動態性，Java 并不要求常量一定只有編譯期才能產生，也就是說并非預置入 Class 文件常量池的內容才能進入方法區運行時常量池，運行期間也可以將新的常量放入池中，例如 String 類的 intern 方法。

由于運行時常量池是方法區的一部分，自然受到方法區內存的限制，當常量池無法再申請到內存時會拋出 OutOfMemoryError 異常。

直接內存

直接內存不是運行時數據區的一部分，也不是虛擬機規范中定義的內存區域，但這部分內存被頻繁使用，而且可能導致內存溢出。

JDK 1.4 中新加入了 NIO 模型，引入了一種基于通道與緩沖區的 IO 方式，它可以使用 Native 函數庫直接分配堆外內存，然后通過一個存儲在 Java 堆里的 DirectByteBuffer 對象作為這塊內存的引用進行操作，能在一些場景中顯著提高性能，避免了在 Java 堆和 Native堆中來回復制數據。

直接內存的分配不會受到 Java 堆大小的限制，但還是會受到本機總內存大小以及處理器尋址空間的限制，一般配置虛擬機參數時會根據實際內存設置 -Xmx 等參數信息，但經常忽略掉直接內存，使各個內存區域總和大于物理內存限制，導致動態擴展時出現 OOM 異常。

---

P2：對象創建的過程

字節碼角度

• NEW：如果找不到 Class 對象則進行類加載。加載成功后在堆中分配內存，從 Object 到本類路徑上的所有屬性值都要分配內存。分配完畢后進行零值設置。這個指令完成后，將指向實例對象的引用變量壓入虛擬機棧頂。
• DUP：在棧頂復制該引用變量，這時棧頂有兩個指向堆內實例的引用變量。如果 init 方法有參數還需要把參數壓入操作棧中。兩個引用變量的目的不同，棧底的引用用于賦值或保存到局部變量表，棧頂的引用作為句柄調用相關方法。
• INVOKESPECIAL：通過棧頂的引用變量調用 init 方法。

執行角度

當 JVM 遇到一條字節碼 new 指令時，首先將檢查該指令的參數能否在常量池中定位到一個類的符號引用，并檢查這個引用代表的類是否已被加載、解析和初始化，如果沒有就必須先執行類加載。

在類加載檢查通過后虛擬機將為新生對象分配內存。對象所需內存的大小在類加載完成后便可完全確定，分配空間的任務實際上等于把一塊確定大小的內存塊從 Java 堆中劃分出來。假設 Java 堆內存是規整的，被使用過的內存都放在一邊，空閑的內存放在另一邊，中間放著一個指針作為分界指示器，分配內存就是把該指針向空閑方向挪動一段與對象大小相等的距離，這種方式叫"指針碰撞"。

如果 Java 堆中的內存不是規整的，那么虛擬機就必須維護一個列表記錄哪些內存塊可用，在分配時從列表中找到一塊足夠大的空間劃分給對象實例并更新列表上的記錄，這種方式叫做"空閑列表"。

選擇哪種分配方式由堆是否規整決定，堆是否規整又由所用垃圾回收器是否帶有空間壓縮整理能力決定。因此使用 Serial、ParNew 等帶壓縮整理的收集器時，系統采用指針碰撞；當使用 CMS 這種基于清除算法的垃圾收集器時，采用空間列表。

對象創建十分頻繁，即使修改一個指針的位置在并發情況下也不是線程安全的，可能出現正給對象 A 分配內存，指針還沒來得及修改，對象 B 又同時使用了指針來分配內存的情況。解決該問題有兩個方法：① 采用 CAS 加失敗重試保證更新操作的原子性。② 把內存分配的動作按照線程劃分在不同空間進行，即每個線程在 Java 堆中預先分配一小塊內存，叫做本地線程分配緩沖 TLAB，哪個線程要分配內存就在對應的 TLAB 分配，只有 TLAB 用完了才需要同步。

內存分配完成后虛擬機必須將成員變量設定為零值，保證對象的實例字段可以不賦初始值就直接使用。

初始化為零值后，設置對象頭，包括哈希碼、GC 信息、鎖信息、對象所屬類的類元信息等。

最后執行 init 方法，初始化成員變量，執行實例化代碼塊，調用類的構造方法，并把堆內對象的首地址賦值給引用變量。

---

P3：對象的內存布局

在 HotSpot 虛擬機中，對象在堆內存中的存儲布局可分為三個部分。

對象頭

對象頭占用 12B，存儲內容包括對象標記和類元信息。對象標記存儲對象本身的運行時數據，如哈希碼、GC 標記、鎖信息、線程關聯信息等，這部分數據在 64 位 JVM 上占用 8B，稱為"Mark Word"。為了存儲更多的狀態信息，對象標記的存儲格式是不固定的，與具體 JVM 實現有關。

類元信息存儲的是對象指向它的類元數據的首地址，占用 4B。JVM 通過該指針來確定對象是哪個類的實例。并非所有虛擬機實現都必須在對象數據上保留類型指針，查找對象的元數據不一定要經過對象本身。此外如果對象是一個 Java 數組，在對象頭還必須有一塊用于記錄數組長度的數據。

實例數據

實例數據是對象真正存儲的有效信息，即本類對象的實例成員變量和所有可見的父類成員變量。存儲順序會受到虛擬機分配策略參數和字段在源碼中定義順序的影響。相同寬度的字段總是被分配到一起存放，在滿足該前提條件的情況下父類中定義的變量會出現在子類之前。

對齊填充

這部分不是必然存在的，僅起占位符的作用。由于 HotSpot 虛擬機的自動內存管理系統要求對象的起始地址必須是 8 字節的整數倍，而對象頭已經被設為正好是 8 字節的整數倍，因此如果對象實例數據部分沒有對齊，就需要對齊填充來補全。

---

P4：對象的訪問定位

Java 程序會通過棧上的 reference 數據來操作堆上的具體對象，而具體對象訪問方式是由虛擬機決定的，主流的訪問方式主要有使用句柄和直接指針兩種。

使用句柄

如果使用句柄訪問，Java 堆中將可能會劃分出一塊內存作為句柄池，reference 中存儲的就是對象的句柄地址，而句柄中包含了對象實例數據與類型數據各自具體的地址信息。

優點是 reference 中存儲的是穩定句柄地址，在對象被移動（處于垃圾收集過程中）時只會改變句柄中的實例數據指針，而 reference 本身不需要被修改。

直接指針

如果使用直接指針訪問的話，Java 堆中對象的內存布局就必須考慮如何放置訪問類型數據的相關信息，reference中存儲的直接就是對象地址，如果只是訪問對象本身的話就不需要多一次間接訪問的開銷。

優點就是速度更快，節省了一次指針定位的時間開銷，HotSpot 主要使用的就是直接指針來進行對象訪問。

---

P5：內存溢出異常

Java 堆溢出

Java 堆用于存儲對象實例，我們只要不斷創建對象，并且保證GC Roots到對象有可達路徑來避免垃圾回收機制清除這些對象，那么隨著對象數量的增加，總容量觸及最大堆容量的限制后就會產生OOM異常。例如在 while 死循環中一直 new 創建實例。

Java 堆內存的 OOM 是實際應用中最常見的 OOM 情況，常規的處理方法是先通過內存映像分析工具對 Dump 出來的堆轉儲快照進行分析，確認內存中導致 OOM 的對象是否是必要的，即分清楚到底是出現了內存泄漏還是內存溢出。

如果是內存泄漏，可進一步通過工具查看泄漏對象到 GC Roots 的引用鏈，找到泄露對象是通過怎樣的引用路徑、與哪些GC Roots相關聯才導致垃圾收集器無法回收它們，一般可以準確定位到對象創建的位置進而找出產生內存泄漏代碼的具體位置。

如果不是內存泄漏，即內存中的對象確實都是必須存活的那就應當檢查 JVM 的堆參數設置，與機器的內存相比是否還有向上調整的空間。再從代碼上檢查是否存在某些對象生命周期過長、持有狀態時間過長、存儲結構設計不合理等情況，盡量減少程序運行期的內存消耗。

虛擬機棧和本地方法棧溢出

由于HotSpot虛擬機不區分虛擬機和本地方法棧，因此設置本地方法棧大小的參數沒有意義，棧容量只能由 -Xss 參數來設定，存在兩種異常：

• StackOverflowError：如果線程請求的棧深度大于虛擬機所允許的深度，將拋出StackOverflowError異常。例如一個遞歸方法不斷調用自己。
  該異常有明確錯誤堆棧可供分析，容易定位到問題所在。

• OutOfMemoryError：如果 JVM 棧容量可以動態擴展，當棧擴展時無法申請到足夠的內存會拋出OutOfMemoryError異常。HotSpot 虛擬機不支持虛擬機棧的擴展，所以除非在創建線程申請內存時就因無法獲得足夠內存而出現OOM異常，否則在線程運行時是不會因為擴展而導致內存溢出的，只會因為棧容量無法容納新的棧幀而導致StackOverflowError異常。

運行時常量池溢出

String 類的 intern 方法是一個本地方法，作用是如果字符串常量池中已經包含一個等于此 String 對象的字符串，則返回代表池中這個字符串的 String 對象的引用，否則將此 String 對象包含的字符串添加到常量池并返回此 String 對象的引用。

在 JDK 6 及之前常量池都分配在永久代，因此可以通過 -XX:PermSize 和 -XX:MaxPermSize 限制永久代大小，間接限制常量池。在 while 死循環中不斷調用 intern 方法導致運行時常量池溢出。

在 JDK 7 及之后不會出現該問題，因為存放在永久代的字符串常量池已經被移至 Java 堆中。

方法區溢出

方法區的主要職責是存放類型信息，如類名、訪問修飾符、常量池、字段描述、方法描述等。只要不斷在運行時產生大量的類去填滿方法區，就會導致溢出。例如使用 JDK 反射或 CGLib 直接操作字節碼在運行時生成大量的類。當前的很多主流框架如 Spring、Hibernate 等對類增強時都會使用 CGLib 這類字節碼技術，增強的類越多就需要越大的方法區保證動態生成的新類型可以載入內存，也就更容易導致方法區溢出。

JDK 8 之后永久代完全被廢棄，取而代之的是元空間，HotSpot 提供了一些參數作為元空間的防御措施：

-XX:MaxMetaspaceSize：設置元空間的最大值，默認 -1，表示不限制即只受限于本地內存大小。

-XX:MetaspaceSize：指定元空間的初始大小，以字節為單位，達到該值就會觸發垃圾收集進行類型卸載，同時收集器會對該值進行調整：如果釋放了大量空間就適當降低該值，如果釋放了很少的空間就適當提高該值。

-XX:MinMetaspaceFreeRatio：作用是在垃圾收集之后控制最小的元空間剩余容量百分比，可減少因為元空間不足導致的垃圾收集的頻率。類似的還有-XX:MinMetaspaceFreeRatio，用于控制最大的元空間剩余容量百分比。

本機直接內存溢出

直接內存的容量大小可通過 -XX:MaxDirectMemorySize 指定，如果不指定則默認與 Java 堆的最大值一致。

由直接內存導致的內存溢出，一個明顯的特征是在 Heap Dump 文件中不會看見明顯的異常，如果發現內存溢出后產生的 Dump 文件很小，而程序中又直接或間接使用了直接內存（典型的間接使用就是 NIO），那么就可以考慮檢查直接內存方面的原因。

---

P6：判斷對象是否是垃圾

在堆中存放著所有對象實例，垃圾收集器在對堆進行回收前，首先要判斷對象是否還存活著。

引用計數算法

在對象中添加一個引用計數器，如果有一個地方引用它計數器就加1，引用失效時計數器就減1，如果計數器為0則該對象就是不再被使用的。該算法原理簡單，效率也高，但是在 Java中很少使用，因為它存在對象之間互相循環引用的問題，導致計數器無法清零。

可達性分析算法

當前主流語言的內存管理子系統都是使用可達性分析算法來判斷對象是否存活的。這個算法的基本思路就是通過一系列稱為 GC Roots 的根對象作為起始節點集，從這些節點開始，根據引用關系向下搜索，搜索過程所走過的路徑稱為引用鏈，如果某個對象到 GC Roots之間沒有任何引用鏈相連，則此對象是不可能再被使用的。

可作為GC Roots的對象包括虛擬機棧中引用的對象、方法區中類靜態屬性引用的對象、方法區中常量引用的對象、本地方法棧中引用的對象等。

---

P7：引用類型

無論通過引用計數還是可達性分析判斷對象是否存活，都和引用離不開關系。在 JDK1.2 之前引用的定義是：如果 reference 類型數據存儲的數值代表另外一塊內存的起始地址，那么就稱該 reference 數據是代表某塊內存、某個對象的引用。在 JDK 1.2之后 Java 對引用的概念進行了擴充，按強度分為四種：

強引用：最常見的引用，例如 Object obj = new Object 這樣的變量聲明和定義就會產生對該對象的強引用。只要對象有強引用指向，并且 GC Roots 可達，那么進行內存回收時即使瀕臨內存耗盡也不會回收該對象。

軟引用：弱于強引用，描述非必需對象。在系統將要發生內存溢出異常前，會把軟引用關聯的對象加入回收范圍以獲得更多的內存空間。主要用來緩存服務器中間計算結果及不需要實時保存的用戶行為等。

弱引用：弱于軟引用，描述非必需對象。被弱引用關聯的對象只能生存到下一次 YGC 之前，當垃圾收集器開始工作時無論當前內存是否足夠都會回收只被弱引用關聯的對象。由于 YGC 具有不確定性，因此弱引用何時被回收也有不確定性。

虛引用：是最弱的引用關系，定義完成后就無法通過該引用獲取指向的對象。一個對象是否有虛引用存在，完全不會對其生存時間造成影響。該引用的唯一目的就是為了能在這個對象被垃圾收集器回收時收到一個系統通知。虛引用必須與引用隊列聯合使用，當垃圾回收時如果出現虛引用，就會在回收對象內存之前把這個虛引用加入關聯的引用隊列。

---

P8：GC 算法

標記-清除算法

• 原理：分為標記和清除兩個階段，首先從每個 GC Roots 出發依次標記有引用關系的對象，最后將沒有被標記的對象清除。
• 特點：① 執行效率不穩定，如果堆中包含大量對象且其中大部分是需要被回收的，這時必須進行大量標記和清除，導致效率隨對象數量增長而降低。② 內存空間碎片化問題，會產生大量不連續的內存碎片，空間碎片太多可能會導致以后在程序運行中需要分配較大對象時容易觸發 Full GC。

標記-復制算法

• 原理：為了解決內存碎片問題，將可用內存按容量劃分為大小相等的兩塊，每次只使用其中一塊。當這一塊的空間用完了，就將還存活著的對象復制到另一塊，然后再把已使用過的內存空間一次清理掉。主要用于進行新生代的垃圾回收。
• 特點：① 實現簡單、運行高效，解決了內存碎片問題。② 代價是將可用內存縮小為原來的一半，浪費了過多空間。
• HotSpot 的新生代劃分
  把新生代劃分為一塊較大的 Eden 空間和兩塊較小的 Survivor 空間，每次分配內存只使用 Eden 和其中一塊 Survivor。發生垃圾收集時將 Eden 和 Survivor 中仍然存活的對象一次性復制到另一塊 Survivor 上，然后直接清理掉 Eden 和已用過的那塊 Survivor 空間。HotSpot虛擬機默認Eden和Survivor的大小比例是8：1，即每次新生代中可用空間為整個新生代的90%。

標記-整理算法

• 原理：標記-復制算法在對象存活率較高時要進行較多的復制操作，效率將會降低。并且如果不想浪費空間，就需要有額外空間進行分配擔保，應對被使用內存中所有對象都100%存活的極端情況，所以老年代一般不使用此算法。老年代使用標記-整理算法，標記過程與標記-清除算法一樣，只是后續步驟不是直接對可回收對象進行清理，而是讓所有存活的對象都向內存空間一端移動，然后直接清理掉邊界以外的內存。
• 特點：標記-清除與標記-整理的差異在于前者是一種非移動式回收算法而后者是移動式的。是否移動回收后的存活對象優缺點并存：① 如果移動存活對象，尤其是在老年代這種每次回收都有大量對象存活的區域，是一種極為負重的操作，而且這種移動必須全程暫停用戶線程。② 如果不移動對象就會導致空間碎片問題，只能依賴更復雜的內存分配器和訪問器來解決。所以是否移動對象都存在弊端，移動則內存回收更復雜，不移動則內存分配更復雜。

---

P9：垃圾收集器

經典垃圾收集器：指 JDK 11之前的垃圾收集器。

Serial

最基礎、歷史最悠久的收集器，該收集器是一個使用復制算法的單線程工作收集器，單線程的意義不僅是說明它只會使用一個處理器或一條收集線程去完成垃圾收集工作，更重要的是強調它進行垃圾收集時必須暫停其他所有工作線程直到收集結束。

Serial 是虛擬機運行在客戶端模式下的默認新生代收集器，優點是簡單高效，對于內存受限的環境它是所有收集器中最小的；對于單核處理器或處理器核心較少的環境來說，Serial 收集器由于沒有線程交互開銷，因此可獲得最高的單線程收集效率。

ParNew

實質上是 Serial 的多線程版本，除了使用多線程進行垃圾收集外其余行為完全一致。

ParNew 是虛擬機運行在服務端模式下的默認新生代收集器，一個重要原因是除了 Serial 外只有它能與 CMS 配合。自從 JDK 9 開始，ParNew 加 CMS 收集器的組合就不再是官方推薦的服務端模式下的收集器解決方案了，官方希望他能被 G1 完全取代。

Parallel Scavenge

新生代收集器，基于標記-復制算法，是可以并行的多線程收集器，與 ParNew 類似。

特點是它的關注點與其他收集器不同，CMS 等收集器的關注點是盡可能縮短收集時用戶線程的停頓時間，而 Parallel Scavenge 的目標是達到一個可控制的吞吐量，吞吐量就是處理器用于運行用戶代碼的時間與處理器消耗總時間的比值。自適應調節策略也是它區別于 ParNew 的一個重要特性。

Serial Old

Serial 的老年代版本，同樣是一個單線程收集器，使用標記-整理算法。

Serial Old 是虛擬機在客戶端模式下的默認老年代收集器，用于服務端有兩種用途：一種是 JDK 5 及之前與 Parallel Scavenge 搭配使用，另一種是作為CMS 發生失敗時的預案。

Parellel Old

Parallel Scavenge 的老年代版本，支持多線程收集，基于標記-整理算法實現。這個收集器直到 JDK 6 才開始提供，在注重吞吐量優先的場景可以有效考慮Parallel Scavenge 加 Parallel Old 組合。

CMS

以獲取最短回收停頓時間為目標的收集器，如果希望系統停頓時間盡可能短以給用戶帶來更好的體驗就可以使用 CMS。

基于標記-清除算法，過程相對復雜，分為四個步驟：初始標記、并發標記、重新標記、并發清除。

其中初始標記和重新標記仍然需要 STW（Stop The World，表示系統停頓），初始標記僅是標記 GC Roots 能直接關聯到的對象，速度很快。并發標記就是從 GC Roots 的直接關聯對象開始遍歷整個對象圖的過程，耗時較長但不需要停頓用戶線程，可以與垃圾收集線程并發運行。重新標記則是為了修正并發標記期間因用戶程序運作而導致標記產生變動的那一部分對象的標記記錄，該階段停頓時間比初始標記稍長，但遠比并發標記短。最后是并發清除，清理標記階段判斷的已死亡對象，由于不需要移動存活對象，因此該階段也可以與用戶線程并發。

由于整個過程中耗時最長的并發標記和并發清除階段中，垃圾收集器都可以和用戶線程一起工作，所以從總體上說 CMS 的內存回收過程是與用戶線程并發執行的。

CMS 是 HotSpot 追求低停頓的第一次成功嘗試，但還存在三個明顯缺點：① 對處理器資源敏感，在并發階段雖然不會導致用戶線程暫停，但會降低總吞吐量。② 無法處理浮動垃圾，有可能出現并發失敗而導致另一次 Full GC。③ 基于標記-清除算法，會產生大量空間碎片，給大對象分配帶來麻煩。

G1

開創了收集器面向局部收集的設計思路和基于Region的內存布局，是一款主要面向服務端的收集器，最初設計目標是替換CMS。

G1 之前的收集器，垃圾收集的目標要么是整個新生代，要么是整個老年代或整個堆。而 G1 可以面向堆內存任何部分來組成回收集進行回收，衡量標準不再是它屬于哪個分代，而是哪塊內存中存放的垃圾數量最多，回收受益最大。

不再堅持固定大小及數量的分代區域劃分，而是把 Java 堆劃分為多個大小相等的獨立區域（Region），每一個 Region 都可以根據需要扮演新生代的 Eden 空間、Survivor 空間或老年代空間。收集器能夠對扮演不同角色的 Region 采用不同的策略處理，這樣無論是新創建的對象還是已經存活了一段時間、熬過多次收集的舊對象都能獲取很好的收集效果。

跟蹤各個 Region 里垃圾堆積的價值大小，價值即回收所獲得的空間大小以及回收所需時間的經驗值，在后臺維護一個優先級列表，每次根據用戶設定允許的收集停頓時間優先處理回收價值收益最大的 Region。這種方式保證了 G1 在有限時間內獲取盡可能高的收集效率。

G1的運作過程：

• 初始標記：標記 GC Roots 能直接關聯到的對象，讓下一階段用戶線程并發運行時能正確地在可用 Region 中分配新對象。該階段需要 STW 但耗時很短，是借用進行 Minor GC 時同步完成的。
• 并發標記：從 GC Roots 開始對堆中對象進行可達性分析，遞歸掃描整個堆的對象圖，找出需要回收的對象。該階段耗時長，但可與用戶線程并發執行，當對掃描完成后還要重新處理 SATB 記錄的在并發時有引用變動的對象。
• 最終標記：對用戶線程做一個短暫暫停，用于處理并發階段結束后仍遺留下來的少量 SATB 記錄。
• 篩選回收：對各個 Region 的回收價值和成本排序，根據用戶期望的停頓時間制定回收計劃，可自由選擇任意多個 Region 構成回收集然后把決定回收的那部分存活對象復制到空的 Region 中，再清理掉整個舊 Region 的全部空間。該操作必須暫停用戶線程，由多條收集器線程并行完成。

可以由用戶指定期望停頓時間是 G1 的一個強大功能，但該值不能設得太低，一般設置為100~300毫秒比較合適。G1不存在內存空間碎片的問題，但為了垃圾收集產生的內存占用和程序運行時的額外執行負載都高于 CMS。

---

低延遲垃圾收集器：指 Shenandoah 和 ZGC，這兩個收集器幾乎整個工作過程都是并發的，只有初始標記、最終標記這些階段有短暫停頓，停頓時間基本上固定。

Shenandoah

相比 G1 內存布局同樣基于 Region，默認回收策略也是優先處理回收價值最大的 Region。但在管理堆內存方面與 G1 有不同：① 支持并發整理，G1 的回收階段不能與用戶線程并發。② 默認不使用分代收集，不會有專門的新生代 Region 或老年代 Region。③ 摒棄了在 G1 中耗費大量內存和計算資源維護的記憶集，改用名為連接矩陣的全局數據結構記錄跨 Region 的引用關系。

ZGC

JDK 11中新加入的具有實驗性質的低延遲垃圾收集器，和 Shenandoah 的目標相似，都希望在盡可能對吞吐量影響不大的前提下實現把停頓時間限制在 10ms 以內的低延遲。

基于 Region 內存布局，不設分代，使用了讀屏障、染色指針和內存多重映射等技術實現可并發的標記-整理，以低延遲為首要目標。 ZGC 的 Region 具有動態性，是動態創建和銷毀的，并且區容量大小也是動態變化的。

---

P10：內存分配與回收策略

以 Seial + Serial Old 客戶端默認收集器組合為例：

對象優先在 Eden 區分配

大多數情況下對象在新生代 Eden 區分配，當 Eden 區沒有足夠空間進行分配時將發起一次 Minor GC。

可通過 -XX:Xms 和 -XX:Xmx 設置堆大小， -Xmn 設置新生代的大小， -XX:SurvivorRatio 設置新生代中 Eden 和 Survivor 的比例。

大對象直接進入老年代

大對象指需要大量連續內存空間的對象，典型的是很長的字符串或元素數量龐大的數組。大對象容易導致內存明明還有不少空間就提前觸發垃圾收集以獲得足夠的連續空間，復制對象時大對象就意味著高額內存復制開銷。

HotSpot 提供了 -XX:PretenureSizeThreshold 參數，大于該值的對象直接在老年代分配，避免在 Eden 和 Survivor 之間來回復制產生大量內存復制操作。

長期存活對象進入老年代

虛擬機給每一個對象定義了一個對象年齡計數器，存儲在對象頭。對象通常在 Eden 誕生，如果經歷過第一次 MinorGC 仍然存活并且能被 Survivor 容納，該對象就會被移動到 Survivor 中并將年齡設置為 1。對象在 Survivor 中每熬過一次 MinorGC 年齡就加 1 ，當增加到一定程度（默認15）就會被晉升到老年代。對象晉升老年代的年齡閾值可通過 -XX:MaxTenuringThreshold 設置。

動態對象年齡判定

為了適應不同程序的內存狀況，虛擬機并不永遠要求對象年齡達到閾值才能晉升老年代，如果在 Survivor 中相同年齡所有對象大小的總和大于 Survivor 的一半，年齡不小于該年齡的對象就可以直接進入老年代，無需等到 -XX:MaxTenuringThreshold 參數設置的年齡。

空間分配擔保

發生 MinorGC 前，虛擬機必須先檢查老年代最大可用連續空間是否大于新生代所有對象總空間，如果這個條件成立，那這一次 MinorGC可以確定是安全的。

如果不成立，虛擬機會先查看 -XX:HandlePromotionFailure 參數的值是否允許擔保失敗，如果允許會繼續檢查老年代最大可用連續空間是否大于歷次晉升老年代對象的平均大小，如果滿足將冒險嘗試一次 MinorGC，如果不滿足或不允許擔保失敗就會改成一次 FullGC。

之所以說冒險是因為新生代使用復制算法，為了內存利用率只使用其中一個 Survivor 作為備份，因此當出現大量對象在 MinorGC 后仍然存活的情況時需要老年代進行分配擔保，把 Survivor 無法容納的對象直接送入老年代。

---

P11：故障處理工具

jps：虛擬機進程狀況工具

jps 即 JVM Process Status，參考了 UNIX 命令的命名格式，功能和 ps 命令類似：可以列出正在運行的虛擬機進程，并顯示虛擬機執行主類名稱以及這些進程的本地虛擬機唯一 ID（LVMID)。LVMID 與操作系統的進程 ID（PID）是一致的，使用 Windows 的任務管理器或 UNIX 的 ps 命令也可以查詢到虛擬機進程的 LVMID，但如果同時啟動了多個虛擬機進程，無法根據進程名稱定位就必須依賴 jps 命令。

jps 還可以通過 RMI 協議查詢開啟了 RMI 服務的遠程虛擬機進程狀態，參數 hostid 為 RMI 注冊表中注冊的主機名。

jstat：虛擬機統計信息監視工具

jstat 即 JVM Statistic Monitoring Tool，是用于監視虛擬機各種運行狀態信息的命令行工具。它可以顯示本地或者遠程虛擬機進程中的類加載、內存、垃圾收集、即時編譯器等運行時數據，在沒有 GUI 界面的服務器上是運行期定位虛擬機性能問題的常用工具。

一些參數的含義：S0 和 S1 表示兩個 Survivor 區，E 表示新生代，O 表示老年代，YGC 表示 Young GC 次數，YGCT 表示Young GC 耗時，FGC 表示 Full GC 次數，FGCT 表示 Full GC 耗時，GCT 表示所有 GC 總耗時。

jinfo：Java 配置信息工具

jinfo 表示 Configuration Info for Java，作用是實時查看和調整虛擬機各項參數，使用 jps 的 -v 參數可以查看虛擬機啟動時顯式指定的參數列表，但如果想知道未被顯式指定的參數的系統默認值就只能使用 jinfo 的 -flag 選項進行查詢。jinfo 還可以把虛擬機進程的 System.getProperties() 的內容打印出來。

jmap：Java 內存映像工具

jmap 表示 Memory Map for Java，jamp 命令用于生成堆轉儲快照，還可以查詢 finalize 執行隊列、Java 堆和方法區的詳細信息，如空間使用率，當前使用的是哪種收集器等。和 jinfo 命令一樣，有部分功能在 Windows 平臺下受限，除了生成堆轉儲快照的 -dump 選項和用于查看每個類實例的 -histo 選項外，其余選項都只能在 Linux 使用。

jhat：虛擬機堆轉儲快照分析工具

jhat 表示 JVM Heap Analysis Tool，JDK 提供 jhat 命令與 jmap 搭配使用來分析 jamp 生成的堆轉儲快照。jhat 內置了一個微型的 HTTP/Web 服務器，生成堆轉儲快照的分析結果后可以在瀏覽器中查看。

jstack：Java 堆棧跟蹤工具

jstack 表示 Stack Trace for Java，jstack 命令用于生成虛擬機當前時刻的線程快照。線程快照就是當前虛擬機內每一條線程正在執行的方法堆棧的集合，生成線程快照的目的通常是定位線程出現長時間停頓的原因，如線程間死鎖、死循環、請求外部資源導致的長時間掛起等。線程出現停頓時通過 jstack 查看各個線程的調用堆棧，就可以獲知沒有響應的現場到底在后臺做什么或等待什么資源。

除了上述的基礎故障處理工具，還有一些可視化故障處理工具，例如 JHSDB 基于服務性代理的調試工具、JConsole Java 監視與管理控制臺、VisualVM 多合一故障處理工具、Java Mission Control 可持續在線監控工具。

---

P12：Java 程序運行的過程

通過 Javac 編譯器將 .java 代碼轉為 JVM 可以加載的 .class 字節碼文件。

Javac 編譯器是由 Java 語言編寫的程序，從 Javac 代碼的總體結構看，編譯過程可以分為： ① 詞法解析，通過空格分割處單詞、操作符、控制符等信息，將其形成 token 信息流，傳遞給語法解析器。② 語法解析，把詞法解析得到的 token 信息流按照 Java 語法規則組裝成一顆語法樹。④ 語義分析，檢查關鍵字的使用是否合理、類型是否匹配、作用域是否正確等。④ 字節碼生成，將前面各個步驟的信息轉換為字節碼。

字節碼必須通過類加載過程加載到 JVM 環境后才可以執行，執行有三種模式，解釋執行、JIT 編譯執行、JIT 編譯與解釋器混合執行（主流 JVM 默認執行的方式）。混合模式的優勢在于解釋器在啟動時先解釋執行，省去編譯時間。

通過即時編譯器 JIT 把字節碼文件編譯成本地機器碼。

Java 程序最初都是通過解釋器進行解釋執行的，當虛擬機發現某個方法或代碼塊的運行特別頻繁，就會把這些代碼認定為"熱點代碼"，熱點代碼的檢測主要有基于采樣和基于計數器兩種方式，為了提高熱點代碼的執行效率，在運行時虛擬機會把這些代碼編譯成本地機器碼，并盡可能對代碼優化，在運行時完成這個任務的后端編譯器被稱為即時編譯器。

還可以通過靜態的提前編譯器 AOT 直接把程序編譯成與目標機器指令集相關的二進制代碼。

---

P13：類加載機制和初始化時機

在 Class 文件中描述的各類信息最終都需要加載到虛擬機后才能運行和使用。JVM 把描述類的數據從 Class 文件加載到內存，并對數據進行校驗、解析和初始化，最終形成可以被虛擬機直接使用的 Java類型，這個過程被稱為虛擬機的類加載機制。與其他在編譯時需要連接的語言不同，Java 中類型的加載、連接和初始化都是在程序運行期間完成的，這種策略讓 Java 進行類加載時增加了性能開銷，但卻為 Java 應用提供了極高的擴展性和靈活性，Java 可以動態擴展的語言特性就是依賴運行期動態加載和動態連接這個特點實現的。

一個類型從被加載到虛擬機內存開始，到卸載出內存為止，整個生命周期將會經歷加載、驗證、準備、解析、初始化、使用和卸載七個階段，其中驗證、解析和初始化三個部分統稱為連接。加載、驗證、準備、初始化和卸載這五個階段的順序是確定的，而解析階段則不一定：它在某些情況下可以在初始化階段之后再開始，這是為了支持 Java 語言的動態綁定特性。

關于何shuyu時需要開始類加載的第一個階段"加載"，《 Java 虛擬機規范》沒有強制約束，但對于初始化嚴格規定了有且只有6種情況：

• 遇到 new、getstatic、putstatic 或 invokestatic 這四條字節碼指令時，如果類型沒有初始化則需要先觸發初始化。典型場景有：① 使用new關鍵字實例化對象。② 讀取或設置一個類型的靜態字段。③ 調用一個類型的靜態方法。
• 對類型進行反射調用時，如果類型沒有初始化則需要先觸發初始化。
• 當初始化類時，如果其父類沒有初始化則需要先觸發父類的初始化。
• 當虛擬機啟動時，用戶需要指定一個要執行的主類即包含 main 方法的類，虛擬機會先初始化該類。
• 當使用 JDK 7 新加入的動態語言支持時，如果 MethodHandle 實例的解析結果為指定類型的方法句柄且這個句柄對應的類沒有進行過初始化，則需要先觸發其初始化。
• 當一個接口定義了默認方法時，如果該接口的實現類發生初始化，那接口要在其之前初始化。

除了這六種情況外其余所有引用類型的方式都不會觸發初始化，稱為被動引用。被動引用的實例：① 子類使用父類的靜態字段時，只有直接定義這個字段的父類會被初始化。② 通過數組定義使用類。③ 常量在編譯期會存入調用類的常量池，不會初始化定義常量的類。

接口的加載過程和類真正有所區別的是當初始化類時，如果其父類沒有初始化則需要先觸發其父類的初始化，但在一個接口初始化時并不要求其父接口全部完成了初始化，只有在真正使用到父接口時（如引用接口中定義的常量）才會初始化。

---

P14：類加載過程

加載

加載是類加載的第一個階段，在該階段虛擬機需要完成三件事：① 通過一個類的全限定類名來獲取定義此類的二進制字節流。② 將這個字節流所代表的靜態存儲結構轉化為方法區的運行時數據區結構。③ 在內存中生成對應該類的 Class 實例，作為方法區這個類的各種數據的訪問入口。加載與連接的部分動作是交叉進行的，加載尚未完成時連接可能已經開始。

驗證

驗證是連接的第一步，目的是確保 Class 文件的字節流中包含的信息符合約束要求，保證這些信息不會危害虛擬機的安全。如果虛擬機不檢查輸入的字節流，很可能因為載入了有錯誤或惡意企圖的字節流而導致整個系統受攻擊。驗證主要包含了四個階段：文件格式驗證、元數據驗證、字節碼驗證、符號引用驗證。

驗證對于虛擬機的類加載機制來說是一個非常重要但非必需的階段，因為驗證只有通過與否的區別，只要通過了驗證其后就對程序運行期沒有任何影響了。如果程序運行的全部代碼都已被反復使用和驗證過，在生產環境的就可以考慮關閉大部分類驗證措施縮短類加載時間。

準備

準備是正式為類靜態變量分配內存并設置零值的階段，該階段進行的內存分配僅包括類變量，而不包括實例變量，實例變量將會在對象實例化時隨著對象一起分配在 Java 堆中。如果變量被final修飾，編譯時 Javac 會為變量生成 ConstantValue 屬性，那么在準備階段虛擬機就會將該變量的值設為程序員指定的值。

解析

解析是將常量池內的符號引用替換為直接引用的過程。

• 符號引用：符號引用以一組符號描述引用目標，可以是任何形式的字面量，只要使用時能無歧義地定位到目標即可。與虛擬機內存布局無關，引用目標并不一定是已經加載到虛擬機內存中的內容。
• 直接引用：直接引用是可以直接指向目標的指針、相對偏移量或者能間接定位到目標的句柄。和虛擬機的內存布局直接相關，引用目標必須已在虛擬機的內存中存在。

解析部分主要針對類或接口、字段、類方法、接口方法、方法類型、方法句柄和調用點限定符這7類符合引用進行。

初始化

初始化是類加載過程的最后一步，直到該階段，JVM 才真正開始執行類中編寫的代碼。準備階段時變量已經賦過一次系統零值，而在初始化階段會根據程序員的編碼去初始化類變量和其他資源。初始化階段就是執行類構造方法中的 方法，該方法是 Javac 編譯器自動生成的。

---

P15：類加載器和雙親委派模型

類加載階段中"通過一個類的全限定名來獲取描述該類的二進制字節流"的動作被設計為放到 JVM 外部實現，以便讓應用程序自己決定如何獲取所需的類，實現這個動作的代碼就是類加載器。

自 JDK1.2 起 Java 一直保持著三層類加載器、雙親委派的類加載模型：

• 啟動類加載器
  啟動類加載器在 JVM 啟動時創建，負責加載最核心的類，例如 Object、System、String 等。啟動類加載器無法被 Java 程序直接引用，如果用戶需要把加載請求委派給啟動類加載器，直接使用 null 代替即可，因為啟動類加載器通常由操作系統相關的本地代碼實現，并不存在于 JVM 體系中。
• 平臺類加載器
  從 JDK9 開始從擴展類加載器更換為平臺類加載器，負載加載一些擴展的系統類，比如 XML、加密、壓縮相關的功能類等。
• 應用類加載器
  也稱系統類加載器，負載加載用戶類路徑上的所有類庫，可以直接在代碼中使用。如果應用程序中沒有自定義類加載器，一般情況下應用類加載器就是中默認的類加載器。自定義類加載器通過繼承 ClassLoader 并重寫 findClass 方法，調用 defineClass 方法實現。

雙親委派模型

類加載器具有等級制度，但并非繼承關系，以組合的方式來復用父加載器的功能，這也符合組合優先原則。雙親委派模型要求除了頂層的啟動類加載器外，其余的類加載器都應該有自己的父加載器。

如果一個類加載器收到了類加載請求，它不會自己去嘗試加載這個類，而首先將該請求委派給自己的父加載器完成，每一個層次的類加載器都是如此，因此所有的加載請求最終都應該傳送到最頂層的啟動類加載器中，只有當父加載器反饋自己無法完成請求時，子加載器才會嘗試自己完成加載。

好處是 Java 中的類跟隨它的類加載器一起具備了一種帶有優先級的層次關系，可以保證某個類在程序的各個類加載器環境中都是同一個類，對于保證程序的穩定運行極為重要。

比較兩個類是否相等

對于任意一個類，都必須由加載它的類加載器和這個類本身一起共同確立其在虛擬機中的唯一性，每一個類加載器都擁有一個獨立的類名稱空間。只有在兩個類是由同一個類加載器加載的前提下才有意義，否則即使兩個類來源于同一個 Class 文件，被同一個 JVM 加載，只要加載它們的類加載器不同，那這兩個類就必定不相等。

總結

以上是生活随笔為你收集整理的【备战秋招系列-3】Java高频知识点——排序、设计模式、JavaSE、JVM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。