数据结构 之 Map & Set
1. 概念及使用场景:
Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。以前常见的 搜索方式有：
- 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
- 二分查找，时间复杂度为,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
- 根据姓名查询考试成绩
- 通讯录，即根据姓名查询联系方式
- 不重复集合，即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是 一种适合动态查找的集合容器。
2. 模型:
一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：
< 1 > key模型
< 2 > key - value模型
2.1 key模型:
key模型也就是只有需要搜索的数据的模型
例如:
- 在英文字典中,查找某一个单词是否在词典中
- 查看某一个好友是否在我的好友列表中
以上的搜索方式都是key模型;
2.2 key - value模型:
key - value模型也就是不仅仅只存放改数据的关键字,还需要存放这个关键字所对应的值;
例如:
查找某一个人的身份信息,在查找时,我们可以根据关键字key来找到这个人的身份,在生活中也就是根据身份证号码来查找这个人的身份,然后会显示一系列关于此人的身份信息,也就是显示其value值
在我们的数据结构中,Map使用的是key - value模型, 而Set使用的是key模型
3. Map 的使用:
3.1 Map的说明:
根据集合的关系图,我们可知, Map是一个接口类, 没有继承于Collection,在Map的类中, 存储的是键值对<K, V> , 并且其中的K是唯一的,不能够重复;
3.2 Map.Entry<K, V> :
Map.Entry 是Map内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了 <key, value> 的获取，value的设置以及Key的比较方式。
方法 | 解释 |
|---|---|
K getKey() | 返回 entry 中的 key |
V getValue() | 放回entry中的value |
V setValue(V | 将键值对中的value替换为指定value |
注意：Map.Entry并没有提供设置Key的方法
3.3 Map的常见方法:
方法 | 解释 |
|---|---|
V get(Object key) | 返回 key 对应的 value |
V getOrDefault(Object key, V defaultValue) | 返回 key 对应的 value，key 不存在，返回默认值 |
V put(K key, V value) | 设置 key 对应的 value |
V remove(Object key) | 删除 key 对应的映射关系 |
Set<K> keySet() | 返回所有 key 的不重复集合 |
Collection<V> values() | 返回所有 value 的可重复集合 |
Set <Map.Entry<K, V>> entrySet() | 返回所有的 key-value 映射关系 |
boolean containsKey(Object key) | 判断是否包含 key |
boolean containsValue(Object value) | 判断是否包含 value |
3.4 Map的注意事项:
1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行 重新插入。
7. TreeMap和HashMap的区别
Map底层结构 | TreeMap | HashMap |
|---|---|---|
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间 复杂度 | O(log 2 n) | O(1) |
是否有序 | 关于Key有序 | 无序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
比较与覆写 | key必须能够比较，否则会抛出 ClassCastException异常 | 自定义类型需要覆写equals和 hashCode方法 |
应用场景 | 需要Key有序场景下 | Key是否有序不关心，需要更高的 时间性能 |
4 Set的使用:
根据集合的关系图,我们可知:：Set是继承自Collection的接口类;
Set与Map不同的一点在于, Set使用的是key模型;
4.1 常见方法说明:
方法 | 解释 |
|---|---|
boolean add(E e) | 添加元素，但重复元素不会被添加成功 |
void clear() | 清空集合 |
boolean contains(Object o) | 判断 o 是否在集合中 |
Iterator<E> iterator() | 返回迭代器 |
boolean remove(Object o) | 删除集合中的 o |
int size() | 返回set中元素的个数 |
boolean isEmpty() | 检测set是否为空，空返回true，否则返回false |
Object[] toArray() | 将set中的元素转换为数组返回 |
boolean containsAll(Collection<?> c) | 集合c中的元素是否在set中全部存在，是返回true，否则返回 false |
boolean addAll(Collection<? extends E> c) | 将集合c中的元素添加到set中，可以达到去重的效果 |
4.2 Set的注意事项:
1. Set是继承自Collection的一个接口类
2. Set中只存储了key，并且要求key一定要唯一
3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. TreeSet中不能插入null的key，HashSet可以。
8. TreeSet和HashSet的区别
Set底层结构 | TreeSet | HashSet |
|---|---|---|
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间 复杂度 | O(log 2 n) | O(1) |
是否有序 | 关于Key有序 | 不一定有序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 按照红黑树的特性来进行插入和删除 | 1. 先计算key哈希地址 2. 然后进行 插入和删除 |
比较与覆写 | key必须能够比较，否则会抛出 ClassCastException异常 | 自定义类型需要覆写equals和 hashCode方法 |
应用场景 | 需要Key有序场景下 | Key是否有序不关心，需要更高的 时间性能 |
以上就是本篇文章的全部内容,感谢大家观看!!!!!!
如果觉得文章不错的话，麻烦大家三连支持一下ಠ_ಠ
制作不易，三连支持谢谢！！！ 以上代码都是内容都是本人的思路,若有错误或不足,望多多包涵!!! 最后送给大家一句话，同时也是对我自己的勉励： 梦想是不会发光的,发光的是追逐梦想的你!!!!!!!!
腾讯云开发者
