《数据结构》map和set-蒲公英云

一.模型

我们首先明白一组模型：

纯 key 模型，比如：

有一个英文词典，快速查找一个单词是否在词典中

快速查找某个名字在不在通讯录中

Key-Value 模型，比如：

统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数： < 单词，单词出现的次数 >

梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

Map采用的就是 key- value模型，而set采用的是纯key模型

二. 关于 Map 的说明

2.1

Map 是一个接口类，该类没有继承自 Collection ， 该类中存储的是 结构的键值对，并且 K 一定是唯一的，不

能重复 。

2.2 关于 Map.Entry 的说明

Map.Entry 是 Map 内部实现的用来存放 键值对映射关系的内部类 ，该内部类中主要提供了

的获取， value 的设置以及key的比较方式（由于我们无法在map中获取key的值，一般我们需要获取key的值时，我们一般选择使用map.entry）

注意： Map.Entry 并没有提供设置 Key 的方法

2.3 Map 的常用方法说明

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

重新插入。

TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员，其中 TreeMap 是 Map 接口的常用实现类，而 TreeSet 是 Set 接口的常用实现类。虽然 TreeMap 和TreeSet 实现的接口规范不同，但 TreeSet 底层是通过 TreeMap 来实现的（如同HashSet底层是是通过HashMap来实现的一样），因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法

TreeSet和TreeMap的关系

　　与HashSet完全类似，TreeSet里面绝大部分方法都市直接调用TreeMap方法来实现的。

相同点：

TreeMap和TreeSet都是非同步集合，因此他们不能在多线程之间共享，不过可以使用方法Collections.synchroinzedMap()来实现同步

运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)，而HashMap/HashSet则为O(1)。

TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是拍好序的。

不同点：

最主要的区别就是TreeSet和TreeMap分别实现Set和Map接口

TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）

TreeSet中不能有重复对象，而TreeMap中可以存在

TreeMap的底层采用红黑树的实现，完成数据有序的插入，排序。

注意：

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

重新插入。

TreeMap 和 HashMap 的区别

3. Set 的说明

3.1 常见方法说明

注意：

Set 是继承自 Collection 的一个接口类
Set 中只存储了 key ，并且要求 key 一定要唯一
Set 的底层是使用 Map 来实现的， 其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的
Set 最大的功能就是对集合中的元素进行去重
实现 Set 接口的常用类有 TreeSet 和 HashSet ，还有一个 LinkedHashSet ， LinkedHashSet 是在 HashSet 的基础