目录

一.什么是Map和Set

二.Map和Set的应用场景

1.生活中查找的例子

2.查找方式

三.初始Map

1.什么是map

 2.Java中map的使用

（1）map中的方法

 (2)map中常用方法的使用

 （3）map的注意事项

3.Map.Entry的理解

（1）概念

（2）里面的方法

 （3）Map.Entry的使用方法

四.初始Set

1.什么是Set

2.Java中set的使用

（1）Set中的方法

 （2）Set中常用方法的使用

五.认识TreeMap和HashMap

 1.TreeMap

（1）什么是红黑树

（2）红黑树的示意图

 （3）TreeMap查找/删除/插入的时间复杂度

（4）线程是否安全

（5）是否有序及查找的条件

（6）应用场景

2.HashMap

（1）使用hash的背景

（2）简单的hash示意图

 （3）哈希map中插入/删除/查找的时间复杂度

（4）线程是否安全

（5）是否有序及查找的条件

（6）应用场景

一.什么是Map和Set

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

二.Map和Set的应用场景

1.生活中查找的例子

手机通讯录中查找联系人，学生根据姓名查找成绩，在网页上根据关键字查找自己需要的内容等。

2.查找方式

之前我们学过的查找方式有直接遍历和二分查找（前提有序），但是之前的查找操作要么有限制，要么效率低；而且在日常生活中我们需要快速查找元素，并且想要对该位置的元素进行操作，这时侯就需要使用Map和Set这样的动态容器来进行查找。

三.初始Map

1.什么是map

Map中是根据这种结构来进行使用，其中K称为关键字，V为关键字中对应的值。

例如在字典中，其中的第一个字母在目录中相当于关键字K，其中对应的单词就是关键字中的值。

 2.Java中map的使用

‘首先map是一个接口，使用map的时候，需要使用HashMap或TreeMap来进行实现。

其中TreeMap是有序的，HashMap是无序的。

在使用之前，我们首先需要直到map中的常用方法

（1）map中的方法

 (2)map中常用方法的使用

public class TestMap {

    public static void main(String[] args) {
        Map map = new TreeMap<>();
        map.put("banana","香蕉");
        map.put("apple","苹果");
        map.put("lemon","柠檬");
        System.out.println(map.containsKey("banana"));
        System.out.println(map.containsValue("香蕉"));
        System.out.println(map.get("apple"));
        System.out.println(map.containsKey("lemon"));
        System.out.println(map.containsValue("null"));
        System.out.println(map.getOrDefault("grape","葡萄"));
        map.put("orange","橘子");
        //返回覆盖前的结果
        System.out.println(map.put("orange","橙子"));
        //k相同时就会覆盖value
        System.out.println(map.get("orange"));
        System.out.println(map.size());
        System.out.println(map.remove("lemon"));
        System.out.println(map.size());
        //tree为有序的，k不能为空，v可以为空
        map.put("fruit",null);
        System.out.println(map.size());
//        map.put(null,"null");
//        System.out.println(map.get(null));

    }
}

 （3）map的注意事项

1.Map中的key是不能重复的，但是value是可以重复的

2.Map是接口，不能实例化对象，需要借助TreeMap或者HashMap来进行实例化

3.Map中的Key不能直接修改，但是其中的value可以进行修改；如果需要修改key，只能将key删除，然后重新插入。

4.在插入键值对的时候key不能为null，否则会出现空指针异常。

5.可以将map中的key分离出来存储到set中，这就需要借助map中的keySet方法来进行实现。

6.Map没有继承Collection，是一个独立的接口。

3.Map.Entry的理解

（1）概念

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

（2）里面的方法

 （3）Map.Entry的使用方法

需要借助Map.entry来进行实现，在遍历的时候可以进行调用里面的方法。

package structdata.map;

import java.util.*;


public class TestMap {
  
    public static void main(String[] args) {
        Map map = new TreeMap<>();
        map.put("banana","香蕉");
        map.put("apple","苹果");
        map.put("lemon","柠檬");
        Set> setEntry = map.entrySet();
        for(Map.Entry se:setEntry){
            System.out.println(se.getKey()+"-->"+se.getValue());//遍历Map中的key和value
        }
        
    }
}

四.初始Set

1.什么是Set

set中只包含了关键字K，相当于上面中只包含了水浒英雄中的绰号，不包含对应的姓名。

2.Java中set的使用

Set也是一个接口，使用的时候不能直接实例化对象，需要借助TreeSet或者HashSet来进行实现。

（1）Set中的方法

 （2）Set中常用方法的使用

package structdata.map;

import java.util.*;


public class TestMap {
    public static void main(String[] args) {
        Set set2 = new TreeSet<>();
        set2.add("aaa");
        set2.add("aaa");//不会添加重复的元素
        set2.add("bbb");
        set2.add("ccc");
        System.out.println(set2.size());
        System.out.println(set2.contains("aaa"));//true
        set2.remove("ccc");
        System.out.println(set2.size());
        System.out.println(set2.isEmpty());
        String[] str;
        str = set2.toArray(new String[0]);//将set转化为数组
        System.out.println(Arrays.toString(str));

//        set2.clear();
//        System.out.println(set2.size());
        List list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);
        Set set3 = new TreeSet<>();
        set3.addAll(list);//对collection中的元素可以进行去重
        //通过迭代器来实现set中的遍历操作
        Iterator it = set2.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }

    }
}

五.认识TreeMap和HashMap

 1.TreeMap

底层结构为红黑树

（1）什么是红黑树

什么是平衡树：任意结点的子树的高度差都小于等于1。

红黑树的条件：
1.结点颜色不是红就是黑

2.根结点颜色必须是黑的  

3.不能有连在一起的红色结点

4.每条路径中黑色结点个数必须相等  

5.叶子（这里的叶子指的是空结点）结点必须是黑的，没有的叶子默认为黑的，这是因为空树也为红黑树，为了保证“根结点”（空树）为黑的这个结论，所以有了5这个条件。 

6.是一个近似平衡的而二叉搜索树，最长路径中结点的个数不超过最短路径中结点个数的2倍。

（2）红黑树的示意图

 （3）TreeMap查找/删除/插入的时间复杂度

因为红黑树是一颗近似平衡的二叉搜索树，所以时间复杂度相当于树的深度，因为二叉搜索树的中序遍历就是有序，因为左子树的所有结点都比根结点的值小，右子树的值都比根结点的值大。

（4）线程是否安全

线程不安全

（5）是否有序及查找的条件

TreeMap是有关Key有序的，所以插入的map中的key是能够进行比较的，否则会抛出类型转换异常。查找元素时，需要元素之间进行比较。

（6）应用场景

需要关键字key有序的时候可以使用TreeMap。

2.HashMap

底层结构：使用hash桶来进行实现

（1）使用hash的背景

不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素。

（2）简单的hash示意图

 （3）哈希map中插入/删除/查找的时间复杂度

由于没有进行比较，直接通过哈希函数来获取位置，所以时间复杂度为O(1)

（4）线程是否安全

不安全

（5）是否有序及查找的条件

不一定有序，因为在存储过程中，没有有序的要求，可能有序或者不有序。

查找方式：先计算哈希地址，然后通过哈希地址来进行删除或者插入操作。

（6）应用场景

不考虑key有序，需要更高的时间性能。