數據結構學習基礎和從包裝類緩存到泛型擦除的避坑指南

1.數據結構的概念和算法

1.1 數據結構的概念?

1.2 數據結構的集合框架

1.3 算法?

?1.3.1 時間復雜度

1.3.2 空間復雜度?

?2.包裝類

2.1 為什么需要包裝類？

?2.2 裝箱和拆箱

?3. 初識泛型

?3.1 認識泛型

3.2 泛型類的使用?

3.3 泛型的編譯

3.4 通配符

?3.4.1 無界通配符

3.4.2 上界通配符?

3.4.3 下界通配符?

1.數據結構的概念和算法

1.1 數據結構的概念?

數據結構是程序的骨架，算法是程序的靈魂。什么是數據結構？

在《大話數據結構》這本書中，作者指出：數據結構是相互之間存在一種或多種特定關系的數據元素的集合。也就是說，數據結構是計算機中存儲、組織數據的方式。就像現實生活中我們使用文件夾整理文檔、用書架分類書籍一樣，程序也需要合理的方式管理數據。

1.2 數據結構的集合框架

數據結構的主要集合框架為上圖。

學習數據結構，就要了解以上集合框架圖的關系和每個具體的類是什么樣的數據結構。這個圖做一個簡單的了解即可，不必刻意深記，在后面的學習中都會詳細介紹。

1.3 算法?

?算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條指令表示一個或多個操作。

怎么衡量一個算法的好壞？這就要談到算法的效率。算法的效率分為兩種，一是時間效率，也稱為時間復雜度，二是空間效率，也稱為空間復雜度。二者通常用大O的漸進表示法來計算。

?1.3.1 時間復雜度

時間復雜度（Time Complexity）?是衡量算法執行時間隨輸入規模增長的變化趨勢的指標。它不計算具體的運行時間，而是描述算法在最壞或平均情況下執行基本操作的次數與輸入規模?n?的關系，通常用?大O符號（Big-O Notation）?表示。?

?大O漸進法怎么表示？

用常數 1 代替運行時間中的所有加法常數?
保留最高項，并且忽略最高項的系數

?怎么理解大O漸進表示？

通常在衡量一個算法的效率時，都是根據最壞情況去衡量。當然會有一些算法存在平均情況和最后情況。

最壞情況：任意輸入規模的最大允許次數

平均情況：任意輸入規模的期望運行次數

最壞情況：任意輸入規模的最小運行次數?

比如在一個長度為n的整數?升序?數組中，查找數組中是否存在某一個值時，如果按照線性查找的方式（從前到后或者從后到前）查找，那么最壞的可能是最后一個數組元素才是需要查找的值，或者這個數組本身就沒有這個值的時候，其時間復雜度便是達到?O(n) ，如果第一個元素就是要查找的值，這個時候就可以達到0(1) 。如果使用二分查找的方式（每次取這個數組的中間元素進行比較）進行查找，如果中間元素的值大于需要查找的值，則說明要查找的值在這個中間元素的左邊，那么下次查找只需要在左邊進行查找，依次類推，直到找到與需要查找的值相等或者最后一個元素為止，?這種方式時間復雜度最壞情況只有，同理，如果第一個元素就是要查找的值，這個時候就可以達到0(1) 。

1.3.2 空間復雜度?

?空間復雜度（Space Complexity）是衡量算法在運行過程中?臨時占用的內存空間?隨輸入規模（n）增長的變化趨勢。與時間復雜度類似，空間復雜度也用?大O表示法（Big-O Notation）?描述。

有一些說法是：空間復雜度就是計算變量的個數?。

這個說法并不完全正確，空間復雜度計算的是?算法運行過程中額外占用的內存空間，而不僅僅是變量的個數。變量個數是影響因素之一，還需考慮：

變量的規模（如數組、鏈表、遞歸棧等占用的空間與輸入規模?n?相關）。
數據結構的內存占用（如?HashMap?比?Array?更占空間）。
遞歸調用的棧空間（每次遞歸都會占用額外的棧幀）。

比如曾經在遞歸的學習中，計算第 n 項的斐波那契數時，當項數達到一定值時，就會發生棧溢出。這是因為每一次遞歸時，都會產生一個臨時的內存空間來存儲參數和返回地址等。

?2.包裝類

2.1 為什么需要包裝類？

在Java中，由于基本類型并不是繼承 Object 類，為了在泛型代碼中可以支持基本類型，Java為8種基本數據類型提供的對應的引用類型（對象類型），用于將基本類型“包裝”成對象。其基本數據類型?的對應的包裝類如下：

?可以看出，出來 int 和 char 的包裝類分別對應 Integer 和 Character ，其余的基本數據類型對應的包裝類都是首字母大寫。

那么，為什么需要包裝類呢？

1. Java是面向對象的語言，但是基本數據類型并不是對象。包裝類的作用：

存儲在集合中：如?List<Integer>（集合只能存對象，不能存基本類型）

調用對象方法：如?Integer.parseInt(String s)

支持泛型：泛型類型必須為對象（如?ArrayList<Integer>），而 ArrayList<int> 是錯誤的

如果沒有包裝類，就無法使用?ArrayList、HashMap?等集合存儲基本類型。

2. 允許null值

基本類型不能為null，但包裝類可以表示數據缺失或未初始化。

3. 提供豐富的工具方法

如 Integer.toBinaryString() ，可以把一個 int 類型的數據轉為二進制字符串，Character.isLetter() ，判斷一個字符是否為字母等

4. 自動裝箱和拆箱

?2.2 裝箱和拆箱

裝箱（Boxing）：將基本數據類型轉換為對應的包裝類對象。分為手動裝箱和自動裝箱。

public class Main {public static void main(String[] args) {int a = 10;//裝箱操作--手動裝箱Integer A11 = Integer.valueOf(a);Integer A12 = new Integer(a);//這種創建新對象已經過時，但是可以用//裝箱操作--自動裝箱Integer A21 = a;}
}

拆箱（Unboxing）：將包裝類對象轉換回基本數據類型。分為手動拆箱和自動拆箱。

public class Main {public static void main(String[] args) {Integer a = 10;//拆箱操作--手動拆箱int A = a.intValue();////拆箱操作--自動拆箱int B = a;//編譯器自動轉換}
}

注意事項：

1. 前面提到包裝類允許有 null ，但是如果把包裝類換成基本類型時，就會拋出異常NullPointerException?。

2.?部分包裝類（如Integer）緩存?-128 ~ 127?的值，超出范圍會新建對象：?

?觀察以下代碼：

public class Main {public static void main(String[] args) {Integer a = 100;Integer b = 100;Integer c = 200;Integer d = 200;System.out.println(a == b);//結果1：System.out.println(c == d);//結果2：System.out.println(a.equals(b));//結果3：System.out.println(c.equals(d));//結果4：}
}

?輸出結果：

?為什么 c 和 d 都等于200時，輸出結果卻是 false呢？這是因為Java 對?Integer?包裝類設計了緩存機制（范圍默認是?-128~127 )，當超出這個范圍后，就會 new 一個新的對象，而對于對象的比較，不能用 == ，要用?equals() 或者對其拆箱再用 == 進行比較。

?3. 初識泛型

?3.1 認識泛型

關于泛型的概念，在《Java編程思想》中這樣介紹：一般的類和方法，只能使用具體的類型，要么是基本類型，要么是自定義的類。如果要編寫可以應用于多種類型的代碼，這種刻板的限制對代碼的束縛就會很大。也就是說，泛型的出現，是為了適用于許多種的類型。

當需要什么樣的類型時，就傳遞什么類型即可，包括 Integer、Character 等，也可以是自定義的類，使用泛型，可以在編譯時檢查類型匹配，避免運行時發生異常?ClassCastException

語法：

class? 泛型名稱 <類型形參列表> {

? ? ? ?//使用的類型參數

}?

比如在實現一個通用的哈希桶（在后面會學習到）時，就可以有以下代碼：

public class HashBuck<K,V> {static class Node<K, V> {public K key;public V val;public Node<K, V> next;public Node(K key , V val) {this.key = key;this.val = val;}}//往后實現具體方法等....
}

?泛型類用尖括號 <類型形參列表> 來表示，類型形參一般用大寫字母表示，常用的名稱有：

E：表示Element
K：表示Key
V：表示Value
N：表示Number
T：表示Type等

3.2 泛型類的使用?

語法：

泛型類<類型實參> 變量名；//定義一個泛型類引用

new 泛型類<類型實參>(構造方法實參);//實例化一個泛型類對象，實例化的泛型實參和構造方法可以沒有??

?泛型類也是一個類，在使用泛型時要 new 一個新的對象。如

ArrayList<Integer> list = new ArrayList<>();

3.3 泛型的編譯

?Java 泛型的核心在于編譯時的類型檢查和運行時的類型擦除。

類型擦除的原則（和繼承類似）：

無邊界類型參數

? ? ? ? 對于沒有邊界的泛型類（如<T>），在編譯時都會默認上界是 Object 類，也就是上 T 全部變為Object ，因為 Object 類?是所有類的父類

有上界的類型參數

? ? ? ? 對于有上界的泛型類（如T? extends? Numbers），編譯時 T 會替換成 Number。

泛型方法

? ? ? ? 編譯后，方法簽名中的?<T>被移除，參數和返回值的T替換為Object或上界。

// 源碼（編譯前）
public class Box<T> {private T value;public void set(T value) {this.value = value;}public T get() {return value;}
}// 字節碼（編譯后，等效代碼）
public class Box {private Object value; // T被擦除為Objectpublic void set(Object value) {this.value = value;}public Object get() {return value;}
}

?因此，List<String>和?List<Integer>的類對象是相同的，因為類型擦除，編譯后<String>、<Integer>）將被替換為原始類型（Object?或指定的上界類型），運行時均為List.class。