1.搜索樹

1.定義

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

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

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

2.基本操作

1.查找

查找過程：

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

2.插入

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

3.刪除

設(shè)待刪除結(jié)點(diǎn)為 cur, 待刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 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
需要使用替換法進(jìn)行刪除，即在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來處理該結(jié)點(diǎn)的刪除問題

4.代碼實(shí)現(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;}/*** 插入一個(gè)數(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é)點(diǎn)* @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.簡(jiǎn)單介紹

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

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

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

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

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

2.模型

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

1. 純 key 模型，比如：

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

2. Key-Value 模型，比如：

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

而Map中存儲(chǔ)的就是key-value的鍵值對(duì)，Set中只存儲(chǔ)了Key。

3.Map的使用

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

1.關(guān)于Map.Entry<K, V>的說明

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

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

2.Map 的常用方法說明

注意：

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

4.Set的使用

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

1.Set的常見方法說明

注意：

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

3.哈希表

1.概念

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

• 插入元素

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

• 搜索元素

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

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

2.哈希沖突

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

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

3.哈希函數(shù)

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

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

常見哈希函數(shù)

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

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

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

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

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

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

4. 折疊法–(了解)

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

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

選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key) = random(key),其中random為隨機(jī)數(shù)函數(shù)。
通常應(yīng)用于關(guān)鍵字長(zhǎng)度不等時(shí)采用此法

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

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

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

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

負(fù)載因子和沖突率的關(guān)系粗略演示

所以當(dāng)沖突率達(dá)到一個(gè)無法忍受的程度時(shí)，我們需要通過降低負(fù)載因子來變相的降低沖突率。

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

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

1.閉散列

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

1. 線性探測(cè)

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

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

• 插入

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

2. 二次探測(cè)

線性探測(cè)的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個(gè)空位置有關(guān)系，因?yàn)檎铱瘴恢玫姆绞骄褪前ぶ笾饌€(gè)去找，因此二次探測(cè)為了避免該問題，找下一個(gè)空位置的方法為： = ( + )% m, 或者：= ( - )% m。其中：i = 1,2,3…， 是通過散列函數(shù)Hash(x)對(duì)元素的關(guān)鍵碼 key 進(jìn)行計(jì)算得到的位置，m是表的大小。

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

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

2.開散列

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

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

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

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

具體實(shí)現(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;}//采用頭插法進(jìn)行插入Node node = new Node(key,val);node.next = arr[index];arr[index] = node;usedSize++;if (calculateLoadFactor() >= LOAD_FACTOR) {//擴(kuò)容resize();}}//如果要擴(kuò)容每個(gè)元素到要進(jìn)行重新的哈希計(jì)算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ù)組當(dāng)中的位置cur.next = newArray[index];newArray[index] = cur;cur = curNext;}}arr = newArray;}//計(jì)算負(fù)載因子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.性能分析

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