前言

Java 中的數(shù)據(jù)結(jié)構(gòu)是用來存儲(chǔ)和組織數(shù)據(jù)的方式，不同的數(shù)據(jù)結(jié)構(gòu)適用于不同的場(chǎng)景。數(shù)據(jù)結(jié)構(gòu)的理解非常重要，如果哪里寫的不對(duì)，請(qǐng)指出。

一、數(shù)組（Array）

數(shù)組是一種線性表，就是數(shù)據(jù)排列成一條直線一樣的結(jié)構(gòu)。在內(nèi)容空間中，數(shù)組的表現(xiàn)是一塊連續(xù)的內(nèi)存和儲(chǔ)存有相同的數(shù)據(jù)類型。正因?yàn)檫@個(gè)特性，數(shù)組可以實(shí)現(xiàn)通過索引下標(biāo)，在O(1)的時(shí)間復(fù)雜度內(nèi)快速檢索某個(gè)數(shù)據(jù)，這就是“隨機(jī)訪問”。但是由于內(nèi)存空間是連續(xù)的，所以數(shù)組在進(jìn)行插入和刪除操作時(shí)，就需要對(duì)數(shù)據(jù)進(jìn)行維護(hù)，進(jìn)行大量的數(shù)據(jù)搬移工作。

數(shù)組初始化的方式

使用動(dòng)態(tài)初始化
動(dòng)態(tài)初始化是指先使用 new 關(guān)鍵字指定數(shù)組的長(zhǎng)度，之后再為數(shù)組元素賦值。

public class ArrayDynamicInitialization {
    public static void main(String[] args) {
        // 動(dòng)態(tài)初始化一個(gè)長(zhǎng)度為 5 的整型數(shù)組
        int[] arr = new int[5];
        // 為數(shù)組元素賦值
        arr[0] = 1;
        arr[1] = 2;
        // 輸出數(shù)組元素
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}    

使用靜態(tài)初始化
靜態(tài)初始化時(shí)，無需使用 new 關(guān)鍵字顯式指定數(shù)組長(zhǎng)度，而是直接在聲明數(shù)組的同時(shí)為其元素賦值。

public class ArrayStaticInitialization {
    public static void main(String[] args) {
        // 靜態(tài)初始化一個(gè)整型數(shù)組
        int[] arr = {1, 2, 3, 4, 5};
        // 輸出數(shù)組元素
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

注意：如果聲明了數(shù)組但沒有進(jìn)行初始化就直接使用，會(huì)導(dǎo)致編譯通過，但在運(yùn)行時(shí)拋出 NullPointerException 異常。

數(shù)組能否存儲(chǔ)空值（null）

基本類型數(shù)組不能存儲(chǔ) null 值。Java 中的基本數(shù)據(jù)類型（如 int、double、char 等）有其對(duì)應(yīng)的默認(rèn)值，當(dāng)創(chuàng)建基本類型數(shù)組時(shí)，數(shù)組元素會(huì)被初始化為這些默認(rèn)值，而不能將 null 賦值給它們。
例如：

public class PrimitiveArrayNull {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè) int 類型的數(shù)組
        int[] intArray = new int[3];
        // 嘗試將 null 賦值給基本類型數(shù)組元素，會(huì)導(dǎo)致編譯錯(cuò)誤
        // intArray[0] = null; 
        // 基本類型數(shù)組元素有默認(rèn)值，int 類型默認(rèn)值為 0
        System.out.println(intArray[0]); 
    }
}    

引用類型數(shù)組可以存儲(chǔ) null 值。引用類型數(shù)組的元素存儲(chǔ)的是對(duì)象的引用，null 表示該引用不指向任何對(duì)象。
例如：

class Person {
    private String name;
    public Person(String name) {
        this.name = name;
    }
    public String getName() {
        return name;
    }
}
public class ReferenceArrayNull {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè) Person 類型的數(shù)組
        Person[] personArray = new Person[3];
        // 可以將 null 賦值給引用類型數(shù)組元素
        personArray[0] = null; 
        // 創(chuàng)建一個(gè) Person 對(duì)象并賦值給數(shù)組元素
        personArray[1] = new Person("Alice");
        // 輸出數(shù)組元素
        for (int i = 0; i < personArray.length; i++) {
            if (personArray[i] != null) {
                System.out.println(personArray[i].getName());
            } else {
                System.out.println("Element at index " + i + " is null");
            }
        }
    }
}    

Java中的包裝類是引用數(shù)據(jù)類型‌。包裝類（Wrapper Classes）是為Java中的8種基本數(shù)據(jù)類型（boolean、char、byte、short、int、long、float、double）分別定義的對(duì)應(yīng)引用類型。這些包裝類包括：Boolean、Character、Byte、Short、Integer、Long、Float、Double‌。
包裝類的作用是將基本數(shù)據(jù)類型轉(zhuǎn)換為引用數(shù)據(jù)類型，以便在泛型和集合中使用。通過包裝類，可以將基本數(shù)據(jù)類型作為對(duì)象處理，從而可以使用對(duì)象的屬性和方法。例如，Integer類提供了將字符串轉(zhuǎn)換為整數(shù)的靜態(tài)方法valueOf()，以及將整數(shù)轉(zhuǎn)換為字符串的toString()方法‌。

內(nèi)置方法

新增
數(shù)組沒有內(nèi)置的新增方法，只能根據(jù)索引賦值，（如 arr[0] = 10;）。

刪除
數(shù)組沒有內(nèi)置的刪除方法，不過，你可以通過一些間接的方法來模擬刪除操作。如果需要頻繁進(jìn)行刪除操作，使用 Java 的集合類（如 ArrayList）會(huì)更方便。
例如：
創(chuàng)建一個(gè)新數(shù)組，把原數(shù)組中除了要?jiǎng)h除元素之外的其他元素復(fù)制到新數(shù)組中。

public class DeleteElementByNewArray {
    public static void main(String[] args) {
        int[] originalArray = {1, 2, 3, 4, 5};
        int indexToDelete = 2; // 要?jiǎng)h除元素的索引
        int[] newArray = new int[originalArray.length - 1];
        int newIndex = 0;
        for (int i = 0; i < originalArray.length; i++) {
            if (i != indexToDelete) {
                newArray[newIndex] = originalArray[i];
                newIndex++;
            }
        }
        // 輸出新數(shù)組元素
        for (int element : newArray) {
            System.out.println(element);
        }
    }
}    

修改
數(shù)組沒有內(nèi)置的修改方法，只能覆蓋值，通過索引賦值（如 arr[0] = 10;）是唯一修改數(shù)組元素的方式。

查詢
數(shù)組沒有內(nèi)置專門用于查詢特定元素是否存在或獲取元素位置的方法，通過循環(huán)遍歷數(shù)組中的每一個(gè)元素，將其與目標(biāo)元素進(jìn)行比較，從而判斷數(shù)組中是否包含該元素，或者找到元素所在的位置。

遍歷
數(shù)組沒有內(nèi)置的遍歷方法，只能通過傳統(tǒng) for 循環(huán)，或增強(qiáng) for 循環(huán)（for - each 循環(huán)）實(shí)現(xiàn)數(shù)組的遍歷。

擴(kuò)容
無法直接擴(kuò)容：數(shù)組沒有像 ArrayList 的 add() 方法那樣的動(dòng)態(tài)擴(kuò)容機(jī)制。

存儲(chǔ)位置

不管是基本類型的數(shù)組還是其他對(duì)象數(shù)組，都會(huì)存于堆內(nèi)存。棧內(nèi)存里只存放指向這些數(shù)組對(duì)象的引用， 通過引用可以在程序中對(duì)數(shù)組對(duì)象進(jìn)行操作。

數(shù)組對(duì)象存于堆內(nèi)存

堆內(nèi)存是用于存儲(chǔ)對(duì)象實(shí)例的區(qū)域。數(shù)組本質(zhì)上也是對(duì)象，不管是基本類型（如 int、char 等）的數(shù)組，還是對(duì)象類型（如自定義類、String 等）的數(shù)組，都是通過 new 關(guān)鍵字或者靜態(tài)初始化（編譯器會(huì)隱式轉(zhuǎn)換為 new 操作）來創(chuàng)建的，而使用 new 操作創(chuàng)建的對(duì)象都會(huì)被分配到堆內(nèi)存中。
對(duì)于對(duì)象類型，這些引用也存儲(chǔ)在堆上的數(shù)組對(duì)象內(nèi)部；而對(duì)象實(shí)體本身則可能（但不是一定）存儲(chǔ)在堆上。

棧內(nèi)存存放數(shù)組對(duì)象引用

棧內(nèi)存主要用于存儲(chǔ)局部變量和方法調(diào)用的上下文信息。當(dāng)在方法內(nèi)部聲明一個(gè)數(shù)組變量時(shí)，這個(gè)變量實(shí)際上是一個(gè)引用類型的變量，它存儲(chǔ)在棧內(nèi)存中，其值是指向堆內(nèi)存中數(shù)組對(duì)象的地址。
在程序中，對(duì)數(shù)組對(duì)象的各種操作（如訪問元素、修改元素值等）都是通過棧內(nèi)存中的引用進(jìn)行的。

優(yōu)點(diǎn)和影響
動(dòng)態(tài)內(nèi)存分配： 堆內(nèi)存允許在運(yùn)行時(shí)動(dòng)態(tài)分配和釋放內(nèi)存，使得數(shù)組的大小可以根據(jù)程序的需求進(jìn)行調(diào)整（雖然 Java 數(shù)組本身大小固定，但可以通過創(chuàng)建新數(shù)組并復(fù)制元素來模擬動(dòng)態(tài)調(diào)整）。

多方法共享對(duì)象： 不同的方法可以通過引用訪問同一個(gè)堆內(nèi)存中的數(shù)組對(duì)象，實(shí)現(xiàn)數(shù)據(jù)的共享和傳遞。
不過，也存在一些潛在的問題，比如堆內(nèi)存的垃圾回收機(jī)制會(huì)帶來一定的性能開銷，需要合理管理對(duì)象的生命周期以避免內(nèi)存泄漏。

數(shù)組特性：

查詢和修改速度快

連續(xù)內(nèi)存存儲(chǔ)：數(shù)組在內(nèi)存中是一段連續(xù)的存儲(chǔ)空間，每個(gè)元素在內(nèi)存中依次排列
高效的地址計(jì)算：根據(jù)數(shù)組的起始地址和元素的索引，能通過簡(jiǎn)單的計(jì)算快速定位到元素的位置。假設(shè)數(shù)組的起始地址是 baseAddress，每個(gè) int 類型元素占用 4 個(gè)字節(jié)，要訪問索引為 i 的元素，其內(nèi)存地址可以通過公式 baseAddress + i * 4 計(jì)算得出。這種基于地址計(jì)算的訪問方式時(shí)間復(fù)雜度是 O(1)，意味著無論數(shù)組的長(zhǎng)度是多少，訪問任意元素的時(shí)間都是固定的，所以查詢速度非?？臁?br />直接覆蓋值：修改數(shù)組元素時(shí)，只需定位到該元素的內(nèi)存位置，然后將新的值覆蓋原來的值即可。由于查詢?cè)匚恢玫牟僮骱芸?，所以修改操作也能快速完成，時(shí)間復(fù)雜度同樣為 O(1)。

增加和刪除操作慢

插入操作：在數(shù)組中插入元素時(shí)，通常需要將插入位置之后的所有元素向后移動(dòng)，為新元素騰出空間。
刪除操作：刪除數(shù)組中的元素時(shí)，需要將刪除位置之后的所有元素向前移動(dòng)，填補(bǔ)刪除元素所留下的空位。
擴(kuò)容問題：如果數(shù)組容量不足，在增加元素時(shí)還需要進(jìn)行擴(kuò)容操作。通常的做法是創(chuàng)建一個(gè)更大的新數(shù)組，再把原數(shù)組的元素復(fù)制到新數(shù)組中，這也會(huì)增加操作的時(shí)間復(fù)雜度。

基礎(chǔ)數(shù)組，在增加和刪除，以及擴(kuò)容上，其實(shí)不符合數(shù)據(jù)結(jié)構(gòu)中對(duì)數(shù)組的定義，因?yàn)樵臄?shù)組沒有增加和刪除方法，也不能自動(dòng)擴(kuò)容。

在深入一些，數(shù)組的底層代碼數(shù)據(jù)結(jié)構(gòu)

在 Java 里，數(shù)組實(shí)際上是一個(gè)對(duì)象。每個(gè)數(shù)組對(duì)象都包含一個(gè)頭部信息和元素?cái)?shù)據(jù)區(qū)。
頭部信息： 包含數(shù)組的一些元數(shù)據(jù)，例如數(shù)組的長(zhǎng)度。這個(gè)長(zhǎng)度信息在數(shù)組創(chuàng)建時(shí)就被確定，并且后續(xù)無法更改?？梢酝ㄟ^數(shù)組對(duì)象的 length 屬性來獲取這個(gè)長(zhǎng)度值，像 arr.length 就能得到數(shù)組 arr 的長(zhǎng)度。
元素?cái)?shù)據(jù)區(qū)： 數(shù)組的元素存儲(chǔ)在連續(xù)的內(nèi)存塊中。對(duì)于基本數(shù)據(jù)類型的數(shù)組（如int[]、double[]等），這些元素直接存儲(chǔ)在這個(gè)內(nèi)存塊中。對(duì)于對(duì)象數(shù)組（如Object[]、String[]等），這些對(duì)象引用存儲(chǔ)在內(nèi)存塊中，而對(duì)象本身一般存儲(chǔ)在堆內(nèi)存中。

多維數(shù)組

Java 支持多維數(shù)組，多維數(shù)組本質(zhì)上是數(shù)組的數(shù)組。例如，二維數(shù)組可以看作是由多個(gè)一維數(shù)組組成的。

int[][] twoDArray = new int[3][4];

這里創(chuàng)建了一個(gè) 3 行 4 列的二維數(shù)組。在底層，它首先是一個(gè)包含 3 個(gè)元素的一維數(shù)組，每個(gè)元素又是一個(gè)包含 4 個(gè) int 類型元素的一維數(shù)組。每個(gè)一維子數(shù)組在內(nèi)存中也是連續(xù)存儲(chǔ)的，但不同的一維子數(shù)組在內(nèi)存中不一定是連續(xù)的。

二、鏈表

在 Java 里，鏈表主要有三種，分別是單向鏈表、雙向鏈表和循環(huán)鏈表。鏈表的節(jié)點(diǎn)和數(shù)組一樣，都存儲(chǔ)在堆內(nèi)存中。鏈表的每個(gè)節(jié)點(diǎn)都是獨(dú)立的對(duì)象，通過引用相互連接，數(shù)組是連續(xù)內(nèi)存，而鏈表是不連續(xù)內(nèi)存。

單向鏈表

結(jié)構(gòu)特點(diǎn)
單向鏈表由一系列節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)包含兩部分：數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的引用（指針）。鏈表的第一個(gè)節(jié)點(diǎn)稱為頭節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的引用指向 null，表示鏈表的結(jié)束。
插入和刪除操作： 在已知節(jié)點(diǎn)的情況下，在鏈表中間插入或刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1)，因?yàn)橹恍枰薷墓?jié)點(diǎn)的引用。但如果要在指定位置插入或刪除節(jié)點(diǎn)，需要先遍歷鏈表找到該位置，此時(shí)時(shí)間復(fù)雜度為 O(n)。
查詢操作： 由于單向鏈表只能從頭節(jié)點(diǎn)開始依次遍歷，所以查詢指定位置或值的節(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n)。
空間開銷： 每個(gè)節(jié)點(diǎn)只需要額外存儲(chǔ)一個(gè)指向下一個(gè)節(jié)點(diǎn)的引用，空間開銷相對(duì)較小。

雙向鏈表

結(jié)構(gòu)特點(diǎn)
雙向鏈表的節(jié)點(diǎn)除了包含數(shù)據(jù)域和指向下一個(gè)節(jié)點(diǎn)的引用外，還包含一個(gè)指向前一個(gè)節(jié)點(diǎn)的引用。這使得鏈表可以雙向遍歷，既可以從頭節(jié)點(diǎn)開始向后遍歷，也可以從尾節(jié)點(diǎn)開始向前遍歷。
插入和刪除操作： 在已知節(jié)點(diǎn)的情況下，插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為
O(1)，因?yàn)榭梢灾苯有薷那昂蠊?jié)點(diǎn)的引用。同樣，如果要在指定位置插入或刪除節(jié)點(diǎn)，需要先遍歷鏈表找到該位置，時(shí)間復(fù)雜度為 O(n)。
查詢操作： 查詢指定位置或值的節(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n)，但可以根據(jù)節(jié)點(diǎn)的位置選擇從頭部或尾部開始遍歷，在某些情況下可以提高查詢效率。
空間開銷： 每個(gè)節(jié)點(diǎn)需要額外存儲(chǔ)兩個(gè)引用（指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)），空間開銷相對(duì)單向鏈表較大。

循環(huán)鏈表

結(jié)構(gòu)特點(diǎn)
循環(huán)鏈表分為單向循環(huán)鏈表和雙向循環(huán)鏈表。單向循環(huán)鏈表中，最后一個(gè)節(jié)點(diǎn)的引用指向頭節(jié)點(diǎn)，形成一個(gè)閉環(huán)；雙向循環(huán)鏈表中，頭節(jié)點(diǎn)的前一個(gè)引用指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的后一個(gè)引用指向頭節(jié)點(diǎn)。
插入和刪除操作： 與單向鏈表和雙向鏈表類似，在已知節(jié)點(diǎn)的情況下，插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1)，但在指定位置插入或刪除節(jié)點(diǎn)需要先遍歷鏈表，時(shí)間復(fù)雜度為 O(n)。
查詢操作： 查詢指定位置或值的節(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n)，由于鏈表是循環(huán)的，在遍歷過程中需要注意避免陷入無限循環(huán)。
應(yīng)用場(chǎng)景： 循環(huán)鏈表適用于需要循環(huán)訪問數(shù)據(jù)的場(chǎng)景，如實(shí)現(xiàn)循環(huán)隊(duì)列、游戲中的循環(huán)角色列表等。

數(shù)組與鏈表的區(qū)別是什么？

內(nèi)存分配：
數(shù)組在內(nèi)存中是連續(xù)分配的，而鏈表的節(jié)點(diǎn)在內(nèi)存中不一定連續(xù)，通過指針相互連接。
隨機(jī)訪問：
數(shù)組支持隨機(jī)訪問，通過索引可以直接訪問數(shù)組中的元素，時(shí)間復(fù)雜度為 O (1)。鏈表不支持隨機(jī)訪問，要訪問某個(gè)節(jié)點(diǎn)，需要從鏈表頭開始遍歷，時(shí)間復(fù)雜度為 O (n)。
插入和刪除操作：
在數(shù)組中間插入或刪除元素時(shí)，需要移動(dòng)大量元素，時(shí)間復(fù)雜度為 O (n)。鏈表在插入和刪除節(jié)點(diǎn)時(shí)，只需修改相關(guān)節(jié)點(diǎn)的指針，時(shí)間復(fù)雜度為 O (1)（前提是已經(jīng)找到要操作節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)）。
內(nèi)存空間：
數(shù)組需要預(yù)先分配固定大小的內(nèi)存空間，如果元素?cái)?shù)量不確定，可能會(huì)造成內(nèi)存浪費(fèi)或溢出。鏈表則根據(jù)需要?jiǎng)討B(tài)分配內(nèi)存，靈活性更高，但每個(gè)節(jié)點(diǎn)需要額外的空間存儲(chǔ)指針。

三、Collection （單列集合）

List接口：

List是一個(gè)有序的集合，允許重復(fù)元素，并且每個(gè)元素都有一個(gè)位置索引。

ArrayList:

底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快，增刪慢，線程不安全，效率高，可以存儲(chǔ)重復(fù)元素。

ArrayList擴(kuò)容機(jī)制
ArrayList 的底層是基于數(shù)組實(shí)現(xiàn)的，當(dāng)向 ArrayList 中添加元素時(shí)，如果當(dāng)前數(shù)組的容量不足以容納新元素，就會(huì)觸發(fā)擴(kuò)容操作。
具體的擴(kuò)容步驟如下：
計(jì)算新容量：默認(rèn)情況下，新容量是舊容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。例如，初始容量為 10，當(dāng)添加第 11 個(gè)元素時(shí)，會(huì)觸發(fā)擴(kuò)容，新容量為 10 + (10 >> 1) = 15。
創(chuàng)建新數(shù)組： 根據(jù)計(jì)算得到的新容量，創(chuàng)建一個(gè)新的數(shù)組。
復(fù)制元素： 將舊數(shù)組中的元素復(fù)制到新數(shù)組中。
更新引用： 將 ArrayList 內(nèi)部的數(shù)組引用指向新數(shù)組。

LinkedList:

底層數(shù)據(jù)結(jié)構(gòu)是雙向鏈表，查詢慢，增刪快，線程不安全.效率高，可以存儲(chǔ)重復(fù)元素。

LinkedList不存在 “擴(kuò)容” 概念的原因
與 ArrayList 基于數(shù)組實(shí)現(xiàn)不同，LinkedList 是基于鏈表實(shí)現(xiàn)的。數(shù)組在創(chuàng)建時(shí)需要指定固定的長(zhǎng)度，當(dāng)元素?cái)?shù)量超過數(shù)組容量時(shí)，需要?jiǎng)?chuàng)建一個(gè)更大的數(shù)組并將原數(shù)組元素復(fù)制過去，這就是 ArrayList 的擴(kuò)容機(jī)制。而 LinkedList 中的節(jié)點(diǎn)是動(dòng)態(tài)分配內(nèi)存的，每添加一個(gè)新元素，就會(huì)創(chuàng)建一個(gè)新的節(jié)點(diǎn)對(duì)象，并將其插入到鏈表中，不需要預(yù)先分配固定大小的內(nèi)存空間，因此不存在擴(kuò)容的問題。只要系統(tǒng)的內(nèi)存足夠，就可以不斷地向 LinkedList 中添加元素。

Vector:

底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快.，增刪慢. 線程安全，它通過在方法上使用 synchronized 關(guān)鍵字來保證線程安全，效率低，可以存儲(chǔ)重要元素。

在選擇線程安全的 List 時(shí)，需要根據(jù)具體的業(yè)務(wù)場(chǎng)景來決定：
如果對(duì)性能要求不高，且使用簡(jiǎn)單，可以選擇 Vector。
如果需要將現(xiàn)有的非線程安全的 List 轉(zhuǎn)換為線程安全的，可以使用 Collections.synchronizedList。
如果是讀多寫少的場(chǎng)景，CopyOnWriteArrayList 是一個(gè)更好的選擇。

CopyOnWriteArrayList ：
是 Java 并發(fā)包（java.util.concurrent）中提供的線程安全的 List 實(shí)現(xiàn)。它采用==寫時(shí)復(fù)制（Copy-On-Write）==的策略，當(dāng)進(jìn)行寫操作（如 add、remove 等）時(shí)，會(huì)先將原數(shù)組復(fù)制一份，在新數(shù)組上進(jìn)行操作，操作完成后再將原數(shù)組的引用指向新數(shù)組。讀操作則直接在原數(shù)組上進(jìn)行，不需要加鎖。
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：讀操作不需要加鎖，并發(fā)讀的性能非常高，適用于讀多寫少的場(chǎng)景。
缺點(diǎn)：寫操作需要復(fù)制數(shù)組，會(huì)占用額外的內(nèi)存空間，并且寫操作的性能較低。同時(shí)，由于寫時(shí)復(fù)制的特性，迭代器遍歷的是創(chuàng)建迭代器時(shí)的數(shù)組副本，可能無法反映最新的修改。

Set接口：

Set是一個(gè)不包含重復(fù)元素的集合，沒有順序的概念。

HashSet:

hashSet 是基于哈希表的 Set 實(shí)現(xiàn)，提供了快速查找、添加和刪除性能，但它不保證元素的順序，并允許一個(gè) null 元素。

LinkedHashSet:

LinkedHashSet 繼承自 HashSet，并且維護(hù)了一個(gè)雙向鏈表來記錄插入順序，因此它既保持了插入順序又具備 HashSet 的高效性能。

TreeSet :

TreeSet 實(shí)現(xiàn)了 SortedSet 接口，能夠?qū)υ剡M(jìn)行排序，默認(rèn)按照自然順序或根據(jù)提供的比較器進(jìn)行排序。底層使用紅黑樹數(shù)據(jù)結(jié)構(gòu)，保證了對(duì)數(shù)級(jí)別的性能。

TreeSet 的對(duì)數(shù)級(jí)性能意味著其操作時(shí)間與數(shù)據(jù)規(guī)模的對(duì)數(shù)成正比，這使得它在需要排序和高效操作的場(chǎng)景中表現(xiàn)優(yōu)異。紅黑樹的自平衡特性是實(shí)現(xiàn)這一性能的關(guān)鍵。

安全的ConcurrentSkipListSet
ConcurrentSkipListSet 是線程安全的 SortedSet 實(shí)現(xiàn)，基于跳表（Skip List）結(jié)構(gòu)，支持并發(fā)訪問而不需要外部同步。采用了無鎖算法（基于 CAS，Compare-And-Swap）來保證并發(fā)操作的線程安全性，避免了傳統(tǒng)鎖機(jī)制帶來的性能開銷。

跳表是什么，下次再更

Queue接口：

隊(duì)列是一個(gè)典型的先進(jìn)先出的容器，常被當(dāng)作一種可靠的將對(duì)象從程序的某個(gè)區(qū)城傳輸?shù)搅?區(qū)域的途徑.，在并發(fā)編程中特別重要。

四、Map（雙列集合）

Map保存具有映射關(guān)系的數(shù)據(jù)。 key和value。 key不能重復(fù)，沒有繼承Collection接口。

HashMap

HashMap中的對(duì)象并不是線程安全的，最多只有一個(gè)key值為null。但可以有多個(gè)value值為null，性能最好。HashMap 允許 key 為 “”，并且可以和其他鍵同時(shí)存在，因?yàn)榭兆址彩且粋€(gè)有效的鍵。
底層結(jié)構(gòu)： 基于數(shù)組 + 鏈表 + 紅黑樹實(shí)現(xiàn)。數(shù)組作為哈希桶，鏈表用于解決哈希沖突，當(dāng)鏈表長(zhǎng)度超過 8 且數(shù)組長(zhǎng)度大于 64 時(shí)，鏈表會(huì)轉(zhuǎn)化為紅黑樹，以提升查找性能。
擴(kuò)容觸發(fā)條件： HashMap 有兩個(gè)關(guān)鍵參數(shù)，初始容量（默認(rèn) 16）和負(fù)載因子（默認(rèn) 0.75）。當(dāng)元素?cái)?shù)量超過閾值（閾值 = 容量 × 負(fù)載因子）時(shí)，就會(huì)觸發(fā)擴(kuò)容操作。
擴(kuò)容步驟
創(chuàng)建新數(shù)組：新數(shù)組的容量是原數(shù)組的 2 倍。
重新計(jì)算哈希值并遷移元素：將原數(shù)組中的元素重新計(jì)算哈希值，然后根據(jù)新的哈希值插入到新數(shù)組的相應(yīng)位置。對(duì)于鏈表節(jié)點(diǎn)，會(huì)根據(jù)新的哈希值拆分成兩個(gè)鏈表；對(duì)于紅黑樹節(jié)點(diǎn)，會(huì)拆分成兩個(gè)紅黑樹或鏈表。

LinkedHashMap

LinkedHashMap 結(jié)合了哈希表和雙向鏈表的特性。它不僅像 HashMap 一樣可以快速地存儲(chǔ)和檢索鍵值對(duì)，還能維護(hù)鍵值對(duì)的插入順序（默認(rèn)）或者訪問順序。
底層結(jié)構(gòu)： 繼承自 HashMap，在 HashMap 的基礎(chǔ)上維護(hù)了一個(gè)雙向鏈表，用于記錄元素的插入順序或訪問順序。
擴(kuò)容觸發(fā)條件： 和 HashMap 一致，當(dāng)元素?cái)?shù)量超過閾值時(shí)觸發(fā)擴(kuò)容。
擴(kuò)容步驟： 和 HashMap 相同，創(chuàng)建新數(shù)組，重新計(jì)算哈希值并遷移元素，同時(shí)維護(hù)雙向鏈表的順序。

Hashtable

是同步的.這個(gè)類中的-些方法加入了synchronized關(guān)鍵字，保證了
Hashtable中的對(duì)象是線程安全的，性能最差，
Hashtable 不允許 key 為 null。當(dāng)嘗試將 null 作為 key 插入 Hashtable 時(shí)，會(huì)拋出 NullPointerException。這是因?yàn)?Hashtable 的 put 方法內(nèi)部會(huì)對(duì) key 進(jìn)行 null 檢查。
Hashtable 允許 key 為 “”，可以正常存儲(chǔ)和訪問。
底層結(jié)構(gòu)： 基于數(shù)組 + 鏈表實(shí)現(xiàn)，通過 synchronized 保證線程安全。
擴(kuò)容觸發(fā)條件：當(dāng)元素?cái)?shù)量超過閾值（閾值 = 容量 × 負(fù)載因子，默認(rèn)負(fù)載因子為 0.75）時(shí)，觸發(fā)擴(kuò)容。
擴(kuò)容步驟 創(chuàng)建新數(shù)組：新數(shù)組容量為原數(shù)組的 2 倍 + 1。
重新計(jì)算哈希值并遷移元素：將原數(shù)組元素重新計(jì)算哈希值，插入到新數(shù)組相應(yīng)位置。

TreeMap

底層基于 紅黑樹（Red-Black Tree） 實(shí)現(xiàn)，這是一種自平衡的二叉搜索樹。紅黑樹的性質(zhì)確保了鍵的有序性，每個(gè)節(jié)點(diǎn)存儲(chǔ)的是 Entry<K, V> 對(duì)象，其中 K 是鍵，V 是值。
TreeMap 不允許 key 為 null，因?yàn)?TreeMap 基于紅黑樹實(shí)現(xiàn)，需要對(duì) key 進(jìn)行比較排序，而 null 無法參與比較，所以如果嘗試將 null 作為 key 插入 TreeMap，會(huì)拋出 NullPointerException。
TreeMap 允許 key 為 “”，它會(huì)根據(jù)鍵的自然順序或指定的比較器對(duì)空字符串鍵進(jìn)行排序存儲(chǔ)。
底層結(jié)構(gòu)： 基于紅黑樹實(shí)現(xiàn)，元素按照鍵的自然順序或指定的比較器順序排序。
擴(kuò)容機(jī)制： TreeMap 不存在像數(shù)組那樣的擴(kuò)容概念。紅黑樹是動(dòng)態(tài)調(diào)整結(jié)構(gòu)的，插入和刪除元素時(shí)會(huì)通過旋轉(zhuǎn)和變色操作來保持樹的平衡。

在選擇線程安全的 Map 時(shí)，需要根據(jù)具體的業(yè)務(wù)場(chǎng)景來決定：
如果對(duì)性能要求不高，且使用簡(jiǎn)單，可以選擇 Hashtable。
如果需要將現(xiàn)有的非線程安全的 Map 轉(zhuǎn)換為線程安全的，可以使用 Collections.synchronizedMap。
如果是高并發(fā)的讀寫場(chǎng)景，ConcurrentHashMap 是一個(gè)不錯(cuò)的選擇。
如果需要鍵有序且支持并發(fā)操作，可以選擇 ConcurrentSkipListMap。

安全的map

ConcurrentHashMap
原理： ConcurrentHashMap 是 Java 并發(fā)包（java.util.concurrent）中提供的線程安全的 Map 實(shí)現(xiàn)。在 Java 7 及以前，它采用分段鎖機(jī)制，將整個(gè) Map 分成多個(gè)段（Segment），不同的段可以被不同的線程同時(shí)訪問，從而提高并發(fā)性能。在 Java 8 及以后，ConcurrentHashMap 采用了 CAS（Compare-And-Swap）和 synchronized 來實(shí)現(xiàn)并發(fā)控制，進(jìn)一步優(yōu)化了性能。
ConcurrentHashMap不允許 key 為 null。因?yàn)?ConcurrentHashMap 是為多線程環(huán)境設(shè)計(jì)的，null 可能會(huì)導(dǎo)致歧義，例如在 get 方法返回 null 時(shí)，無法確定是鍵不存在還是值為 null，所以不允許 key 為 null。
ConcurrentHashMap 允許 key 為 “”，可以正常存儲(chǔ)和訪問。
底層結(jié)構(gòu)： Java 8 及之后版本采用數(shù)組 + 鏈表 + 紅黑樹的結(jié)構(gòu)，通過 CAS 和 synchronized 保證線程安全。
擴(kuò)容觸發(fā)條件： 和 HashMap 類似，當(dāng)元素?cái)?shù)量超過閾值時(shí)會(huì)觸發(fā)擴(kuò)容。此外，插入元素時(shí)若發(fā)現(xiàn)鏈表長(zhǎng)度超過 8 且數(shù)組長(zhǎng)度小于 64，會(huì)先嘗試擴(kuò)容數(shù)組而非將鏈表轉(zhuǎn)為紅黑樹。
擴(kuò)容步驟 創(chuàng)建新數(shù)組：新數(shù)組容量為原數(shù)組的 2 倍。
多線程協(xié)助遷移元素：一個(gè)線程發(fā)現(xiàn)需要擴(kuò)容時(shí)，先創(chuàng)建新數(shù)組并標(biāo)記擴(kuò)容戳。其他線程在插入元素時(shí)若發(fā)現(xiàn)正在擴(kuò)容，會(huì)協(xié)助進(jìn)行元素遷移。每個(gè)線程負(fù)責(zé)遷移一段連續(xù)的桶，遷移完成后將原數(shù)組對(duì)應(yīng)桶置為 null。

ConcurrentSkipListMap
原理： ConcurrentSkipListMap 也是 Java 并發(fā)包中的線程安全的 Map 實(shí)現(xiàn)，它基于跳表（Skip List）數(shù)據(jù)結(jié)構(gòu)。跳表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)中維護(hù)多個(gè)指向其他節(jié)點(diǎn)的指針，從而可以在 O(logn) 的平均時(shí)間復(fù)雜度內(nèi)完成插入、刪除和查找操作。ConcurrentSkipListMap 的鍵是有序的，默認(rèn)按照鍵的自然順序排序，也可以通過構(gòu)造函數(shù)傳入 Comparator 來指定排序規(guī)則。

ConcurrentSkipListMap不允許 key 為 null。ConcurrentSkipListMap 實(shí)現(xiàn)了 SortedMap 接口，它會(huì)對(duì) key 進(jìn)行排序。其底層基于跳表（Skip List）數(shù)據(jù)結(jié)構(gòu)，排序操作依賴于 key 實(shí)現(xiàn) Comparable 接口或者在創(chuàng)建 ConcurrentSkipListMap 時(shí)傳入一個(gè) Comparator 來定義排序規(guī)則。由于 null 無法與其他對(duì)象進(jìn)行比較，所以不能作為 key 使用。
在多線程環(huán)境下，如果允許 key 為 null，在進(jìn)行查找、插入等操作時(shí)會(huì)產(chǎn)生歧義。例如，當(dāng)調(diào)用 get 方法返回 null 時(shí)，無法確定是因?yàn)?key 不存在，還是 key 對(duì)應(yīng)的 value 為 null。

ConcurrentSkipListMap 沒有傳統(tǒng)的擴(kuò)容機(jī)制，而是通過跳表的動(dòng)態(tài)調(diào)整來適應(yīng)元素的插入和刪除操作。這種方式使得 ConcurrentSkipListMap 具有良好的并發(fā)性能和自適應(yīng)性能，能夠在不同的數(shù)據(jù)規(guī)模下保持高效的操作。

五、增刪改查方法

List 操作：使用 ArrayList 演示，借助 add 方法添加元素，set 方法修改元素，remove 方法刪除元素，get 方法查找元素。
Set 操作：使用 HashSet 演示，通過 add 方法添加元素，remove 方法刪除元素，contains 方法查找元素。
Map 操作：使用 HashMap 演示，利用 put 方法添加或修改元素，remove 方法刪除元素，get 方法查找元素。

六、迭代器

迭代器（Iterator）是一種設(shè)計(jì)模式，它提供了一種統(tǒng)一的方式來遍歷集合（如 List、Set、Map 等）中的元素，而不需要關(guān)心集合的具體實(shí)現(xiàn)細(xì)節(jié)。
迭代器是一個(gè)對(duì)象，它實(shí)現(xiàn)了 java.util.Iterator 接口，該接口定義了三個(gè)主要方法：
boolean hasNext()： 判斷集合中是否還有下一個(gè)元素，如果有則返回 true，否則返回 false。
E next()： 返回集合中的下一個(gè)元素，并將迭代器的位置向后移動(dòng)一位。如果沒有下一個(gè)元素，調(diào)用該方法會(huì)拋出 NoSuchElementException 異常。
void remove()： 移除迭代器最后返回的元素。該方法只能在每次調(diào)用 next() 方法之后調(diào)用一次，如果違反此規(guī)則，會(huì)拋出 IllegalStateException 異常。

遍歷 List(set使用方式和list相同)

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class IteratorListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("banana");
        list.add("cherry");
        // 獲取迭代器
        Iterator<String> iterator = list.iterator();
        // 遍歷集合
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
        }
    }
}

遍歷 Map
對(duì)于 Map，需要先獲取 Map 的 entrySet 或 keySet，然后再使用迭代器進(jìn)行遍歷。

mport java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class IteratorMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);
        // 獲取 entrySet 的迭代器
        Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
        // 遍歷集合
        while (iterator.hasNext()) {
            Entry<String, Integer> entry = iterator.next();
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

優(yōu)點(diǎn)
統(tǒng)一的遍歷方式： 迭代器提供了一種統(tǒng)一的方式來遍歷不同類型的集合，使得代碼更加簡(jiǎn)潔和易于維護(hù)。
支持并發(fā)修改檢測(cè)： 在使用迭代器遍歷集合時(shí)，如果在迭代過程中對(duì)集合進(jìn)行了結(jié)構(gòu)上的修改（如添加、刪除元素），會(huì)拋出 ConcurrentModificationException 異常，從而避免了并發(fā)修改帶來的問題。
可以在遍歷過程中刪除元素：通過迭代器的 remove() 方法，可以在遍歷集合的過程中安全地刪除元素。
缺點(diǎn)
只能單向遍歷： 迭代器只能從前往后依次遍歷集合中的元素，不能反向遍歷。
性能相對(duì)較低： 與增強(qiáng) for 循環(huán)和 forEach 方法相比，迭代器的性能相對(duì)較低，因?yàn)樗枰~外的方法調(diào)用和狀態(tài)維護(hù)。

七、其他遍歷方法

增強(qiáng) for 循環(huán)

增強(qiáng) for 循環(huán)是 Java 5 引入的一種簡(jiǎn)化的遍歷方式，它可以更方便地遍歷數(shù)組和集合。與迭代器相比，增強(qiáng) for 循環(huán)的語法更加簡(jiǎn)潔，但它不能在遍歷過程中刪除元素。

import java.util.ArrayList;
import java.util.List;
public class EnhancedForLoopExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("banana");
        list.add("cherry");
        // 使用增強(qiáng) for 循環(huán)遍歷集合
        for (String element : list) {
            System.out.println(element);
        }
    }
}

forEach 方法

forEach 方法是 Java 8 引入的一種函數(shù)式編程風(fēng)格的遍歷方式，它結(jié)合了 Lambda 表達(dá)式，可以更簡(jiǎn)潔地遍歷集合。與迭代器相比，forEach 方法的語法更加簡(jiǎn)潔，但它也不能在遍歷過程中刪除元素。

import java.util.ArrayList;
import java.util.List;
public class ForEachExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("banana");
        list.add("cherry");
        // 使用 forEach 方法遍歷集合
        list.forEach(element -> System.out.println(element));
    }
}

八、 棧（Stack）

棧是一種線性數(shù)據(jù)結(jié)構(gòu)，它就像一疊盤子，你只能從最上面添加或移除盤子。添加元素的操作叫入棧（push），移除元素的操作叫出棧（pop）。除此之外，通常還會(huì)有查看棧頂元素（peek）、判斷棧是否為空（isEmpty）以及獲取棧中元素?cái)?shù)量（size）等操作。

java.util.Stack 類

Stack 類繼承自 Vector 類，它是 Java 早期提供的棧實(shí)現(xiàn)。不過，由于 Vector 是線程安全的，其操作會(huì)帶來一定的性能開銷。

import java.util.Stack;
public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        // 入棧操作
        stack.push(1);
        stack.push(2);
        stack.push(3);
        // 出棧操作
        int poppedElement = stack.pop();
        System.out.println("出棧元素: " + poppedElement);
        // 查看棧頂元素
        int topElement = stack.peek();
        System.out.println("棧頂元素: " + topElement);
        // 判斷棧是否為空
        boolean isEmpty = stack.isEmpty();
        System.out.println("棧是否為空: " + isEmpty);
        // 獲取棧的大小
        int size = stack.size();
        System.out.println("棧的大小: " + size);
    }
}

Deque 接口

Deque（雙端隊(duì)列）接口可以當(dāng)作棧來使用，并且它的性能通常比 Stack 類更好。ArrayDeque 是 Deque 接口的一個(gè)常用實(shí)現(xiàn)類。

import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAsStackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 入棧操作
        stack.push(1);
        stack.push(2);
        stack.push(3);
        // 出棧操作
        int poppedElement = stack.pop();
        System.out.println("出棧元素: " + poppedElement);
        // 查看棧頂元素
        int topElement = stack.peek();
        System.out.println("棧頂元素: " + topElement);
        // 判斷棧是否為空
        boolean isEmpty = stack.isEmpty();
        System.out.println("棧是否為空: " + isEmpty);
        // 獲取棧的大小
        int size = stack.size();
        System.out.println("棧的大小: " + size);
    }
}

使用場(chǎng)景
棧在很多場(chǎng)景中都有廣泛應(yīng)用，以下是一些常見的例子：
表達(dá)式求值：在計(jì)算中綴表達(dá)式、后綴表達(dá)式時(shí)，?？梢杂脕硖幚磉\(yùn)算符和操作數(shù)，確保運(yùn)算順序正確。
函數(shù)調(diào)用：在程序執(zhí)行過程中，函數(shù)調(diào)用棧用于記錄函數(shù)的調(diào)用關(guān)系和局部變量，當(dāng)函數(shù)調(diào)用結(jié)束時(shí)，會(huì)按照后進(jìn)先出的順序返回。
回溯算法：在回溯算法中，棧可以用來保存路徑和狀態(tài)，方便進(jìn)行回溯操作。
瀏覽器的前進(jìn)后退功能：瀏覽器使用兩個(gè)棧分別記錄用戶的前進(jìn)和后退歷史，通過棧的操作實(shí)現(xiàn)頁面的前進(jìn)和后退。

九、樹（Tree）

二叉樹（Binary Tree）

結(jié)構(gòu)靈活： 每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，結(jié)構(gòu)相對(duì)簡(jiǎn)單但能表示各種復(fù)雜的層次關(guān)系。
無特定順序： 節(jié)點(diǎn)的值沒有特定的大小順序要求，節(jié)點(diǎn)的排列可以非常多樣化。
應(yīng)用廣泛： 是許多其他樹結(jié)構(gòu)的基礎(chǔ)，可用于模擬各種具有層次特性的場(chǎng)景。

原理
二叉樹由節(jié)點(diǎn)和邊組成，節(jié)點(diǎn)包含數(shù)據(jù)和指向左右子節(jié)點(diǎn)的引用。節(jié)點(diǎn)之間通過這些引用形成樹狀結(jié)構(gòu)。創(chuàng)建和操作二叉樹主要圍繞節(jié)點(diǎn)的插入、刪除和遍歷展開。在插入節(jié)點(diǎn)時(shí)，根據(jù)具體需求和規(guī)則將新節(jié)點(diǎn)添加到合適的位置；刪除節(jié)點(diǎn)時(shí)，需要處理節(jié)點(diǎn)的子節(jié)點(diǎn)以及維護(hù)樹的結(jié)構(gòu)完整性；遍歷則是按照特定順序訪問樹中的每個(gè)節(jié)點(diǎn)。
用于表示具有層次關(guān)系的數(shù)據(jù)，如文件系統(tǒng)目錄結(jié)構(gòu)、XML 解析等。

二叉搜索樹（Binary Search Tree，BST）

有序性： 對(duì)于樹中的任意節(jié)點(diǎn)，其左子樹中所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹中所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。
高效查找： 平均情況下，查找、插入和刪除操作的時(shí)間復(fù)雜度為 (O(log n))，因?yàn)槊看尾僮鞫伎梢愿鶕?jù)節(jié)點(diǎn)值的大小縮小搜索范圍。
中序遍歷有序： 對(duì)二叉搜索樹進(jìn)行中序遍歷會(huì)得到一個(gè)有序的節(jié)點(diǎn)值序列。

原理
基于節(jié)點(diǎn)值的比較來構(gòu)建和維護(hù)樹的結(jié)構(gòu)。插入新節(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始比較，若新節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)值，則進(jìn)入左子樹繼續(xù)比較；若大于，則進(jìn)入右子樹，直到找到合適的插入位置。查找和刪除操作也遵循類似的比較規(guī)則。刪除節(jié)點(diǎn)時(shí)，需要處理不同情況，如節(jié)點(diǎn)無子節(jié)點(diǎn)、有一個(gè)子節(jié)點(diǎn)或有兩個(gè)子節(jié)點(diǎn)，以保證樹的結(jié)構(gòu)仍然滿足二叉搜索樹的特性。

平衡二叉搜索樹 - AVL 樹定義

高度平衡： 每個(gè)節(jié)點(diǎn)的左右子樹的高度差不超過 1，這保證了樹的高度始終保持在 (O(log n)) 級(jí)別。
性能穩(wěn)定： 由于高度平衡，查找、插入和刪除操作的時(shí)間復(fù)雜度始終為 (O(log n))，避免了二叉搜索樹在最壞情況下退化為鏈表的問題。
旋轉(zhuǎn)操作頻繁： 為了保持平衡，在插入和刪除節(jié)點(diǎn)后可能需要進(jìn)行多次旋轉(zhuǎn)操作（左旋、右旋、左右旋、右左旋）。

原理
在插入或刪除節(jié)點(diǎn)后，會(huì)計(jì)算每個(gè)節(jié)點(diǎn)的平衡因子（左子樹高度 - 右子樹高度）。如果平衡因子的絕對(duì)值大于 1，則通過旋轉(zhuǎn)操作來調(diào)整樹的結(jié)構(gòu)，使其重新達(dá)到平衡。旋轉(zhuǎn)操作會(huì)改變節(jié)點(diǎn)之間的父子關(guān)系，但保證樹仍然滿足二叉搜索樹的特性。

紅黑樹（Red - Black Tree）

近似平衡： 紅黑樹并不像 AVL 樹那樣嚴(yán)格平衡，但它通過顏色標(biāo)記和特定規(guī)則保證了樹的最長(zhǎng)路徑不超過最短路徑的兩倍，從而保證了操作的時(shí)間復(fù)雜度為 (O(log n))。
插入和刪除效率高： 相比于 AVL 樹，紅黑樹在插入和刪除節(jié)點(diǎn)時(shí)需要的調(diào)整操作相對(duì)較少，因?yàn)樗钠胶庖笙鄬?duì)寬松。
應(yīng)用廣泛： Java 中的 TreeMap 和 TreeSet 底層就是基于紅黑樹實(shí)現(xiàn)的，在需要有序存儲(chǔ)和高效查找的場(chǎng)景中表現(xiàn)出色。

原理
紅黑樹的每個(gè)節(jié)點(diǎn)都有一個(gè)顏色屬性（紅色或黑色），并遵循以下規(guī)則：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。根節(jié)點(diǎn)是黑色。每個(gè)葉子節(jié)點(diǎn)（NIL 節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色。如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。對(duì)每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)。在插入和刪除節(jié)點(diǎn)時(shí)，通過顏色調(diào)整和旋轉(zhuǎn)操作來維護(hù)這些規(guī)則，從而保證樹的近似平衡。

多路搜索樹 - B 樹和 B+ 樹

B 樹
多路存儲(chǔ)： 每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)（通常大于 2），這使得 B 樹可以在一個(gè)節(jié)點(diǎn)中存儲(chǔ)更多的鍵值對(duì)，減少了樹的高度。
適用于磁盤存儲(chǔ)： 由于樹的高度較低，B 樹在磁盤存儲(chǔ)中非常有用，因?yàn)榇疟P I/O 操作的次數(shù)與樹的高度成正比，較低的樹高度可以減少磁盤 I/O 次數(shù)。
所有節(jié)點(diǎn)都存儲(chǔ)數(shù)據(jù)： B 樹的每個(gè)節(jié)點(diǎn)都可以存儲(chǔ)鍵值對(duì)和指向子節(jié)點(diǎn)的指針。

B+ 樹
數(shù)據(jù)集中在葉子節(jié)點(diǎn)： 所有的數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)只存儲(chǔ)索引信息，這使得范圍查詢更加高效。
葉子節(jié)點(diǎn)相連： 葉子節(jié)點(diǎn)之間通過指針相連，形成一個(gè)有序鏈表，方便進(jìn)行范圍查詢和順序訪問。
更適合數(shù)據(jù)庫索引： 在數(shù)據(jù)庫系統(tǒng)中，B+ 樹廣泛應(yīng)用于索引結(jié)構(gòu)，因?yàn)樗軌蚋咝У刂С植檎?、插入、刪除和范圍查詢操作。

原理
B 樹
插入節(jié)點(diǎn)時(shí)，當(dāng)節(jié)點(diǎn)中的鍵值對(duì)數(shù)量超過一定閾值（節(jié)點(diǎn)的最大容量）時(shí)，會(huì)進(jìn)行節(jié)點(diǎn)分裂操作，將節(jié)點(diǎn)一分為二，并將中間的鍵值提升到父節(jié)點(diǎn)。刪除節(jié)點(diǎn)時(shí)，若節(jié)點(diǎn)中的鍵值對(duì)數(shù)量小于一定閾值（節(jié)點(diǎn)的最小容量），會(huì)進(jìn)行節(jié)點(diǎn)合并或借鍵操作來保持樹的結(jié)構(gòu)。

B+ 樹
插入和刪除操作與 B 樹類似，但由于數(shù)據(jù)只存儲(chǔ)在葉子節(jié)點(diǎn)，操作主要集中在葉子節(jié)點(diǎn)上。在插入時(shí)，若葉子節(jié)點(diǎn)已滿，則進(jìn)行分裂操作；刪除時(shí)，若葉子節(jié)點(diǎn)的鍵值對(duì)數(shù)量過少，則進(jìn)行合并或借鍵操作。同時(shí)，需要維護(hù)葉子節(jié)點(diǎn)之間的鏈表結(jié)構(gòu)。

特性對(duì)比

十、 哈希是什么

哈希是把任意長(zhǎng)度的輸入通過哈希函數(shù)轉(zhuǎn)換為固定長(zhǎng)度輸出的過程，這個(gè)輸出值就是哈希值（也叫哈希碼或散列值）。哈希的核心目標(biāo)是高效地存儲(chǔ)和查找數(shù)據(jù)。借助哈希函數(shù)，能把數(shù)據(jù)的鍵映射到一個(gè)特定的位置，進(jìn)而實(shí)現(xiàn)快速訪問。

哈希函數(shù)

哈希函數(shù)是哈希技術(shù)的關(guān)鍵，它接收一個(gè)鍵作為輸入，然后返回一個(gè)哈希值。在 Java 中，Object 類有一個(gè) hashCode() 方法，所有類都繼承了這個(gè)方法，可用于生成對(duì)象的哈希碼。例如：

public class HashExample {
    public static void main(String[] args) {
        String str = "hello";
        int hashCode = str.hashCode();
        System.out.println("字符串 \"hello\" 的哈希碼: " + hashCode);
    }
}

在上述代碼里，String 類重寫了 hashCode() 方法，按照特定算法生成字符串的哈希碼。一個(gè)好的哈希函數(shù)應(yīng)該具備以下特性：
確定性：相同的輸入始終產(chǎn)生相同的輸出。
高效性：計(jì)算哈希值的過程要快速。
均勻性：盡可能讓哈希值均勻分布，減少哈希沖突的發(fā)生。

哈希沖突

當(dāng)不同的鍵通過哈希函數(shù)計(jì)算出相同的哈希值時(shí)，就會(huì)產(chǎn)生哈希沖突。因?yàn)楣：瘮?shù)的輸出空間通常比輸入空間小，所以哈希沖突難以避免。例如，在一個(gè)大小為 10 的哈希表中，若有 11 個(gè)不同的鍵，必然會(huì)有至少兩個(gè)鍵的哈希值相同。

解決哈希沖突的方法

鏈地址法（Separate Chaining）
這種方法是在哈希表的每個(gè)位置維護(hù)一個(gè)鏈表。當(dāng)發(fā)生哈希沖突時(shí)，把沖突的元素添加到對(duì)應(yīng)位置的鏈表中。Java 的 HashMap 就采用了鏈地址法，當(dāng)鏈表長(zhǎng)度超過一定閾值（默認(rèn)為 8）且哈希表長(zhǎng)度大于 64 時(shí)，鏈表會(huì)轉(zhuǎn)換為紅黑樹，以提升查找性能。

開放地址法（Open Addressing）
開放地址法是在發(fā)生哈希沖突時(shí)，通過某種規(guī)則在哈希表中尋找下一個(gè)可用的位置。常見的開放地址法有線性探測(cè)、二次探測(cè)和雙重哈希等。

哈希在 Java 中是一種高效的數(shù)據(jù)存儲(chǔ)和查找技術(shù)，通過合理選擇哈希函數(shù)和解決哈希沖突的方法，能顯著提升程序的性能。

到此這篇關(guān)于一文掌握J(rèn)ava 數(shù)據(jù)結(jié)構(gòu)超詳細(xì)筆記(收藏版)的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論