??Map與Set的概念及場景

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

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

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

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

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

??Map與Set模型介紹

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

1. 純 key 模型，比如：

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

2. Key-Value 模型，比如：

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

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

??Map 的使用

Map官方文檔

??Map說明

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

??Map.Entry<K, V>的說明

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

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

??Map 的常用方法說明

??注意事項

1. Map是一個接口，不能直接實例化對象，如果要實例化對象只能實例化其實現(xiàn)類TreeMap或者HashMap

2. Map中存放鍵值對的Key是唯一的，value是可以重復(fù)的

3. 在TreeMap中插入鍵值對時，key不能為空，否則就會拋NullPointerException異常，value可以為空。但是HashMap的key和value都可以為空。

4. Map中的Key可以全部分離出來，存儲到Set中來進(jìn)行訪問(因為Key不能重復(fù))。

5. Map中的value可以全部分離出來，存儲在Collection的任何一個子集合中(value可能有重復(fù))。

6. Map中鍵值對的Key不能直接修改，value可以修改，如果要修改key，只能先將該key刪除掉，然后再來進(jìn)行重新插入。

7. TreeMap和HashMap的區(qū)別
   

??TreeMap的使用

import java.util.Map;
import java.util.TreeMap;

public class TestMap {
    public static void main(String[] args) {
        TestMap();
    }
    public static void TestMap() {
        Map<String, String> m = new TreeMap<>();

        // put(key, value):插入key-value的鍵值對
        // 如果key不存在，會將key-value的鍵值對插入到map中,返回null
        m.put("林沖", "豹子頭");
        m.put("魯智深", "花和尚");
        m.put("武松", "行者");
        m.put("宋江", "及時雨");
        String str = m.put("李逵", "黑旋風(fēng)");
        System.out.println(m.size());
        System.out.println(m);

        // put(key,value): 注意key不能為空，但是value可以為空
        // key如果為空，會拋出空指針異常
        //m.put(null, "花名");
        str = m.put("無名", null);
        System.out.println(m.size());

        // put(key, value):
        // 如果key存在，會使用value替換原來key所對應(yīng)的value，返回舊value
        str = m.put("李逵", "鐵牛");

        // get(key): 返回key所對應(yīng)的value
        // 如果key存在，返回key所對應(yīng)的value
        // 如果key不存在，返回null
        System.out.println(m.get("魯智深"));
        System.out.println(m.get("史進(jìn)"));

        //GetOrDefault(): 如果key存在，返回與key所對應(yīng)的value，如果key不存在，返回一個默認(rèn)值
        System.out.println(m.getOrDefault("李逵", "鐵牛"));
        System.out.println(m.getOrDefault("史進(jìn)", "九紋龍"));
        System.out.println(m.size());

        //containKey(key)：檢測key是否包含在Map中，時間復(fù)雜度：O(logN)
        // 按照紅黑樹的性質(zhì)來進(jìn)行查找
        // 找到返回true，否則返回false
        System.out.println(m.containsKey("林沖"));
        System.out.println(m.containsKey("史進(jìn)"));

        // containValue(value): 檢測value是否包含在Map中，時間復(fù)雜度: O(N)
        // 找到返回true，否則返回false
        System.out.println(m.containsValue("豹子頭"));
        System.out.println(m.containsValue("九紋龍"));

        // 打印所有的key
        // keySet是將map中的key防止在Set中返回的
        for (String s : m.keySet()) {
            System.out.print(s + " ");
        }
        System.out.println();

        // 打印所有的value
        // values()是將map中的value放在collect的一個集合中返回的
        for (String s : m.values()) {
            System.out.print(s + " ");
        }
        System.out.println();

        // 打印所有的鍵值對
        // entrySet(): 將Map中的鍵值對放在Set中返回了
        for (Map.Entry<String, String> entry : m.entrySet()) {
            System.out.println(entry.getKey() + "--->" + entry.getValue());
        }
        System.out.println();
    }
}

運(yùn)行結(jié)果如下：

??Set 的說明

Set官方文檔

Set與Map主要的不同有兩點：

• Set是繼承自Collection的接口類

• Set中只存儲了Key

?常見方法說明

??注意事項：

1. Set是繼承自Collection的一個接口類

2. Set中只存儲了key，并且要求key一定要唯一

3. TreeSet的底層是使用Map來實現(xiàn)的，其使用key與Object的一個默認(rèn)對象作為鍵值對插入到Map中的

4. Set最大的功能就是對集合中的元素進(jìn)行去重

5. 實現(xiàn)Set接口的常用類有TreeSet和HashSet，還有一個LinkedHashSet，LinkedHashSet是在HashSet的基礎(chǔ)上維護(hù)了一個雙向鏈表來記錄元素的插入次序。

6. Set中的Key不能修改，如果要修改，先將原來的刪除掉，然后再重新插入

7. TreeSet中不能插入null的key，HashSet可以。

8. TreeSet和HashSet的區(qū)別
   

??TreeSet使用案例

import java.util.Set;
import java.util.Iterator;
import java.util.TreeSet;

public class TestSet {
    public static void main(String[] args) {
        TestSet();
    }
    public static void TestSet(){
        Set<String> s = new TreeSet<>();

        // add(key): 如果key不存在，則插入，返回ture
        // 如果key存在，返回false
        boolean 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，否則返回false
        System.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);
        s.remove("watermelen");
        System.out.println(s);
        
        //迭代器
        Iterator<String> it = s.iterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
    }
}

??哈希表

?????概念

順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個元素時，必須要經(jīng)過關(guān)鍵碼的多次比較。

順序查找時間復(fù)雜度為O(N)，平衡樹中為樹的高度，即O( )，搜索的效率取決于搜索過程中元素的比較次數(shù)。

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

當(dāng)向該結(jié)構(gòu)中：

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

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

例如：數(shù)據(jù)集合{1，7，6，4，5，9}；

哈希函數(shù)設(shè)置為：hash(key) = key % capacity; capacity為存儲元素底層空間總的大小。

用該方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較，因此搜索的速度比較快

但是問題出現(xiàn)了：按照上述哈希方式，向集合中插入元素44，會出現(xiàn)什么問題？

這就涉及我們下面要講的沖突

??沖突

??沖突的概念

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

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

??沖突避免

首先，我們需要明確一點，由于我們哈希表底層數(shù)組的容量往往是小于實際要存儲的關(guān)鍵字的數(shù)量的，這就導(dǎo)致一個問題，沖突的發(fā)生是必然的，但我們能做的應(yīng)該是盡量的降低沖突率

??哈希函數(shù)設(shè)計避免沖突

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

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

• 哈希函數(shù)計算出來的地址能均勻分布在整個空間中

• 哈希函數(shù)應(yīng)該比較簡單

常見哈希函數(shù)有：

??直接定制法–(常用)

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

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

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

??平方取中法–(了解)

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

??折疊法–(了解)

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

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

選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key) = random(key),其中random為隨機(jī)數(shù)函數(shù)。

通常應(yīng)用于關(guān)鍵字長度不等時采用此法

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

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

假設(shè)要存儲某家公司員工登記表，如果用手機(jī)號作為關(guān)鍵字，那么極有可能前7位都是 相同的，那么我們可以選擇后面的四位作為散列地址，如果這樣的抽取工作還容易出現(xiàn) 沖突，還可以對抽取出來的數(shù)字進(jìn)行反轉(zhuǎn)(如1234改成4321)、右環(huán)位移(如1234改成4123)、左環(huán)移位、前兩數(shù)與后兩數(shù)疊加(如1234改成12+34=46)等方法。

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

注意：哈希函數(shù)設(shè)計的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無法避免哈希沖突

?????負(fù)載因子調(diào)節(jié)避免沖突

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

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

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

??沖突解決

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

??閉散列

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

那如何尋找下一個空位置呢？我們有以下兩個方法

??線性探測

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

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

插入

• 通過哈希函數(shù)獲取待插入元素在哈希表中的位置

• 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測找到下一個空位置，插入新元素
  

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

??二次探測

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

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

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

?????開散列/哈希桶

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

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

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

??沖突嚴(yán)重時的解決辦法

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

1. 每個桶的背后是另一個哈希表

2. 每個桶的背后是一棵搜索樹

??哈希表性能分析

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

?哈希java類集的關(guān)系

1. HashMap 和 HashSet 即 java 中利用哈希表實現(xiàn)的 Map 和 Set

2. java 中使用的是哈希桶方式解決沖突的

3. java 會在沖突鏈表長度大于一定閾值后，將鏈表轉(zhuǎn)變?yōu)樗阉鳂洌t黑樹）

4. java 中計算哈希值實際上是調(diào)用的類的 hashCode 方法，進(jìn)行 key 的相等性比較是調(diào)用 key 的 equals 方法。所以如果要用自定義類作為 HashMap 的 key 或者 HashSet 的值，必須覆寫 hashCode 和 equals 方法，而且要做到 equals 相等的對象，hashCode 一定是一致的

?總結(jié)

關(guān)于《【數(shù)據(jù)結(jié)構(gòu)】 Map和Set詳解》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關(guān)注，點贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-708405.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 Map和Set詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！