【数据结构】Map与Set的简单使用

🌟Map

✍1.Map是什么

✍2.Map的常用方法说明

✍3.Map的使用（重点是遍历方式）

🌟Set

✍Set的常见方法

✍Set的使用

 🌟相关OJ题

✍ 宝石与石头

✍ 坏键盘

✍ 复制带随机指针的链表

🐵今天的文章主要学习 Map和Set的基础语法，了解它们的特性。

🌟前言

        Map和Set是专门用来进行搜索的容器或者数据结构。其中，我们一般将搜索的数据称为关键字(Key)，和关键字对应的称为值(Value)，所以称其为Key-Value的键值对。所以一般分为两种模型：

（1）纯Key模型

比如：快速查找某个姓名在不在通讯录中，快速查找某个单词在不在字典中；

（2）Key-Value模型

比如：统计一段文本中每个字的出现次数，要求统计结果是<字，字出现的次数>；

那么Map中存储的就是Key-Value的键值对，而Set中存储的就是Key。

好啦，知道了这些，我们现在开始愉快的学习下面两个知识点吧~😎

🌟Map

✍1.Map是什么

        Map是 一个接口类，并没有继承Collection，该类存储的是<K,V>结构的键值对，并且Key一定是唯一的，不可以重复。具体看下面这张结构关系表（黄色表示接口类型）：

✍2.Map的常用方法说明

主要使用的方法就是put,  getOrDefault   和 Set<Map.Entry<K,V>> entrySet()。

 其他：

（1）Map是一个接口，不能直接实例化对象；如果要实例化对象只能实例化其实现类HashMap（哈希桶）或者TreeMap（红黑树）。

（2）Map中的Key值是唯一的，但是Value可以是重复的；

（3）在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。

（4）Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
（5）Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(因为value可能有重复)。
（6）Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

✍3.Map的使用（重点是遍历方式）

（1）Map的遍历方式：

🌸 打印所有的键值对

    🌸 打印所有的Key:

   🌸 打印所有的Value:

 （2）如果修改 当前entry中的Value值，会同步修改Map中的值。 

🌟Set

✍Set的常见方法

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。

        Set的常用方法主要有add：需要知道与Map不同的是，添加元素时，如果是重复元素，则不会被添加成功。

注意：        
        1. Set是继承自Collection的一个接口类；
        2. Set中只存储了key，并且要求key一定要唯一；
        3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的；
        4. Set最大的功能就是对集合中的元素进行去重；
    5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。（LinkedHashSet的添加顺序与存储顺序是一致的，TreeSet是不一致的。）
        6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入；
        7. TreeSet中不能插入null的key，HashSet可以；

✍Set的使用

 🌟相关OJ题

✍ 宝石与石头

（1）问题描述：给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

（2）主要思路: 

        题目说的这么花哨，但是其实问题简化就是两个字符串，第一个字符串的每个字符就是一种类型，判断第二个字符串中每个字符是否属于第一个字符串中的字符，如果是的话，使用计数器计数即可。当然这里计数的时候可能会出现相同字符重复计数，所以使用Set的去重特性！

（3）代码实现

    public int numJewelsInStones(String jewels, String stones) {
        //先遍历jewels字符串，取出里面的宝石类型存储到Set接口中
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        //再遍历stones字符串，判断里面的每个字符是否是Set中的宝石类型：是的话计数器+1，否则不操作
        int num = 0;
        for (int i = 0; i < stones.length(); i++) {
            if(set.contains(stones.charAt(i))){
                num++;
            }
        }
        return num;
    }

✍ 坏键盘

（1）问题描述：旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。

（2）主要思路：

         该题其实和第一题的类型是一样的，简化就是有一个期望的字符串S1（表示希望的键盘输入），有一个实际的字符串S2（表示键盘实际输出的字符串），然后得出坏掉的键盘字符。有几个细节要注意：第一点：字符串中有大写和小写，但是最后结果只输出大写，所以这里要将所有的字符先转为大写字符；第二点就是每个字符只输出一次，所以这里用到的还是Set的去重特性；第三点：要求输出结果是按照发现顺序输出的，所以这里要使用LinkedHashSet存储数据。

        先将S1,S2字符串转为大写，遍历S2获取其中的每个字符保存在Set中；遍历S1，判断S1中的字符在Set中是否存在，不存在的就是坏掉的键盘。

（3）代码实现

     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String expectedStr = in.nextLine().toUpperCase();
            String actualStr = in.nextLine().toUpperCase();
            // 1.使用Set集合存储实际的字符
            Set<Character> set = new HashSet<>();
            for(int i = 0;i < actualStr.length();i++) {
                set.add(actualStr.charAt(i));
            }
            // 2.拿着实际存在的字符Set扫描期望的字符串
            // 所谓的坏键就是期望中存在的字符，set中没有的字符
            Set<Character> badKey = new LinkedHashSet<>();
            for(int i = 0;i < expectedStr.length();i++) {
                char c = expectedStr.charAt(i);
                if(!set.contains(c)) {
                    badKey.add(c);
                }
            }
            // 最终将badKeySet中的每个字符输出一次
            for(char c : badKey) {
                System.out.print(c);
            }
            // 换行进行下一组数据的处理
            System.out.println();
        }
    }

 ✍ 复制带随机指针的链表（要掌握!）

（1）问题描述

        给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

（2）主要思路：参考题解

🌻 创建一个Map保存原链表的node和新链表对应的newNode;

🌻 需要清楚：       

        map.get(原节点)，得到的就是对应的新节点
        map.get(原节点.next)，得到的就是对应的新节点.next
        map.get(原节点.random)，得到的就是对应的新节点.random

🌻 两者的关系：       
        新节点.next -> map.get(原节点.next)
        新节点.random -> map.get(原节点.random)

        新节点： map.get(原节点)
🌻 综合：         

        map.get(原节点).next -> map.get(原节点.next)

        map.get(原节点).random-> map.get(原节点.random)

​  （3）代码实现

`public Node copyRandomList(Node head) {
        //遍历原链表，构建新链表，保存在Map接口中
        Map<Node,Node> map = new HashMap<>();//Map接口的两个Node分别表示原链表的节点和新链表对应位置的节点
        Node temp = head;
        while (temp != null){
            Node node = new Node(temp.val);//每走到一个节点，创建一个新节点
            map.put(temp,node);//将原节点和对应位置的新节点存储到map中
            temp = temp.next;
        }
        //此时map中已经保存了原链表和新链表两两对应位置的节点
        temp = head;//重新从链表头部开始，建立节点的next引用以及random关系
        while (temp!=null){
            map.get(temp).next = map.get(temp.next);//next 引用
            map.get(temp).random = map.get(temp.random);//random引用
            temp = temp.next;
        }
        return map.get(head);//通过原链表的头结点找到新链表的头结点
    }