⭐️前言⭐️

在之前我们常见的搜索方式有直接遍历【时间复杂度O(N)】、二分查找【时间复杂度O($lo{g}_{2}N$)】等静态查找方式，在实际查找中可能会进行一些插入、删除的动态操作，上述的两种方式就不合适了，本文介绍的Map和Set便是一种适合动态查找的集合容器。

🍉博客主页： 🍁【如风暖阳】🍁
🍉精品Java专栏【JavaSE】、【备战蓝桥】、【JavaEE初阶】、【MySQL】、【数据结构】
🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁

🍉本文由 【如风暖阳】 原创，首发于 CSDN🙉

🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传码云(gitee)、GitHub

---

Map和Set

在学习这两个接口之前，我们先对以及学习到的类和接口，以及即将要将到的两个接口之间的关系图做个总览。
类与接口示意图：

🍅1.Map与Set

1.1 Map和Set的说明

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。我们一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

• 纯Key模型，比如在英文词典中查找一个单词是否存在，对应的就是Set接口
• Key—Value模型，比如梁山好汉的绰号，一个人有一个自己的绰号，对应的就是Map接口

Map是一个接口类，该类没有继承自Collection，该类中存储的是结构的键值对（一个Key对应一个Value），并且K一定是唯一的，不能重复。

Set是继承自Collection的接口类，Set中只存储了Key。

由于Map和Set都是接口，并不能直接实例化，所以需要实例化实现了对应接口的类
Map可以通过HashMap或者TreeMap来实现
Set可以通过HashSet或者TreeSet来实现
（HashMap和HashSet底层通过哈希表来进行存储，TreeMap和TreeSet底层通过搜索树来进行存储）【注：哈希表见文章【哈希表】，搜索树见文章【二叉搜索树】】

代码实现：

	public static void main(String[] args) {
        Map<String,Integer> map1=new TreeMap<>();
        Map<String,Integer> map2=new HashMap<>();
        Set<String> set1=new TreeSet<>();
        Set<String> set2=new HashSet<>();
    }
1
2
3
4
5
6

1.2 Map.Entry的说明

Map.Entry 是Map内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了的获取，value的设置以及Key的比较方式

注：Map.Entry并没有提供设置Key的方法

代码实现：

	public static void main(String[] args) {
        Map<String,Integer> map=new HashMap<>();
        map.put("abc",10);
        map.put("hello",3);
        map.put("double",5);
        Set<Map.Entry<String,Integer>> entrySet=map.entrySet();
        for (Map.Entry<String,Integer> entry:entrySet) {
            System.out.println("key:"+entry.getKey()+"  val:"+entry.getValue());
        }
    }
//
key:abc  val:10
key:double  val:5
key:hello  val:3

Process finished with exit code 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.3 Map的常用方法

注意：

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap。
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
4. Map中的value可以全部分离出来，存储在Collection集合中(value可能有重复)。
5. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

1.4 Set的常用方法

注意：

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。

🍅2.HashMap与TreeMap

🍅3.HashSet与TreeSet

关于红黑树和哈希桶数据结构的具体详情将会在后续的篇章中介绍。

🍅4.练习

4.1 功能函数

给你10w个数据，设计三个函数完成三个对应的功能

• 把这10w个数据中相同的元素删除掉
• 找到这10w个数据中第一个重复的数据
• 统计这10w个数据中每个数据出现的次数

代码实现：
初始化数组与测试：

	public static void main(String[] args) {
        int[] array=new int[10_0000];
        Random random=new Random();
        //随机生成十万个数字（给定范围5000，一定有重复的数字）
        for (int i = 0; i < array.length; i++) {
            array[i]=random.nextInt(5_000);
        }
        func1(array);
        System.out.println(func2(array));
        func3(array);
    }
1
2
3
4
5
6
7
8
9
10
11

功能实现：

	/**
     * 删除重复元素 直接用Set集合
     * @param array
     */
    public static void func1(int[] array) {
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }

    /**
     * 找第一个重复出现的数值
     * @param array
     */
    public static int func2(int[] array) {
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            //第一次出现，就将其添加到集合中；若不是第一次出现，则返回该值
            if(!set.contains(array[i])) {
                set.add(array[i]);
            }else {
                return array[i];
            }
        }
        return -1;
    }

    /**
     * 统计每个数值出现的次数
     * @param array
     */
    public static void func3(int[] array) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int key=array[i];
            //第一次出现，Value值为1；再重复出现时，将Value值加1
            if(map.get(key)==null) {
                map.put(key,1);
            }else {
                int val=map.get(key);
                map.put(key,val+1);
            }
        }
        System.out.println(map);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

4.2 只出现一次的数字

【力扣题目链接】

思路：
方法一：
利用异或操作符，相同数值异或为0，0与任何数异或结果仍为该数，所以遍历整个数组进行异或操作，最后的结果就是只出现一次的数字。

方法二：
利用Set集合，遍历数组如果第一次出现则放入集合，如果第二次出现则将该数从集合中移除（此时集合中只剩下只出现一次的元素），再次遍历数组，找到集合中仅存的数字返回。

代码实现：
法一：

class Solution {
    public int singleNumber(int[] nums) {
        int ret=0;
        for(int i=0;i<nums.length;i++) {
            ret^=nums[i];
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9

法二：

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        for(int i=0;i<nums.length;i++) {
            if(set.contains(nums[i]))
            return nums[i];
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.3 复制带随机指针的链表

【力扣题目链接】



思路：
深拷贝应该正好由 n 个全新节点组成，复制链表中的指针都不应指向原链表中的节点，可以先遍历一遍链表，用原链表的值先创建出新链表，并在Map中将原节点与复制节点一一对应，再次遍历链表通过Map得到复制链表节点的地址，通过Map中的一一对应关系给复制链表中的next域和random域赋值。

代码实现：

class Solution {
    public 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) {
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.4 宝石与石头

【力扣题目链接】

思路：
先遍历宝石数组，将宝石对应字符存储在Set集合中，再遍历石头数组，设置数值计数，若在遍历石头数组的过程中Set集合含有该字符，计数加1

代码实现：

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set=new HashSet<>();
        for(char ch:jewels.toCharArray()) {
            set.add(ch);
        }
        int count=0;
        for(char ch:stones.toCharArray()) {
            if(set.contains(ch))
            count++;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.5 旧键盘

【牛客题目链接】

思路：
先将输出的字符数组（都通过toUpperCase（）方法转换为大写）存储在Set集合中，再遍历键盘敲击的字符数组，如果集合中不存在则打印（而且是第一次出现，不能出现多次）

代码实现：

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        Set<Character> set=new HashSet<>();
        String s1=scanner.nextLine();
        String s2=scanner.nextLine();
        //先遍历实际输出字符数组，将其存储到Set集合中（完成去重）
        for (char ch:s2.toUpperCase().toCharArray()) {
             set.add(ch);
        }
        //为了保证相同的字符只出现一次，所以再实例化一个集合用于存储坏掉的键，只打印一次
        Set<Character> set1=new HashSet<>();
        for (char ch:s1.toUpperCase().toCharArray()) {
        //若set集合中不存在则说明该键坏掉了；若set1集合中也不存在说明为第一次出现
            if(!set.contains(ch)&&!set1.contains(ch)) {
              System.out.print(ch);
              set1.add(ch);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.6 前K个高频单词

【力扣题目链接】

思路：

1.利用Map统计所有单词的词频（在4.1功能函数中涉及到相同的问题）
【(Top—K问题) 详解见【PriorityQueue——优先级队列（堆）3.2】】
2.建立K个结点的小根堆
3.剩余Map中元素依次与堆顶元素比较，进行堆顶元素的替换
4.最后将得到的小根堆中元素依次存到List集合中，利用Collections.reverse()方法完成逆置，按从大到小的顺序依次输出结果。

下边我们按照上述思路来一步一步实现代码：

1.统计词频

		Map<String,Integer> map=new HashMap<>();
        for(String s:words) {
            if(map.get(s)==null) {
                map.put(s,1);
            }else {
                int count=map.get(s);
                map.put(s,count+1);
            }
        }
1
2
3
4
5
6
7
8
9

2.建立K个节点的小根堆

在这一步我们需要注意一个问题，就是在词频一致的情况下，我们应该将新元素插入堆顶还是堆尾。

假设我们插入堆尾，在Collections完成逆置后，list中的结果为[“d”,“c”,“a”]，但我们预期的结果为[“d”,“a”,“c”] (词频一致的情况下，字典序靠前的先输出)

所以在实例化优先级队列时需要重写比较方法：

		PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            	//词频相同时，字典序大的反而被认为小
                if(o1.getValue().compareTo(o2.getValue())==0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                //词频不同时，o1-o2默认为小根堆
                return o1.getValue()-o2.getValue();
            }
        });
1
2
3
4
5
6
7
8
9
10
11

3.与堆顶元素的比较完成替换

Map中剩余的元素，只有在词频比堆顶元素大或者词频一致，字典序小的情况下才完成替换。
2、3代码实现：

		for (Map.Entry<String,Integer> m: map.entrySet()) {
            if(minHeap.size()<k) {
                minHeap.offer(m);
            }else {
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue()==m.getValue()&&m.getKey().compareTo(top.getKey())<0) {
                    minHeap.poll();
                    minHeap.offer(m);
                }
                if(m.getValue()>top.getValue()) {
                    minHeap.poll();
                    minHeap.offer(m);
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.将小根堆元素存放到集合并完成逆置

 		List<String> list=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
1
2
3
4
5

本题代码实现：

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map=new HashMap<>();
        for(String s:words) {
            if(map.get(s)==null) {
                map.put(s,1);
            }else {
                int count=map.get(s);
                map.put(s,count+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        for (Map.Entry<String,Integer> m: map.entrySet()) {
            if(minHeap.size()<k) {
                minHeap.offer(m);
            }else {
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue()==m.getValue()&&m.getKey().compareTo(top.getKey())<0) {
                    minHeap.poll();
                    minHeap.offer(m);
                }
                if(m.getValue()>top.getValue()) {
                    minHeap.poll();
                    minHeap.offer(m);
                }
            }
        }
        List<String> list=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

⭐️最后的话⭐️
总结不易，希望uu们不要吝啬你们的👍哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正😁