[本節目標]

*掌握HashMap/TreeMap/HashSet/TreeSet的使用

*掌握了解HashSet和HashSet背后的哈希原理和簡單的實現

1. 搜索樹

1.1 概念

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

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

1.2 操作-查找?

代碼思路:

先判斷根節點,然后再分別判斷左右子樹.

public class Demo50 {class Treenode{int val;Treenode right;Treenode left;public Treenode(int val){this.val = val;}}public Treenode root;public boolean search(int key){
Treenode cur = root;
while(cur != null){if(cur.val == key){return true;} else if (cur.val < key) {cur = cur.left;}else{cur = cur.right;}
}
return false;}}

1.3 操作-插入

代碼思路:?

先用while循環找到插入的位置,然后再用parent記錄下來,再創建一個新的,接在記錄parent的子類.

public class Demo51 {class Treenode{int val;Treenode right;Treenode left;public Treenode(int val){this.val = val;}}public Treenode root;public boolean insert(int val){
if(root==null){Treenode root = new Treenode(val);
}
Treenode cur = root;
Treenode parent = null;
while(cur != null){if(cur.val < val){parent = cur;cur=cur.right;} else if (cur.val > val) {parent = cur;cur = cur.left;}else{return false;}
}Treenode node = new Treenode(val);
if(parent.val>val){parent.right = node;
}
else {parent.left = node;
}
return true;}
}

1.4 操作-刪除(難點)

設待刪除結點為 cur, 待刪除結點的雙親結點為 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
1). cur 是 root，則 root = cur.left
2). cur 不是 root，cur 是 parent.left，則 parent.left = cur.left
3). cur 不是 root，cur 是 parent.right，則 parent.right = cur.left

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

public class Demo52 {class Treenode{int val;Treenode right;Treenode left;}public Treenode root = null;public void remove(int key) {Treenode partent = null;Treenode cur = root;while (cur != null) {if (cur.val < key) {partent = cur;break;} else if (cur.val > key) {partent = cur;cur = cur.right;} else {removenode(cur, partent);}}}public void removenode(Treenode cur,Treenode partent) {if (cur.left == null) {if (root == cur) {root = cur.right;} else if (cur == partent.left) {partent.left = cur.right;} else {partent.right = cur.right;}} else if (cur.right == null) {if(root == cur){root = cur.left;}else if(cur == partent.left){partent.left = cur.left;}else{partent.right = cur.left;}} else {//圖片的解說對應這里
Treenode targetParent = cur;
Treenode target = cur.right;
while(target.left != null){targetParent = target;target = target.left;
}
cur.val = target.val;
if(targetParent.left == target){targetParent.left = target.right;
}
else{targetParent.right =target.right;
}}}
}

1.6? 性能分析

插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數，即結點越深，則比較次數越多。
但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹：

1.7 和集合類的關系

TreeMap 和 TreeSet 即 java 中利用搜索樹實現的 Map 和 Set；實際上用的是紅黑樹，而紅黑樹是一棵近似平衡的二叉搜索樹，即在二叉搜索樹的基礎之上 + 顏色以及紅黑樹性質驗證，關于紅黑樹的內容后序再進行講解。

2. 搜索

2.1 概念即場景

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

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

上述排序比較適合靜態類型的查找，即一般不會對區間進行插入和刪除操作了，而現實中的查找比如：
1. 根據姓名查詢考試成績
2. 通訊錄，即根據姓名查詢聯系方式
3. 不重復集合，即需要先搜索關鍵字是否已經在集合中
可能在查找時進行一些插入和刪除的操作，即動態查找，那上述兩種方式就不太適合了，本節介紹的Map和Set是一種適合動態查找的集合容器。

2.2? 模型

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

?純 key 模型，比如：
有一個英文詞典，快速查找一個單詞是否在詞典中
快速查找某個名字在不在通訊錄中
2. Key-Value 模型，比如：
統計文件中每個單詞出現的次數，統計結果是每個單詞都有與其對應的次數：<單詞，單詞出現的次數>
梁山好漢的江湖綽號：每個好漢都有自己的江湖綽號

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

3.? Map的使用

3.1 關于Map的說明

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

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

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

解釋+例子:map.put("hello",5),就是對應Map.Entry<K, V>,entry是Map里面的一個接口,然后把K,V看成了一個整體,然后Set包含了很多個map.

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

3.3 Map的常用方法

V get(Object key)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回 key 對應的 value
V getOrDefault(Object key, V defaultValue)? ? ? ? ? ? ? ? ? 返回 key 對應的 value，key 不存在，返回默認值
V put(K key, V value)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?設置 key 對應的 value
V remove(Object key)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 刪除 key 對應的映射關系
Set<K> keySet()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回所有 key 的不重復集合
Collection<V> values()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回所有 value 的可重復集合
Set<Map.Entry<K, V>> entrySet()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回所有的 key-value 映射關系
boolean containsKey(Object key)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?判斷是否包含 key
boolean containsValue(Object value)? ? ? ? ? ? ? ? ? ? ? ? ? ?判斷是否包含 value

注意：
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刪除掉，然后再來進行重新插入。
7. TreeMap和HashMap的區別(最后會講到)

Map示例:

import java.util.Arrays;
import java.util.TreeMap;
import java.util.Map;public class Mapdemo1 {public static void main(String[] args) {Map<String, String> treeMap = new TreeMap<>();treeMap.put("林沖", "豹子頭");treeMap.put("魯智深", "花和尚");treeMap.put("武松", "行者");treeMap.put("宋江", "及時雨");String str = treeMap.put("李逵", "黑旋風");System.out.println(treeMap.size());System.out.println(treeMap);System.out.println(str);// put(key,value): 注意key不能為空，但是value可以為空// key如果為空，會拋出空指針異常//treeMap.put(null, "花名");     這里會拋出異常treeMap.put("無名", null);System.out.println(treeMap.size());// put(key, value):// 如果key存在，會使用value替換原來key所對應的value，返回舊valuetreeMap.put("李逵", "鐵牛");System.out.println(treeMap);// get(key): 返回key所對應的value// 如果key存在，返回key所對應的value// 如果key不存在，返回nullSystem.out.println(treeMap.get("魯智深"));System.out.println(treeMap.get("史進"));System.out.println("***************************");//GetOrDefault(): 如果key存在，返回與key所對應的value，如果key不存在，返回一個默認值System.out.println(treeMap.getOrDefault("李逵", "鐵牛"));System.out.println(treeMap.getOrDefault("史進", "九紋龍"));//containKey(key)：檢測key是否包含在Map中，時間復雜度：O(logN)// 按照紅黑樹的性質來進行查找// 找到返回true，否則返回falseSystem.out.println(treeMap.containsKey("林沖"));System.out.println(treeMap.containsKey("史進"));// 打印所有的key// keySet是將map中的key防止在Set中返回的for(String s : treeMap.keySet()){System.out.print(s + " ");}System.out.println();System.out.println("********************************");// 打印所有的value// values()是將map中的value放在collect的一個集合中返回的for(String s : treeMap.values()){System.out.print(s + " ");}System.out.println();// 打印所有的鍵值對// entrySet(): 將Map中的鍵值對放在Set中返回了for(Map.Entry<String, String> entry : treeMap.entrySet()){System.out.println(entry.getKey() + "--->" + entry.getValue());}System.out.println();}}

4. Set的使用

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

4.1 Set常見的方法和使用

方法? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?解釋
boolean add(E e)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 添加元素，但重復元素不會被添加成功
void clear()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 清空集合
boolean contains(Object o)? ? ? ? ? ? ? ? ? ? ? ? ? ? ?判斷 o 是否在集合中
Iterator<E> iterator()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?返回迭代器
boolean remove(Object o)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 刪除集合中的 o
int size()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 返回set中元素的個數
boolean isEmpty()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 檢測set是否為空，空返回true，否則返回false
Object[] toArray()? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 將set中的元素轉換為數組返回
boolean containsAll(Collection<?> c)? ? ? ? ? ? ?集合c中的元素是否在set中全部存在，是返回true，否則返回false
boolean addAll(Collection<? extends E> c)? ? 將集合c中的元素添加到set中，可以達到去重的效果

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

Set示例

import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
public class SetDemo1 {public static void main(String[] args) {Set<String> s = new TreeSet<>();
// add(key): 如果key不存在，則插入，返回ture
// 如果key存在，返回falseboolean isIn = s.add("apple");s.add("orange");s.add("peach");s.add("banana");System.out.println(s.size());System.out.println(s);isIn = s.add("apple");
// add(key): key如果是空，拋出空指針異常
//s.add(null);
// contains(key): 如果key存在，返回true，否則返回falseSystem.out.println(s.contains("apple"));System.out.println(s.contains("watermelen"));
// remove(key): key存在，刪除成功返回true
// key不存在，刪除失敗返回false
// key為空，拋出空指針異常s.remove("apple");System.out.println(s);System.out.println("********");System.out.println(s.remove("watermelen"));System.out.println(s);Iterator<String> it = s.iterator();while (it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();}
}

5. 哈希表

5.1 概念

順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵碼的多次比較。順序查找時間復雜度為O(N)，平衡樹中為樹的高度，即O( )，搜索的效率取決于搜索過程中元素的比較次數。

理想的搜索方法：可以不經過任何比較，一次直接從表中得到要搜索的元素。 如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數可以很快找到該元素。

當向該結構中：
插入元素:
據待插入元素的關鍵碼，以此函數計算出該元素的存儲位置并按此位置進行存放

搜索元素:

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

該方式即為哈希(散列)方法，哈希方法中使用的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(HashTable)(或者稱散列表)

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

用該方法進行搜索不必進行多次關鍵碼的比較，因此搜索的速度比較快 問題：按照上述哈希方式，向集合中插入元素44,就會出現問題.

接下來我們就來討論這些問題.

5.2 沖突-概念

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

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

5.3 沖突-避免

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

5.4 沖突-避免-哈希函數升級

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

*哈希函數的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間

*哈希函數計算出來的地址能均勻分布在整個空間中

*哈希函數應該比較簡單
常見哈希函數

1.直接定制法(常用)

取關鍵字的某個線性函數為散列地址：Hash（Key）= A*Key + B 優點：簡單、均勻 缺點：需要事先知道關鍵字的分布情況 使用場景：適合查找比較小且連續的情況?

2.除留余數法(常用)

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

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

4. 折疊法--(了解)

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

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

6. 數學分析法--(了解)
設有n個d位數，每一位可能有r種不同的符號，這r種不同的符號在各位上出現的頻率不一定相同，可能在某些位上分布比較均勻，每種符號出現的機會均等，在某些位上分布不均勻只有某幾種符號經常出現。可根據散列表的大小，選擇其中各種符號分布均勻的若干位作為散列地址。

數字分析法通常適合處理關鍵字位數比較大的情況，如果事先知道關鍵字的分布且關鍵字的若干位分布較均勻的情況

綜上

注意：哈希函數設計的越精妙，產生哈希沖突的可能性就越低，但是無法避免哈希沖突

5.5 沖突-避免-負載因子調節(重點)

所以當沖突率達到一個無法忍受的程度時，我們需要通過降低負載因子來變相的降低沖突率。
已知哈希表中已有的關鍵字個數是不可變的，那我們能調整的就只有哈希表中的數組的大小.

5.6 沖突-解決

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

5.7 沖突-解決-閉散型

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

1. 線性探測
比如上面的場景，現在需要插入元素44，先通過哈希函數計算哈希地址，下標為4，因此44理論上應該插在該位置，但是該位置已經放了值為4的元素，即發生哈希沖突。
線性探測：從發生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。
? ? ? 插入:

? ? ? 通過哈希函數獲取待插入元素在哈希表中的位置??
? ? ? 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發生哈希沖突，使用線性探測找到下一個空位置，插入新元素

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

2.二次探測

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

這就是一次和二次的區別

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

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

5.8 沖突-解決-開散列/哈希桶（重點)

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

從上圖可以看出，開散列中每個桶中放的都是發生哈希沖突的元素。
開散列，可以認為是把一個在大集合中的搜索問題轉化為在小集合中做搜索了。

5.9 沖突嚴重時的解決辦法

剛才我們提到了，哈希桶其實可以看作將大集合的搜索問題轉化為小集合的搜索問題了，那如果沖突嚴重，就意味著小集合的搜索性能其實也時不佳的，這個時候我們就可以將這個所謂的小集合搜索問題繼續進行轉化，例如：
1. 每個桶的背后是另一個哈希表
2. 每個桶的背后是一棵搜索樹

演示(創建桶):

class MHashMap{final static double Loodfactor = 0.75;static class Node{int k;int val;Node next;public Node(int k, int val) {this.k = k;this.val = val;}}Node[] array ;int size;public MHashMap() {array = new Node[10];}public  void put(int key, int val){int index = key % array.length;//遍歷index下標的key,看是否存在key,如果存在則更新val;Node cur = array[index];while(cur != null){if(key == cur.val){cur.val = val;return;}cur = cur.next;}Node node = new Node(key,val);node.next = array[index];array[index] = node;size++;if(doLoodfactor()>Loodfactor){}}public double doLoodfactor(){return size*1.0/ array.length;}public void resize(){Node[] newarray = new Node[2* array.length];for (int i = 0; i < array.length ; i++) {Node cur = array[i];while(cur != null){int newIndex = cur.k% newarray.length;Node node = new Node(cur.k, cur.val);node.next = newarray[newIndex];newarray[newIndex] = node;cur = cur.next;}}array = newarray;}public int get(int key){int index = key % array.length;//遍歷index下標的key,看是否存在key,如果存在則更新val;Node cur = array[index];while(cur != null){if(cur.k == key){return cur.val;}cur = cur.next;}return -1;}
}

雖然哈希表一直在和沖突做斗爭，但在實際使用過程中，我們認為哈希表的沖突率是不高的，沖突個數是可控的，
也就是每個桶中的鏈表的長度是一個常數，所以，通常意義下，我們認為哈希表的插入/刪除/查找時間復雜度是O(1).

6. 和Java類的關系

1. HashMap 和 HashSet 即 java 中利用哈希表實現的 Map 和 Set
2. java 中使用的是哈希桶方式解決沖突的
3. java 會在沖突鏈表長度大于一定閾值后，將鏈表轉變為搜索樹（紅黑樹）
4. java 中計算哈希值實際上是調用的類的 hashCode 方法，進行 key 的相等性比較是調用 key 的 equals 方法。所以如果要用自定義類作為 HashMap 的 key 或者 HashSet 的值，必須覆寫 hashCode 和 equals 方法，而且要做到 equals 相等的對象，hashCode 一定是一致的。