秒懂数据结构之Map _ Set ，竟如此简单

Map、Set

---

前言

• Set和Map天然就是高效搜索/查找的语义
• 在这里我为什么将这两个集合分别列举比较呢？
• 希望通过我的这篇博客可以增进大家对Map和Set的认识！

---

一、Map、Set的初步理解

1.Map

• 一次保存一个键值对对象（key==value）=>这种映射对象
• 常见的两个子类：HashMap：基于哈希表（数组+链表的实现）

                                   TreeMap：基于二分搜索平衡树（红黑树的实现）

• 核心的应用场景：高效的搜索，存储的是key-value键值对，若需要根据不重复的key去查找value的内容，使用Map集合

2.Set

• 保存单个不重复元素的集合，若某些场景下，只是判定某个Key值是否存在，使用Set，如：手机通化录，查找某个人名是否存在
• Set集合所有的元素都是唯一不重复的，Set集合只能保存单个元素
• 常见的两个子类：HashSet 

                                    TreeSet

二、Map、Set的CURD方法的实现

1.Map

• add、update (添加和修改)

元素的添加和更新操作都是同一个方法， 将键值对key和value保存到当前的Map集合中

  

1. 因为在Map集合中，key不能重复，若put时，发现key重复，则会将当前Map集合中对应的value值更新为此时的put的value值

2.  value可以重复

  3.  在Map集合中，键值对之间是无序的，元素的保存顺序和添加顺序无关

   4. 关于Map集合中保存null值：

               HashMap部分： key和value可以为null，key值唯一，只能存在一个null值的key

 

               TreeMap部分：key不可为空，value可为空，元素的添加顺序也为乱序（在TreeMap中key不可为空，且key必须实现Comparable接口或者通过TreeMap的构造方法传入比较器对象）               =>        换句话说：保存在TreMap中的key必须是可比较的，因为它的结构是一个搜索树结构（左子树<根节点，根节点<右子树）

5.在Map集合中元素的添加顺序和保存顺序相同的子类

LinkedHashMap ： 相当于给普通的HashMap加了一个链表，这个链表就保存了元素的添加顺序key和value可以为null（可以改造LinkeddHashMap做LRU缓存） 

• get（搜索查询特定的值） 

根据key值搜索对应的value值，若没有对应的key值，返回null

 根据key值搜索Map中对应的value值，若没找到，返回默认值defaultvalue（此方法经常和map.put方法搭配使用，简化代码逻辑，多用于解决重复元素出现统计次数问题）

map.put(i,map.getOrDefault(i,0) + 1);
 
1.map中存在key值为i的value，返回value
2.不存在value对应的key值，返回0

•  contain （查询元素是否存在）

boolean containsKey（K key）：在当前Map集合中是否包含指定的key值

boolean containsValue（V value）:在当前Map集合中是否包含指定的value值 

• remove（删除Map中指定的key和value）

 

 remove（Object key） 删除key值对应的键值对对象，返回删除之前的value值

remove（Object key，Object value）删除指定的key以及对应的value值对象，返回是否删除成功

 clear（）慎用！所有元素全部删除，多用于提桶跑路！

2.Set

• add（添加）

boolean add（E e）向当前Set集合中添加一个新的元素e，若e不存在则成功添加，返回true。若e存在，添加失败，返回false（因此可以方便的使用Set集合的add做去重处理）

• remove（删除指定元素o）

 boolean remove（Object o）

删除指定元素o

• contains（查询）

boolean contains（Object o）

查询当前Set集合中是否包含元素o

• 在Set集合中没有提供元素的修改方法，只能将这个元素删了，再添加新值

三、Map、Set的遍历

1.Map

• Map集合的遍历比较低效，for-each循环只能用于Iterable接口及其子类，由图可知，Map集合和Iterable接口毫无关系！

---

所以，要想进行Map集合的遍历，必须先进行将Map转为Set集合

在Map源码中，我们可以发现，里面有一个内部类的同时，还有一个内部接口

Map接口存储键值对对象时，内部存储的都是一个个Map.Entry对象 ，即：将Map对象转换成Set对象，Set对象的内部就存储在Map的一个个键值对Entry对象，转为Set对象之后就可以方便的使用for-each循环进行遍历，其中的每个元素就是Map的Entry对象（Map.Entry这个接口是map接口的内部接口） 

将Map集合转为Set集合entrySet，Set集合就保存一个个Map.Entry对象

•  补充Map的一个方法

 

 keySet()    取出当前Map集合中所有的Key值，返回类型为Set

values()    取出当前Map集合中所有的value值，返回值类型为Collection

 2.Set

for-each 循环即可，此处不再赘述

总结

Set集合和Map集合的关系：

Set集合是保存单个不重复元素的集合，Map是保存一对键值对对象的集合。

Set的常用子类如HashSet、TreeSet，内部使用的是对应的Map对象。

HashSet元素就在HashMap的key上存储

TreeSet元素就在TreeMap的key上存储。

在源码中，内部将元素放在Map的key上，所有的value都是一个相同的空的Object对象