Java Map和Set

目錄

• • 1. 二叉排序樹(二叉搜尋樹)
  • • 1.1 二叉搜尋樹的查找
    • 1.2 二叉搜尋樹的插入
    • 1.3 二叉搜尋樹的删除（7種情況）
    • 1.4 二叉搜尋樹和TreeMap、TreeSet的關系
  • 2. Map和Set的差別與聯系
  • • 2.1 從接口架構的角度分析
    • 2.2 從存儲的模型角度分析【2種模型】
  • 3. 關于Map
  • • 3.1 Map的注意事項
    • 3.2 TreeMap 和 HashMap的對比
    • 3.3 Map.Entry<k,v>的用法 （周遊）
  • 4. 關于Set
  • • 4.1 Set的注意事項
    • 4.2 TreeSet 和 HashSet的對比
    • 4.3 疊代器周遊Set
  • 5. 哈希表
  • • 5.1 哈希函數
    • 5.2 沖突
    • 5.3 沖突的解決：開放位址法和鍊位址法
    • 5.4 哈希表與Java集合類的關系
  • 6. HashMap源碼分析
  • • 6.1 成員變量
    • 6.2 構造方法
    • 6.3 put方法源碼

1. 二叉排序樹(二叉搜尋樹)

二叉搜尋樹又稱二叉排序樹

• 若左子樹不為空，則左子樹上所有節點的值都小于根節點的值
• 若右子樹不為空，則右子樹上所有節點的值都大于根節點的值

• 左右子樹也分别是二叉搜尋樹

  【左小右大】

1.1 二叉搜尋樹的查找

【二叉搜尋樹的查找，一般情況下一次可以幹掉很多資料】

為了保證每次可以幹掉很多資料

思路：取周遊節點為cur，每次要查找的值val和cur的val進行比較，如果要查找的值比cur的val小，則去cur的左邊繼續查找，如果大則去cur的右邊繼續查找。

public boolean search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }else if (cur.val > val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        return false;
    }
           

1.2 二叉搜尋樹的插入

思路：整體思路與查找的思路類似，但是二叉搜尋樹的每次插入的節點一定是葉子節點，是以需要記錄待插入節點的雙親。

當cur為空時，parent記錄了待插入結點的父親位置，再用val和parent的val比較進行插入。

public void insert (int val) {
        Node node = new Node(val);
        if (root == null) {
            root = node;
            return;
        }
        Node cur = root;
        Node parent = root;
        while (cur != null) {
            if (cur.val == val) {
                return;
            }else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }
        if (parent.val > val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
    }
           

1.3 二叉搜尋樹的删除（7種情況）

設待删除結點為cur，待删除結點的雙親結點為parent

整體看分以下3種大情況：

①cur的左為空

②cur的右為空

③cur的左和右都不為空

繼續細分：cur是不是root；cur不是root的話，是parent的左還是parent的右

故有3 + 3 + 1 = 7種情況。

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

   此時需要使用替換法進行删除，即在它的右子樹種尋找中序下的第一個結點（關鍵碼最小），用它的值填補到被删除節點中，再來處理該結點的删除問題。

   1.4 二叉搜尋樹和TreeMap、TreeSet的關系

   TreeMap和TreeSet是Java種利用搜尋樹實作的Map和Set，實際上用的是紅黑樹，紅黑樹是一顆近似平衡的二叉搜尋樹，即在二叉搜尋樹的基礎之上+顔色以及紅黑樹性質。

2. Map和Set的差別與聯系

2.1 從接口架構的角度分析

Map是一個獨立的接口，而Set繼承自Collection接口。

TreeMap 和 TreeSet 都繼承了一個Sorted接口，說明 Tree某某 都是經過排序的，即 Tree某某 都是關于key有序的。

2.2 從存儲的模型角度分析【2種模型】

1. Map中存儲的是鍵值對key-value
2. Set中隻存儲了key

3. 關于Map

Map是一個接口類，該類沒有繼承collection，該類中存儲的是<k,v>結構的鍵值對，并且k一定是唯一的，不能重複。

3.1 Map的注意事項

1. Map是一個接口，不能直接執行個體化對象，如果要執行個體化對象隻能執行個體化其實作類TreeMap或者HashMap。

Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new TreeMap<>();
           

1. Map中存放鍵值對的鍵key是唯一的，key不可以重複，但是value可以重複。
2. 在TreeMap中插入鍵值隊的時候，key不能為空，否則會抛出NPE（空指針異常），但是value可以為空，因為TreeMap中的key是要進行比較的；反而HashMap的key和value都可以為空，因為HashMap不涉及比較。
3. Map中的key可以全部分離出來，存儲到Set中進行通路（因為key不能重複，set是天然的去重），Map中的value可以全部分離出來，存儲到Collection的任何一個子集合中（value可能有重複）

3.2 TreeMap 和 HashMap的對比

Map底層結構	TreeMap	HashMap
底層結構	紅黑樹	哈希桶
插入/删除/查找時間複雜度	O(log2N)	O(1)
是否有序	關于key有序	無序
線程安全	不安全	不安全
插入/删除/查找差別	需要進行元素比較	通過哈希函數計算哈希位址
比較與覆寫	key必須能夠比較，否則會抛出類型轉換異常	自定義類型需要覆寫equals和hashcode方法
應用場景	需要key有序的場景下	key是否有序不關心，需要更高的時間性能

3.3 Map.Entry<k,v>的用法 （周遊）

Set<Map.Entry <k,v>> entrySet()， 傳回所有的key-value映射關系

Map<Integer, Integer> map = new TreeMap<>();
        map.put(1,2);
        map.put(2,3);
        map.put(3,6);
        //key一定是可以進行比較的

        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
           

分析：

列印所有的鍵值對

entrySet()：将Map中的鍵值對放在Set中傳回了。

4. 關于Set

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

①Set是繼承自Collection的接口類

②Set中隻存儲了Key

Map不能使用疊代器周遊，但是Set可以，因為Set實作了Iterable接口

4.1 Set的注意事項

1. Set是繼承自Collection的一個接口類
2. Set中隻存儲了key，并且要求key一定要唯一
3. Set的底層使用Map來實作的，其使用key與Object的一個預設對象作為鍵值對插入到Map中

   

4. Set最大的功能就是對集合中的元素進行去重
5. TreeSet中不能插入null的key，但是HashSet可以

4.2 TreeSet 和 HashSet的對比

Set底層結構	TreeSet	HashSet
底層結構	紅黑樹	哈希桶
插入/删除/查找時間複雜度	O(log2N)	O(1)
是否有序	關于key有序	不一定有序
線程安全	不安全	不安全
插入/删除/查找差別	按照紅黑樹的特性進行插入和删除	通過哈希函數計算哈希位址
比較與覆寫	key必須能夠比較，否則會抛出類型轉換異常	自定義類型需要覆寫equals和hashcode方法
應用場景	需要key有序的場景下	key是否有序不關心，需要更高的時間性能

4.3 疊代器周遊Set

Iterator< E> iterator() 傳回疊代器，可以利用其進行周遊

Set<Integer> set = new TreeSet<>();
        set.add(1);
        set.add(3);
        set.add(2);
        set.add(8);
        set.add(4);
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
           

運作結果：

5. 哈希表

5.1 哈希函數

1. 哈希表的效率非常高，查找、删除、插入的時間複雜度都是O(1)。
2. 理想的搜尋方法：不經過任何比較，一次直接從表中得到想要搜尋的元素，即一一映射關系。
3. 哈希方法中使用的轉換函數稱為哈希函數，構造出來的結構稱為哈希表(Hash Table)。
4. 哈希函數計算出來的位址能均勻分布在整個空間中。

5.2 沖突

1. 沖突： 不同關鍵字通過相同哈希函數計算出相同的哈希位址
2. 沖突的發生是必然的，沖突是不可避免的，隻能降低沖突率。
3. 避免沖突：負載因子調節，其值= 填入表中的元素個數/哈希表的長度，是以可以增加哈希表的長度避免沖突。Java的系統庫限制了荷載因子為0.75。

5.3 沖突的解決：開放位址法和鍊位址法

1. 開放位址法（閉散列）

   ①線性探測

   ②二次探測

   閉散列最大的缺陷：空間使用率比較低

2. 鍊位址法（開散列） 數組+連結清單+紅黑樹

   思路：首先對關鍵碼集合用散列函數計算散列位址，具有相同位址的關鍵碼歸于桶一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單連結清單連結起來，各連結清單的頭結點存儲在哈希表中。

   注意：數組長度>=64，連結清單長度>=8，就會變成紅黑樹。

5.4 哈希表與Java集合類的關系

1. HashMap和HashSet是用哈希表實作的Map和Set。
2. Java會在沖突連結清單長度大于一定門檻值後，将連結清單轉變成紅黑樹（搜尋樹）。
3. Java中計算哈希值實際上調用的是類的hashcode方法，進行key的相等性比較是調用key的equals方法。
4. 所有自定義類的HashMap的key或者HashSet的值，必須重寫hashcode和euqals方法，而且必須做到euqals相等的對象，hashcode一定也是一樣的。
5. 擴容之後要注意每個元素都要重新計算hashcode哈希值。

面試問題：

1. 問：如果2個對象hashcode一樣，equals一定一樣嗎？

   答：不一定，hashcode一樣隻能證明我們要找的位置一樣，位置一樣的下面有很多值，無法确定2個對象的euqals。

2. 問：如果2個對象equals一樣，hashcode一定一樣嗎？

   答：一定，equals一樣則hashcode一定一樣。

6. HashMap源碼分析

6.1 成員變量

1. 預設容量：16，最大容量：2的30次方

   

2. 預設的負載因子：0.75

   

3. 樹化的條件（數組+連結清單變成紅黑樹）

   連結清單長度超過8，數組的容量大于等于64

   

4. 解樹的條件（紅黑樹退化為連結清單+數組）

   連結清單的門檻值為6的時候

   

5. table數組的每一個元素是node類型的結點位址

   

6.2 構造方法

1. 不帶參數的構造方法

   負載因子等于預設的負載因子0.75，沒有給table數組進行初始化，意味着table數組沒有配置設定記憶體，數組的大小是0。

   （是以，為什麼等會put元素可以put進去？----> 說明在第一次put的時候，會把數組進行初始化為預設容量16）

   

2. 帶2個參數的構造方法

   一個是給定的容量參數，一個是給定的負載因子參數

   

   如果給定的參數容量大于2的30次方，則容量為2的30次方；

   如果給定的參數容量小于0或者給定的負載因子小于0那麼就抛異常。

   最後負載因子滿足條件直接指派，但是容量還需要經過tableSizeFor進一步篩選。

   

   tableSizeFor裡面：傳回最接近目标的一個二次幂整數。

   例如：

   傳入10：2的3次方=8，2的4次方16，是以傳回16。

面試題：調用構造方法給了1000，請問最後哈希數組的長度是多少？

答：1024

HashMap的最大容量保證是2的n次方，但是如果沒有傳入一個2的次方怎麼辦？

答：HashMap會将傳入的參數做校驗，傳回距離傳參最近的一個2的n次方的值，例如傳入15會初始化為16。

那麼，為什麼傳回二次幂呢？

分析put源碼。

6.3 put方法源碼

①先把key給到hash函數中，hash(key)，調用hash方法，将引用類型key轉換成整數類型

②hash這個方法中調用了hashcode方法，如果key重寫了hashcode方法則會調用自己的hashcode方法，如果沒有重寫，則會調用Object類的hashcode方法。

h是通過hashcode方法得到的32位的整數，h 異或上 h右移16位

為什麼要右移16位？

答：為了更好的均勻分布，低16位和高16位異或，可以讓結果更均勻。

③i = (n - 1) & hash 等價于 n % len，位運算一定是最快的，一定要保證n是2的次幂，這樣2個公式才等價。【是以初始化的長度為2的整數次幂】