1概念

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

1. 直接遍歷，時間復雜度為O(N)，元素如果比較多效率會非常慢
2. 二分查找，時間復雜度為
   ,但搜索前必須要求序列是有序的
   上述排序比較適合靜態型別的查找，即一般不會對區間進行插入和洗掉操作了，而現實中的查找比如：
3. 根據姓名查詢考試成績
4. 通訊錄，即根據姓名查詢聯系方式
5. 不重復集合，即需要先搜索關鍵字是否已經在集合中
   可能在查找時進行一些插入和洗掉的操作，即動態查找，那上述兩種方式就不太適合了，本節介紹的Map和Set是
   一種適合動態查找的集合容器
   重要的概念：
   1.一般把搜索的資料稱為關鍵字（Key），和關鍵字對應的稱為值（Value），將其稱之為Key-value的鍵值對
6. 純 key 模型，比如：
   有一個英文詞典，快速查找一個單詞是否在詞典中
   快速查找某個名字在不在通訊錄中
7. Key-Value 模型，比如：
   統計檔案中每個單詞出現的次數，統計結果是每個單詞都有與其對應的次數：<單詞，單詞出現的次數>
   梁山好漢的江湖綽號：每個好漢都有自己的江湖綽號
   而Map中存盤的就是key-value的鍵值對，Set中只存盤了Key，

2.Map

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

2.1Map.Entry<K, V>

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

2.2Map的常用方法

注意：

1. Map是一個介面，不能直接實體化物件，如果要實體化物件只能實體化其實作類TreeMap或者HashMap
2. Map中存放鍵值對的Key是唯一的，value是可以重復的
3. 在Map中插入鍵值對時，key不能為空，否則就會拋NullPointerException例外，但是value可以為空
4. Map中的Key可以全部分離出來，存盤到Set中來進行訪問(因為Key不能重復)，
5. Map中的value可以全部分離出來，存盤在Collection的任何一個子集合中(value可能有重復)，
6. Map中鍵值對的Key不能直接修改，value可以修改，如果要修改key，只能先將該key洗掉掉，然后再來進行
   重新插入，
7. TreeMap和HashMap的區別

3.Set

Set與Map主要的不同有兩點：Set是繼承自Collection的介面類，Set中只存盤了Key

3.1Set的常見方法說明

注意：

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

4 面試題練習

1.只出現一次的數字

題目：
給定一個非空整數陣列，除了某個元素只出現一次以外，其余每個元素均出現兩次，找出那個只出現了一次的元素，

說明：

你的演算法應該具有線性時間復雜度， 你可以不使用額外空間來實作嗎？

來源：力扣（LeetCode）
鏈接：只出現一次的數字
分析：
這個陣列中只有一個元素出現了一次，其余元素都出現了2次
因此可以用Set的性質，遍歷陣列
遇到set中沒有的元素就添加到set中，若已有此元素，則洗掉set中已有的元素
代碼示例

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int tmp:nums){
            if(!set.contains(tmp)){
                set.add(tmp);
            }else{
                set.remove(tmp);
            }
        }
        
        int a=0;
        for(int b:set){
            a=b;
        }
        return a;
    }
}

2.復制帶隨機指標的鏈表

題目：
復制帶隨機指標的鏈表
分析
題目給定的是一個頭節點，鏈表給的節點由兩個指向，一個指向next而另一個指向random，
想要復制整個鏈表，需要借助HashMap將每個節點進行村春原節點映射為新的節點，
Map中存盤原節點和新節點，每個原節點都對應一個新節點，
通過遍歷鏈表來訪問Map將新節點鏈接起來，即可完成復制
代碼示例：

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

    }
}

3.寶石與石頭

題目
寶石與石頭
分析：
給定寶石字串和自己擁有的石頭字串，需要統計出石頭字串中和寶石字串中相同字符的個數
此題只需要遍歷石頭字串，如果當前字符也存在于寶石字串當中，那么自己含有的寶石數量就+1
利用Set的性質
代碼示例

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

4.舊鍵盤打字

題目
舊鍵盤打字
舊鍵盤上壞了幾個鍵，于是在敲一段文字的時候，對應的字符就不會出現，現在給出應該輸入的一段文字、以及實際被輸入的文字，請你列出肯定壞掉的那些鍵
輸入描述:
輸入在2行中分別給出應該輸入的文字、以及實際被輸入的文字，每段文字是不超過80個字符的串，由字母A-Z（包括大、小寫）、數字0-9、以及下劃線“_”（代表空格）組成，題目保證2個字串均非空，
輸出描述:
按照發現順序，在一行中輸出壞掉的鍵，其中英文字母只輸出大寫，每個壞鍵只輸出一次，題目保證至少有1個壞鍵，
分析
題目指出在列印一段文字時壞掉的字符沒有出現，
給定實際輸入的文字，列出壞掉的鍵
利用Set1保存期望輸入的鍵，Set2保存實際輸入的鍵即可
遍歷期望輸入的鍵，當實際輸入的鍵中保存了已有的鍵就將其移除Set1，最終Set1中剩下的鍵就是壞掉的鍵
代碼示例

import java.util.*;
public class Main {
    public static void function(String strExc,String strAct){
        //
        HashSet<Character> setAct = new HashSet<>();
        for(char ch : strAct.toUpperCase().toCharArray()) {
            setAct.add(ch);
        }
        
        HashSet<Character> setBroken = new HashSet<>();
        HashSet<Character> set = new HashSet<>();
        //setAct就存盤了 我實際輸入的資料
        //遍歷strExc 看哪個鍵不在setAct集合當中
        for(char ch : strExc.toUpperCase().toCharArray()) {
              if(!setAct.contains(ch)&&!set.contains(ch)  ) {
                  //1、把他放到集合  2、
                  set.add(ch);
                  System.out.print(ch);
              }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String strExc = scan.nextLine();//期望輸入的
        String strAct = scan.nextLine();//實際輸入的
        function(strExc,strAct);
    }
}