Set 和 Map
Set 代表一种集合元素无序、集合元素不可重复的集合，Map则代表一种由多个 key-value 对组成的集合，Map 集合类似于传统的关联数组。表面上看它们之间相似性很少，但实际上 Map 和 Set 之间有莫大的关联，可以说，Map 集合是 Set 集合的扩展。
Set 和 Map 的关系
title=再看 Set 和 Map 之间的关系之前，先来看看 Set 集合的继承体系，如上图左侧所示。
再来看 Map 集合的继承体系，如上图右侧所示。
仔细观察上图中 Map 集合的继承体系里被灰色覆盖的区域，可以发现，这些 Map 接口、实现类和 Set 集合的接口、实现类的类名完全相似，把 Map 后缀改为 Set 后缀即可。Set 集合和 Map 集合的对饮关系如下：
- Set <-\> Map
- EnumSet <-\> EnumMap
- SortedSet <-\> SortedMap
- TreeSet <-\> TreeMap
- NavigableSet <-\> NavigableMap
- HashSet <-\> HashMap
- LinkedHashSet <-\> LinkedHashMap
这些接口和类名如此相似绝不是偶然现象，肯定其必然有原因。
表名上看，这两种集合并没有太多的相似之处，但如果只考察 Map 集合的 key，不难发现，这些 Map 集合的 key 具有一个特性：所有 key 不能重复，key 质检没有顺序。也就是说，如果将 Map 集合的所有 key 集中起来，那这些 key 就组成了一个 Set 集合。所以，发现 Map 集合提供了如下方法来返回所有 key 组成的 Set 集合。
Set<K> keySet()
由此可见，Map 集合的所有 key 将具有 Set 集合的特征，只要把 Map 的所有 key 集中起来看，那它就是一个 Map，这实现了从 Map 到 Set 的转换。其实，还可以实现从 Set 到 Map 的扩展————对于 Map 而言，相当于每个元素都是 key-value 的 Set 集合。
换一种思维来理解 Map 集合，如果把 Map 集合中的 value 当成 key 的“附属物”（实际上也是，对于一个 Map 集合而言，只要给出指定的 key，Map 总是可以根据该 key 快速查询到对应的 value），那么 Map 集合在保存 key-value 对时只考虑 key 即可。
title=对于一个 Map 集合而言，它本质上是一个关联数组，如上图左侧所示。
对于上图左侧所示的关联数组，其实可以改为使用一个 Set 集合来保存它们，反正上面关联数组中 key-value 对质检有严格的对应关系，那么干脆将 key-value 对捆绑在一起对待，如上图右侧所示。
为了把 Set 扩展成 Map，可以考虑新增定义一个 SimpleEntry 类，该类代表一个 key-value 对；当 Set 集合的集合元素都是 SimpleEntry 对象时，该 Set 集合就能被当成 Map 使用。下面程序示范了如何将一个 Set 集合扩展成 Map 集合。
import java.io.Serializable;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
class SimpleEntry<K, V> implements Map.Entry<K, V>, Serializable {
private static final long serialVersionUID = 1L;
private final K key;
private V value;
//定义如下2个构造器
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}
public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
//获取key
@Override
public K getKey() {
return key;
}
//获取value
@Override
public V getValue() {
return value;
}
//改变该Key-value对的value值
@Override
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
//根据key计算hashCode
@Override
public int hashCode() {
return key == null ? 0 : key.hashCode();
}
//根据key比较2个SimpleEntry是否相等
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (o.getClass() == SimpleEntry.class) {
@SuppressWarnings("rawtypes")
SimpleEntry se = (SimpleEntry)o;
return se.getKey().equals(getKey());
}
return false;
}
@Override
public String toString() {
return key + "=" + value;
}
}
//继承HashSet实现一个Map
public class Set2Map<K, V> extends HashSet<SimpleEntry<K, V>> {
private static final long serialVersionUID = 1L;
//实现清空所有key-value对的方法
@Override
public void clear() {
super.clear();
}
//判断是否包含某个key
@SuppressWarnings({ "unchecked", "rawtypes" })
public boolean containsKey(K key) {
return super.contains(new SimpleEntry(key, null));
}
//判断是否包含某个value
boolean containsValue(V value) {
for (SimpleEntry<K, V> se : this) {
if (se.getValue().equals(value)) {
return true;
}
}
return false;
}
//根据指定key取出对应的value
public V get(K key) {
for (SimpleEntry<K, V> se : this) {
if (se.getKey().equals(key)) {
return se.getValue();
}
}
return null;
}
//将指定key-value对放入集合
public V put(K key, V value) {
super.add(new SimpleEntry<K, V>(key, value));
return value;
}
//将另外一个Map的key-value对放入该Map中
@SuppressWarnings({ "unchecked", "rawtypes" })
public void putAll(Map<? extends K, ? extends V> m) {
for (K key : m.keySet()) {
super.add(new SimpleEntry(key, m.get(key)));
}
}
//根据指定key删除Key-value对
public V removeEntry(K key) {
for (Iterator<SimpleEntry<K, V>> it = this.iterator();it.hasNext();) {
SimpleEntry<K, V> en = it.next();
if (en.getKey().equals(key)) {
V v = en.getValue();
it.remove();
return v;
}
}
return null;
}
//获取该Map中包含多少个key-value对
@Override
public int size() {
return super.size();
}
}下面程序简单测试了扩展出来的“Map”集合
public class Set2MapTest {
public static void main(String[] args) {
Set2Map<String, Integer> scores = new Set2Map<String, Integer>();
//将key-value对放入集合
scores.put("语文", 89);
scores.put("数学", 83);
scores.put("英文", 80);
System.out.println(scores);
//访问Map集合里包含的key-value对
System.out.println(scores.size());
scores.removeEntry("数学");
System.out.println("删除key为\"数学\"的Entry之后：" + scores);
//根据key取出value
System.out.println("语文成绩：" + scores.get("语文"));
//判断是否包含指定key
System.out.println("是否包含\"英文\"key：" + scores.containsKey("英文"));
//判断是否包含指定value
System.out.println("是否包含82 value：" + scores.containsValue(82));
//清空集合
scores.clear();
System.out.println("执行clear()方法之后的集合：" + scores);
}
}输出结果为：
[英文=80, 数学=83, 语文=89]
3
删除key为"数学"的Entry之后：[英文=80, 语文=89]
语文成绩：89
是否包含"英文"key：true
是否包含82 value：false
执行clear()方法之后的集合：[]根据此处介绍的这个程序不难看出，只要对传统 Set 稍加改造，就可以将 Set 改造成 Map 集合，而且，这个 Map 集合在功能上几乎可以与系统提供的 Map 类媲美。
HashMap 和 HashSet
前面将一个 Set 集合扩展成了 Map 集合，由于这个 Set 采用了 HashSet 作为实现类，HashSet 会使用 Hash 算法来保存每个 SimpleEntry 元素，因此扩展出来的 Map 本质上是一个 HashMap。
实际上，HashSet 和 HashMap 之间有很多相似之处。对于 HashSet 而言，系统采用 Hash 算法决定集合元素的储存位置，这样可以保证快速存、取集合元素；对于 HashMap 而言，系统将 value 当成 key 的附属，系统根据 Hash 算法来决定 key 的储存位置，这样可以保证快速存、取集合 key，而 value 总是紧随 key 储存。
在介绍集合存储之前需要指出一点：虽然集合号称储存的是 Java 对象，但实际上并不会真正将 Java 对象放入 Set 集合中，而只是在 Set 集合中保留这些对象的引用而已。也就是说，Java 集合实际上是多个引用变量所组成的集合，这样引用变量将指向实际的 Java 对象。
就像引用类型的数组一样，当把 Java 对象放入数组之时，并不是真正把 Java 对象放入数组中，而只是把对象的引用放入数组中，每个数组元素都是一个引用变量。
对于每个 Java 集合来说，其实它只是多个引用变量的集合，下面的程序可以证明这一点。
import java.util.ArrayList;
import java.util.List;
class Apple {
double weight;
public Apple(double weight) {
this.weight = weight;
}
}
public class ListTest {
public static void main(String[] args) {
//创建2个Apple对象
Apple t1 = new Apple(2.2);
Apple t2 = new Apple(1.8);
List<Apple> list = new ArrayList<Apple>(4);
//将2个Apple对象放入List集合中
list.add(t1);
list.add(t2);
//判断从集合里取出的引用变量和原有引用变量是否指向同一个元素
System.out.println(list.get(0) == t1);
System.out.println(list.get(1) == t2);
}
}ArrayList 底层是基于数组实现的，也就是说 ArrayList 底层封装的是数组，每次创建 ArrayList 时传入的 int 参数就是它所包装的数组的长度；如果创建 ArrayList 时没有传入 int 参数，那么 ArrayList 的初始长度为 10，也就是底层所封装的数组的长度为 10。
实际上，此时 t1 和 list 集合的第 1 个元素都指向同一个 Java 对象，t2 和 list 的第 2 个元素也指向同一个 Java 对象，因此上面的程序将会输出 2 个 true。
下面将详细介绍 HashSet、HashMap 对集合元素的储存方式。当程序视图将多个 key-value 放入 HashMap 中时，示例代码片段如下：
HashMap<String, Double> map = new HashMap<String, Double>();
map.put("语文", 80.0);
map.put("数学", 89.0);
map.put("英语", 78.2);对于 HashMap 而言，它的储存方式要比 ArrayList 复杂一些，采用一种所谓的“Hash 算法”来决定每个元素的储存位置。
当程序执行 map.put("语文", 80.0); 时，系统将调用“语文”的 hashCode() 方法得到其 hashCode 值————每个 Java 对象都有 hashCode() 方法，都可以通过该方法获得它的 hashCode() 值。而得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的储存位置。
HashMap 类 put(K key, V value) 方法的源代码如下（JDK8）：
public V put(K key, V value) {
//根据key计算Hash值，并调用putVal方法
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断Node数组table是否为空，如果为空创建一个新的Node数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果hash值对应的索引在Node数组中的Node为null，则在该索引对应的Node数组中创建一个新的Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果索引对应的Node数组中的Node不为null
else {
Node<K,V> e; K k;
//判断需要添加的Node是否和原来的Node一致，并且key不会null
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断Node是否是一个TreeNode，TreeNode是继承于LinkedHashMap.Entry<K,V>，用于标记一个有序的Node
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//找到指定key与需要放入的key相等的Node
for (int binCount = 0; ; ++binCount) {
//索引处的Node的下一个Node为null
if ((e = p.next) == null) {
//创建一个新的Node关联到Node的next属性上，形成一个Node链
p.next = newNode(hash, key, value, null);
//当bin计算器达到TreeNode的最低要求8时候，就将当前的Node数组转换为TreeNode，以提高操作效率
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//判断是否该Node和需要添加的Node一样
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判断已经找到key匹配的Node
if (e != null) { // existing mapping for key
V oldValue = e.value;
//判断Node数组的值已经被修改过或者该Node之前的value为null，就修改该Node的value为传入的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//操作计数符
++modCount;
//如果Map中的key-value对超过了Node数组的极限，就对Node数组进行扩容，默认是在 resize() 方法中，将原来的数组扩大一倍
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}在这里，JDK1.7 和 JDK1.8 有一些区别，在 JDK1.7 中，使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同（hash collision），那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表。在hashcode特别差的情况下，比方说所有key的hashcode都相同，这个链表可能会很长，那么put/get操作都可能需要遍历这个链表，也就是说时间复杂度在最差情况下会退化到 O(n)。
在 JDK1.8 中，使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构。如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treeifyBin函数，将链表转换为红黑树。那么即使hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要 O(log n) 的开销，也就是说put/get的操作的时间复杂度最差只有 O(log n)。听起来挺不错，但是真正想要利用JDK1.8的好处，有一个限制：key 的对象，必须正确的实现了 Compare 接口，如果没有实现Compare接口，或者实现得不正确，那JDK1.8的HashMap其实还是慢于JDK1.7 的。
上面的程序中用到了一个重要的内部接口 Map.Entry, 每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出：当系统决定储存 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，而仅仅只是根据 key 来计算并决定每个 Entry 的储存位置。这也说明了前面的结论；完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的储存位置之后，value 随之保存在那里即可。
从上面 put 方法的源代码可以看出，当程序视图将一个 Key-value 对放入 HashMap 中时，首先根据该 key 的 hashCode() 返回值觉得该 Entry 的储存位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的储存位置相同；如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加的 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖；如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有的 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部————具体请看 addEntry() 方法的说明（addEntry 方法在 JDK1.7 及以下版本）。
当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（JDK1.7 中是 Entry 对象，JDK1.8 中是 Node 对象或者 红黑树对象）的储存位置。当两个 key-value 对象的 key 的 hashCode() 返回值相同时，将由 key 通过 eqauls() 比较值决定覆盖行为（返回 true），还是产生链式结构（返回 false）
程序中使用的 table 其实就是一个普通数组，每个数组都有一个固定的长度，这个数组的长度就是 HashMap 的容量。HashMap 包含了如下几个构造器：
- HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
- HashMap(Map<? extends K, ? extends V> m)：以给定的 Map 对象进行初始化。
当创建一个 HashMap 时，系统会自动创建一个 table 数组来保存 HashMap 中的 Enrty（JDK1.8之前）或 Node（JDK1.8及以后）。下面是 HashMap 中一个构造器的代码：
//以指定的初始化容量、负载因子创建HashMap
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能为负数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果负载因子大于最大容量，让初始容量等于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子必须是大于0的数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置容量极限，如果initialCapacity等于2的n次幂，极限容量就等于initialCapacity，如果不等于，容量极限就等于大于initialCapacity的最小的2的n次幂
this.threshold = tableSizeFor(initialCapacity);
}上面的代码中，需要计算出数组的容量 threshold，这个值是 2的n次幂，如果 initialCapacity 不为 2的n次幂，那么就让 threshold 等于大于 initialCapacity 的最小的 2的n次幂。例如：initialCapacity 为 1，threshold 就为 1；initialCapacity 为 2，threshold 就为 2；initialCapacity 为 10，threshold 就为16。
在 JDK1.8 中，除了在使用 HashMap(Map<? extends K, ? extends V> m) 构造器时，根据给定的 Map 对象的容量大小对 table 数组进行了初始化。在另外三种构造器中并没有在构造器中对 table 数组进行初始化，采用了懒加载的模式进行初始化，在调用了 put(K key, V value) 之后，会检测 table 数组是否初始化。
从上面的代码中可以看出，创建 HashMap 时指定的 initialCapacity 并不等于 HashMap 的实际容量。通常来说，HashMap 的实际容量总比 initialCapacity 大一些，除非指定的 initialCapacity 参数值恰好是 2的n次方。在 JDK1.8 之前的版本中，应该在创建 HashMap 时将 initialCapacity 参数值指定的为 2的n次方，这样可以减少系统的计算开销；但在 JDK1.8 中采用了 tableSizeFor(int cap) 方法来寻找这个 2的n次方，该方法不会循环计算，所以对系统开销影响不明显。对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的储存位置。当系统开始初始化 HashMap 时，系统会创建一个固定长度的数组。这个数组里可以储存元素的位置被成为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里储存的元素。
无论何时，HashMap 的每个“桶”只储存一个元素。但是由于 Entry 或者 Node 的设计中包含了一个引用变量用于指引下一个 Entry 或者 Node，甚至 TreeNode 是基于红黑树设计，包含了四个引用变量。因此可能出现：HashMap 的 bucket 中只有一个元素，但这个元素指向了另外一个元素，从而形成了链式结构。
当 HashMap 的每个 bocket 里储存的元素只是单个元素时，即没有产生链式结构，此时 HashMap 具有最好的性能。当程序通过 key 取出对象的 value 时，系统只要先计算该 key 的 hashCode() 返回值，再根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的元素，最后返回该 key 对应的 value。HashMap类的 get(K key) 方法代码如下（JDK1.8）：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断table数组不为null且table数组的长度不为0且table的第一个元素不为null
if ((tab = table) != null && (n = tab.length) > 0 &&
//直接根据key的hash值取出该hash值指定的元素
(first = tab[(n - 1) & hash]) != null) {
//首先检查第一个元素，如果第一个元素的hash值与给定的hash值相同，且该key的引用相同或key的值相同（调用equals方法）
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//判断该元素是否引用下一个元素
if ((e = first.next) != null) {
//如果元素是红黑树TreeNode，就调用红黑树的搜索方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//搜索该元素的下一个元素
do {
//如果该元素的hash值与给定的hash值相同，且该key的引用相同或key的值相同（调用equals方法）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}从上面的代码中可以看出，如果 HashMap 的每个 bucket 里只有一个元素，HashMap 可以根据索引快速取出该 bucket 里的元素。在发生“Hash冲突”的情况下，单个 bucket 里储存的不是一个元素，而是一个链式结构，系统只能必须按顺序遍历每个元素，直到找到想搜索的元素为止。如果恰好要搜索的元素位于该连接结构的末端，那必须循环到最后才能找到该元素。在 JDK1.8 中如果链式结构中的元素超过了8个，就会自动将 Node 转换为 TreeNode（红黑树），由于红黑树的搜索效果比较高，但必须正确实现Compare接口。
归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry、Node或者TreeNode 对象。HashMap 底层采用一个数组来保存所有的 key-value 对，当需要储存一个元素时，会根据 Hash 算法来决定其储存位置；当需要取出一个元素时，也会根据 Hash 算法找到起储存位置，直接取出该元素。由此可见，HashMap 之所以能快速存、取它所包含的元素，完全类似于现实生活中的：不同的东西要放在不同的位置，需要时才能快速找到它。
当创建 HashMap 时，又一个默认的负载因子（load factor），其默认值为 0.75.这是时间和空间成本是的一种折衷：增大负载因子可以减少 Hash 表所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减少负载因子会提高数据查询的性能，但它会降低 Hash 表所占用的内存空间。
掌握了上面的知识之后，可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值。如果程序比较关心空间开销，内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕，则可以适当较少负载因子。通常情况下，程序员无需改变负载因子的值。
如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中元素数量一直不会超过极限容量（capacity * load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的元素数组），因此创建 HashMap 时初始化容量设置也需要小心对待。
对于 HashSet 而言，它是基于 HashMap 实现的。HashSet 底层采用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，查看 HashSet 的源代码，可以看到如下所示：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
//使用HashMap的key保存HashSet中的所有元素
private transient HashMap<E,Object> map;
//定义一个虚拟的Object对象作为HashMap的value
private static final Object PRESENT = new Object();
//初始化HashSet，底层会初始化一个HashMap
public HashSet() {
map = new HashMap<>();
}
//以指定的initialCapacity、loadFactor、已存在的集合创建HashSet
//就是以相应参数创建HashMap
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//调用map的keyset来返回所有的key
public Iterator<E> iterator() {
return map.keySet().iterator();
}
//调用HashMap的size()方法返回元素数量，得到该Set里元素的个数
public int size() {
return map.size();
}
//调用HashMap的isEmpty()判断该HashSet是否也为空
//当HashMap为空时，对应的HashSet也为空
public boolean isEmpty() {
return map.isEmpty();
}
//调用HashMap的containsKey判断是否包含指定key
//HashSet的所有元素就是通过HashMap的Key来保存的
public boolean contains(Object o) {
return map.containsKey(o);
}
//将指定元素放入HashSet中，也就是将该元素作为key放入HashMap
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//调用HashMap的remove方法删除指定的元素，也就删除了HashSet中对应的元素
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//调用Map的clear方法清空所有元素，也就清空了HashSet中所有元素
public void clear() {
map.clear();
}
//...
//省略部分代码
}从上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来储存所有的集合元素。所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则储存了一个PRESENT，它是一个静态的 Object 对象。
HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现上本质上是相同的。
由于 HashSet 的 add() 方法添加集合元素时实际上转变为调用 HashMap 的 put() 方法来添加 key-value 对，当放入 HashMap 的元素中 key 与集合中原有元素的 key 相同（hashCode() 返回值相等，通过 equals 比较也返回 true）时，新添加的元素的 value 将覆盖原来元素的 value，但 key 不会有任何改变。因此，如果向 HashSet 中添加一个已经存在的元素，新添加的集合元素（底层由 HashMap 的 key 保存）不会覆盖已有的集合元素。
class Name {
private String first;
private String last;
public Name(String first, String last) {
this.first = first;
this.last = last;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first) && n.last.equals(last);
}
return false;
}
}
public class HashSetTest {
public static void main(String[] args) {
Set<Name> s = new HashSet<>();
s.add(new Name("abc", "123"));
System.out.println(s.contains(new Name("abc", "123")));
}
}运行上面的程序将看到程序输出 false，这是因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外，还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法，两个 Name 对象的 hashCode() 返回值并不相同，因此 HashSet 会把它们当成 2 个对象对象，程序返回 false。
由此可见，当试图把某个类的对象当成 HashMap 的key，或者视图将这个类的对象放入 HashSet 中保存时，重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致。当该类的两个 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
class Name {
private String first;
private String last;
public Name(String first, String last) {
this.first = first;
this.last = last;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first);
}
return false;
}
public int hashCode() {
return first.hashCode();
}
public String toString() {
return "Name[first=" + first + ", last=" + last + "]";
}
}
public class HashSetTest {
public static void main(String[] args) {
Set<Name> set = new HashSet<>();
set.add(new Name("abc", "123"));
set.add(new Name("abc", "456"));
System.out.println(set);
}
}上面程序提供了一个 Name 类，该 Name 类重写了 equals() 和 hashCode() 2 个方法。这 2 个方法都是根据 Name 类的 first 实例变量来判断的，当 2 个 Name 对象的 fist 实例相等时，这 2 个 Name 对象的 hashCOde() 返回值也相同，通过 equals() 比较也会返回 true。
程序主方法先将第一个 Name 对象添加到 HashSet 中，该 Name 对象的 first 实例变量值为 "abc"。接着程序再次视图将一个 first 为 "abc" 的 Name 对象添加到 HashSet 中。很明显，此时没法将新的 Name 对象添加到该 HashSet 中，因为此处视图添加的 Name 对象的 first 也是 "abc"，HashSet 会判断此处新增的 Name 对象与原有的 Name 对象相同，因此无法添加进入。运行代码可以看到，该集合只包含一个 Name 对象，就是第一个、即 last Field 值为 "123" 的 Name 对象。
TreeMap 和 TreeSet
类似于前面介绍的 HashMap 和 HashSet 之间的关系，HashSet 底层依赖于 HashMap 实现，TreeSet 底层则采用一个 NavigableMap 来保存 TreeSet 集合的元素。但实际上，由于 NavigableMap 只是一个接口，因此底层依然是使用 TreeMap 来包含 Set 集合中的所有元素。
下面是 TreeSet 类的部分源代码
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
//使用 NavigableMap的key来保存Set集合的元素
private transient NavigableMap<E,Object> m;
//使用一个PRESENT作为Map集合的所有value
private static final Object PRESENT = new Object();
//包访问权限的构造器，以指定NavigableMap对象创建Set集合
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
//以自然排序方式创建一个新的TreeMap，根据该TreeSet创建一个TreeSet
//使用该TreeMap的key来保存Set集合的元素
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
//以定制排序方式创建一个新的TreeMap，根据该TreeSet创建一个TreeSet
//使用该TreeMap的key来保存Set集合的元素
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
//调用无参的构造器创建一个TreeSet，底层以TreeMap保存集合元素
this();
//向TreeSet中添加Collection集合c里的所有元素
addAll(c);
}
public TreeSet(SortedSet<E> s) {
//调用指定排序方式的构造器创建一个TreeSet，底层以TreeMap保存集合元素
this(s.comparator());
//向TreeSet中添加Collection集合c里的所有元素
addAll(s);
}
//TreeSet的其他方法都只是直接调用TreeMap的方法来提供实现
//...
//省略部分代码
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
//把c集合强制转换为SortedSet集合
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
//把m结合强制转换为TreeMap集合
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
//如果cc和mc两个Comparator相等
if (cc==mc || (cc != null && cc.equals(mc))) {
//把Collection中所有元素添加成TreeMap集合的key
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
//直接调用父类的addAll()方法来实现
return super.addAll(c);
}
//...
//省略部分代码
}对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存Map中的每个 Entry————每个 Entry 都被当成“红黑树”的一个节点对待。示例如下：
public class TreeMapTest {
public static void main(String[] args) {
TreeMap<String, Double> map = new TreeMap<>();
map.put("ccc", 89.0);
map.put("aaa", 80.0);
map.put("zzz", 80.0);
map.put("bbb", 89.0);
System.out.println(map);
}
}当程序执行 map.put("ccc", 89.0); 时，系统将直接把 "ccc"-89.0 这个 Entry 放入 Map 中，这个 Entry 就是该红黑树的根节点。接着程序执行 map.put("aaa", 80.0); 时，会将 "aaa"-80.0 作为新节点添加到已有的红黑数中。
以后每向 TreeMap 中放入一个 Key-value 对，系统都需要将该 Entry 当成一个新节点，添加到已有红黑树中，通过这种方式就可保证 TreeMap 中所有的 key 总是由小到大地排列。例如，输出上面的程序，将看到如下结果（所有 key 由小到大地排列）：{aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0}
可以形象地归纳 HashMap、HashSet 与 TreeMap 、TreeSet 两类集合。HashMap、HashSet 的储存集合元素的方式类似于“妈妈放东西”，不同的东西放在不同的位置，需要时就可以快速的找到它们；TreeMap、TreeSet 的储存集合元素的方式类似于“体育课站队”，第一个人（相当于元素）自成一个对，以后每添加一个人都要先找到这个人应该插入的位置（队伍头端的所有人比新插入的人矮，队伍尾端所有人比新插入的人高），然后在该位置插入即可。这样可以保证该队伍总是由矮到高地排列————当然，二叉排序树的算法比“体育课站队”排序方式高效多了。
对于 TreeMap 而言，由于它底层采用一颗“红黑树”来保存集合中的 Entry，这意味着 TreeMap 添加元素、取出元素的性能都比 HashMap 低。当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 相比 HashMap、HashSet 的优势在于总是根据指定排序规则保持有序状态。
红黑树是一种自平衡二叉查找树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在书中查找和定位所需节点。
对于 TreeMap 集合而言，其关键就是 put(K key, V value)，该方法实现了将 Entry 放入 TreeMap 的 Entry 链，并保证该 Entry 链总是处于有序状态。下面是该方法的源代码。
public V put(K key, V value) {
//先以t保存链表的root节点
Entry<K,V> t = root;
//如果t==null，表名是一个空链表，即该TreeMap里没有任何Entry
if (t == null) {
//检查是否正确是否排序方法，而可以作为null检测
compare(key, key); // type (and possibly null) check
//将新的key-value创建一个Entry，并将该Entry作为root
root = new Entry<>(key, value, null);
size = 1;
//记录修改次数为1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比较器cpr不为null，即表名采用定制排序
if (cpr != null) {
do {
//使用parent上次循环后的t所引用的Entry
parent = t;
//拿新插入的key和t的key进行比较
cmp = cpr.compare(key, t.key);
//如果新插入的key小于t的key，t等于t的左边节点
if (cmp < 0)
t = t.left;
//如果新插入的key大于t的key，t等于t的右边节点
else if (cmp > 0)
t = t.right;
//如果两个key相等，新value覆盖原有的value，并返回原有的value
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//使用parent上次循环后的t所引用的Entry
parent = t;
//拿新插入的key和t的key进行比较
cmp = k.compareTo(t.key);
//如果新插入的key小于t的key，t等于t的左边节点
if (cmp < 0)
t = t.left;
//如果新插入的key大于t的key，t等于t的右边节点
else if (cmp > 0)
t = t.right;
//如果两个key相等，新value覆盖原有的value，并返回原有的value
else
return t.setValue(value);
} while (t != null);
}
//将新插入的节点作为parent节点的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新插入key小于parent的key，则e作为parent的左子节点
if (cmp < 0)
parent.left = e;
//如果新插入key大于parent的key，则e作为parent的右子节点
else
parent.right = e;
//修复红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}上面的代码就是实现“排序二叉树”的关键算法。每当程序希望添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。如果新增节点大于当前节点且当前节点的右子节点存在，则以右子节点作为当前节点；如果新增节点小于当前节点且当前节点的左子节点存在，则以左子节点作为当前节点；如果新增节点等于当前节点，则用新增节点覆盖当前节点，并结束循环————直到找到某个节点的左、右节点不存在，将新节点添加为该节点的子节点。如果新节点比该节点大，则添加右子节点；如果新街点比该节点小，则添加其为左子节点。
由于大学课程总是强调“算法 + 数据结构 = 程序”的等式，所以导致很多变成爱好者对算法、数据结构十分重视。当然笔者并不是说算法、数据结构不重要，但可能并没有大家想象的那么紧急。这个等式是很早以前提出的，那时候还没有很多高级语言可以使用，很多事情都必须由程序员自己来做，比如实现一个关联数组的结构等，因此对算法、数据结构的要求很高。今天有很多高级语言、基础库可以使用，因此对算法、数据结构的要求并没有那么高。
public V get(Object key) {
//根据指定的key取出对应的Entry
Entry<K,V> p = getEntry(key);
//返回该Entry所包含的value
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
//如果comparator不为null，表名程序采用定制排序
if (comparator != null)
//调用getEntryUsingComparator方法取出对应的key
return getEntryUsingComparator(key);
//如果key形参的值为null,抛出NullPointerException异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//将key强制类型转换为Comparable实例
Comparable<? super K> k = (Comparable<? super K>) key;
//从树的根节点开始
Entry<K,V> p = root;
while (p != null) {
//拿key与当前节点的key进行比较
int cmp = k.compareTo(p.key);
//如果key小雨当前节点的key，向“左子树”搜索
if (cmp < 0)
p = p.left;
//如果key大于当前节点的key，向“右子树”搜索
else if (cmp > 0)
p = p.right;
//如果既不大于也不小于，就是找到了目标Entry
else
return p;
}
return null;
}上面的 getEntry(Object obj) 方法也是充分利用排序二叉树的特征来搜索目标Entry。程序依然从二叉树的根节点开始，如果被搜索节点大于当前节点，程序向“右子树”搜索；如果被搜索节点小于当前节点，程序向“左子树”搜索；如果相等，那就是招到了指定节点。
当 TreeMap 里的 comparator != null，即表名该 TreeMap 采用了定制排序。在采用定制排序的方式下，TreeMap 采用 getEntryUsingComparator(key) 方法来根据 key 获取 Entry。下面是该方法的代码：
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
//获取该TreeMap的comparator
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//从根节点开始
Entry<K,V> p = root;
while (p != null) {
//拿key与当前节点的key进行比较
int cmp = cpr.compare(k, p.key);
//如果Key小于当前节点的key，向“左子树”搜索
if (cmp < 0)
p = p.left;
//如果Key大于当前节点的key，向“右子树”搜索
else if (cmp > 0)
p = p.right;
//如果既不大于也不小于，就是找到了目标Entry
else
return p;
}
}
return null;
}其实 getEntry、getEntryUsingComparator 这 2 个方法的实现思路完全类似，只是前者对自然排序的 TreeMap 获取有效，后者对定制排序的 TreeMap 有效。
通过上面的源代码分析不难看出，TreeMap 这个工具类的实现其实很简单。或者说，从内部结构来看，TreeMap 本质上就是一颗“红黑树”，而 TreeMap 的每个 Entry 就是该红黑树的一个节点。
Map 和 List
前面介绍了 Map 和 Set 的相似之处，当把 Map 中的 key-value 对当成单独的集合元素来对待时，Map 和 Set 也就统一起来了。接下来依然把 Map 的 key-value 分开来对待，从另外一个角度来看，就可以把 Map 和 List 统一起来。
Map 的 values() 方法
Map 集合是一个关联数组，它包含两组值：一组是所有 key 组成的集合，因为 Map 集合的 key 不允许重复，而且 Map 不会保存 key 加入的顺序，因此这些 key 可以组成一个 Set 集合；另外一组是 value 组成的集合，因为 Map 集合的 value 完全可以重复，而且 Map 可以根据 key 来获取对应的 value，所以这些 value 可以组成一个 List 集合。
实际上，Map 的 values 方法并未返回一个 List 集合，示例如下：
public class MapValueTest {
public static void main(String[] args) {
HashMap<String, Double> scores = new HashMap<>();
scores.put("语文", 89.0);
scores.put("数学", 83.0);
scores.put("英文", 80.0);
//输出scores集合的values()方法返回值
System.out.println(scores.values());
System.out.println(scores.values().getClass());
TreeMap<String, Double> health = new TreeMap<>();
health.put("身高", 173.0);
health.put("体重", 71.2);
//输出health集合的values()方法返回值
System.out.println(health.values());
System.out.println(health.values().getClass());
}
}输出结果：
[80.0, 83.0, 89.0]
class java.util.HashMap$Values
[71.2, 173.0]
class java.util.TreeMap$Values从上面的结果可以看出，HashMap 和 TreeMap 2 个集合的 values() 方法返回值确实是包含 Map 中所有 value 的集合，但它们并不是 List 对象，而分别是 HashMap$Values 和 TreeMap$Values 对象。
先来看 HashMap 的 values() 方法的源代码：
public Collection<V> values() {
//获取values实例变量
Collection<V> vs = values;
//如果vs=null，将返回new Values()对象
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}再来看 TreeMap 的 values() 方法的源代码：
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}由此可见，HashMap 和 TreeMap 这 2 个Map 类的 values() 方法的实现完全相同。当程序第一个调用这个 2 个 Map 对象的 values 方法时，它们会创建一个新的 Values 对象，并将该 Values 对象赋给 values 实例变量；当程序下次调用 values() 方法时，将直接以 values 实例变量作为返回值。
由此可见，对于 HashMap 和 TreeMap 而言，它们 values() 方法返回值的区别主要体现在各自 Values 内部类的实现上。
下面来看 HashMap 的Values 内部类的源代码：
final class Values extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<V> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}注意上面这个 Values 集合类，它虽然继承了 AbstractCollection 抽象类，但不不是一个 Collection 集合。因为它并未实现 add(Object e) 方法，而且 AbstractCollection 抽象类也没有实现 add(Object e) 方法，也就是说，这个 Values 集合对象并没有真正盛装任何 Java 对象。
ValueIterator 类的实现非常简单，它是通过调用 HashMap 的 nextEntry()（JDK1.8以前）或者 nextNode()（JDK1.8） 方法来实现的。下面是该类的源代码。
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}经过上面观察可以发现，HashMap 的 values() 方法表面上返回了一个 Values 集合对象，但这个集合对象并不能添加元素。它的主要功能是用于遍历 HashMap 里的所有 value，而遍历集合的所有 value 则主要依赖于 HashIterator 的 nextEntry()（JDK1.8以前）或者 nextNode()（JDK1.8） 方法来实现。对于 HashMap 而言，每个 Entry 或 Node 都持有一个引用变量指向下一个 Entry 或 Node，因此 HashMap 实现 nextEntry() 方法非常简单。
下面是 HashIterator 的 nextNode() 方法的源代码：
final Node<K,V> nextNode() {
Node<K,V>[] t;
//获取下一个元素
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}与 HashMap 类似的是，TreeMap 的 values() 方法同样返回了一个 Values 对象。此处的 Values 是 TreeMap 的私有内部类，该内部类的代码如下：
class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
//已TreeMap中最小的节点创建一个ValueIterator对象
return new ValueIterator(getFirstEntry());
}
public int size() {
//调用外部类的size()实例方法的返回值作为返回值
return TreeMap.this.size();
}
public boolean contains(Object o) {
//调用外部类的containsValue(o)实例方法的返回值作为返回值
return TreeMap.this.containsValue(o);
}
public boolean remove(Object o) {
//从TreeMap中最小的节点开始搜索，不断搜索下一个节点
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
//如果找到指定节点
if (valEquals(e.getValue(), o)) {
//执行删除
deleteEntry(e);
return true;
}
}
return false;
}
public void clear() {
//调用外部类的clear()方法来清空该集合
TreeMap.this.clear();
}
public Spliterator<V> spliterator() {
return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
}
}上面 Values 类与 HashMap 中 Values 类的区别不是太大，其中 size()、contains(Object o) 和 clear() 等方法也依赖于外部类 HashMap 的方法来提供实现。不过由于 TreeMap 是通过 “红黑树” 来实现的，因此上面程序中还用到了 TreeMap 提供的以下两个简单的工具类方法。
- getFirstEntry：获取 TreeMap 底层“红黑树”中最左边的“叶子节点”，也就是“红黑树”中最小的节点，即 TreeMap 中第一个节点。
- successor(Entry<K, V> t)：获取 TreeMap 中指定 Entry(t) 的下一个节点，也就是“红黑树”中大于 t 节点的最小节点。
getFirstEntry() 方法实现的比较简单：程序不断搜索“左子树”，直到找到最左边的“叶子节点”。该方法的实现代码如下：
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
//不断搜索左子节点，直到p成为最左子树的叶子节点
if (p != null)
while (p.left != null)
p = p.left;
return p;
}successor(Entry<K, V> t) 方法实现的稍稍复杂一点，该方法实现了搜索“红黑树”中大于指定节点的最小节点，其代码如下：
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
//如果其右子树存在，搜索右子树中最小的节点（也就是右子树中最左的叶子节点）
else if (t.right != null) {
//先获取其右子节点
Entry<K,V> p = t.right;
//不断搜索左子节点，知道找到最左的叶子节点
while (p.left != null)
p = p.left;
return p;
//如果右子树不存在
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
//只要父节点存在，且ch是父节点的右节点，表明ch大于其父节点，循环一直继续，直到父节点为null，或者ch变成父节点的子节点————此时父节点大于被搜索节点
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}通过 TreeMap 提供的这个 successor(Entry<K, V> t) 静态方法，可以非常方便地、由小到大遍历 TreeMap 底层的“二叉树”。实际上，完全可以通过这个静态方法来由小到大地遍历 TreeMap 的所有元素。但 TreeMap 为了保持 Map 用法上的一致性，依然通过 Values 的 iterator() 方法来遍历 Map 中所有 value。Values 的 iterator() 方法则由 ValueIterator 提供实现，ValueIterator 类的代码非常简单，如下所示：
final class ValueIterator extends PrivateEntryIterator<V> {
ValueIterator(Entry<K,V> first) {
super(first);
}
public V next() {
//调用其父类的nextEntry()方法获取下一个Entry，再返回该Entry的value
return nextEntry().value;
}
}对于 ValueIterator 而言，它只是简单地调用了其抽象父类 PrivateEntryIterator 的方法来实现 next() 方法。该抽象父类的代码如下：
abstract class PrivateEntryIterator<T> implements Iterator<T> {
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//获取e的下一个节点
next = successor(e);
lastReturned = e;
return e;
}
final Entry<K,V> prevEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//获取e的上一个节点
next = predecessor(e);
lastReturned = e;
return e;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
//删除指定节点
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}上面 PrivateEntryIterator 类中有以下两个重要方法。
- nextEntry()：获取当前节点的下一个节点。
- prevEntry()：获取当前节点的上一个节点。
这两个方法的实现其实很简单，它们只是对 successor(Entry<K, V> t)、predecessor(Entry<K, V> t) 两个方法的包装。PrivateEntryIterator 采用 next 记录了当前正在处理的节点，然后将 next 作为参数传给 successor(Entry<K, V> t)、predecessor(Entry<K, V> t) 两个方法即可实现 nextEntry()、prevEntry() 两个方法。
归纳起来可以发现：不管是 HashMap 还是TreeMap，它们的 values() 方法都可返回其所有 value 组成的 Collection 集合————按照通常理解，这个 Collection 集合应该是一个 List 集合，因为 Map 的多个 value 允许重复。
但实际上，HashMap、TreeMap 的 values() 方法的实现要更巧妙。这两个 Map 对象 values() 方法返回的是一个不存储元素的 Collection 集合，当程序遍历 Collection 集合时，实际上就是遍历 Map 对象的 value。
HashMap 和 TreeMap的 values() 方法并未把 Map 中的 value 重新组合成一个包含元素的集合对象，这样就可以降低系统内存开销。
Map 和 List 的关系
从底层实现来看，Set 和 Map 很相似；如果从用法的角度来看，Map 和 List 也有很大的相似之处：
- Map 接口提供了 get(K key) 方法允许 Map 对象根据 key 来取得 value；
- List 接口提供了 get(int index) 方法允许 List 对象根据元素索引来取得 value。
对于 List 接口而言，它仅按照元素的加入顺序保存了系统的 Java 对象。不过，可以换一种眼光来看待 List 集合，将索引当作 Map 的 key。当换一种方式来看待 List 集合之后可以发现：List 集合也包含 2 组值，其中一组是虚拟的 int 类型的索引，另一种是 List 集合元素。从这个意义上来看，可以说 List 相当于所有的 key 都是 int 类型的 Map。
Map 和 List 底层实现上并没有太大的相似之处，只是在用法上存在一些相似之处：既可以说 List 相当于所有 key 都是 int 类型的 Map，也可以说 Map 相当于索引是任意类型的 List。
下面介绍一个 JavaScript 中对象的用法。JavaScript 的对象有点类似于 Java 的 Map 结构，也是由多个 key-value 对组成，只是习惯上把 JavaScript 对象的 key-value 称为属性名、属性值。对于 JavaScript 对象而言，除了可使用属性语法来访问属性值之外，完全可以用数组语法来访问它的属性值。
JavaScript 没有提供 List 之类的集合，也没有提供 Map 集合，如果需要在 JavaScript 变成中使用 List 集合，使用 JavaScript 数组就可以了。也就是说，JavaScript 的数组既可以代替 Java 的数组，也可以代替 Java 的 List 集合。如果需要在 JavaScript 中使用 Map 集合，使用 JavaScript 的对象就可以了，JavaScript 的对象就是多个 key-value 对组成的关联数组。
本文内容来自以下：
- 《疯狂Java 突破程序员基本功的16课》第三章 常见的 Java 集合的实现细节
- HashMap在Java1.7与1.8中的区别