1.搜索樹

1.定義

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

• 若它的左子樹不為空，則左子樹上所有節(jié)點的值都小于根節(jié)點的值
• 若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于根節(jié)點的值
• 它的左右子樹也分別為二叉搜索樹

int[] array ={5,3,4,1,7,8,2,6,0,9};

2.基本操作

1.查找

查找過程：

1. 拿著待查元素和根節(jié)點比較；
2. 如果比根節(jié)點小，繼續(xù)在左子樹中查找；
3. 如果比根節(jié)點大，繼續(xù)在右子樹中查找；
4. 如果當前元素查找到null也沒找到，說明該元素不存在。

2.插入

1. 如果樹是空樹，即根== null，直接插入即可，返回true。
2. 如果樹不是空樹，按照 查找邏輯（大的放左邊，小的放右邊） 確定插入位置，插入新結(jié)點。
   注意：最后確定的插入位置一定是葉子節(jié)點

3.刪除

設待刪除結(jié)點為 cur, 待刪除結(jié)點的雙親結(jié)點為 parent
1.cur.left == null

1. cur 是 root，則 root = cur.right
2. cur 不是 root，cur 是 parent.left，則 parent.left = cur.right
3. cur 不是 root，cur 是 parent.right，則 parent.right = cur.right
   

2.cur.right == null
4. cur 是 root，則 root = cur.left
5. cur 不是 root，cur 是 parent.left，則 parent.left = cur.left
6. cur 不是 root，cur 是 parent.right，則 parent.right = cur.left

3. cur.left != null && cur.right != null
需要使用替換法進行刪除，即在它的右子樹中尋找中序下的第一個結(jié)點(關鍵碼最小)，用它的值填補到被刪除節(jié)點中，再來處理該結(jié)點的刪除問題

4.代碼實現(xiàn)

public class BinarySearchTree {static class TreeNode {public int val;public TreeNode right;public TreeNode left;public TreeNode(int val) {this.val = val;}}TreeNode root = null;/*** 查找二叉搜索樹中指定的val值* @param val* @return*/public TreeNode find(int val) {TreeNode cur = root;while (cur != null) {if(cur.val > val) {cur = cur.left;}else if(cur.val < val) {cur = cur.right;}else {return cur;}}return null;}/*** 插入一個數(shù)據(jù)* @param val*/public void insert(int val) {if(root == null) {root = new TreeNode(val);return;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (cur.val > val) {parent = cur;cur = cur.left;} else if (cur.val < val) {parent = cur;cur = cur.right;} else {return;}}TreeNode node = new TreeNode(val);if(parent.val < val) {parent.right = node;}else {parent.left = node;}}public void inorder(TreeNode root) {if(root == null) {return;}inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}/*** 刪除值為val的節(jié)點* @param val*/public void remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val == val) {removeNode(parent,cur);return;}else if(cur.val < val) {parent = cur;cur = cur.right;}else {parent = cur;cur = cur.left;}}}private void removeNode(TreeNode parent, TreeNode cur) {if(cur.left == null) {if(cur == root) {root = cur.right;}else if(parent.left == cur) {parent.left = cur.right;}else {parent.right = cur.right;}}else if(cur.right == null) {if(cur == root) {root = cur.left;}else if (parent.left == cur) {parent.left = cur.left;}else {parent.right = cur.left;}}else {TreeNode target = cur.right;TreeNode targetParent = cur;while (cur.left != null) {targetParent = target;target = target.left;}cur.val = target.val;if(target == targetParent.left) {targetParent.left = target.right;}else {targetParent.right = target.right;}}}
}

2.Map和Set的使用

1.簡單介紹

Map和set是一種專門用來進行搜索的容器或者數(shù)據(jù)結(jié)構(gòu)，其搜索的效率與其具體的實例化子類有關。以前常見的搜索方式有：

1. 直接遍歷，時間復雜度為O(N)，元素如果比較多效率會非常慢。
2. 二分查找，時間復雜度為 ,但搜索前必須要求序列是有序的。

上述排序比較適合靜態(tài)類型的查找，即一般不會對區(qū)間進行插入和刪除操作了，而現(xiàn)實中的查找比如：

1. 根據(jù)姓名查詢考試成績。
2. 通訊錄，即根據(jù)姓名查詢聯(lián)系方式。
3. 不重復集合，即需要先搜索關鍵字是否已經(jīng)在集合中。

可能在查找時進行一些插入和刪除的操作，即動態(tài)查找，那上述兩種方式就不太適合了，本節(jié)介紹的Map和Set是一種適合動態(tài)查找的集合容器。

2.模型

一般把搜索的數(shù)據(jù)稱為關鍵字（Key），和關鍵字對應的稱為值（Value），將其稱之為Key-value的鍵值對，所以
模型會有兩種：

1. 純 key 模型，比如：

• 有一個英文詞典，快速查找一個單詞是否在詞典中
• 快速查找某個名字在不在通訊錄中

2. Key-Value 模型，比如：

• 統(tǒng)計文件中每個單詞出現(xiàn)的次數(shù)，統(tǒng)計結(jié)果是每個單詞都有與其對應的次數(shù)：<單詞，單詞出現(xiàn)的次數(shù)>
• 梁山好漢的江湖綽號：每個好漢都有自己的江湖綽號

而Map中存儲的就是key-value的鍵值對，Set中只存儲了Key。

3.Map的使用

Map是一個接口類，該類沒有繼承自Collection，該類中存儲的是<K,V>結(jié)構(gòu)的鍵值對，并且K一定是唯一的，不能重復。

1.關于Map.Entry<K, V>的說明

Map.Entry<K, V> 是Map內(nèi)部實現(xiàn)的用來存放<key, value>鍵值對映射關系的內(nèi)部類，該內(nèi)部類中主要提供了<key, value>的獲取，value的設置以及Key的比較方式。

注意：Map.Entry<K,V>并沒有提供設置Key的方法

2.Map 的常用方法說明

注意：

1. Map是一個接口，不能直接實例化對象，如果要實例化對象只能實例化其實現(xiàn)類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刪除掉，然后再來進行重新插入。

4.Set的使用

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

1.Set的常見方法說明

注意：

1. Set是繼承自Collection的一個接口類。
2. Set中只存儲了key，并且要求key一定要唯一。
3. TreeSet的底層是使用Map來實現(xiàn)的，其使用key與Object的一個默認對象作為鍵值對插入到Map中的。
4. Set最大的功能就是對集合中的元素進行去重。
5. 實現(xiàn)Set接口的常用類有TreeSet和HashSet，還有一個LinkedHashSet，LinkedHashSet是在HashSet的基礎上維護了一個雙向鏈表來記錄元素的插入次序。
6. Set中的Key不能修改，如果要修改，先將原來的刪除掉，然后再重新插入。
7. TreeSet中不能插入null的key，HashSet可以。

3.哈希表

1.概念

順序結(jié)構(gòu)以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，因此在**查找一個元素時，必須要經(jīng)過關鍵碼的多次比較。順序查找時間復雜度為O(N)，平衡樹中為樹的高度，即O( logn)，**搜索的效率取決于搜索過程中元素的比較次數(shù)。
理想的搜索方法：可以不經(jīng)過任何比較，一次直接從表中得到要搜索的元素。 如果構(gòu)造一種存儲結(jié)構(gòu)，通過某種函數(shù)(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數(shù)可以很快找到該元素。
當向該結(jié)構(gòu)中：

• 插入元素

根據(jù)待插入元素的關鍵碼，以此函數(shù)計算出該元素的存儲位置并按此位置進行存放

• 搜索元素

對元素的關鍵碼進行同樣的計算，把求得的函數(shù)值當做元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關鍵碼相等，則搜索成功

該方式即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表(HashTable)(或者稱散列表)

2.哈希沖突

對于兩個數(shù)據(jù)元素的關鍵字 和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同關鍵字通過相同哈希哈數(shù)計算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或哈希碰撞。

把具有不同關鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱為“同義詞”.

3.哈希函數(shù)

引起哈希沖突的一個原因可能是：哈希函數(shù)設計不夠合理。 哈希函數(shù)設計原則：

• 哈希函數(shù)的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間
• 哈希函數(shù)計算出來的地址能均勻分布在整個空間中
• 哈希函數(shù)應該比較簡單

常見哈希函數(shù)

1. 直接定制法–(常用)

取關鍵字的某個線性函數(shù)為散列地址：Hash（Key）= A*Key + B 優(yōu)點：簡單、均勻 缺點：需要事先知道關鍵字的分布情況 使用場景：適合查找比較小且連續(xù)的情況 面試題：字符串中第一個只出現(xiàn)一次字符

2. 除留余數(shù)法–(常用)

設散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：
Hash(key) = key% p(p<=m),將關鍵碼轉(zhuǎn)換成哈希地址

3. 平方取中法–(了解)

假設關鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希地址； 再比如關鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希地址 平方取中法比較適合：不知道關鍵字的分布，而位數(shù)又不是很大的情況

4. 折疊法–(了解)

折疊法是將關鍵字從左到右分割成位數(shù)相等的幾部分(最后一部分位數(shù)可以短些)，然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。
折疊法適合事先不需要知道關鍵字的分布，適合關鍵字位數(shù)比較多的情況

5. 隨機數(shù)法–(了解)

選擇一個隨機函數(shù)，取關鍵字的隨機函數(shù)值為它的哈希地址，即H(key) = random(key),其中random為隨機數(shù)函數(shù)。
通常應用于關鍵字長度不等時采用此法

6. 數(shù)學分析法–(了解)

設有n個d位數(shù)，每一位可能有r種不同的符號，這r種不同的符號在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號出現(xiàn)的機會均等，在某些位上分布不均勻只有某幾種符號經(jīng)常出現(xiàn)?？筛鶕?jù)散列表的大小，選擇其中各種符號分布均勻的若干位作為散列地址。

數(shù)字分析法通常適合處理關鍵字位數(shù)比較大的情況，如果事先知道關鍵字的分布且關鍵字的若干位分布較均勻的情況
注意：哈希函數(shù)設計的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無法避免哈希沖突

4.負載因子調(diào)節(jié)

負載因子和沖突率的關系粗略演示

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

已知哈希表中已有的關鍵字個數(shù)是不可變的，那我們能調(diào)整的就只有哈希表中的數(shù)組的大小。

5.解決哈希沖突兩種常見的方法：閉散列和開散列

1.閉散列

閉散列：也叫開放定址法，當發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個” 空位置中去。那如何尋找下一個空位置呢？

1. 線性探測

比如現(xiàn)在需要插入元素44，先通過哈希函數(shù)計算哈希地址，下標為4，因此44理論上應該插在該位置，但是該位置已經(jīng)放了值為4的元素，即發(fā)生哈希沖突。

線性探測：從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。

• 插入

• 1. 通過哈希函數(shù)獲取待插入元素在哈希表中的位置
• 2. 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測找到下一個空位置，插入新元素
• 3. 采用閉散列處理哈希沖突時，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來可能會受影響。因此線性探測采用標記的偽刪除法來刪除一個元素。

2. 二次探測

線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個空位置有關系，因為找空位置的方式就是挨著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為： = ( + )% m, 或者：= ( - )% m。其中：i = 1,2,3…， 是通過散列函數(shù)Hash(x)對元素的關鍵碼 key 進行計算得到的位置，m是表的大小。

研究表明：當表的長度為質(zhì)數(shù)且表裝載因子a不超過0.5時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時可以不考慮表裝滿的情況，但在插入時必須確保表的裝載因子a不超過0.5，如果超出必須考慮增容。

因此：比散列最大的缺陷就是空間利用率比較低，這也是哈希的缺陷。

2.開散列

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

開散列，可以認為是把一個在大集合中的搜索問題轉(zhuǎn)化為在小集合中做搜索了。

剛才我們提到了，哈希桶其實可以看作將大集合的搜索問題轉(zhuǎn)化為小集合的搜索問題了，那如果沖突嚴重，就意味著小集合的搜索性能其實也時不佳的，這個時候我們就可以將這個所謂的小集合搜索問題繼續(xù)進行轉(zhuǎn)化，例如：

1. 每個桶的背后是另一個哈希表
2. 每個桶的背后是一棵搜索樹

具體實現(xiàn)：

public class HashBuck {static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] arr;public int usedSize;public static final double LOAD_FACTOR = 0.75;public HashBuck() {arr = new Node[10];}public void put(int key,int val) {int index = key % arr.length;Node cur = arr[index];while (cur != null) {if(cur.key == key) {cur.val = val;return;}cur = cur.next;}//采用頭插法進行插入Node node = new Node(key,val);node.next = arr[index];arr[index] = node;usedSize++;if (calculateLoadFactor() >= LOAD_FACTOR) {//擴容resize();}}//如果要擴容每個元素到要進行重新的哈希計算private void resize() {Node[] newArray = new Node[2 * arr.length];for (int i = 0; i < arr.length; i++) {Node cur = arr[i];while (cur != null) {Node curNext = cur.next;int index = cur.key % newArray.length;//找到了在新的數(shù)組當中的位置cur.next = newArray[index];newArray[index] = cur;cur = curNext;}}arr = newArray;}//計算負載因子private double calculateLoadFactor() {return usedSize * 1.0 / arr.length;}public int get(int key) {int index = key % arr.length;Node cur = arr[index];while (cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return -1;}
}

6.性能分析

通常情況下我們認為哈希表的插入/刪除/查找時間復雜度是O(1) 。