【java数据结构】map和set

一、Map和Set的概念以及背景
- - 1.1 概念
  - 1.2 背景
  - 1.3 模型
二、Map
- - 2.1 Map说明
  - 2.2 Map的常用方法
三、Set
- - 3.1 Set说明
  - 3.2 Set的常用方法
四、Set和Map的关系

博客最后附有整篇博客的全部代码！！！

一、Map和Set的概念以及背景

1.1 概念

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

1.2 背景

背景：

到现在为止，当我们要找一个元素的时候，我们可以采取直接遍历的方式，时间复杂度为O（N），或者采用二分查找法，时间复杂度为O(logn)，但这两个搜索方式是要求这组序列是有序的！并且这两种方式比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了。
但现实生活中，我们会遇到这类情况：

根据学生学号找到相应的学生姓名
通讯录中，根据姓名找到电话
抖音带货，根据链接号找到相应的商品

这些情况我们在日常生活中经常遇到，并且会实时更新里面的内容，例如删除，修改，即动态查找，此时，二分查找，以及直接遍历，都不适合了。而 Map 和 Set 是一种适合动态查找的集合容器。

在这里插入图片描述

1.3 模型

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

纯 key 模型，比如：
有一个英文词典，快速查找一个单词是否在词典中
快速查找某个名字在不在通讯录中
Key-Value 模型，比如：
统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对，Set中只存储了Key。

二、Map

2.1 Map说明

Map的官方文档

Map是一个接口类，但是并没有继承Iterable和Collection接口，它的存储方式是Key-Value 模型<K,V>,并且K是唯一值，不能重复。

2.2 Map的常用方法

介绍Map接口之前，先给大家讲一下Map.Entry<K, V> ，它是Map的内部类。

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类。
注意：Map.Entry<K,V>并没有提供设置Key的方法

Map.Entry<K, V>提供的方法：
这里主要带你了解 Map.Entry<K, V>提供的前三种方法。
在这里插入图片描述

        /** getKey() 方法* getValue() 方法*/Map<String, Integer> map=new TreeMap<>();map.put("李四",5);map.put("张三",6);map.put("赵六",20);//map.entrySet()将Map集合变为Set集合for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}

       /** setValue(V value) 方法*/Map<String, String> map=new TreeMap<>();map.put("key1", "value1");map.put("key2", "value2");String oldValue = map.put("key1", "newValue1");System.out.println("Old Value: " + oldValue); // 输出旧值 value1for (Map.Entry<String, String> entry : map.entrySet()) {System.out.println("Key: " + entry.getKey() +" Value: " + entry.getValue());}}

Map的常用方法：在这里插入图片描述

        Map<String,Integer> map = new TreeMap<>();map.put("A", 1);map.put("B", 2);map.put("C", 3);// get()方法System.out.println(map.get("A"));// getOrDefault()方法System.out.println(map.getOrDefault("D",-1));// remove()方法map.put("D",4);System.out.println(map);map.remove("D");System.out.println(map);// containsKey()方法System.out.println(map.containsKey("A"));//trueSystem.out.println(map.containsKey("D"));///false// containsValue()方法System.out.println(map.containsValue(1));//trueSystem.out.println(map.containsValue(5));//false// keySet()方法获取所有的键Set<String> keys = map.keySet();System.out.println("Keys: " + keys);// values()方法获取所有的值Collection<Integer> values = map.values();System.out.println("Values: " + values);

注意：

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

TreeMap和HashMap的区别

三、Set

3.1 Set说明

Set的官方文档

Set是一个接口，它继承了Iterable和Collection接口，它的存储方式是Key 模型,并且K是唯一值，不能重复。

3.2 Set的常用方法

在这里插入图片描述

        Set<String> set = new TreeSet<String>();set.add("A");set.add("B");set.add("C");// contains()方法
//        System.out.println(set.contains("A"));//ture
//        System.out.println(set.contains("D"));//false// remove()方法
//        set.add("E");
//        System.out.println(set);
//        set.remove("E");
//        System.out.println(set);// size()方法
//        System.out.println(set.size());// isEmpty()方法
//        System.out.println(set.isEmpty());// clear()方法
//        System.out.println(set.size());
//        set.clear();
//        System.out.println(set.size());Object[] array = set.toArray();System.out.println("Array from set: " + Arrays.toString(array));// 创建另一个集合Collection<String> collection = Arrays.asList("Banana", "Cherry", "Date");// 使用containsAll()方法检查set是否包含集合中的所有元素boolean containsAll = set.containsAll(collection);System.out.println("是否包含Set集合中所有的元素 " + containsAll);// 使用addAll()方法将集合中的元素添加到set中（可以达到去重的效果）boolean added = set.addAll(collection);System.out.println("将所有元素是否成功添加到set集合中 " + added);System.out.println("添加成功后的集合 " + set);}

注意：

Set是继承自Collection和Iterator的一个接口类，所以它可以通过迭代器打印集合元素
Set中只存储了key，并且要求key一定要唯一
Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
Set最大的功能就是对集合中的元素进行去重
实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序
Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
Set中不能插入null的key。

TreeSet和HashSet的区别：

四、Set和Map的关系

HashSet：

底层数据结构是HashMap。
利用HashMap的键来存储元素，由于HashMap的键不允许重复，因此保证了HashSet中元素的唯一性。
不保证元素的顺序。

LinkedHashSet：

底层数据结构是LinkedHashMap。
同样利用LinkedHashMap的键来存储元素，保证了元素的唯一性。
与HashSet相比，LinkedHashSet保持了元素的插入顺序。

TreeSet：

底层数据结构是TreeMap（在Java7及之前）或红黑树（在Java 8及之后）。利用TreeMap的键来存储元素，通过树形结构保证了元素的有序性。
元素按照自然顺序或构造时指定的比较器（Comparator）排序。
上述这三种都是通过Map来实现Set的，但并不是所有Set集合都是通过Map来实现的。