引言
Map 和 Set 是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。
一、Map 接口
Map是一个接口，该接口并没有继承（拓展）Collection接口。Map 接口中存储的是<K,V>结构的键值对，将键 Key 映射到值 Value 的对象。 此外，Map 中不能包含重复的键，每个键可以映射到最多一个值。
Map<K,V> //Key ——键 //Value ——值
1. Map 的常用方法
2. 使用 Map 时的说明
① Map 是一个接口，所以不能直接通过 new 来实例化对象，如果要实例化对象，那么只能实例化其实现类 TreeMap 或者 HashMap.
② Map 中存放键值对的 Key 是唯一的，Value 是可以重复的。而重复的 Key 对应的 Value 会在底层被更新。
③ Map中的 Key 可以全部分离出来，存储到Set中来进行访问(因为 Key 不能重复)。
④ Map 中的 Value 可以全部分离出来，存储在 Collection 的任何一个子集合中(Value 可能有重复)。
⑤ Map中键值对的 Key 不能直接修改，Value 可以修改，如果要修改 Key ，只能先将该 Key 删除掉，然后再来进行重新插入。
⑥ TreeMap 和 HashMap的区别：
3. Java 中 Map 的使用
/** * Map 接口 */ import java.util.HashMap; import java.util.Map; public class Test1 { public static void main(String[] args) { //Map<K,V> key,value Map<String, Integer> map = new HashMap<>(); map.put("hello", 3); map.put("world",4); map.put("nice",5); map.put("nice",666);//重复的 Key 对应的 Val 会更新 map.put(null, null); System.out.println(map); int ret = map.get("world");//获得当前 Key 在 map 中的次数 System.out.println(map.get("world")); System.out.println(map.get("world2")); System.out.println(map.getOrDefault("world3",-1)); map.remove("world"); System.out.println(map); } }
输出结果：
4. 注意
在上面我们使用 map.put( ) 方法的时候，我们会发现一个问题，我们 put 进去 map 的数据顺序是 [hello, world, nice, null ]，但是输出的却是 [ null, world, hello, nice ]，可以发现，我们从输出数据的顺序上来看，这很糟糕。
但是我在引言中提到，Map 是一种专门用来进行搜索的容器或者数据结构，其核心在于查找，并不是排序。也就是说，我们在使用 Map 和 Set 时，更多地是思考用来查找、统计数据，而对数据的顺序并不关心。
/** * Map 接口 */ import java.util.HashMap; import java.util.Map; import java.util.Set; public class Test2 { public static void main(String[] args) { Map<String, Integer> map = new HashMap<>(); map.put("hello", 3); map.put("world",4); map.put("nice",5); //此时 Set 集合中放的数据类型是: String //Set 这个集合中，存储的元素都是不重复的 Set<String> set = map.keySet(); System.out.println(set); //Set 集合中放的数据类型是: Map.Entry<String, Integer> //所以此时 Set 集合中放的就是 String 和 Integer 的集合体 Set<Map.Entry<String, Integer>> entrySet = map.entrySet(); for (Map.Entry<String, Integer> s : entrySet) { System.out.println(s.getKey()+" -> "+ s.getValue() ); } } }
输出结果：
二、Set 接口
Set 接口与 Map 接口主要有两点不同：
① Set 接口是继承了 (拓展) Collection 的接口
② Set 中只存储了 Key
Set<K> //K —— 键
1. Set 的常用方法
2. 使用 Set 时的说明
① Set 接口是继承了 (拓展) Collection 的接口。
② Set 中只存储了 Key ，并且要求 Key 一定要唯一。
③ Set 的底层是使用 Map 来实现的，其使用 Key 与 Object 的一个默认对象作为键值对插入到 Map 中的。
④ Set 最大的功能就是对集合中的元素进行去重。
⑤ 实现 Set 接口的常用类有 TreeSet 和 HashSet，还有一个 LinkedHashSet，LinkedHashSet 是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序。
⑥ Set 中的 Key 不能修改，如果要修改，先将原来的删除掉，然后再重新插入。
⑦ Set 中不能插入 null 的 Key 。
⑧ TreeMap 和 HashMap 的区别：
3. Java 中 Set 的使用
import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class Test2 { public static void main(String[] args) { Set<String> set = new HashSet<>(); set.add("hello"); set.add("world"); set.add("nice"); set.add("nice"); System.out.println(set); Iterator<String> iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } } }
输出结果：
4. 注意
在上面我们使用 set.add( ) 方法的时候，我们会发现，当添加重复的元素时，集合会自动帮我们去除重复的元素。此外，我们输出的元素会和 Map 一样，并不是按我们输入的顺序排序好的。因为我在引言中提到，同样地，Set 也只是一个用于搜索、查找的数据结构。
三、一些有关 Map 和 Set 的题目
1. 统计一组数据中的每个数据出现了多少次
/** * 统计一组数据中的每个数据出现了多少次 */ import java.util.HashMap; import java.util.Map; public class Test { public static void main(String[] args) { char[] arr = {'a','c','e','c','b','d','f','c','d'}; Map<Character,Integer> map = computer(arr); System.out.println(map); } public static Map<Character,Integer> computer(char[] arr){ Map<Character,Integer> map = new HashMap<>(); //如果在 map 中没有数组对应的 Key，那么就添加 1个 Key 进去 //如果在 map 中包含了和数组对应的 Key，且 Key 对应 count个 Val, //那么就添加 count + 1个 Key 进去 for (char x :arr) { if(map.containsKey(x)){ int count = map.get(x); map.put(x, count+1); }else { map.put(x,1); } } return map; } }
输出结果：
2. 将一组数据中多余的数据去重
/** * 将一组数据中多余的数据去重 */ import java.util.HashSet; import java.util.Set; public class Test { public static void main(String[] args) { int[] arr = {1,3,5,7,9,3,2,4,6,8,5,4,6}; Set<Integer> set = new HashSet<>(); for (int x : arr) { set.add(x); } System.out.println(set); } }
输出结果：
3. 找出第一个重复出现的数据
/** * 在一组数据中，找出第一个重复出现的数据 */ import java.util.HashSet; import java.util.Set; public class Test6 { public static void main(String[] args) { int[] arr = {1,3,5,7,9,3,2,4,6,8,5,4,6}; Set<Integer> set = new HashSet<>(); int i = 0; //如果在添加元素到 set 之前，就已经发现了 set 中包含某个数组的元素， //那么就 break for (i = 0; i < arr.length; i++) { if(set.contains(arr[i])){ break; } set.add(arr[i]); } System.out.println(arr[i]); //拿到的就是第一次出现的重复值 } }
4. 只出现一次的数字
方法一：
/** * 利用两两元素之间异或，最终得出的就是单独元素 */ class Solution { public int singleNumber(int[] nums) { int x = nums[0]; for(int i= 1; i<nums.length; i++){ x = x^nums[i]; } return x; } }
方法二：
/** * 利用集合 Set * 如果集合中有相同元素，就移除，反之，就添加 */ 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; } }
5. 复制带随机指针的链表
本题需要详细掌握 Map 的操作，与其对应的映射关系，才能将本题理解到位。
/** * 通过 Map 的映射关系 * 知道了 Key 的状态，实现 Value 的状态 * 即通过旧节点之间的关系，实现新节点之间的关系 */ class Solution { public Node copyRandomList(Node head) { if(head == null) return null; //Key - 旧节点，Value - 新节点 Map<Node,Node> map = new HashMap<>(); Node cur = head; //1. 创建新的节点 while(cur != null){ map.put(cur, new Node(cur.val)); cur = cur.next; } cur = head; //2. 连接各个节点 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); } }
6. 宝石与石头
方法一
/** * 方法一 * 1. 将 jewels 字符串中的字符放入集合 set 中 * 2. 查看集合 set 中是否包含 stones 字符数组中字符 * 3. 用 count 计数，最后返回 */ class Solution { public int numJewelsInStones(String jewels, String stones) { Set<Character> set = new HashSet<>(); for(char x:jewels.toCharArray()){ //1. set.add(x); } int count = 0; for(char j:stones.toCharArray()){ //2. if(set.contains(j)){ count++; } } return count; //3. } }
方法二
/** * 方法二 * 两层 for 循环 */ class Solution { public int numJewelsInStones(String jewels, String stones) { int count = 0; for(int i=0; i<jewels.length(); i++){ for(int j=0; j<stones.length();j++){ if( jewels.charAt(i) == stones.charAt(j) ){ count++; } } } return count; } }
7. 键盘坏了的键
import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; import java.util.Set; /** * 1. 将实际输入的文字 str2 放在集合 set 中 * 2. for 循环遍历应该输入的文字 str1, * 若集合 set 不包含某个字符，且线性表之前也未出现该字符，就输出打印 * 3. 将步骤 2 中不包含的字符放入顺序表中,以便下一次判断 */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str1 = scanner.nextLine(); //应该输入的文字 String str2 = scanner.nextLine(); //实际输入的文字 out(str1,str2); } public static void out(String str1, String str2){ Set<Character> set = new HashSet<>(); ArrayList<Character> list = new ArrayList<>(); for (char x:str2.toUpperCase().toCharArray()) { set.add(x); //1. } for(char x:str1.toUpperCase().toCharArray()){ //2. if(!set.contains(x) && !list.contains(x)){ System.out.print(x); } list.add(x); //3. } } }
