??? 博客新人，希望大家一起加油進(jìn)步
??? 乾坤未定，你我皆黑馬
我們首先來(lái)看一下集合的框架結(jié)構(gòu)：
Set實(shí)現(xiàn)了Collection接口，Map是一個(gè)單獨(dú)存在的接口。
而下面又分別各有兩個(gè)類(lèi)，分別是TreeSet（HashSet）和 HashSet（HashMap）
Map和Set的作用是用來(lái)查找和搜索的；以后涉及到查找和搜索的可以選擇使用這兩個(gè)接口下面具體的類(lèi)。
搜索樹(shù)(“Tree”)
1、搜索樹(shù)(“Tree”)
1.1 概念
二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù):
- 若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
- 若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
- 它的左右子樹(shù)也分別為二叉搜索樹(shù)
如圖所示：
1.2 操作 - 查找
思路如圖：
- 代碼實(shí)現(xiàn)
/**
* 查找二叉搜索樹(shù)中指定的val值
*
* @param val
* @return
*/
public TreeNode find(int val) {
TreeNode cur = root;
// if(null == cur) {
// return null;
// }
while (cur != null) {
if (cur.val > val) {
cur = cur.right;
} else if (cur.val < val) {
cur = cur.left;
} else {
return cur;
}
}
return null;
}
1.3 操作 - 插入
- 如果樹(shù)為空樹(shù)，即根 == null，直接插入
- 如果樹(shù)不是空樹(shù)，按照查找邏輯確定插入位置，插入新節(jié)點(diǎn)
-
注意： 一般情況下是不插入相同的數(shù)據(jù)的
- 代碼實(shí)現(xiàn)
/**
* 插入一個(gè)數(shù)據(jù)
*
* @param val
*/
public void insert2(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.right;
}
if(cur.val > val) {
parent = cur;
cur = cur.left;
}
}
//走完之后判斷前一個(gè)結(jié)點(diǎn)是否比val大
if(cur.val < val) {
//parent.right.val = val;
parent.right = new TreeNode(val);
}
if(cur.val > val) {
//parent.left.val = val;
parent.left = new TreeNode(val);
}
}
1.4 操作-刪除（難點(diǎn)）
設(shè)待刪除結(jié)點(diǎn)為 cur, 待刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 parent
分為三種情況：
1. cur.left == null
- cur 是 root，則 root = cur.right
- cur 不是 root，cur 是 parent.left，則 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，則 parent.right = cur.right
2. cur.right == null
-
cur 是 root，則 root = cur.left
-
cur 不是 root，cur 是 parent.left，則 parent.left = cur.left
-
cur 不是 root，cur 是 parent.right，則 parent.right = cur.left
3. cur.left != null && cur.right != null
需要使用替換法進(jìn)行刪除，即在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小)，用它的值填補(bǔ)到被刪除節(jié)點(diǎn)中，再來(lái)處理該結(jié)點(diǎn)的刪除問(wèn)題
- 1.4.1 三種情況下也有具體要細(xì)分的：
- 待刪除的左邊為空 cur.left == null ，如圖所示：
- 待刪除的右邊為空 cur.left == null ，如圖所示：
- 待刪除的節(jié)點(diǎn)左右邊都不為空 .cur.left != null && cur.right != null ，如圖所示：
思路：找到刪除節(jié)點(diǎn)cur的右邊節(jié)點(diǎn)中最小的值，替換到cur處，最后把替換到最后的一個(gè)節(jié)點(diǎn)給刪除掉即可。
- 代碼實(shí)現(xiàn)
/**
* 刪除值為val的節(jié)點(diǎn)
* @param val
*/
//自己練習(xí)寫(xiě)的
public void remove(int val) {
TreeNode cur = root;
TreeNode parent = null; //用于記錄cur的前一個(gè)節(jié)點(diǎn)
while(cur != null) {
if(cur.val == val) {
removeNode2(parent,cur);
return;
}else if(cur.val > val) {
parent = cur;
cur = cur.left;
}else {
parent = cur;
cur = cur.right;
}
}
}
//自己練習(xí)寫(xiě)的
private void removeNode2(TreeNode parent, TreeNode cur) {
//第一種情況 cur是root
if(cur.left == null) {
if(cur == root) {
root = cur.right; //此時(shí)cur所在節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
return;
} else {
if(cur == parent.right) {
//第二種情況 cur不是root，cur是parent.right
parent.right = cur.right;
} else {
//第三種情況 cur不是root，cur是parent.left
parent.left = cur.right;
}
}
} else if(cur.right == null) {
if(cur == root) { //第一種情況 cur是root
root = cur.left; //此時(shí)cur所在節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
return;
} else {
if(cur == parent.right) {
//第二種情況 cur不是root，cur是parent.right
parent.right = cur.left;
} else {
//第三種情況 cur不是root，cur是parent.left
parent.left = cur.left;
}
}
} else { //cur左右都不為空節(jié)點(diǎn) 思路：找到cur右邊節(jié)點(diǎn)最小的值與之進(jìn)行交換就可以了
TreeNode targetP = cur;
TreeNode target = cur.right;
while(target.left != null) {
targetP = target;
target = target.left;
}
//走到這說(shuō)明target的左節(jié)點(diǎn)為空了
//進(jìn)行交換
cur.val = target.val;
if(target == targetP.left) {
targetP.left = target.right; //target.right為空也沒(méi)事，給到targetP.left，說(shuō)明targetP節(jié)點(diǎn)左側(cè)為空了
}
if(target == targetP.right) {
targetP.right = target.right; //這種情況是target沒(méi)有左節(jié)點(diǎn)，相當(dāng)于cur右邊節(jié)點(diǎn)是個(gè)右單樹(shù)
}
}
}
1.5 性能分析
-
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹(shù)中各個(gè)操作的性能。
-
對(duì)有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)，若每個(gè)元素查找的概率相等，則二叉搜索樹(shù)平均查找長(zhǎng)度是結(jié)點(diǎn)在二叉搜索樹(shù)的深度的函數(shù)，即結(jié)點(diǎn)越深，則比較次數(shù)越多。
-
但對(duì)于同一個(gè)關(guān)鍵碼集合，如果各關(guān)鍵碼插入的次序不同，可能得到不同結(jié)構(gòu)的二叉搜索樹(shù)。
最優(yōu)情況下，二叉搜索樹(shù)為完全二叉樹(shù)，其平均比較次數(shù)為：logN
最差情況下，二叉搜索樹(shù)退化為單支樹(shù)，其平均比較次數(shù)為：N/2
- TreeMap 和 TreeSet 即 java 中利用搜索樹(shù)實(shí)現(xiàn)的 Map 和 Set；實(shí)際上用的是紅黑樹(shù)，而紅黑樹(shù)是一棵近似平衡的二叉搜索樹(shù)，即在二叉搜索樹(shù)的基礎(chǔ)之上 + 顏色以及紅黑樹(shù)性質(zhì)驗(yàn)證。
2、搜索
2.1 概念及場(chǎng)景
Map和set是一種專(zhuān)門(mén)用來(lái)進(jìn)行搜索的容器或者數(shù)據(jù)結(jié)構(gòu)，其搜索的效率與其具體的實(shí)例化子類(lèi)有關(guān)。以前常見(jiàn)的搜索方式有：
- 直接遍歷，時(shí)間復(fù)雜度為O(N)，元素如果比較多效率會(huì)非常慢
- 二分查找，時(shí)間復(fù)雜度為 ,但搜索前必須要求序列是有序的
上述排序比較適合靜態(tài)類(lèi)型的查找，即一般不會(huì)對(duì)區(qū)間進(jìn)行插入和刪除操作了，而現(xiàn)實(shí)中的查找比如： - 根據(jù)姓名查詢(xún)考試成績(jī)
- 通訊錄，即根據(jù)姓名查詢(xún)聯(lián)系方式
- 不重復(fù)集合，即需要先搜索關(guān)鍵字是否已經(jīng)在集合中可能在查找時(shí)進(jìn)行一些插入和刪除的操作，即動(dòng)態(tài)查找，那上述兩種方式就不太適合了，本節(jié)介紹的Map和Set是一種適合動(dòng)態(tài)查找的集合容器。
2.2 模型
一般把搜索的數(shù)據(jù)稱(chēng)為關(guān)鍵字（Key），和關(guān)鍵字對(duì)應(yīng)的稱(chēng)為值（Value），將其稱(chēng)之為Key-value的鍵值對(duì)，所以模型會(huì)有兩種：
- 純 key 模型，比如：
有一個(gè)英文詞典，快速查找一個(gè)單詞是否在詞典中快速查找某個(gè)名字在不在通訊錄中 - 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的使用
3.1 關(guān)于Map的說(shuō)明
Map是一個(gè)接口類(lèi)，該類(lèi)沒(méi)有繼承自Collection，該類(lèi)中存儲(chǔ)的是<K,V>結(jié)構(gòu)的鍵值對(duì)，并且K一定是唯一的，不能重復(fù)。
3.2 關(guān)于Map.Entry<K, V>的說(shuō)明
Map.Entry<K, V> 是Map內(nèi)部實(shí)現(xiàn)的用來(lái)存放<key, value>鍵值對(duì)映射關(guān)系的內(nèi)部類(lèi)，該內(nèi)部類(lèi)中主要提供了<key, value>的獲取，value的設(shè)置以及Key的比較方式。
| 方法 | 解釋 |
|---|---|
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 將鍵值對(duì)中的value替換為指定value |
注意：Map.Entry<K,V>并沒(méi)有提供設(shè)置Key的方法
3.3 Map 的常用方法說(shuō)明
注意：
- Map是一個(gè)接口，不能直接實(shí)例化對(duì)象， 如果要實(shí)例化對(duì)象只能實(shí)例化其實(shí)現(xiàn)類(lèi)TreeMap或者HashMap
- Map中存放鍵值對(duì)的Key是唯一的，value是可以重復(fù)的
- 在TreeMap中插入鍵值對(duì)時(shí)，key不能為空，否則就會(huì)拋NullPointerException異常，value可以為空。但是HashMap的key和value都可以為空。
- Map中的Key可以全部分離出來(lái)，存儲(chǔ)到Set中來(lái)進(jìn)行訪問(wèn)(因?yàn)镵ey不能重復(fù))。
- Map中的value可以全部分離出來(lái)，存儲(chǔ)在Collection的任何一個(gè)子集合中(value可能有重復(fù))。
- Map中鍵值對(duì)的Key不能直接修改，value可以修改，如果要修改key，只能先將該key刪除掉，然后再來(lái)進(jìn)行重新插入。
- TreeMap和HashMap的區(qū)別如下圖所示：
4. Set的說(shuō)明
Set 的官方文檔：https://docs.oracle.com/javase/8/docs/api/java/util/Set.html
4.1 常見(jiàn)方法說(shuō)明
| 方法 | 解釋 |
|---|---|
| boolean add(E e) | 添加元素，但重復(fù)元素不會(huì)被添加成功 |
| void clear() | 清空集合 |
| boolean contains(Object o) | 判斷 o 是否在集合中 |
| Iterator iterator() | 返回迭代器 |
| boolean remove(Object o) | 刪除集合中的 o |
| int size() | 返回set中元素的個(gè)數(shù) |
| boolean isEmpty() | 檢測(cè)set是否為空，空返回true，否則返回false |
| Object[] toArray() | 將set中的元素轉(zhuǎn)換為數(shù)組返回 |
| boolean containsAll(Collection<?> c) | 集合c中的元素是否在set中全部存在，是返回true，否則返回false |
| boolean addAll(Collection<? extendsE> c) | 將集合c中的元素添加到set中，可以達(dá)到去重的效果 |
注意：
- Set是繼承自Collection的一個(gè)接口類(lèi)
- Set中只存儲(chǔ)了key，并且要求key一定要唯一
- TreeSet的底層是使用Map來(lái)實(shí)現(xiàn)的，其使用key與Object的一個(gè)默認(rèn)對(duì)象作為鍵值對(duì)插入到Map中的
- Set最大的功能就是對(duì)集合中的元素進(jìn)行去重
- 實(shí)現(xiàn)Set接口的常用類(lèi)有TreeSet和HashSet，還有一個(gè)LinkedHashSet，LinkedHashSet是在HashSet的基礎(chǔ)
上維護(hù)了一個(gè)雙向鏈表來(lái)記錄元素的插入次序。- Set中的Key不能修改，如果要修改，先將原來(lái)的刪除掉，然后再重新插入
- TreeSet中不能插入null的key，HashSet可以。
- TreeSet和HashSet的區(qū)別 如下圖所示：
| Set底層結(jié)構(gòu) | TreeSet | HashSet |
|---|---|---|
| 底層結(jié)構(gòu) | 紅黑樹(shù) | 哈希桶 |
| 插入/刪除/查找時(shí)間復(fù)雜度 | 0(Log N) | O(1) |
| 是否有序 | 關(guān)于Key有序 | 不一定有序 |
| 線程安全 | 不安全 | 不安全 |
| 插入/刪除/查找區(qū)別 | 按照紅黑樹(shù)的特性來(lái)進(jìn)行插入和刪除 | 1. 先計(jì)算key哈希地址 2. 然后進(jìn)行插入和刪除 |
| 比較與覆寫(xiě) | key必須能夠比較，否則會(huì)拋出ClassCastException異常 | 自定義類(lèi)型需要覆寫(xiě)equals和hashCode方法 |
| 應(yīng)用場(chǎng)景 | 需要Key有序場(chǎng)景下 | Key是否有序不關(guān)心，需要更高的時(shí)間性能 |
解決下面的三個(gè)問(wèn)題:
- 統(tǒng)計(jì)10W個(gè)數(shù)據(jù)當(dāng)中，不重復(fù)的數(shù)據(jù)？(去重)
- 統(tǒng)計(jì)10W個(gè)數(shù)據(jù)當(dāng)中，第一個(gè)重復(fù)的數(shù)據(jù)？
- 統(tǒng)計(jì)10W個(gè)數(shù)據(jù)當(dāng)中，每個(gè)數(shù)據(jù)出現(xiàn)的次數(shù)？(對(duì)應(yīng)的關(guān)系)
-
解題思路： 利用set可以達(dá)到去重的效果，出現(xiàn)的次數(shù)可以用到K - V 模型，即是map
-
代碼實(shí)現(xiàn)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-409473.html
import java.util.*;
public class Test {
//1、統(tǒng)計(jì)10W個(gè)數(shù)據(jù)當(dāng)中，不重復(fù)的數(shù)據(jù)？[去重]
public static void func1(int[] array) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < array.length; i++) {
set.add(array[i]);
}
System.out.println(set);
}
//2、統(tǒng)計(jì)10W個(gè)數(shù)據(jù)當(dāng)中，第一個(gè)重復(fù)的數(shù)據(jù)？
public static void func2(int[] array) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < array.length; i++) {
if(!set.contains(array[i])) {
set.add(array[i]);
}else {
System.out.println(array[i]);
break;
}
}
}
//3、統(tǒng)計(jì)10W個(gè)數(shù)據(jù)當(dāng)中，每個(gè)數(shù)據(jù)出現(xiàn)的次數(shù)？ 對(duì)應(yīng)的關(guān)系
public static void func3(int[] array) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i++) {
int key = array[i];
if(map.get(key) == null) {
map.put(key, 1);
}else {
int val = map.get(key);
map.put(key, val+1);
}
}
//利用foreach語(yǔ)句 來(lái)遍歷Map.Entry<K, V>導(dǎo)出的K-V 對(duì)應(yīng)的關(guān)系來(lái)獲取次數(shù)
for (Map.Entry<Integer, Integer> entry:map.entrySet()) {
System.out.println("key: "+ entry.getKey()+"出現(xiàn)了: "+entry.getValue()+" 次");
}
}
public static void main(String[] args) {
int[] array = new int[10_0000];
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(5_0000);
}
func1(array);
func2(array);
func3(array);
}
}
????????? 好啦，到這里我們的 Set 和 Map 的分享就沒(méi)了，如果感覺(jué)做的還不錯(cuò)的可以點(diǎn)個(gè)贊，關(guān)注一下，你的支持就是我繼續(xù)下去的動(dòng)力，蟹蟹大家了，我們下期再見(jiàn)，拜拜~ ☆*: .?. o(≧▽≦)o .?.:*☆文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-409473.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 | java中 map和set 詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]-map和set](https://imgs.yssmx.com/Uploads/2024/02/764611-1.png)
