📕1. 二叉搜索樹

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:

1. 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
2. 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
3. 它的左右子樹也分別為二叉搜索樹

??1.1 查找操作

    //搜索public TreeNode search(int value){TreeNode cur = root;while(cur!=null){if(value<cur.value){cur = cur.left;}else if(value>cur.value){cur = cur.right;} else if (value == cur.value) {return cur;}}return null;}

??1.2 插入操作

//插入public boolean insert(int value){TreeNode treeNode = new TreeNode(value);if (root==null){root = treeNode;return true;}TreeNode cur = root;TreeNode parent = null;while (cur!=null){if (value>cur.value){parent = cur;cur = cur.right;} else if (value<cur.value) {parent = cur;cur = cur.left;}else if (value==cur.value){return false;}}//整體思路是先找到要插入節點的父節點，比父節點的值大就插入到父節點的右邊，反之插入到父節點的左邊if (value>parent.value){parent.right = treeNode;}else {parent.left = treeNode;}return true;}

??1.3 刪除操作

待補充！！！

📕2. Map的使用

Map是?個接?，可以有HashMap實現或者TreeMap實現，該類沒有繼承?Collection，該類中存儲的是<K,V>結構的鍵值對，并且K?定是唯?的，不能重復。

Map.Entry<K, V> 是Map內部實現的?來存放<key, value>鍵值對映射關系的內部類，該內部類中主要提供了<key, value>的獲取，value的設置以及Key的?較?式。Map.Entry<K,V>并沒有提供設置Key的?法

??2.1 Map的常用方法

💡💡💡注意：

1. Map是?個接?，不能直接實例化對象，如果要實例化對象只能實例化其實現類TreeMap或者HashMap
2. Map中存放鍵值對的Key是唯?的，value是可以重復的
3. TreeMap中插?鍵值對時，key不能為空，否則就會拋NullPointerException異常，value可以為空。但是HashMap的key和value都可以為空。
4. Map中的Key可以全部分離出來，存儲到Set中來進?訪問(因為Key不能重復)
5. Map中的value可以全部分離出來，存儲在Collection的任何?個?集合中(value可能有重復)
6. Map中鍵值對的Key不能直接修改，value可以修改，如果要修改key，只能先將該key刪除掉，然
   后再來進?重新插?

??2.2 TreeMap和HashMap的區別

??2.3 HashMap的底層實現

1. JDK1.8 之前

JDK1.8 之前 HashMap 底層是 數組和鏈表 結合在一起使用也就是 鏈表散列。

2. JDK1.8 之后

相比于之前的版本， JDK1.8 之后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）（將鏈表轉換成紅黑樹前會判斷，如果當前數組的長度小于 64，那么會選擇先進行數組擴容，而不是轉換為紅黑樹）時，將鏈表轉化為紅黑樹。這樣做的目的是減少搜索時間：鏈表的查詢效率為 O(n)（n 是鏈表的長度），紅黑樹是一種自平衡二叉搜索樹，其查詢效率為 O(log n)。當鏈表較短時，O(n) 和 O(log n) 的性能差異不明顯。但當鏈表變長時，查詢性能會顯著下降。

為什么優先擴容而非直接轉為紅黑樹？

數組擴容能減少哈希沖突的發生概率（即將元素重新分散到新的、更大的數組中），這在多數情況下比直接轉換為紅黑樹更高效。紅黑樹需要保持自平衡，維護成本較高。并且，過早引入紅黑樹反而會增加復雜度。

為什么選擇閾值 8 和 64？

1. 泊松分布表明，鏈表長度達到 8 的概率極低（小于千萬分之一）。在絕大多數情況下，鏈表長度都不會超過 8。閾值設置為 8，可以保證性能和空間效率的平衡。
2. 數組長度閾值 64 同樣是經過實踐驗證的經驗值。在小數組中擴容成本低，優先擴容可以避免過早引入紅黑樹。數組大小達到 64 時，沖突概率較高，此時紅黑樹的性能優勢開始顯現。

📕3. Set的使用

Set與Map主要的不同有兩點：Set是繼承?Collection的接?類，Set中只存儲了Key

??3.1 Set的常用方法

💡💡💡注意：

1. Set是繼承?Collection的?個接?
2. Set中只存儲了key，并且要求key?定要唯一
3. TreeSet的底層是使?Map來實現的，其使?key與Object的?個默認對象作為鍵值對插?到Map中的
4. Set最?的功能就是對集合中的元素進?去重
5. 實現Set接?的常?類有TreeSet和HashSet
6. Set中的Key不能修改，如果要修改，先將原來的刪除掉，然后再重新插?
7. reeSet中不能插?null的key，HashSet可以

??3.2 TreeSet和HashSet的區別

📕4. 哈希表

哈希表（Hash table），又稱為散列表，是一種根據關鍵碼值（Key value）直接進行訪問的數據結構。它通過將關鍵碼值映射到表中的一個位置來訪問記錄，從而加快查找的速度。這個映射函數稱為散列函數，存放記錄的數組稱為散列表。

例如：
數據集合{1，7，6，4，5，9}；
哈希函數設置為：hash(key) = key % capacity; capacity為存儲元素底層空間總的??

?該?法進?搜索不必進?多次關鍵碼的?較，因此搜索的速度?較快

??4.1 哈希表沖突

對于兩個數據元素的關鍵字 ki 和 kj(i != j)，有 i != j ，但有：Hash( ki ) == Hash( kj )，

即：不同關鍵字通過相同哈希函數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞。

把具有不同關鍵碼?具有相同哈希地址的數據元素稱為“同義詞”。

??4.2 避免哈希表沖突

?先，我們需要明確?點，由于我們哈希表底層數組的容量往往是?于實際要存儲的關鍵字的數量的，這就導致?個問題，沖突的發?是必然的，但我們能做的應該是盡量的降低沖突率。

1. 🌈設計哈希函數

引起哈希沖突的?個原因可能是：哈希函數設計不夠合理。常見的哈希函數有：

1. 直接定制法（常用）
   取關鍵字的某個線性函數為散列地址：Hash（Key）= A*Key + B優點：簡單、均勻缺點：需
   要事先知道關鍵字的分布情況使?場景：適合查找?較?且連續的情況
2. 除留余數法（常用）
   設散列表中允許的地址數為m，取?個不?于m，但最接近或者等于m的質數p作為除數，按
   照哈希函數：Hash(key) = key% p(p<=m),將關鍵碼轉換成哈希地址
3. 平方取中法（了解）
4. 折疊法（了解）
5. 隨機數法（了解）
6. 數學分析法（了解）

2. 🌈調節負載因子

所以當沖突率達到?個?法忍受的程度時，我們需要通過降低負載因?來變相的降低沖突率。

已知哈希表中已有的關鍵字個數是不可變的，那我們能調整的就只有哈希表中的數組的??。

??4.3 解決哈希表沖突

解決哈希沖突兩種常?的?法是：開放地址法和拉鏈法

📏4.3.1 開放地址法

開放地址法 ：當發?哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到沖突位置中的“下?個” 空位置中去。那如何尋找下?個空位置呢？

1. 🌈線性探測

?如上?的場景，現在需要插?元素44，先通過哈希函數計算哈希地址，下標為4，因此44理論上應該插在該位置，但是該位置已經放了值為4的元素，即發?哈希沖突。

線性探測：從發?沖突的位置開始，依次向后探測，直到尋找到下?個空位置為?。

采?閉散列處理哈希沖突時，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他元素的搜索。?如刪除元素4，如果直接刪除掉，44查找起來可能會受影響。因此線性探測采?標記的偽刪除法來刪除?個元素。

2. 🌈二次探測

線性探測的缺陷是產?沖突的數據堆積在?塊，這與其找下?個空位置有關系，因為找空位置的?式就是挨著往后逐個去找，因此?次探測為了避免該問題，找下?個空位置的?法為： Hi = ( H0 +（-） i^2 )% m )，其中：i = 1,2,3…， 是通過散列函數Hash(x)對元素的關鍵碼key 進?計算得到的位置，m是表的??。對于2.1中如果要插?44，產?沖突，使?解決后的情況為：

📏4.3.2 拉鏈法

開散列法?叫鏈地址法(開鏈法)，?先對關鍵碼集合?散列函數計算散列地址，具有相同地址的關鍵碼歸于同??集合，每?個?集合稱為?個桶，各個桶中的元素通過?個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中。

從上圖可以看出，開散列中每個桶中放的都是發?哈希沖突的元素。

拉鏈法，可以認為是把?個在?集合中的搜索問題轉化為在?集合中做搜索了。