搜索
概念及场景
Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。
以前常见的搜索方式有：
直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
二分查找，时间复杂度为O(log2 N) ,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
根据姓名查询考试成绩
通讯录，即根据姓名查询联系方式
不重复集合，即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本文介绍的Map和Set是一种适合动态查找的集合容器。
模型
一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：
纯 key 模型，比如：
有一个英文词典，快速查找一个单词是否在词典中
快速查找某个名字在不在通讯录中
Key-Value 模型，比如：
统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对，Set中只存储了Key。
Map的使用
关于Map的说明
Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。
Map 的常用方法说明
注意：
Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
Map中存放键值对的Key是唯一的，value是可以重复的
在Map中插入键值对时，key可以为空，value可以为空
Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
TreeMap和HashMap的区别
关于Map.Entry<K, V>的说明
Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。
注意：Map.Entry<K,V>并没有提供设置Key的方法
Set的说明
Set与Map主要的不同有两点：
- Set是继承自Collection的接口类
- Set中只存储了Key。
Set常见方法说明
注意：
1.Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2.Map中存放键值对的Key是唯一的，value是可以重复的
3.在Map中插入键值对时，key可以为空，value可以为空
4.Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5.Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6.Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
7.TreeMap和HashMap的区别
关于Map.Entry<K, V>的说明
Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。
注意：Map.Entry<K,V>并没有提供设置Key的方法
Set的说明
Set与Map主要的不同有两点：
- Set是继承自Collection的接口类
- Set中只存储了Key。
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.TreeSet和HashSet的区别
面试题练习
只出现一次的数字
思路：
我们知道Set的特点就是key不会重复，所以这题第一时间想到的就是用HashSet，每读取一个数据，就将其存入我们的set里，如果set已经有这个数据了，说明这是第二次出现了，就把原来存在set里的这个数据给删除掉，遍历完全部数据后，还存在于set里的就是只出现一次的数据了
代码:
class Solution {
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0 ; i < nums.length ; i++){
if(set.contains(nums[i])){
set.remove(nums[i]);
}else{
set.add(nums[i]);
}
}
for(int key:set){
return key;
}
return -1;
}
}
复制带随机指针的链表
思路：
题目要求进行深拷贝，所以就是说，我们要返回一个新的链表，新链表和原链表里的东西是一模一样的，但是互不相干，由于存在一 一对应的关系，首先想到的就是用Map，原链表的节点就是key–value里的key，而新链表的节点就是value，两者形成了一 一对应的关系，然后再利用map将原节点对应的next和random依次复制给新节点，具体看代码注释
代码：
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head==null) return null;
Node cur = head;//创建一个cur节点遍历原链表
HashMap<Node,Node> map = new HashMap<>();//建一个HashMap
while(cur!=null){//依次遍历原链表
Node copyNode = new Node(cur.val);//创建新节点，值和原链表中节点值一样
map.put(cur,copyNode);//将原链表的节点和新创建的值一样的节点放入Map中
cur = cur.next;
}
//已经将复制好的新节点和原节点按对应方式存入了map中
//最后需要利用map处理新节点的next和random
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);
}
}
宝石与石头
思路：
遍历字符串 jewels，使用HashSet存储其中的字符，然后遍历字符串 stones，对于其中的每个字符，如果其在哈希集合（HashSet）中，则是宝石。
代码：
class Solution {
public int numJewelsInStones(String jewels, String stones) {
HashSet<Character> set = new HashSet<>();
for(int i = 0; i < jewels.length() ; i++){
set.add(jewels.charAt(i));
}
int count = 0;
for(int i = 0; i < stones.length() ; i++){
if(set.contains(stones.charAt(i)))
count++;
}
return count;
}
}
坏键盘打字
思路：
将实际输入的字符存入一个Set里，Set里的值不会重复，也就是说这个Set（setActul）里代表的就是好的键
遍历期望输入的字符串，如果setActual里边没有期望字符串里的字符，说明这个键是坏的，因为题目要求只输出一次坏的键，所以还需要用一个setBroken来记录坏的键，这样就不会重复输出坏的键了
代码：
import java.util.*;
public class 坏键盘 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str1 = scan.nextLine();//期望的
String str2 = scan.nextLine();//实际的
HashSet<Character> setActual = new HashSet<>();
for(char ch : str2.toUpperCase().toCharArray()) {
setActual.add(ch);//把实际的字符串放到一个set里
}
HashSet<Character> setBroken = new HashSet<>();
//再把坏了的键放到一个set里
for(char ch : str1.toUpperCase().toCharArray()) {//遍历期望的字符串
if(!setActual.contains(ch) && !setBroken.contains(ch)) {//在对比已经存在setActul里实际输入的字符串
setBroken.add(ch);
//这个ch就是坏了的
//setBroken里只存一次这个坏了的键，存的时候同时打印一次
System.out.print(ch);
}
}
}
}
10w个数据去除重复数据
思路：
- 原理就是利用Set的性质，set里的值不会重复，只要去重就想到用Set
- 遍历生成的10w个随机数，这里假设随机数是1~100之间的，每遍历一个数据就判断一下set里是否已经存有，若没有则存入set，若有则进行下一个数据的检查
代码：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
public class 去除10w个数据中的重复数据 {
public static void main(String[] args) {
Random random = new Random();
ArrayList<Integer> list = new ArrayList<Integer>();//将随机生成的10w个数据存到顺序表中
for (int i = 0; i < 100000; i++) {
list.add(random.nextInt(100));//生成0~100之间的随机数
}
HashSet<Integer> set = new HashSet();//创建一个HashSet容器，存放数据
//由于Set的性质，里面的元素不会重复，将顺序表里的数据存进这个容器就可以达到去除重复数据的目的了
for (int i = 0 ; i< list.size(); i++){
set.add(list.get(i));
}
System.out.println("不重复的数据有："+set.size()+"个");
System.out.println(set);
}
}
运行结果：
在10w个数据中找到第一个重复的数据
思路：
- 和去重方法一样，用set，每遍历一个数据就检查set里是否已经存在这个数据，若不存在，则存入set，若已经存在，则说明已经找到第一次出现重复的数据了
代码：import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
public class 在10w个数据中找到第一个重复的数据 {
public static void main(String[] args) {
Random random = new Random();
ArrayList<Integer> list = new ArrayList<Integer>();//将随机生成的10w个数据存到顺序表中
for (int i = 0; i < 100000; i++) {
list.add(random.nextInt(100));//生成0~100之间的随机数
}
HashSet<Integer> set = new HashSet<Integer>();//还是用set
for (int i = 0; i < list.size(); i++) {
if (set.contains(list.get(i))) {//如果set里已经有此数据
System.out.println(list.get(i));//输出，这就是第一个重复的数据
break;//找到第一个从重复数据就可以退出了
}else {
set.add(list.get(i));//否则把新数据加入到set里
}
}
}
}
运行结果：
统计10w个数据重复出现的次数
思路：
统计重复次数的题，首先想到就是map，利用map的性质，键值对，一 一对应的关系
遍历数据，若map里没有这个数据，则加入到map里，并给 key–value里 的value初始化为1，代表出现了1次
后续再次遍历到这个数据的时候，value值+1，表示重复次数+1
代码：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class 统计10w个数据重复出现的次数 {
public static void main(String[] args) {
Random random = new Random();
ArrayList<Integer> list = new ArrayList<Integer>();//将随机生成的10w个数据存到顺序表中
for (int i = 0; i < 10; i++) {
list.add(random.nextInt(10));//生成0~100之间的随机数
}
// 数据 出现次数
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer key : list) {//循环遍历list
if (map.get(key)==null){//如果map里找不到key（数据）对应的值（次数）
map.put(key, 1);
}else{//说明之前存过一次了
int count = map.get(key);//count记录原来出现的次数
map.put(key, count+1);//更新key出现的次数
}
}
//输出每个数据的重复次数
System.out.println(map.entrySet());//entrySet()返回的是一个set，里面存放的是键值对（key和value的映射关系）
// Map.Entry<Integer, Integer>是一个内部类 map.entrySet()返回的是一个set集合
for (Map.Entry<Integer, Integer> entry : map.entrySet()){
System.out.println("数据："+entry.getKey()+" "+"出现次数:"+entry.getValue());
}
}
}
运行结果：
数据已经简化，方便观看
