[Java数据结构与算法] 详解Map和Set接口

一、引言

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

Map 和 Set 通常用在动态查找的情况（在查找的同时进行插入或删除操作）。

二、模型

我们通常把搜索的数据称为关键字（key），与之对应的称为值（value），将这个组合称为 Key-Value键值对。

因此，会有两种模型：

1. 纯 Key 模型
2. Key-Value 模型

Map 接口中实现的子类通常是 Key-Value键值对，也就是说，Map 对应的是 Key-Value 模型。

而 Set 中存储的只有 Key ，因此 Set 对应的是 纯 Key 模型。

三、Map的使用

3.1 关于Map的说明

Map的官方文档

上图是Java常用集合框架的关系图，可以看到：

Map是一个接口类，它没有继承与自Collection，该类中存储的是 <Key-Value> 结构的键值对，并且 Key 一定是唯一的，每一个 Key 最多只能对应一个 Value。

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

Map.Entry<K, V> 是 Map 内部实现的用来存放 <key, value> 键值对映射关系的内部类。

Entry类 就类似我们模拟实现二叉树时所定义的 TreeNode 内部类。

可见，其底层就是使用红黑树来实现的。

该内部类提供了 Key、Value的获取方法，Value的设置方法以及哈希码的获取方法。

可见，该内部类并没有能够使设置Key的方法。

3.3 Map常用方法说明

3.4 注意事项

1. Map 是一个接口，接口不能被实例化对象；除非实例化其实现类 TreeMap 或 HashMap。

2. Map中存放的键值对中，每一个 Key 都是不可重复的、唯一的，但是 Value 是可重复的。

3. 在TreeMap中放入键值对时，key 不能为空，否则就会抛 NullPointerException 异常。

原因是 TreeMap 是实现了Comparable接口的，每一次新增元素时都要根据Key进行比较

put方法的部分源码如下：

4. Map中的 Key 可以全部分离出来（使用 keySet 方法，返回值是 Set）存储到 Set 中，访问 Set 即可获取到 Map 中所有 Key (因为Key不能重复，Set 存储的元素具有唯一性)。

5. Map中的 value 可以全部分离出来（使用 values 方法，返回值是 Collection）存储在 Collection 的任何一个子集合中(value可能有重复)。

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

7. TreeMap 和 HashMap 都不可以通过迭代器进行遍历操作，原因是 TreeMap 和 HashMap 都没有实现 Iterable接口；但是Set实现了 Iterable接口，若想要遍历Map，可以通过 entrySet方法将Map中的元素通过Set 来遍历（for each或者 Set迭代器）。

8. TreeMap 和 HashMap 的区别：以后的文章将会详细说明

四、Set的使用

4.1 关于 Set 的说明

Set的官方文档

与 Map 不同的是：

1. Set 继承自 Collection 接口类，并且实现了 Iterable接口，可以使用迭代器进行遍历。
2. Set 中只存储 Key，属于纯 Key 模型

4.2 Set常用方法说明

4.3 注意事项

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

2. TreeSet 的底层是使用 Tree Map 来实现的，Set 最大的功能就是对集合中的元素进行去重

可以看到，当调用 TreeSet不带参数的构造方法的时候，其实是调用了 TreeMap的构造方法

而且，TreeSet 的构造方法中含有 NavigableMap接口的参数，我们来看看NavigableMap接口：

它扩展了SortedMap接口的功能，

而 SortedMap接口又拓展了 Map接口的功能，

当调用 TreeSet的 add方法的时候，传进去的参数被当成 Key传入 Map的 put方法中，而 Value是一个固定值 PRESENT（是一个 Object对象）：

因此，TreeSet 的底层就是使用 TreeMap来实现的。

这使得 Set具有了 去重的属性：因为底层是 Map，所以传入的 Key必须唯一不重复。

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

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

5. TreeSet 中不能插入 null 的 key ， HashSet 可以。

因为 TreeSet 底层结构是自平衡的二叉搜索树即红黑树，会对元素进行比较；而 HashSet 底层结构是哈希桶，不需要对元素进行比较。

6. TreeSet 和 HashSet 都可以通过迭代器进行遍历操作，因为它们都实现了 Iterable接口。

7. TreeSet 和 HashSet的区别：以后的文章将会详细说明

完