1. 搜索

1.1 概念

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。Map和Set是一种适合动态查找的集合容器。

常见的搜索方式有：

1. 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
2. 二分查找，时间复杂度为$O(lo{g}_{2}N)$,但搜索前必须要求序列是有序的

1.2 模型

一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

1. 纯 key 模型，比如：
   a) 有一个英文词典，快速查找一个单词是否在词典中
   b) 快速查找某个名字在不在通讯录中
2. Key-Value 模型，比如：
   a) 统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
   b) 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

Map中存储的就是key-value的键值对，Set中只存储了Key。

2. Map 的使用

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

import java.util.HashMap;
import java.util.Map;public class TestMap {public static void main(String[] args) {Map<String, String> map = new HashMap<>();// 1. 使用 put 方法插入键值对//    Map 内部的元素之间的先后顺序和插入顺序关系不大~//    当 put 的时候发现 key 已经存在, 此时就会覆盖原有的 valuemap.put("及时雨", "宋江");map.put("黑旋风", "李逵");map.put("行者", "武松");map.put("及时雨", "宋公明");map.put("小李广", "花荣觉醒形态");System.out.println(map);// 2. 使用 get 方法, 根据 key 获取 value//    如果 key 不存在, get 返回 null//    还可以使用 getOrDefault 来根据 key 获取 value//    如果 key 不存在, getOrDefault 返回一个默认值String value = map.get("行者");String value = map.get("小李广");String value = map.getOrDefault("小李广", "花荣");System.out.println(value);// 3. 使用 isEmpty 判定空System.out.println(map.isEmpty());// 4. 使用 size 获取到键值对的个数System.out.println(map.size());// 5. 使用 clear 清空所有的键值对map.clear();System.out.println(map.isEmpty());System.out.println(map.size());// 6. 遍历 Map (Map 设计出来不是为了遍历!!)//    遍历 Map 是比较复杂的, 需要把 Map 转换成 Set 再遍历for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}// 7. 还可以单独的获取到所有的 key 和所有的 valuefor (String key : map.keySet()) {System.out.println(key);}for (String value : map.values()) {System.out.println(value);}System.out.println(-109 % 101);}
}

注意：

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. 在Map中插入键值对时，key不能为空，否则就会抛NullPointerException异常，但是value可以
   为空
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然
   后再来进行重新插入。
7. TreeMap 和 HashMap 用法相同只是底层实现不同.

3. Set 的使用

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

import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;public static void TestSet(){Set<String> s = new TreeSet<>();// add(key): 如果key不存在，则插入，返回ture// 如果key存在，返回falseboolean isIn = s.add("apple");s.add("orange");s.add("peach");s.add("banana");System.out.println(s.size());System.out.println(s);isIn = s.add("apple");// add(key): key如果是空，抛出空指针异常//s.add(null);// contains(key): 如果key存在，返回true，否则返回falseSystem.out.println(s.contains("apple"));System.out.println(s.contains("watermelen"));// remove(key): key存在，删除成功返回true//             key不存在，删除失败返回false//             key为空，抛出空指针异常s.remove("apple");System.out.println(s);s.remove("watermelen");System.out.println(s);// 抛出空指针异常// s.remove(null);Iterator<String> it = s.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();}

注意：

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。
8. TreeSet 和 HashSet 用法相同, 仅是底层实现不同