JCF中的Map集合

JCF中的Map集合和Set集合之间存在非常密切的关联关系，从相应集合的命名可以看出来，如HashMap集合和HashSet集合、TreeMap集合和TreeSet集合、LinkedHashMap集合和LinkedHashSet集合、ConcurrentSkipListSet集合和ConcurrentSkipListMap集合。因此，如果搞清楚了JCF中的Map集合结构，就基本搞清楚了JCF中的Set集合结构。本书首先介绍JCF中具有代表性的Map集合，然后在此基础上针对性地介绍Set集合。

Map集合概述

Map 集 合 属 于 JCF 的 知 识 范 畴 ， 但 是 代 表 Map 集 合 的 顶 级 接 口java.util.Map并没有继承JCF的顶级接口java.util.Collection。这是因为Map集合结构属于映射式结构，即一个Key键对应一个Value值（简称K-V键值对），并且同一个集合中不能出现两个相同的Key键信息。

JCF原生的一些重要的Map集合的主要继承体系如图3-1所示。

本节会重点介绍TreeMap集合、HashMap集合和LinkedHashMap集合，其中TreeMap集合是基于红黑树结构构造的，HashMap集合和LinkedHashMap集合是基于数组+链表+红黑树的复合结构构造的，这两种集合的区别仅体现在LinkedHashMap集合中增加了一个虚拟的链表结构。ConcurrentHashMap集合和ConcurrentSkipListMap集合也是Map集合体系中重要的线程安全的集合，本书会在介绍完JUC的必要知识后，介绍ConcurrentHashMap集合的相关结构。

K-V键值对节点定义——Entry

Map集合中存储的是K-V键值对节点，即用一个Key键信息和一个Value值信息映射关联后的对象描述。Map集合中可以有成千上万个K-V键值对节点，每一个K-V键值对都使用实现了Map.Entry<K,V>接口的类的对象进行描述——也就是说，一个Map集合中可以有成千上万个Map.Entry<K,V>接口的实例化对象，如图3-2所示。

Map.Entry<K, V>接口的主要源码如下。

实际上，从JDK 1.8开始，Map.Entry<K, V>接口中增加了一些其他定义，这里暂时不予介绍。在一般情况下，实现了Map.Entry<K, V>接口的具体类，都会根据自己的结构特点实现Map.Entry<K, V>接口中的方法。例如，AbstractMap类中的AbstractMap.SimpleEntry类实现了Map.Entry<K, V>接口，HashMap类中的HashMap.Node类实现Map.Entry<K, V>接口，TreeMap类中的TreeMap.Entry类实现Map.Entry<K, V>接口，这些Map.Entry<K, V>接口的具体实现类，都根据自己存储K-V键值对节点的特性做了不同的扩展或调整。

下面以TreeMap集合为例，看一下TreeMap.Entry<K, V>类的定义（TreeMap集合中对K-V键值对节点的定义），源码如下。

使用K-V键值对节点存储数据对象的java.util.TreeMap集合，内部所有的K-V键值对节点构成一棵红黑树。也就是说，代表K-V键值对节点的TreeMap.Entry对象需要记录当前树节点的双亲节点（父节点）、左儿子节点、右儿子节点及当前树节点的颜色。