一. Map和Set的概述

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

以前常见的搜索方式有：

直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢

二分查找，时间复杂度为O(logN) ,但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：

根据姓名查询考试成绩

通讯录，即根据姓名查询联系方式

不重复集合，即需要先搜索关键字是否已经在集合中

可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，这里介绍的Map和Set是一种适合动态查找的集合容器。

两种模型 :

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

纯 key 模型(Set就是一个纯key模型)，比如 :

有一个英文词典，快速查找一个单词是否在词典中。

快速查找某个名字在不在通讯录中。

Key-Value 模型(Map就是一个key-val模型)，比如 :

统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>。

梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号。

二. Map

Map没有继承自Collection/Iterable接口，所以Map不能使用迭代器去遍历, 实现该接口的实现类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

1. 注意事项

Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap

Map中存放键值对的Key是唯一的，value是可以重复的

Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。

Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。

Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

2. 关于Map.Entry<K,V>的说明

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

注意：Map.Entry并没有提供设置Key的方法

3. Map接口中常用方法

通过下面的代码区分get()和 getOrDefault()两个方法的细节

当我们通过get 获取的是Integer类型的值，让他赋值给整形会发生拆包，这里map中没有key，那么会返回null，此时拆包，就会发生空指针异常;

而使用 getOrDefault() , 如果map中没有key , 就会返回我们设置的默认值, 就不会进行拆包操作了 .

4. HashMap和TreeMap

HashMap与TreeMap都实现了Map接口, 两者的区别如下:

TreeMap继承关系图如下:

HashMap继承关系图如下:

5. 遍历Map

Map当中没有实现Iterable接口, 所以遍历map的思路是将Map放到实现Iterable接口中的Set中即可;

• 通过keySet()方法

public static void main(String[] args) {
    Map<String,Integer> map = new HashMap<>();
    map.put("张三",1);
    map.put("李四",2);
    map.put("王五",3);
    Set<String> set = map.keySet();
    for (String s : set) {
        System.out.println(s+" = "+map.get(s));
    }
}

• 通过entrySet()方法

public static void main(String[] args) {
    Map<String,Integer> map = new HashMap<>();
    map.put("张三",1);
    map.put("李四",2);
    map.put("王五",3);
    Set<Map.Entry<String, Integer>> entries = map.entrySet();
    for (Map.Entry<String, Integer> entry : entries) {
        System.out.println(entry.getKey()+" = "+entry.getValue());
    }
}

• 通过Map提供的forEach(BiConsumer)方法

BiConsumer是一个函数式接口，接受两个输入参数

public static void main(String[] args) {
    Map<String,Integer> map = new HashMap<>();
    map.put("张三",1);
    map.put("李四",2);
    map.put("王五",3);
    map.forEach(new BiConsumer<String, Integer>() {
        @Override
        public void accept(String key, Integer value) {
            System.out.println(key+" = "+value);
        }
    });
}

三. Set

1. 注意事项

Set是继承自Collection的一个接口类

Set中只存储了key，并且要求key一定要唯一

Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的

Set最大的功能就是对集合中的元素进行去重

实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入

2. Set接口中常用方法

Set接口中大部分方法都是从Collection接口中扩展的，常用方法如下：

3. TreeSet和HashSet

HashSet与TreeSet都实现了Set接口, 两者的区别如下:

TreeSet继承关系图如下:

HashSet继承关系图如下:

4. 遍历Set

• 通过迭代器遍历

public static void main(String[] args) {
    Set<Integer> set = new HashSet<>();
    set.add(1);
    set.add(2);
    set.add(3);
    Iterator<Integer> it = set.iterator();
    while(it.hasNext()) {
        System.out.print(it.next()+" ");
    }
}

• foreach遍历

public static void main(String[] args) {
    Set<Integer> set = new HashSet<>();
    set.add(1);
    set.add(2);
    set.add(3);
    for (Integer integer : set) {
        System.out.print(integer+" ");
    }
}

• 通过Iterable接口中的forEach(Consumer)方法

Consumer是一个函数式接口，接受一个输入参数

public static void main(String[] args) {
    Set<Integer> set = new HashSet<>();
    set.add(1);
    set.add(2);
    set.add(3);
    set.forEach(new Consumer<Integer>() {
        @Override
        public void accept(Integer key) {
            System.out.print(key+" ");
        }
    });
}

四. 小试牛刀

解决下面的三个问题:

1. 统计10W个数据当中，不重复的数据？(去重)
2. 统计10W个数据当中，第一个重复的数据？
3. 统计10W个数据当中，每个数据出现的次数？ (对应的关系)

import java.util.*;
public class Test {
    //1、统计10W个数据当中，不重复的数据？[去重]
    public static void func1(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }
    //2、统计10W个数据当中，第一个重复的数据？
    public static void func2(int[] array) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.contains(array[i])) {
                set.add(array[i]);
            }else {
                System.out.println(array[i]);
                break;
            }
        }
    }
    //3、统计10W个数据当中，每个数据出现的次数？ 对应的关系
    public static void func3(int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        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);
                map.put(key, val+1);
            }
        }
        for (Map.Entry<Integer, Integer> entry:map.entrySet()) {
            System.out.println("key: "+ entry.getKey()+"出现了: "+entry.getValue()+" 次");
        }
    }
    public static void main(String[] args) {
        int[] array = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(5_0000);
        }
        func1(array);
        func2(array);
        func3(array);
    }
}