前言

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

一、數(shù)組（Array）

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

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

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

public class ArrayDynamicInitialization {
    public static void main(String[] args) {
        // 動態(tài)初始化一個長度為 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)初始化時，無需使用 new 關(guān)鍵字顯式指定數(shù)組長度，而是直接在聲明數(shù)組的同時為其元素賦值。

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

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

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

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

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

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

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)建一個 Person 類型的數(shù)組
        Person[] personArray = new Person[3];
        // 可以將 null 賦值給引用類型數(shù)組元素
        personArray[0] = null; 
        // 創(chuàng)建一個 Person 對象并賦值給數(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）分別定義的對應(yīng)引用類型。這些包裝類包括：Boolean、Character、Byte、Short、Integer、Long、Float、Double‌。
包裝類的作用是將基本數(shù)據(jù)類型轉(zhuǎn)換為引用數(shù)據(jù)類型，以便在泛型和集合中使用。通過包裝類，可以將基本數(shù)據(jù)類型作為對象處理，從而可以使用對象的屬性和方法。例如，Integer類提供了將字符串轉(zhuǎn)換為整數(shù)的靜態(tài)方法valueOf()，以及將整數(shù)轉(zhuǎn)換為字符串的toString()方法‌。

內(nèi)置方法

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

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

public class DeleteElementByNewArray {
    public static void main(String[] args) {
        int[] originalArray = {1, 2, 3, 4, 5};
        int indexToDelete = 2; // 要刪除元素的索引
        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ù)組中的每一個元素，將其與目標(biāo)元素進行比較，從而判斷數(shù)組中是否包含該元素，或者找到元素所在的位置。

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

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

存儲位置

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

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

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

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

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

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

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

數(shù)組特性：

查詢和修改速度快

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

增加和刪除操作慢

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

基礎(chǔ)數(shù)組，在增加和刪除，以及擴容上，其實不符合數(shù)據(jù)結(jié)構(gòu)中對數(shù)組的定義，因為原生的數(shù)組沒有增加和刪除方法，也不能自動擴容。

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

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

多維數(shù)組

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

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

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

二、鏈表

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

單向鏈表

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

雙向鏈表

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

循環(huán)鏈表

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

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

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

三、Collection （單列集合）

List接口：

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

ArrayList:

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

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

LinkedList:

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

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

Vector:

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

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

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

Set接口：

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

HashSet:

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

LinkedHashSet:

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

TreeSet :

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

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

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

跳表是什么，下次再更

Queue接口：

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

四、Map（雙列集合）

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

HashMap

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

LinkedHashMap

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

Hashtable

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

TreeMap

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

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

安全的map

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

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

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

ConcurrentSkipListMap 沒有傳統(tǒ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è)計模式，它提供了一種統(tǒng)一的方式來遍歷集合（如 List、Set、Map 等）中的元素，而不需要關(guān)心集合的具體實現(xiàn)細節(jié)。
迭代器是一個對象，它實現(xiàn)了 java.util.Iterator 接口，該接口定義了三個主要方法：
boolean hasNext()： 判斷集合中是否還有下一個元素，如果有則返回 true，否則返回 false。
E next()： 返回集合中的下一個元素，并將迭代器的位置向后移動一位。如果沒有下一個元素，調(diào)用該方法會拋出 NoSuchElementException 異常。
void remove()： 移除迭代器最后返回的元素。該方法只能在每次調(diào)用 next() 方法之后調(diào)用一次，如果違反此規(guī)則，會拋出 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
對于 Map，需要先獲取 Map 的 entrySet 或 keySet，然后再使用迭代器進行遍歷。

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

七、其他遍歷方法

增強 for 循環(huán)

增強 for 循環(huán)是 Java 5 引入的一種簡化的遍歷方式，它可以更方便地遍歷數(shù)組和集合。與迭代器相比，增強 for 循環(huá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");
        // 使用增強 for 循環(huán)遍歷集合
        for (String element : list) {
            System.out.println(element);
        }
    }
}

forEach 方法

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

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）。除此之外，通常還會有查看棧頂元素（peek）、判斷棧是否為空（isEmpty）以及獲取棧中元素數(shù)量（size）等操作。

java.util.Stack 類

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

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（雙端隊列）接口可以當(dāng)作棧來使用，并且它的性能通常比 Stack 類更好。ArrayDeque 是 Deque 接口的一個常用實現(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);
    }
}

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

九、樹（Tree）

二叉樹（Binary Tree）

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

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

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

有序性： 對于樹中的任意節(jié)點，其左子樹中所有節(jié)點的值都小于該節(jié)點的值，右子樹中所有節(jié)點的值都大于該節(jié)點的值。
高效查找： 平均情況下，查找、插入和刪除操作的時間復(fù)雜度為 (O(log n))，因為每次操作都可以根據(jù)節(jié)點值的大小縮小搜索范圍。
中序遍歷有序： 對二叉搜索樹進行中序遍歷會得到一個有序的節(jié)點值序列。

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

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

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

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

紅黑樹（Red - Black Tree）

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

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

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

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

B+ 樹
數(shù)據(jù)集中在葉子節(jié)點： 所有的數(shù)據(jù)都存儲在葉子節(jié)點，非葉子節(jié)點只存儲索引信息，這使得范圍查詢更加高效。
葉子節(jié)點相連： 葉子節(jié)點之間通過指針相連，形成一個有序鏈表，方便進行范圍查詢和順序訪問。
更適合數(shù)據(jù)庫索引： 在數(shù)據(jù)庫系統(tǒng)中，B+ 樹廣泛應(yīng)用于索引結(jié)構(gòu)，因為它能夠高效地支持查找、插入、刪除和范圍查詢操作。

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

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

特性對比

十、 哈希是什么

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

哈希函數(shù)

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

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

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

哈希沖突

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

解決哈希沖突的方法

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

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

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

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

最新評論