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 Map.Entry的说明
Map.Entry 是Map内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了的获取，value的设置以及Key的比较方式
| 方法 | 解释 |
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 将键值对中的value替换为指定value |
注：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.3 Map的常用方法
| 方法 | 解释 |
| V get(Object key) | 返回 key 对应的 value |
V getOrDefault(Object key, V defaultValue) |
返回 key 对应的 value，key 不存在，返回默认值 |
| V put(K key, V value) | 设置 key 对应的 value |
| V remove(Object key) | 删除 key 对应的映射关系 |
| Set keySet() | 返回所有 key 的不重复集合 |
| Collection values() | 返回所有 value 的可重复集合 |
| Set<Map.Entry<K, V>> entrySet() | 返回所有的 key-value 映射关系 |
| boolean containsKey(Object key) | 判断是否包含 key |
| boolean containsValue(Object value) | 判断是否包含 value |
注意：
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的常用方法
| 方法 | 解释 |
| boolean add(E e) | 添加元素，但重复元素不会被添加成功 |
| void clear() | 清空集合 |
| boolean contains(Object o) | 判断 o 是否在集合中 |
| Iterator iterator() | 返回迭代器 |
| boolean remove(Object o) | 删除集合中的 o |
| int size() | 返回set中元素的个数 |
| boolean isEmpty() | 检测set是否为空，空返回true，否则返回false |
| Object[] toArray() | 将set中的元素转换为数组返回 |
| boolean containsAll(Collection c) | 集合c中的元素是否在set中全部存在，是返回true，否则返回false |
| boolean addAll(Collection c) | 将集合c中的元素添加到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
| Map底层结构 | TreeMap | HashMap |
| 底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 |
O(log2N) |
O(1) |
| 是否有序 | 关于Key有序 | 无序 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
| 比较与覆写 | key必须能够比较，否则会抛出ClassCastException异常 | 自定义类型需要覆写equals和hashCode方法 |
| 应用场景 | 需要Key有序场景下 | Key是否有序不关心，需要更高的时间性能 |
3.HashSet与TreeSet
| Map底层结构 | TreeMap | HashMap |
| 底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 |
O(log2N) |
O(1) |
| 是否有序 | 关于Key有序 | 无序 |
| 线程安全 | 不安全 | 不安全 |
| 插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
| 比较与覆写 | key必须能够比较，否则会抛出ClassCastException异常 | 自定义类型需要覆写equals和hashCode方法 |
| 应用场景 | 需要Key有序场景下 | Key是否有序不关心，需要更高的时间性能 |
关于红黑树和哈希桶数据结构的具体详情将会在后续的篇章中介绍。
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); }
功能实现：
/** * 删除重复元素 直接用Set集合 * @param array */ public static void func1(int[] array) { Set 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 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 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); }
4.2 只出现一次的数字
【力扣题目链接】
思路：
方法一：
利用异或操作符，相同数值异或为0，0与任何数异或结果仍为该数，所以遍历整个数组进行异或操作，最后的结果就是只出现一次的数字。
方法二：
利用Set集合，遍历数组如果第一次出现则放入集合，如果第二次出现则将该数从集合中移除（此时集合中只剩下只出现一次的元素），再次遍历数组，找到集合中仅存的数字返回。
代码实现：
法一：
class Solution { public int singleNumber(int[] nums) { int ret=0; for(int i=0;i ret^=nums[i]; } return ret; } }
法二：
class Solution { public int singleNumber(int[] nums) { Set set=new HashSet<>(); for(int i=0;i if(!set.contains(nums[i])) { set.add(nums[i]); }else { set.remove(nums[i]); } } for(int i=0;i if(set.contains(nums[i])) return nums[i]; } return -1; } }
4.3 复制带随机指针的链表
【力扣题目链接】
思路：
深拷贝应该正好由 n 个全新节点组成，复制链表中的指针都不应指向原链表中的节点，可以先遍历一遍链表，用原链表的值先创建出新链表，并在Map中将原节点与复制节点一一对应，再次遍历链表通过Map得到复制链表节点的地址，通过Map中的一一对应关系给复制链表中的next域和random域赋值。
代码实现：
class Solution { public Node copyRandomList(Node head) { Map 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); } }
4.4 宝石与石头
【力扣题目链接】
思路：
先遍历宝石数组，将宝石对应字符存储在Set集合中，再遍历石头数组，设置数值计数，若在遍历石头数组的过程中Set集合含有该字符，计数加1
代码实现：
class Solution { public int numJewelsInStones(String jewels, String stones) { Set 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; } }
4.5 旧键盘
【牛客题目链接】
思路：
先将输出的字符数组（都通过toUpperCase（）方法转换为大写）存储在Set集合中，再遍历键盘敲击的字符数组，如果集合中不存在则打印（而且是第一次出现，不能出现多次）
代码实现：
public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); Set set=new HashSet<>(); String s1=scanner.nextLine(); String s2=scanner.nextLine(); //先遍历实际输出字符数组，将其存储到Set集合中（完成去重） for (char ch:s2.toUpperCase().toCharArray()) { set.add(ch); } //为了保证相同的字符只出现一次，所以再实例化一个集合用于存储坏掉的键，只打印一次 Set 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); } } } }
4.6 前K个高频单词
【力扣题目链接】
思路：
1.利用Map统计所有单词的词频（在4.1功能函数中涉及到相同的问题）
【(Top—K问题) 详解见【PriorityQueue——优先级队列（堆）3.2】】
2.建立K个结点的小根堆
3.剩余Map中元素依次与堆顶元素比较，进行堆顶元素的替换
4.最后将得到的小根堆中元素依次存到List集合中，利用Collections.reverse()方法完成逆置，按从大到小的顺序依次输出结果。
下边我们按照上述思路来一步一步实现代码：
1.统计词频
Map 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); } }
2.建立K个节点的小根堆
在这一步我们需要注意一个问题，就是在词频一致的情况下，我们应该将新元素插入堆顶还是堆尾。
假设我们插入堆尾，在Collections完成逆置后，list中的结果为[“d”,“c”,“a”]，但我们预期的结果为[“d”,“a”,“c”] (词频一致的情况下，字典序靠前的先输出)
所以在实例化优先级队列时需要重写比较方法：
PriorityQueue> minHeap=new PriorityQueue<>(new Comparator>() { @Override public int compare(Map.Entry o1, Map.Entry o2) { //词频相同时，字典序大的反而被认为小 if(o1.getValue().compareTo(o2.getValue())==0) { return o2.getKey().compareTo(o1.getKey()); } //词频不同时，o1-o2默认为小根堆 return o1.getValue()-o2.getValue(); } });
3.与堆顶元素的比较完成替换
Map中剩余的元素，只有在词频比堆顶元素大或者词频一致，字典序小的情况下才完成替换。
2、3代码实现：
for (Map.Entry m: map.entrySet()) { if(minHeap.size() minHeap.offer(m); }else { Map.Entry 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); } } }
4.将小根堆元素存放到集合并完成逆置
List list=new ArrayList<>(); for (int i = 0; i < k; i++) { list.add(minHeap.poll().getKey()); } Collections.reverse(list);
本题代码实现：
class Solution { public List topKFrequent(String[] words, int k) { Map 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> minHeap=new PriorityQueue<>(new Comparator>() { @Override public int compare(Map.Entry o1, Map.Entry o2) { if(o1.getValue().compareTo(o2.getValue())==0) { return o2.getKey().compareTo(o1.getKey()); } return o1.getValue()-o2.getValue(); } }); for (Map.Entry m: map.entrySet()) { if(minHeap.size() minHeap.offer(m); }else { Map.Entry 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 list=new ArrayList<>(); for (int i = 0; i < k; i++) { list.add(minHeap.poll().getKey()); } Collections.reverse(list); return list; } }
