一、概念、场景及模型

Map 和 set是一种专门用来进行搜索的容器或者数据结构， Map 和 Set是一种适合动态查找的集合容器。TreeMap和TreeSet集合背后的数据结构就是搜索树，红黑树。其中TreeSet底层就是一个TreeMap。

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

1. 纯 key 模型

2. Key-Value 模型

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

二、Map的使用

Map的官方文档：Map (Java Platform SE 8 )

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

1.关于Map的说明

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

2.关于Map.Entry的说明

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

注意： Map.Entry<K,V> 并没有提供设置 Key 的方法

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 删除掉，然后再来进行重新插入。

6. TreeMap 和 HashMap 的区别

4.Map的遍历方式

使用最多也最简单的是for循序遍历:

HashMap<Integer,Integer> map = new HashMap<>();
           map.put(1,1);
           map.put(2,2);
            int[] arr = new int[2];
            int k = 0;
            for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
                arr[k++] = entry.getKey();
            }

其实还有使用迭代遍历map、使用keySet迭代遍历map、使用entrySet遍历map这几种方式，但是觉得使用比较麻烦，直接使用for循环比较方便。

5.试题案例

统计10W个数据当中，每个数据出现的次数以及对应的关系。

public static void func3(int[] array) {
        HashMap<Integer,Integer> map = new HashMap<>();
        //1、遍历原来的数据，统计每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int key = array[i];
            if(map.get(key) == null) {
                map.put(key,1);
            }else {
                int val = map.get(key);//key出现的 次数
                map.put(key,val+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry: map.entrySet()) {
            System.out.println("key: "+entry.getKey()+" 出现了："+entry.getValue()+"次！");
        }
    }

三、Set的使用

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

Set的官方文档：

Set (Java Platform SE 8 )

https://docs.oracle.com/javase/8/docs/api/java/util/Set.html

1.关于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,而Map则可以插入空的key 。

2.试题案例

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

public int singleNumber(int[] nums) {
            HashSet<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;
        }