Java集合框架中如何掌握Map和Set?的使用

這篇文章將為大家詳細(xì)講解有關(guān)Java集合框架中如何掌握Map和Set 的使用，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

1. 搜索

1.1 場景引入

在學(xué)習(xí)編程時，我們常見的搜索方式有：

• 直接遍歷：時間復(fù)雜度為 O(N)，元素如果比較多效率會非常慢

• 二分查找：時間復(fù)雜度為 O(logN)，搜索前必須要求序列有序
  

但是上述排序比較適合靜態(tài)類型的查找，即一般不會對區(qū)間進(jìn)行插入和刪除操作。

而現(xiàn)實(shí)中的查找如：

• 根據(jù)姓名查詢考試成績

• 通訊錄（根據(jù)姓名查詢聯(lián)系方式）
  

可能在查找時需要進(jìn)行一些插入和刪除操作，即動態(tài)查找。因此上述排序的方式就不太適合。

1.2 模型

一般會把要搜索的數(shù)據(jù)稱為關(guān)鍵字（Key），和關(guān)鍵字對應(yīng)的稱為值（Value），這兩者又能組合成為 Key-Value 的鍵值對。

因此動態(tài)查找的模型有下面兩種：

純 Key 模型： Set 的存儲模式，比如：

• 有一個英文詞典，快速查找一個單詞是否在詞典中

• 快速查找某個名字在不在通訊錄中
  

Key-Value 模型： Map 的存儲模式，比如：

• 統(tǒng)計(jì)文件中每個單詞出現(xiàn)的次數(shù)，統(tǒng)計(jì)結(jié)果是每個單詞都有與其對應(yīng)的次數(shù)：<單詞， 單詞出現(xiàn)的次數(shù)>

• 梁山好漢的江湖綽號，每個好漢都有自己的江湖綽號：<好漢， 江湖綽號>
  

2. Map

2.1 關(guān)于 Map 的介紹

簡單介紹：

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

注意：

• Map 接口位于 java.util 包中，使用前需要引入它

• Map 是一個接口類，故不能直接實(shí)例化對象。如果要實(shí)例化對象只能實(shí)例化其實(shí)現(xiàn)類 TreeMap 或 HashMap

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

文檔信息：

2.2 關(guān)于 Map.Entry<K, V> 的介紹

簡單介紹：

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

常用方法：

注意：

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

文檔信息：

2.3 Map 的常用方法說明

注意：

• 往 Map 中存儲數(shù)據(jù)時，會先根據(jù) key 做出一系列的運(yùn)算，再存儲到 Map 中

• 如果 key 一樣，那么新插入的 key 的 value，會覆蓋原來 key 的 value

• 在 Map 中插入鍵值對時，key 和 value 都可以為 null

• Map 中的 key 可以全部分離出來，存儲到 Set 中來進(jìn)行訪問（因?yàn)?key 是不能重復(fù)的）

• Map 中的 value 可以全部分離出來，存儲到 Collection 的任何一個子集中（注意 value 可能有重復(fù)）

• Map 中的鍵值對的 key 不能直接修改，value 可以修改。如果要修改 key，只能先將 key 刪掉，然后再進(jìn)行重新插入（或者直接覆蓋）
  

2.4 關(guān)于 HashMap 的介紹

簡單介紹：

• HashMap 是一個散列表，它存儲的內(nèi)容是鍵值對（key-value）映射

• HashMap 實(shí)現(xiàn)了 Map 接口，根據(jù)鍵的 HashCode 值存儲數(shù)據(jù)，具有很快的訪問速度，最多允許一條記錄的鍵為 null，不支持線程同步

• HashMap 是無序的，即不會記錄插入的順序

• HashMap 繼承于 AbstractMap，實(shí)現(xiàn)了 Map、Cloneable、java.io.Serializable 接口
  

注意：

HashMap 類位于 java.util 包中，使用前需要引入它

文檔信息：

2.5 關(guān)于 TreeMap 的介紹

簡單介紹：

• TreeMap 是一個能比較元素大小的 Map 集合，會對傳入的 key 進(jìn)行大小排序。其中可以使用元素的自然順序，也可以使用集合中自定義的比較器來進(jìn)行排序。

• 不同于 HashMap 的哈希映射，TreeMap 底層實(shí)現(xiàn)了樹形結(jié)構(gòu)，即紅黑樹的結(jié)構(gòu)。

注意：

TreeMap 類位于 java.util 包中，使用前需要引入它

文檔信息：

2.6 HashMap 和 TreeMap 的區(qū)別

2.7 Map 使用示例代碼

注意：Map 是一個接口類，故不能直接實(shí)例化對象，以下以 HashMap 作為實(shí)現(xiàn)類為例

示例一： 創(chuàng)建一個 Map 實(shí)例

Map<String,String> map=new HashMap<>();

示例二： 插入 key 及其對應(yīng)值為 value

map.put("惠城","法師");
map.put("曉","刺客");
map.put("喵班長","盜劍客");
System.out.println(map);
// 結(jié)果為：{惠城=法師, 曉=刺客, 喵班長=盜劍客}

示例三： 返回 key 的對應(yīng) value

String str1=map.get("曉");
System.out.println(str1);
// 結(jié)果為：刺客

示例四： 返回 key 對應(yīng)的 value，若 key 不存在，則返回默認(rèn)值 defaultValue

String str2=map.getOrDefault("彌惠","冒險者");
System.out.println(str2);
// 結(jié)果為：冒險者

示例五： 刪除 key 對應(yīng)的映射關(guān)系

String str3=map.remove("喵班長");
System.out.println(str3);
System.out.println(map);
// 結(jié)果為：盜劍客 和 {惠城=法師, 曉=刺客}

示例六： 除了上述直接打印 map，也可以通過 Set<Map.Entry<K, V>> entrySet() 這個方法進(jìn)行遍歷打印

Set<Map.Entry<String,String>> set=map.entrySet();
for(Map.Entry<String,String> str: set){
    System.out.println("Key="+str.getKey()+" Value="+str.getValue());
}
/** 結(jié)果為：
Key=惠城 Value=法師
Key=曉 Value=刺客
Key=喵班長 Value=盜劍客
*/

示例七： 判斷是否包含 key

System.out.println(map.containsKey("惠城"));
// 結(jié)果為：true

3. Set

3.1 關(guān)于 Set 的介紹

簡單介紹：

Set 是一個繼承于 Collection 的接口，是一個不允許出現(xiàn)重復(fù)元素，并且無序的集合，主要有 HashSet 和 TreeSet 兩大實(shí)現(xiàn)類。

注意：

Set 接口位于 java.util 包中，使用前需要引入它

文檔信息：

3.1 Set 的常用方法說明

注意：

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

3.3 關(guān)于 TreeSet 的介紹

簡單介紹：

TreeSet 實(shí)現(xiàn)類 Set 接口，基于 Map 實(shí)現(xiàn)，其底層結(jié)構(gòu)為紅黑樹

注意：

TreeSet 類位于 java.util 包中，使用前需要引入它

文檔信息：

3.4 關(guān)于 HashSet 的介紹

簡單介紹：

• HashSet 實(shí)現(xiàn)了 Set 接口，底層由 HashMap 實(shí)現(xiàn)，是一個哈希表結(jié)構(gòu)

• 新增元素時，新增的元素，相當(dāng)于 HashMap 的 key，value 則默認(rèn)為一個固定的 Object
  

注意：

HashSet 類位于 java.util 包中，使用前需要引入它

文檔信息：

3.5 TreeSet 和 HashSet 的區(qū)別

3.6 Set 使用示例代碼

注意：Set 是一個接口類，故不能直接實(shí)例化對象，以下以 HashSet 作為實(shí)現(xiàn)類為例

示例一： 創(chuàng)建一個 Set 實(shí)例

Set<Integer> set=new HashSet<>();

示例二： 添加元素（重復(fù)元素?zé)o法添加成功）

set.add(1);
set.add(2);
set.add(3);
set.add(4);
set.add(5);
System.out.println(set);
// 結(jié)果為：[1, 2, 3, 4, 5]

示例三： 判斷 1 是否在集合中

System.out.println(set.contains(1));
// 結(jié)果為：true

示例四： 刪除集合中的元素

System.out.println(set.remove(3));
// 結(jié)果為：true

示例五： 返回 set 中集合的個數(shù)

System.out.println(set.size());
// 結(jié)果為：4

示例六： 檢測 set 是否為空

System.out.println(set.isEmpty());
// 結(jié)果為：false

示例七： 返回迭代器，進(jìn)行遍歷

Iterator<Integer> it=set.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}
// 結(jié)果為：1 2 4 5

hashNext() 方法是判斷當(dāng)前元素是否還有下一個元素，next() 是獲取當(dāng)前元素，并且指向下一個元素

示例八： 清空集合

set.clear();
System.out.println(set);
// 結(jié)果為：[]

4. 編程練習(xí)題

4.1 找出第一個重復(fù)數(shù)據(jù)

題目：

從一些數(shù)據(jù)中，打印出第一個重復(fù)數(shù)據(jù)

代碼：

public static void findNum(int[] array){
    Set<Integer> set=new HashSet<>();
    for(int i=0;i<array.length;i++){
        if(set.contains(array[i])){
            System.out.println(array[i]);
            break;
        }
        set.add(array[i]);
    }
}

4.2 去除重復(fù)數(shù)據(jù)

題目：

去除一些數(shù)據(jù)當(dāng)中重復(fù)的數(shù)據(jù)

代碼：

public static int[] removeSample(int[] array){
    Set<Integer> set=new HashSet<>();
    for(int i=0;i<array.length;i++){
        set.add(array[i]);
    }
    Object[] arr=set.toArray();
    return array;
}

4.3 統(tǒng)計(jì)重復(fù)數(shù)據(jù)的出現(xiàn)次數(shù)

題目：

統(tǒng)計(jì)重復(fù)的數(shù)據(jù)出現(xiàn)的次數(shù)

代碼：

public static Map count(int[] array){
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<array.length;i++){
        if(map.containsKey(array[i])){
            int val=map.get(array[i]);
            map.remove(array[i]);
            map.put(array[i],val+1);
        }else {
            map.put(array[i], 1);
        }
    }
    return map;
}

4.4 只出現(xiàn)一次的數(shù)字

題目（OJ 鏈接）：

給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素

代碼1： 異或法

public int singleNumber(int[] nums) {
    int sum=0;
    for(int i=0;i<nums.length;i++){
        sum=sum^nums[i];
    }
    return sum;
}

代碼2： 使用 HashSet

public int singleNumber(int[] nums) {
    Set<Integer> set=new HashSet<>();
    for(int val: nums){
        if(set.contains(val)){
            set.remove(val);
        }else{
            set.add(val);
        }
    }
    for(int val: nums){
        if(set.contains(val)){
            return val;
        }
    }
    return -1;
}

4.5 復(fù)制帶隨機(jī)指針的鏈表

題目（OJ 鏈接）：

給你一個長度為 n 的鏈表，每個節(jié)點(diǎn)包含一個額外增加的隨機(jī)指針 random ，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。

代碼：

public static Node copyRandomList(Node head) {
    Map<Node,Node> map=new HashMap<>();
    Node cur=head;
    while(cur!=null){
        Node node=new Node(cur.val);
        map.put(cur,node);
        cur=cur.next;
    }
    cur=head;
    while(cur!=null){
        Node node=map.get(cur);
        node.next=map.get(cur.next);
        node.random=map.get(cur.random);
        cur=cur.next;
    }
    return map.get(head);
}

4.6 寶石與石頭

題目（OJ 鏈接）：

給你一個字符串 jewels 代表石頭中寶石的類型，另有一個字符串 stones 代表你擁有的石頭。 stones 中每個字符代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。

字母區(qū)分大小寫，因此 “a” 和 “A” 是不同類型的石頭。

代碼：

public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set=new HashSet<>();
        for(int i=0;i<jewels.length();i++){
            set.add(jewels.charAt(i));
        }
        int count=0;
        for(int i=0;i<stones.length();i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }

4.7 舊鍵盤

題目（OJ 鏈接）：

舊鍵盤上壞了幾個鍵，于是在敲一段文字的時候，對應(yīng)的字符就不會出現(xiàn)?，F(xiàn)在給出應(yīng)該輸入的一段文字、以及實(shí)際被輸入的文字，請你列出
肯定壞掉的那些鍵。

代碼：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Set<Character> set=new HashSet<>();
        List<Character> list=new ArrayList<>();
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.next();
        String str2=scanner.next();
        char[] s1=str1.toUpperCase().toCharArray();
        char[] s2=str2.toUpperCase().toCharArray();
        for(int i=0;i<s2.length;i++){
            set.add(s2[i]);
        }
        for(int i=0;i<s1.length;i++){
            if(!set.contains(s1[i])){
                set.add(s1[i]);
                System.out.print(s1[i]);
            }
        }
    }
}

4.8 前 K 個高頻單詞

題目（OJ 鏈接）：

給一非空的單詞列表，返回前 k 個出現(xiàn)次數(shù)最多的單詞。返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率，按字母順序排序。

代碼：

public List<String> topKFrequent(String[] words, int k) {
    Map<String,Integer> map=new HashMap<>();
    for(String s: words){
        if(map.containsKey(s)){
            map.put(s,map.get(s)+1);
        }else{
            map.put(s,1);
        }
    }
    PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
        @Override
        public int compare(Map.Entry<String,Integer> s1, Map.Entry<String,Integer> s2){
            if(s1.getValue().compareTo(s2.getValue())==0){
                return s2.getKey().compareTo(s1.getKey());
            }
            return s1.getValue()-s2.getValue();
        }
    });
    for(Map.Entry<String,Integer> entry: map.entrySet()){
        if(minHeap.size()<k){
            minHeap.add(entry);
        }else{
            if(entry.getValue().compareTo(minHeap.peek().getValue())>0){
                minHeap.poll();
                minHeap.offer(entry);
            }else if(entry.getValue().compareTo(minHeap.peek().getValue())==0){
                if(entry.getKey().compareTo(minHeap.peek().getKey())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }
    }
    List<String> list=new ArrayList<>();
    for(int i=0;i<k;i++){
        Map.Entry<String,Integer> top=minHeap.poll();
        list.add(top.getKey());
    }
    Collections.reverse(list);
    return list;
}

5. 哈希表

5.1 概念

簡單介紹：

哈希表（也叫做散列表），是根據(jù)關(guān)鍵碼（Key Value）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過把關(guān)鍵碼映射到表中的一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做哈希函數(shù)（也叫做散列函數(shù)），存放記錄的數(shù)組叫做哈希表（也叫散列表）

在之前講解的數(shù)據(jù)結(jié)構(gòu)中，元素關(guān)鍵碼及其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個元素時，必須要經(jīng)過關(guān)鍵碼的多次比較，搜索的效率取決于搜索過程中元素的比較次數(shù)。例如：

• 順序查找的時間復(fù)雜度為：O(N)

• 二分查找的時間復(fù)雜度為：O(log(N))
  

我們希望有一種理想的搜索方法，它可以不經(jīng)過任何比較，能直接從表中得到要搜索的元素。因此就有了哈希表，它的原理就是：通過某種函數(shù)使元素的存儲位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，例如：

插入元素：

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

搜索元素：

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

上述的方法就叫做哈希方法（也叫散列方法），其中哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)（也叫做散列函數(shù)），構(gòu)造出來的結(jié)構(gòu)稱為哈希表（也叫散列表）

示例： 當(dāng)我們將哈希函數(shù)設(shè)置為：hash(key) = key % capacity 時，我們往一個數(shù)組中存放以下幾個元素，存放形式如下

但是使用哈希方法會出現(xiàn)一個問題：哈希沖突

5.2 哈希沖突——概念

簡單介紹：

哈希沖突（也叫做哈希碰撞），是指對于兩個數(shù)據(jù)元素的關(guān)鍵字 ki 和 kj (i != j)，雖然 ki != kj，但是存在：Hash(ki) == Hash(kj)，即不同關(guān)鍵字通過相同哈希函數(shù)，可能會計(jì)算出相同的哈希地址

示例： 當(dāng)我們將哈希函數(shù)設(shè)置為：hash(key) = key % capacity 時，元素 3 和 13 通過該哈希函數(shù)計(jì)算出的存放位置是一樣的

由于哈希表底層數(shù)組的容量往往是小于實(shí)際要存儲的關(guān)鍵字的數(shù)量的，這就導(dǎo)致，哈希沖突的發(fā)生是必然的。并且哈希沖突不能根本上消除，為此我們就要

• 在哈希沖突發(fā)生前：盡量避免

• 在哈希沖突發(fā)生后：重點(diǎn)解決
  

5.3 哈希沖突——避免

5.3.1 哈希函數(shù)設(shè)計(jì)

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

哈希函數(shù)的設(shè)計(jì)原則：

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

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

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

常見哈希函數(shù)：

直接定制法（常用）

• 思路：取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash(Key) = A * Key + B

• 優(yōu)點(diǎn)：簡單、均勻

• 缺點(diǎn)：需要事先知道關(guān)鍵字的分布情況

• 使用場景：適合查找比較小且連續(xù)的情況
  

除留余數(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位數(shù)227作為哈希地址。再比如關(guān)鍵字為3241，它的平方就是18671041，抽取中間的3位671作為哈希地址

• 使用場景：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況
  

折疊法（了解）

• 思路：將關(guān)鍵字從左到右分割成位數(shù)相等的及部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址

• 使用場景：事先不需要知道關(guān)鍵字的分布，且關(guān)鍵字位數(shù)比較多的情況
  

隨機(jī)數(shù)法（了解）

• 思路：選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即 Hash(Key) = random(Key) (random 為隨機(jī)函數(shù))

• 使用場景：通常應(yīng)用于關(guān)鍵字長度不等時的情況
  

數(shù)學(xué)分析法（了解）

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

• 使用場景：適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均與的情況
  

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

負(fù)載因子定義：

散列表的載荷因子定義為：α = 填入表中的元素個數(shù) / 散列表的長度

α 是散列表裝滿程度的標(biāo)志因子。由于表長是定值，α 與填入表中的元素個數(shù)成正比，所以 α 越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大；反之 α 越小，表名填入表中的元素越少，產(chǎn)生沖突的可能性就越小

一些采用開放定址法的 hash 庫，如 Java 的系統(tǒng)庫限制了載荷因子為0.75，超過此值將 resize 散列表

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

通過演示圖我們可以很直觀的了解，當(dāng)沖突率越大時，我們需要通過降低負(fù)載因子來變相降低沖突率。而填入表中的元素個數(shù)已成定局，我們不能夠修改，因此需要調(diào)整哈希表中的數(shù)組大小，即調(diào)整散列表長度

5.4 哈希沖突——解決

解決哈希沖突兩種常見的方法：

• 閉散列

• 開散列
  

5.4.1 閉散列

簡單介紹：

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

尋找沖突位置下一個空位置的方法：

線性探測

• 方法：從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止，如果后面的位置都滿了，則會從頭開始尋找

• 缺點(diǎn)：會將所有沖突元素都堆積在一起
  

二次探測

• 方法：Hi = (H0 + i2) % m 或者 Hi = (H0 - i2) % m（i = 1,2,3…），H0 是通過散列函數(shù) Hash(x) 對元素的關(guān)鍵碼 key 進(jìn)行計(jì)算得到的位置，m是表的大小，Hi 是尋找到的空位置

• 缺點(diǎn)：空間利用率較低，這也是哈希表的缺陷

5.4.2 開散列/哈希桶

簡單介紹：

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

補(bǔ)充：

HashMap 的底層就是一個開散列

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

由于會盡量避免沖突，所以沖突率其實(shí)會有保障，因此當(dāng)在單鏈表中做搜索時，其實(shí)很快，時間復(fù)雜度接近：O(1)

但是當(dāng)沖突很嚴(yán)重時，那么在單鏈表這個小集合中做搜索其實(shí)性能就會大大降低，因此單鏈表就不太適合做小集合的結(jié)構(gòu)

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

• 將哈希桶的結(jié)構(gòu)替換成另一個哈希表

• 將哈希桶的結(jié)構(gòu)替換成搜索樹
  

5.5 相關(guān)習(xí)題

補(bǔ)充： Hash表的平均查找長度（ASL）包括查找成功時的平均查找長度和查找失敗時的平均查找長度

• 查找成功的平均查找長度=表中每個元素查找成功時的比較次數(shù)之和/表中元素個數(shù)

• 查找不成功的平均查找長度=該位置如果查找一個元素失敗的次數(shù)/表的長度

題目：

設(shè)哈希表長度為11，哈希函數(shù) H(K) = (K的第一個字母在字母表中的序號) % 11，若輸入順序?yàn)椋―、BA、TN、M、CI、I、K、X、TA），采用閉散列處理沖突方法為線性探測，要求構(gòu)造哈希表，在等概率的情況下查找成功的平均查找長度為( )，查找不成功的平均查找長度為( )

查找成功的平均查找長度為：20/9

查找不成功的平均查找長度為：58/11

5.6 性能分析

雖然哈希表一直在和沖突做斗爭，但在實(shí)際使用過程中，哈希表的沖突率是不高的，沖突個數(shù)是可控的，也就是每個桶中的鏈表的長度是一個常數(shù)。

因此，通常意義下我們認(rèn)為哈希表的插入、刪除、查找時間復(fù)雜度為：O(1)

6. 手動實(shí)現(xiàn) HashMap（提及 hashCode 和 equals 的作用）

• HashMap 底層是：數(shù)組+單鏈表

• 我們可以先定義一個最基礎(chǔ)的哈希表，讓他可以實(shí)現(xiàn)整形的存值、取值等（哈希函數(shù)設(shè)定為：Hash(Key) = Key % capacity)

class HashBuck{
    static class Node{
        public int key;
        public int value;
        public Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public Node[] array;
    public int usedSize;
    public HashBuck(){
        this.array=new Node[8];
    }
    // 獲取 key 對應(yīng)的 value
    public int get(int key){
        int index=key%this.array.length;
        Node cur=this.array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;  // 這里先用 -1 返回，也可以拋異常
    }
    // 新增元素
    public void put(int key, int val){
        int index=key%this.array.length;
        Node cur=this.array[index];
        Node node=new Node(key,val);
        if(cur==null){
            this.array[index]=node;
        }else{
            while(cur.next!=null){
                if(cur.key==key){
                    cur.value=val;
                    break;
                }
                cur=cur.next;
            }
            cur.next=node;
        }
        this.usedSize++;
        if(loadFactor()>=0.75){
            resize();
        }
    }
    // 計(jì)算負(fù)載因子
    public double loadFactor(){
        return this.usedSize*1.0/this.array.length;
    }
    // 擴(kuò)容后，重新構(gòu)造哈希
    public void resize(){
        Node[] oldArray=this.array;
        this.array=new Node[2*oldArray.length];
        this.usedSize=0;
        for(int i=0;i<oldArray.length;i++){
            Node cur=oldArray[i];
            while(cur!=null){
                put(cur.key,cur.value);
                cur=cur.next;
            }
        }
    }
}

 當(dāng)我們實(shí)現(xiàn)了對整形的部分哈希表的實(shí)現(xiàn)后，如果要實(shí)現(xiàn)其它類型是有問題的，因?yàn)槲覀冊O(shè)計(jì)的哈希函數(shù)為：Hash(Key) = Key % capacity，而其它類型都不能取模，因此我們需要能夠?qū)?Key 進(jìn)行數(shù)字轉(zhuǎn)換的方法。而在 Object 類有一個 hashCode() 方法，它能將傳過來的對象，轉(zhuǎn)換成一個合法的數(shù)字，以此來找到合適的位置，因此使用它就能解決我們上述的麻煩。除此之外，上述代碼中的一些==需要修改為 equals() 方法，因?yàn)?equals 它能夠判斷傳入的對象的實(shí)例是否相等

通過上面一部分的分析，最終可以得到如下代碼：

class HashBuck<K,V>{
    static class Node<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;
        public Node(K key,V val){
            this.key=key;
            this.val=val;
        }
    }
    public Node<K,V>[] array=new Node[8];
    public int usedSize;

    public void put(K key,V val){
        int hash=key.hashCode();
        int index=hash%this.array.length;
        Node<K,V> cur=this.array[index];
        Node<K,V> node=new Node<K,V>(key,val);
        if(cur==null){
            this.array[index]=node;
        }else{
            while(cur.next!=null){
                if(cur.key.equals(key)){
                    cur.val=val;
                    break;
                }
                cur=cur.next;
            }
            cur.next=node;
        }
        this.usedSize++;
        if(loadFactor()>=0.75){
            resize();
        }
    }
    public V get(K key){
        int hash=key.hashCode();
        int index=hash%this.array.length;
        Node<K,V> cur=this.array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur=cur.next;
        }
        return null;
    }
    // 計(jì)算負(fù)載因子
    public double loadFactor(){
        return this.usedSize*1.0/this.array.length;
    }
    // 重新哈希
    public void resize(){
        Node<K,V>[] oldArray=this.array;
        this.array=(Node<K, V>[]) new Node[2*oldArray.length];
        this.usedSize=0;
        for(int i=0;i<oldArray.length;i++){
            Node<K,V> cur=oldArray[i];
            while(cur!=null){
                put(cur.key,cur.val);
                cur=cur.next;
            }
        }
    }
}

7. hashCode 和 equals 的關(guān)系

如果 hashCode 一樣，那么 equals 會一樣嗎？

• equals 不一定一樣，因?yàn)?hashCode 是確定在數(shù)組中存儲的位置是不是一樣，但不能確定在哈希桶中，存放的 key 是不是一樣，即不能確定 equals 的結(jié)果是不是一樣

如果 equals 一樣，那么 hashCode 一樣嗎？

• hashCode 一定一樣，因?yàn)?equals 一樣了，那么在數(shù)組中存儲的位置是肯定一樣的

8. 哈希和 Java 類集的關(guān)系

• HashMap 和 HashSet 即 Java 中利用哈希表實(shí)現(xiàn)的 Map 和 Set

• Java 中會使用哈希桶解決哈希沖突

• Java 會在沖突鏈表長度大于一定閾值后，將鏈表轉(zhuǎn)變?yōu)樗阉鳂洌t黑樹）。具體數(shù)值為當(dāng)前鏈表的長度超過8且當(dāng)前桶的個數(shù)大于等于64時，就會將當(dāng)前長度超過8的鏈表變?yōu)榧t黑樹

• Java 中計(jì)算哈希值實(shí)際上是調(diào)用 Object 類的 hashCode 方法，進(jìn)行 Key 的相等性比較是調(diào)用的 equals 方法

• 自定義類如果需要作為 HashMap 的 Key 或者 HashSet 的值，必須重寫 hashCode 和 equals 方法
  

9. HashMap 部分源碼解讀

HashMap 的默認(rèn)容量是：16

HashMap 的最大容量為：1 << 30（必須為2的倍數(shù)）

HashMap 默認(rèn)負(fù)載因子為：0.75

HashMap 中的單鏈表變?yōu)榧t黑樹的條件，該值將在 putVal 方法中出現(xiàn)

HashMap 有四種構(gòu)造方法

方法一： 沒有參數(shù)，則哈希表容量為：0，負(fù)載因子為：0.75

方法二： 傳入一個 Map 參數(shù)，則哈希表負(fù)載因子為：0.75

方法三： 傳一個容量參數(shù) initialCapacity，則哈希表容量為：initialCapacity，負(fù)載因子為：0.75

方法四： 傳兩個參數(shù)，容量參數(shù) initialCapacity，負(fù)載因子參數(shù) loadFactor，則哈希表負(fù)載因子為：loadFactor

但是哈希表容量在這里不能確定，它有一個 tableSizeFor 的方法，為此我們轉(zhuǎn)到它的源碼

這個方法的意思是返回一個最近接傳入的 initialCapacity 參數(shù)的向上取整的2的次方的數(shù)字，例如傳入的參數(shù)為18，那么哈希表的容量就為32，傳入的參數(shù)為1000，那么哈希表的容量就為1024

put 方法的實(shí)現(xiàn)

hash 方法的實(shí)現(xiàn)，由于 hashCode 被 native 修飾，故無法看到具體源碼

putVal 方法的實(shí)現(xiàn)（代碼太長，就直接了，個人在下面代碼中做了注釋）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 當(dāng)哈希表的大小為 0 時，進(jìn)行 resize 調(diào)整
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // ((n - 1) & hash) 其實(shí)等價于 (n % 數(shù)組長度) 但是前提條件是，n是2的次冪
    // 如果為 null 就是第一次插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果不為 null，就進(jìn)行尾插法
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 當(dāng)單鏈表的長度大于8時，轉(zhuǎn)換為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize 方法的實(shí)現(xiàn)（以2倍的方式進(jìn)行擴(kuò)容）

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

10. HashMap 常考問題

問題一：如果 new HashMap(19)，那么 bucket 數(shù)組有多大？

32，原因在第9大節(jié)的構(gòu)造方法四中

問題二：HashMap 什么時候開辟 bucket 數(shù)組占用內(nèi)存？

第一次 put 的時候

問題三：HashMap 何時擴(kuò)容？

當(dāng)填入的元素/容量大于負(fù)載因子的時候，進(jìn)行擴(kuò)容，jdk1.8 負(fù)載因子默認(rèn)為0.75

問題四：當(dāng)兩個對象的 hashCode 相同時會發(fā)生什么？

會發(fā)生哈希沖突

問題五：如果兩個鍵的 hashCode 相同，你如何獲取值對象？

遍歷當(dāng)前位置的鏈表，通過 equals 返回和要查詢的 Key 值一樣的 Key 的 Value

問題六：你了解重新調(diào)整 HashMap 大小存在什么問題嗎？

重新調(diào)整大小一定要進(jìn)行重新哈希

關(guān)于Java集合框架中如何掌握Map和Set 的使用就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。