yeskery

常见 Java 集合的实现细节(上)

Set 和 Map

Set 代表一种集合元素无序、集合元素不可重复的集合,Map则代表一种由多个 key-value 对组成的集合,Map 集合类似于传统的关联数组。表面上看它们之间相似性很少,但实际上 Map 和 Set 之间有莫大的关联,可以说,Map 集合是 Set 集合的扩展。

Set 和 Map 的关系

set_map_extends

再看 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 即可。

set_map_key_value

对于一个 Map 集合而言,它本质上是一个关联数组,如上图左侧所示。

对于上图左侧所示的关联数组,其实可以改为使用一个 Set 集合来保存它们,反正上面关联数组中 key-value 对质检有严格的对应关系,那么干脆将 key-value 对捆绑在一起对待,如上图右侧所示。

为了把 Set 扩展成 Map,可以考虑新增定义一个 SimpleEntry 类,该类代表一个 key-value 对;当 Set 集合的集合元素都是 SimpleEntry 对象时,该 Set 集合就能被当成 Map 使用。下面程序示范了如何将一个 Set 集合扩展成 Map 集合。

  1. import java.io.Serializable;
  2. import java.util.HashSet;
  3. import java.util.Iterator;
  4. import java.util.Map;
  5. class SimpleEntry<K, V> implements Map.Entry<K, V>, Serializable {
  6. private static final long serialVersionUID = 1L;
  7. private final K key;
  8. private V value;
  9. //定义如下2个构造器
  10. public SimpleEntry(K key, V value) {
  11. this.key = key;
  12. this.value = value;
  13. }
  14. public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) {
  15. this.key = entry.getKey();
  16. this.value = entry.getValue();
  17. }
  18. //获取key
  19. @Override
  20. public K getKey() {
  21. return key;
  22. }
  23. //获取value
  24. @Override
  25. public V getValue() {
  26. return value;
  27. }
  28. //改变该Key-value对的value值
  29. @Override
  30. public V setValue(V value) {
  31. V oldValue = this.value;
  32. this.value = value;
  33. return oldValue;
  34. }
  35. //根据key计算hashCode
  36. @Override
  37. public int hashCode() {
  38. return key == null ? 0 : key.hashCode();
  39. }
  40. //根据key比较2个SimpleEntry是否相等
  41. @Override
  42. public boolean equals(Object o) {
  43. if (o == this) {
  44. return true;
  45. }
  46. if (o.getClass() == SimpleEntry.class) {
  47. @SuppressWarnings("rawtypes")
  48. SimpleEntry se = (SimpleEntry)o;
  49. return se.getKey().equals(getKey());
  50. }
  51. return false;
  52. }
  53. @Override
  54. public String toString() {
  55. return key + "=" + value;
  56. }
  57. }
  58. //继承HashSet实现一个Map
  59. public class Set2Map<K, V> extends HashSet<SimpleEntry<K, V>> {
  60. private static final long serialVersionUID = 1L;
  61. //实现清空所有key-value对的方法
  62. @Override
  63. public void clear() {
  64. super.clear();
  65. }
  66. //判断是否包含某个key
  67. @SuppressWarnings({ "unchecked", "rawtypes" })
  68. public boolean containsKey(K key) {
  69. return super.contains(new SimpleEntry(key, null));
  70. }
  71. //判断是否包含某个value
  72. boolean containsValue(V value) {
  73. for (SimpleEntry<K, V> se : this) {
  74. if (se.getValue().equals(value)) {
  75. return true;
  76. }
  77. }
  78. return false;
  79. }
  80. //根据指定key取出对应的value
  81. public V get(K key) {
  82. for (SimpleEntry<K, V> se : this) {
  83. if (se.getKey().equals(key)) {
  84. return se.getValue();
  85. }
  86. }
  87. return null;
  88. }
  89. //将指定key-value对放入集合
  90. public V put(K key, V value) {
  91. super.add(new SimpleEntry<K, V>(key, value));
  92. return value;
  93. }
  94. //将另外一个Map的key-value对放入该Map中
  95. @SuppressWarnings({ "unchecked", "rawtypes" })
  96. public void putAll(Map<? extends K, ? extends V> m) {
  97. for (K key : m.keySet()) {
  98. super.add(new SimpleEntry(key, m.get(key)));
  99. }
  100. }
  101. //根据指定key删除Key-value对
  102. public V removeEntry(K key) {
  103. for (Iterator<SimpleEntry<K, V>> it = this.iterator();it.hasNext();) {
  104. SimpleEntry<K, V> en = it.next();
  105. if (en.getKey().equals(key)) {
  106. V v = en.getValue();
  107. it.remove();
  108. return v;
  109. }
  110. }
  111. return null;
  112. }
  113. //获取该Map中包含多少个key-value对
  114. @Override
  115. public int size() {
  116. return super.size();
  117. }
  118. }

下面程序简单测试了扩展出来的“Map”集合

  1. public class Set2MapTest {
  2. public static void main(String[] args) {
  3. Set2Map<String, Integer> scores = new Set2Map<String, Integer>();
  4. //将key-value对放入集合
  5. scores.put("语文", 89);
  6. scores.put("数学", 83);
  7. scores.put("英文", 80);
  8. System.out.println(scores);
  9. //访问Map集合里包含的key-value对
  10. System.out.println(scores.size());
  11. scores.removeEntry("数学");
  12. System.out.println("删除key为\"数学\"的Entry之后:" + scores);
  13. //根据key取出value
  14. System.out.println("语文成绩:" + scores.get("语文"));
  15. //判断是否包含指定key
  16. System.out.println("是否包含\"英文\"key:" + scores.containsKey("英文"));
  17. //判断是否包含指定value
  18. System.out.println("是否包含82 value:" + scores.containsValue(82));
  19. //清空集合
  20. scores.clear();
  21. System.out.println("执行clear()方法之后的集合:" + scores);
  22. }
  23. }

输出结果为:

  1. [英文=80, 数学=83, 语文=89]
  2. 3
  3. 删除key"数学"Entry之后:[英文=80, 语文=89]
  4. 语文成绩:89
  5. 是否包含"英文"keytrue
  6. 是否包含82 valuefalse
  7. 执行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 集合来说,其实它只是多个引用变量的集合,下面的程序可以证明这一点。

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. class Apple {
  4. double weight;
  5. public Apple(double weight) {
  6. this.weight = weight;
  7. }
  8. }
  9. public class ListTest {
  10. public static void main(String[] args) {
  11. //创建2个Apple对象
  12. Apple t1 = new Apple(2.2);
  13. Apple t2 = new Apple(1.8);
  14. List<Apple> list = new ArrayList<Apple>(4);
  15. //将2个Apple对象放入List集合中
  16. list.add(t1);
  17. list.add(t2);
  18. //判断从集合里取出的引用变量和原有引用变量是否指向同一个元素
  19. System.out.println(list.get(0) == t1);
  20. System.out.println(list.get(1) == t2);
  21. }
  22. }

ArrayList 底层是基于数组实现的,也就是说 ArrayList 底层封装的是数组,每次创建 ArrayList 时传入的 int 参数就是它所包装的数组的长度;如果创建 ArrayList 时没有传入 int 参数,那么 ArrayList 的初始长度为 10,也就是底层所封装的数组的长度为 10。

实际上,此时 t1 和 list 集合的第 1 个元素都指向同一个 Java 对象,t2 和 list 的第 2 个元素也指向同一个 Java 对象,因此上面的程序将会输出 2 个 true。

下面将详细介绍 HashSet、HashMap 对集合元素的储存方式。当程序视图将多个 key-value 放入 HashMap 中时,示例代码片段如下:

  1. HashMap<String, Double> map = new HashMap<String, Double>();
  2. map.put("语文", 80.0);
  3. map.put("数学", 89.0);
  4. 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):

  1. public V put(K key, V value) {
  2. //根据key计算Hash值,并调用putVal方法
  3. return putVal(hash(key), key, value, false, true);
  4. }
  5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  6. boolean evict) {
  7. Node<K,V>[] tab; Node<K,V> p; int n, i;
  8. //判断Node数组table是否为空,如果为空创建一个新的Node数组
  9. if ((tab = table) == null || (n = tab.length) == 0)
  10. n = (tab = resize()).length;
  11. //如果hash值对应的索引在Node数组中的Node为null,则在该索引对应的Node数组中创建一个新的Node
  12. if ((p = tab[i = (n - 1) & hash]) == null)
  13. tab[i] = newNode(hash, key, value, null);
  14. //如果索引对应的Node数组中的Node不为null
  15. else {
  16. Node<K,V> e; K k;
  17. //判断需要添加的Node是否和原来的Node一致,并且key不会null
  18. if (p.hash == hash &&
  19. ((k = p.key) == key || (key != null && key.equals(k))))
  20. e = p;
  21. //判断Node是否是一个TreeNode,TreeNode是继承于LinkedHashMap.Entry<K,V>,用于标记一个有序的Node
  22. else if (p instanceof TreeNode)
  23. e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  24. else {
  25. //找到指定key与需要放入的key相等的Node
  26. for (int binCount = 0; ; ++binCount) {
  27. //索引处的Node的下一个Node为null
  28. if ((e = p.next) == null) {
  29. //创建一个新的Node关联到Node的next属性上,形成一个Node链
  30. p.next = newNode(hash, key, value, null);
  31. //当bin计算器达到TreeNode的最低要求8时候,就将当前的Node数组转换为TreeNode,以提高操作效率
  32. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  33. treeifyBin(tab, hash);
  34. break;
  35. }
  36. //判断是否该Node和需要添加的Node一样
  37. if (e.hash == hash &&
  38. ((k = e.key) == key || (key != null && key.equals(k))))
  39. break;
  40. p = e;
  41. }
  42. }
  43. //判断已经找到key匹配的Node
  44. if (e != null) { // existing mapping for key
  45. V oldValue = e.value;
  46. //判断Node数组的值已经被修改过或者该Node之前的value为null,就修改该Node的value为传入的value
  47. if (!onlyIfAbsent || oldValue == null)
  48. e.value = value;
  49. afterNodeAccess(e);
  50. return oldValue;
  51. }
  52. }
  53. //操作计数符
  54. ++modCount;
  55. //如果Map中的key-value对超过了Node数组的极限,就对Node数组进行扩容,默认是在 resize() 方法中,将原来的数组扩大一倍
  56. if (++size > threshold)
  57. resize();
  58. afterNodeInsertion(evict);
  59. return null;
  60. }

在这里,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 中一个构造器的代码:

  1. //以指定的初始化容量、负载因子创建HashMap
  2. public HashMap(int initialCapacity, float loadFactor) {
  3. //初始容量不能为负数
  4. if (initialCapacity < 0)
  5. throw new IllegalArgumentException("Illegal initial capacity: " +
  6. initialCapacity);
  7. //如果负载因子大于最大容量,让初始容量等于最大容量
  8. if (initialCapacity > MAXIMUM_CAPACITY)
  9. initialCapacity = MAXIMUM_CAPACITY;
  10. //负载因子必须是大于0的数值
  11. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  12. throw new IllegalArgumentException("Illegal load factor: " +
  13. loadFactor);
  14. this.loadFactor = loadFactor;
  15. //设置容量极限,如果initialCapacity等于2的n次幂,极限容量就等于initialCapacity,如果不等于,容量极限就等于大于initialCapacity的最小的2的n次幂
  16. this.threshold = tableSizeFor(initialCapacity);
  17. }

上面的代码中,需要计算出数组的容量 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):

  1. public V get(Object key) {
  2. Node<K,V> e;
  3. return (e = getNode(hash(key), key)) == null ? null : e.value;
  4. }
  5. final Node<K,V> getNode(int hash, Object key) {
  6. Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  7. //判断table数组不为null且table数组的长度不为0且table的第一个元素不为null
  8. if ((tab = table) != null && (n = tab.length) > 0 &&
  9. //直接根据key的hash值取出该hash值指定的元素
  10. (first = tab[(n - 1) & hash]) != null) {
  11. //首先检查第一个元素,如果第一个元素的hash值与给定的hash值相同,且该key的引用相同或key的值相同(调用equals方法)
  12. if (first.hash == hash && // always check first node
  13. ((k = first.key) == key || (key != null && key.equals(k))))
  14. return first;
  15. //判断该元素是否引用下一个元素
  16. if ((e = first.next) != null) {
  17. //如果元素是红黑树TreeNode,就调用红黑树的搜索方法
  18. if (first instanceof TreeNode)
  19. return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  20. //搜索该元素的下一个元素
  21. do {
  22. //如果该元素的hash值与给定的hash值相同,且该key的引用相同或key的值相同(调用equals方法)
  23. if (e.hash == hash &&
  24. ((k = e.key) == key || (key != null && key.equals(k))))
  25. return e;
  26. } while ((e = e.next) != null);
  27. }
  28. }
  29. return null;
  30. }

从上面的代码中可以看出,如果 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 的源代码,可以看到如下所示:

  1. public class HashSet<E>
  2. extends AbstractSet<E>
  3. implements Set<E>, Cloneable, java.io.Serializable
  4. {
  5. static final long serialVersionUID = -5024744406713321676L;
  6. //使用HashMap的key保存HashSet中的所有元素
  7. private transient HashMap<E,Object> map;
  8. //定义一个虚拟的Object对象作为HashMap的value
  9. private static final Object PRESENT = new Object();
  10. //初始化HashSet,底层会初始化一个HashMap
  11. public HashSet() {
  12. map = new HashMap<>();
  13. }
  14. //以指定的initialCapacity、loadFactor、已存在的集合创建HashSet
  15. //就是以相应参数创建HashMap
  16. public HashSet(Collection<? extends E> c) {
  17. map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
  18. addAll(c);
  19. }
  20. public HashSet(int initialCapacity, float loadFactor) {
  21. map = new HashMap<>(initialCapacity, loadFactor);
  22. }
  23. public HashSet(int initialCapacity) {
  24. map = new HashMap<>(initialCapacity);
  25. }
  26. HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  27. map = new LinkedHashMap<>(initialCapacity, loadFactor);
  28. }
  29. //调用map的keyset来返回所有的key
  30. public Iterator<E> iterator() {
  31. return map.keySet().iterator();
  32. }
  33. //调用HashMap的size()方法返回元素数量,得到该Set里元素的个数
  34. public int size() {
  35. return map.size();
  36. }
  37. //调用HashMap的isEmpty()判断该HashSet是否也为空
  38. //当HashMap为空时,对应的HashSet也为空
  39. public boolean isEmpty() {
  40. return map.isEmpty();
  41. }
  42. //调用HashMap的containsKey判断是否包含指定key
  43. //HashSet的所有元素就是通过HashMap的Key来保存的
  44. public boolean contains(Object o) {
  45. return map.containsKey(o);
  46. }
  47. //将指定元素放入HashSet中,也就是将该元素作为key放入HashMap
  48. public boolean add(E e) {
  49. return map.put(e, PRESENT)==null;
  50. }
  51. //调用HashMap的remove方法删除指定的元素,也就删除了HashSet中对应的元素
  52. public boolean remove(Object o) {
  53. return map.remove(o)==PRESENT;
  54. }
  55. //调用Map的clear方法清空所有元素,也就清空了HashSet中所有元素
  56. public void clear() {
  57. map.clear();
  58. }
  59. //...
  60. //省略部分代码
  61. }

从上面源程序可以看出,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 保存)不会覆盖已有的集合元素。

  1. class Name {
  2. private String first;
  3. private String last;
  4. public Name(String first, String last) {
  5. this.first = first;
  6. this.last = last;
  7. }
  8. public boolean equals(Object o) {
  9. if (this == o) {
  10. return true;
  11. }
  12. if (o.getClass() == Name.class) {
  13. Name n = (Name)o;
  14. return n.first.equals(first) && n.last.equals(last);
  15. }
  16. return false;
  17. }
  18. }
  19. public class HashSetTest {
  20. public static void main(String[] args) {
  21. Set<Name> s = new HashSet<>();
  22. s.add(new Name("abc", "123"));
  23. System.out.println(s.contains(new Name("abc", "123")));
  24. }
  25. }

运行上面的程序将看到程序输出 false,这是因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外,还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法,两个 Name 对象的 hashCode() 返回值并不相同,因此 HashSet 会把它们当成 2 个对象对象,程序返回 false。

由此可见,当试图把某个类的对象当成 HashMap 的key,或者视图将这个类的对象放入 HashSet 中保存时,重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致。当该类的两个 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。

  1. class Name {
  2. private String first;
  3. private String last;
  4. public Name(String first, String last) {
  5. this.first = first;
  6. this.last = last;
  7. }
  8. public boolean equals(Object o) {
  9. if (this == o) {
  10. return true;
  11. }
  12. if (o.getClass() == Name.class) {
  13. Name n = (Name)o;
  14. return n.first.equals(first);
  15. }
  16. return false;
  17. }
  18. public int hashCode() {
  19. return first.hashCode();
  20. }
  21. public String toString() {
  22. return "Name[first=" + first + ", last=" + last + "]";
  23. }
  24. }
  25. public class HashSetTest {
  26. public static void main(String[] args) {
  27. Set<Name> set = new HashSet<>();
  28. set.add(new Name("abc", "123"));
  29. set.add(new Name("abc", "456"));
  30. System.out.println(set);
  31. }
  32. }

上面程序提供了一个 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 类的部分源代码

  1. public class TreeSet<E> extends AbstractSet<E>
  2. implements NavigableSet<E>, Cloneable, java.io.Serializable
  3. {
  4. //使用 NavigableMap的key来保存Set集合的元素
  5. private transient NavigableMap<E,Object> m;
  6. //使用一个PRESENT作为Map集合的所有value
  7. private static final Object PRESENT = new Object();
  8. //包访问权限的构造器,以指定NavigableMap对象创建Set集合
  9. TreeSet(NavigableMap<E,Object> m) {
  10. this.m = m;
  11. }
  12. public TreeSet() {
  13. //以自然排序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
  14. //使用该TreeMap的key来保存Set集合的元素
  15. this(new TreeMap<E,Object>());
  16. }
  17. public TreeSet(Comparator<? super E> comparator) {
  18. //以定制排序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
  19. //使用该TreeMap的key来保存Set集合的元素
  20. this(new TreeMap<>(comparator));
  21. }
  22. public TreeSet(Collection<? extends E> c) {
  23. //调用无参的构造器创建一个TreeSet,底层以TreeMap保存集合元素
  24. this();
  25. //向TreeSet中添加Collection集合c里的所有元素
  26. addAll(c);
  27. }
  28. public TreeSet(SortedSet<E> s) {
  29. //调用指定排序方式的构造器创建一个TreeSet,底层以TreeMap保存集合元素
  30. this(s.comparator());
  31. //向TreeSet中添加Collection集合c里的所有元素
  32. addAll(s);
  33. }
  34. //TreeSet的其他方法都只是直接调用TreeMap的方法来提供实现
  35. //...
  36. //省略部分代码
  37. public boolean addAll(Collection<? extends E> c) {
  38. // Use linear-time version if applicable
  39. if (m.size()==0 && c.size() > 0 &&
  40. c instanceof SortedSet &&
  41. m instanceof TreeMap) {
  42. //把c集合强制转换为SortedSet集合
  43. SortedSet<? extends E> set = (SortedSet<? extends E>) c;
  44. //把m结合强制转换为TreeMap集合
  45. TreeMap<E,Object> map = (TreeMap<E, Object>) m;
  46. Comparator<?> cc = set.comparator();
  47. Comparator<? super E> mc = map.comparator();
  48. //如果cc和mc两个Comparator相等
  49. if (cc==mc || (cc != null && cc.equals(mc))) {
  50. //把Collection中所有元素添加成TreeMap集合的key
  51. map.addAllForTreeSet(set, PRESENT);
  52. return true;
  53. }
  54. }
  55. //直接调用父类的addAll()方法来实现
  56. return super.addAll(c);
  57. }
  58. //...
  59. //省略部分代码
  60. }

对于 TreeMap 而言,它采用一种被称为“红黑树”的排序二叉树来保存Map中的每个 Entry————每个 Entry 都被当成“红黑树”的一个节点对待。示例如下:

  1. public class TreeMapTest {
  2. public static void main(String[] args) {
  3. TreeMap<String, Double> map = new TreeMap<>();
  4. map.put("ccc", 89.0);
  5. map.put("aaa", 80.0);
  6. map.put("zzz", 80.0);
  7. map.put("bbb", 89.0);
  8. System.out.println(map);
  9. }
  10. }

当程序执行 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 链总是处于有序状态。下面是该方法的源代码。

  1. public V put(K key, V value) {
  2. //先以t保存链表的root节点
  3. Entry<K,V> t = root;
  4. //如果t==null,表名是一个空链表,即该TreeMap里没有任何Entry
  5. if (t == null) {
  6. //检查是否正确是否排序方法,而可以作为null检测
  7. compare(key, key); // type (and possibly null) check
  8. //将新的key-value创建一个Entry,并将该Entry作为root
  9. root = new Entry<>(key, value, null);
  10. size = 1;
  11. //记录修改次数为1
  12. modCount++;
  13. return null;
  14. }
  15. int cmp;
  16. Entry<K,V> parent;
  17. // split comparator and comparable paths
  18. Comparator<? super K> cpr = comparator;
  19. //如果比较器cpr不为null,即表名采用定制排序
  20. if (cpr != null) {
  21. do {
  22. //使用parent上次循环后的t所引用的Entry
  23. parent = t;
  24. //拿新插入的key和t的key进行比较
  25. cmp = cpr.compare(key, t.key);
  26. //如果新插入的key小于t的key,t等于t的左边节点
  27. if (cmp < 0)
  28. t = t.left;
  29. //如果新插入的key大于t的key,t等于t的右边节点
  30. else if (cmp > 0)
  31. t = t.right;
  32. //如果两个key相等,新value覆盖原有的value,并返回原有的value
  33. else
  34. return t.setValue(value);
  35. } while (t != null);
  36. }
  37. else {
  38. if (key == null)
  39. throw new NullPointerException();
  40. @SuppressWarnings("unchecked")
  41. Comparable<? super K> k = (Comparable<? super K>) key;
  42. do {
  43. //使用parent上次循环后的t所引用的Entry
  44. parent = t;
  45. //拿新插入的key和t的key进行比较
  46. cmp = k.compareTo(t.key);
  47. //如果新插入的key小于t的key,t等于t的左边节点
  48. if (cmp < 0)
  49. t = t.left;
  50. //如果新插入的key大于t的key,t等于t的右边节点
  51. else if (cmp > 0)
  52. t = t.right;
  53. //如果两个key相等,新value覆盖原有的value,并返回原有的value
  54. else
  55. return t.setValue(value);
  56. } while (t != null);
  57. }
  58. //将新插入的节点作为parent节点的子节点
  59. Entry<K,V> e = new Entry<>(key, value, parent);
  60. //如果新插入key小于parent的key,则e作为parent的左子节点
  61. if (cmp < 0)
  62. parent.left = e;
  63. //如果新插入key大于parent的key,则e作为parent的右子节点
  64. else
  65. parent.right = e;
  66. //修复红黑树
  67. fixAfterInsertion(e);
  68. size++;
  69. modCount++;
  70. return null;
  71. }

上面的代码就是实现“排序二叉树”的关键算法。每当程序希望添加新节点时,总是从树的根节点开始比较,即将根节点当成当前节点。如果新增节点大于当前节点且当前节点的右子节点存在,则以右子节点作为当前节点;如果新增节点小于当前节点且当前节点的左子节点存在,则以左子节点作为当前节点;如果新增节点等于当前节点,则用新增节点覆盖当前节点,并结束循环————直到找到某个节点的左、右节点不存在,将新节点添加为该节点的子节点。如果新节点比该节点大,则添加右子节点;如果新街点比该节点小,则添加其为左子节点。

由于大学课程总是强调“算法 + 数据结构 = 程序”的等式,所以导致很多变成爱好者对算法、数据结构十分重视。当然笔者并不是说算法、数据结构不重要,但可能并没有大家想象的那么紧急。这个等式是很早以前提出的,那时候还没有很多高级语言可以使用,很多事情都必须由程序员自己来做,比如实现一个关联数组的结构等,因此对算法、数据结构的要求很高。今天有很多高级语言、基础库可以使用,因此对算法、数据结构的要求并没有那么高。

  1. public V get(Object key) {
  2. //根据指定的key取出对应的Entry
  3. Entry<K,V> p = getEntry(key);
  4. //返回该Entry所包含的value
  5. return (p==null ? null : p.value);
  6. }
  7. final Entry<K,V> getEntry(Object key) {
  8. //如果comparator不为null,表名程序采用定制排序
  9. if (comparator != null)
  10. //调用getEntryUsingComparator方法取出对应的key
  11. return getEntryUsingComparator(key);
  12. //如果key形参的值为null,抛出NullPointerException异常
  13. if (key == null)
  14. throw new NullPointerException();
  15. @SuppressWarnings("unchecked")
  16. //将key强制类型转换为Comparable实例
  17. Comparable<? super K> k = (Comparable<? super K>) key;
  18. //从树的根节点开始
  19. Entry<K,V> p = root;
  20. while (p != null) {
  21. //拿key与当前节点的key进行比较
  22. int cmp = k.compareTo(p.key);
  23. //如果key小雨当前节点的key,向“左子树”搜索
  24. if (cmp < 0)
  25. p = p.left;
  26. //如果key大于当前节点的key,向“右子树”搜索
  27. else if (cmp > 0)
  28. p = p.right;
  29. //如果既不大于也不小于,就是找到了目标Entry
  30. else
  31. return p;
  32. }
  33. return null;
  34. }

上面的 getEntry(Object obj) 方法也是充分利用排序二叉树的特征来搜索目标Entry。程序依然从二叉树的根节点开始,如果被搜索节点大于当前节点,程序向“右子树”搜索;如果被搜索节点小于当前节点,程序向“左子树”搜索;如果相等,那就是招到了指定节点。

当 TreeMap 里的 comparator != null,即表名该 TreeMap 采用了定制排序。在采用定制排序的方式下,TreeMap 采用 getEntryUsingComparator(key) 方法来根据 key 获取 Entry。下面是该方法的代码:

  1. final Entry<K,V> getEntryUsingComparator(Object key) {
  2. @SuppressWarnings("unchecked")
  3. K k = (K) key;
  4. //获取该TreeMap的comparator
  5. Comparator<? super K> cpr = comparator;
  6. if (cpr != null) {
  7. //从根节点开始
  8. Entry<K,V> p = root;
  9. while (p != null) {
  10. //拿key与当前节点的key进行比较
  11. int cmp = cpr.compare(k, p.key);
  12. //如果Key小于当前节点的key,向“左子树”搜索
  13. if (cmp < 0)
  14. p = p.left;
  15. //如果Key大于当前节点的key,向“右子树”搜索
  16. else if (cmp > 0)
  17. p = p.right;
  18. //如果既不大于也不小于,就是找到了目标Entry
  19. else
  20. return p;
  21. }
  22. }
  23. return null;
  24. }

其实 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 集合,示例如下:

  1. public class MapValueTest {
  2. public static void main(String[] args) {
  3. HashMap<String, Double> scores = new HashMap<>();
  4. scores.put("语文", 89.0);
  5. scores.put("数学", 83.0);
  6. scores.put("英文", 80.0);
  7. //输出scores集合的values()方法返回值
  8. System.out.println(scores.values());
  9. System.out.println(scores.values().getClass());
  10. TreeMap<String, Double> health = new TreeMap<>();
  11. health.put("身高", 173.0);
  12. health.put("体重", 71.2);
  13. //输出health集合的values()方法返回值
  14. System.out.println(health.values());
  15. System.out.println(health.values().getClass());
  16. }
  17. }

输出结果:

  1. [80.0, 83.0, 89.0]
  2. class java.util.HashMap$Values
  3. [71.2, 173.0]
  4. class java.util.TreeMap$Values

从上面的结果可以看出,HashMap 和 TreeMap 2 个集合的 values() 方法返回值确实是包含 Map 中所有 value 的集合,但它们并不是 List 对象,而分别是 HashMap$Values 和 TreeMap$Values 对象。

先来看 HashMap 的 values() 方法的源代码:

  1. public Collection<V> values() {
  2. //获取values实例变量
  3. Collection<V> vs = values;
  4. //如果vs=null,将返回new Values()对象
  5. if (vs == null) {
  6. vs = new Values();
  7. values = vs;
  8. }
  9. return vs;
  10. }

再来看 TreeMap 的 values() 方法的源代码:

  1. public Collection<V> values() {
  2. Collection<V> vs = values;
  3. if (vs == null) {
  4. vs = new Values();
  5. values = vs;
  6. }
  7. return vs;
  8. }

由此可见,HashMap 和 TreeMap 这 2 个Map 类的 values() 方法的实现完全相同。当程序第一个调用这个 2 个 Map 对象的 values 方法时,它们会创建一个新的 Values 对象,并将该 Values 对象赋给 values 实例变量;当程序下次调用 values() 方法时,将直接以 values 实例变量作为返回值。

由此可见,对于 HashMap 和 TreeMap 而言,它们 values() 方法返回值的区别主要体现在各自 Values 内部类的实现上。

下面来看 HashMap 的Values 内部类的源代码:

  1. final class Values extends AbstractCollection<V> {
  2. public final int size() { return size; }
  3. public final void clear() { HashMap.this.clear(); }
  4. public final Iterator<V> iterator() { return new ValueIterator(); }
  5. public final boolean contains(Object o) { return containsValue(o); }
  6. public final Spliterator<V> spliterator() {
  7. return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
  8. }
  9. public final void forEach(Consumer<? super V> action) {
  10. Node<K,V>[] tab;
  11. if (action == null)
  12. throw new NullPointerException();
  13. if (size > 0 && (tab = table) != null) {
  14. int mc = modCount;
  15. for (int i = 0; i < tab.length; ++i) {
  16. for (Node<K,V> e = tab[i]; e != null; e = e.next)
  17. action.accept(e.value);
  18. }
  19. if (modCount != mc)
  20. throw new ConcurrentModificationException();
  21. }
  22. }
  23. }

注意上面这个 Values 集合类,它虽然继承了 AbstractCollection 抽象类,但不不是一个 Collection 集合。因为它并未实现 add(Object e) 方法,而且 AbstractCollection 抽象类也没有实现 add(Object e) 方法,也就是说,这个 Values 集合对象并没有真正盛装任何 Java 对象。

ValueIterator 类的实现非常简单,它是通过调用 HashMap 的 nextEntry()(JDK1.8以前)或者 nextNode()(JDK1.8) 方法来实现的。下面是该类的源代码。

  1. final class ValueIterator extends HashIterator
  2. implements Iterator<V> {
  3. public final V next() { return nextNode().value; }
  4. }

经过上面观察可以发现,HashMap 的 values() 方法表面上返回了一个 Values 集合对象,但这个集合对象并不能添加元素。它的主要功能是用于遍历 HashMap 里的所有 value,而遍历集合的所有 value 则主要依赖于 HashIterator 的 nextEntry()(JDK1.8以前)或者 nextNode()(JDK1.8) 方法来实现。对于 HashMap 而言,每个 Entry 或 Node 都持有一个引用变量指向下一个 Entry 或 Node,因此 HashMap 实现 nextEntry() 方法非常简单。

下面是 HashIterator 的 nextNode() 方法的源代码:

  1. final Node<K,V> nextNode() {
  2. Node<K,V>[] t;
  3. //获取下一个元素
  4. Node<K,V> e = next;
  5. if (modCount != expectedModCount)
  6. throw new ConcurrentModificationException();
  7. if (e == null)
  8. throw new NoSuchElementException();
  9. if ((next = (current = e).next) == null && (t = table) != null) {
  10. do {} while (index < t.length && (next = t[index++]) == null);
  11. }
  12. return e;
  13. }

与 HashMap 类似的是,TreeMap 的 values() 方法同样返回了一个 Values 对象。此处的 Values 是 TreeMap 的私有内部类,该内部类的代码如下:

  1. class Values extends AbstractCollection<V> {
  2. public Iterator<V> iterator() {
  3. //已TreeMap中最小的节点创建一个ValueIterator对象
  4. return new ValueIterator(getFirstEntry());
  5. }
  6. public int size() {
  7. //调用外部类的size()实例方法的返回值作为返回值
  8. return TreeMap.this.size();
  9. }
  10. public boolean contains(Object o) {
  11. //调用外部类的containsValue(o)实例方法的返回值作为返回值
  12. return TreeMap.this.containsValue(o);
  13. }
  14. public boolean remove(Object o) {
  15. //从TreeMap中最小的节点开始搜索,不断搜索下一个节点
  16. for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
  17. //如果找到指定节点
  18. if (valEquals(e.getValue(), o)) {
  19. //执行删除
  20. deleteEntry(e);
  21. return true;
  22. }
  23. }
  24. return false;
  25. }
  26. public void clear() {
  27. //调用外部类的clear()方法来清空该集合
  28. TreeMap.this.clear();
  29. }
  30. public Spliterator<V> spliterator() {
  31. return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
  32. }
  33. }

上面 Values 类与 HashMap 中 Values 类的区别不是太大,其中 size()、contains(Object o) 和 clear() 等方法也依赖于外部类 HashMap 的方法来提供实现。不过由于 TreeMap 是通过 “红黑树” 来实现的,因此上面程序中还用到了 TreeMap 提供的以下两个简单的工具类方法。

  • getFirstEntry:获取 TreeMap 底层“红黑树”中最左边的“叶子节点”,也就是“红黑树”中最小的节点,即 TreeMap 中第一个节点。
  • successor(Entry<K, V> t):获取 TreeMap 中指定 Entry(t) 的下一个节点,也就是“红黑树”中大于 t 节点的最小节点。

getFirstEntry() 方法实现的比较简单:程序不断搜索“左子树”,直到找到最左边的“叶子节点”。该方法的实现代码如下:

  1. final Entry<K,V> getFirstEntry() {
  2. Entry<K,V> p = root;
  3. //不断搜索左子节点,直到p成为最左子树的叶子节点
  4. if (p != null)
  5. while (p.left != null)
  6. p = p.left;
  7. return p;
  8. }

successor(Entry<K, V> t) 方法实现的稍稍复杂一点,该方法实现了搜索“红黑树”中大于指定节点的最小节点,其代码如下:

  1. static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
  2. if (t == null)
  3. return null;
  4. //如果其右子树存在,搜索右子树中最小的节点(也就是右子树中最左的叶子节点)
  5. else if (t.right != null) {
  6. //先获取其右子节点
  7. Entry<K,V> p = t.right;
  8. //不断搜索左子节点,知道找到最左的叶子节点
  9. while (p.left != null)
  10. p = p.left;
  11. return p;
  12. //如果右子树不存在
  13. } else {
  14. Entry<K,V> p = t.parent;
  15. Entry<K,V> ch = t;
  16. //只要父节点存在,且ch是父节点的右节点,表明ch大于其父节点,循环一直继续,直到父节点为null,或者ch变成父节点的子节点————此时父节点大于被搜索节点
  17. while (p != null && ch == p.right) {
  18. ch = p;
  19. p = p.parent;
  20. }
  21. return p;
  22. }
  23. }

通过 TreeMap 提供的这个 successor(Entry<K, V> t) 静态方法,可以非常方便地、由小到大遍历 TreeMap 底层的“二叉树”。实际上,完全可以通过这个静态方法来由小到大地遍历 TreeMap 的所有元素。但 TreeMap 为了保持 Map 用法上的一致性,依然通过 Values 的 iterator() 方法来遍历 Map 中所有 value。Values 的 iterator() 方法则由 ValueIterator 提供实现,ValueIterator 类的代码非常简单,如下所示:

  1. final class ValueIterator extends PrivateEntryIterator<V> {
  2. ValueIterator(Entry<K,V> first) {
  3. super(first);
  4. }
  5. public V next() {
  6. //调用其父类的nextEntry()方法获取下一个Entry,再返回该Entry的value
  7. return nextEntry().value;
  8. }
  9. }

对于 ValueIterator 而言,它只是简单地调用了其抽象父类 PrivateEntryIterator 的方法来实现 next() 方法。该抽象父类的代码如下:

  1. abstract class PrivateEntryIterator<T> implements Iterator<T> {
  2. Entry<K,V> next;
  3. Entry<K,V> lastReturned;
  4. int expectedModCount;
  5. PrivateEntryIterator(Entry<K,V> first) {
  6. expectedModCount = modCount;
  7. lastReturned = null;
  8. next = first;
  9. }
  10. public final boolean hasNext() {
  11. return next != null;
  12. }
  13. final Entry<K,V> nextEntry() {
  14. Entry<K,V> e = next;
  15. if (e == null)
  16. throw new NoSuchElementException();
  17. if (modCount != expectedModCount)
  18. throw new ConcurrentModificationException();
  19. //获取e的下一个节点
  20. next = successor(e);
  21. lastReturned = e;
  22. return e;
  23. }
  24. final Entry<K,V> prevEntry() {
  25. Entry<K,V> e = next;
  26. if (e == null)
  27. throw new NoSuchElementException();
  28. if (modCount != expectedModCount)
  29. throw new ConcurrentModificationException();
  30. //获取e的上一个节点
  31. next = predecessor(e);
  32. lastReturned = e;
  33. return e;
  34. }
  35. public void remove() {
  36. if (lastReturned == null)
  37. throw new IllegalStateException();
  38. if (modCount != expectedModCount)
  39. throw new ConcurrentModificationException();
  40. // deleted entries are replaced by their successors
  41. if (lastReturned.left != null && lastReturned.right != null)
  42. next = lastReturned;
  43. //删除指定节点
  44. deleteEntry(lastReturned);
  45. expectedModCount = modCount;
  46. lastReturned = null;
  47. }
  48. }

上面 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 对组成的关联数组。

本文内容来自以下:

  1. 《疯狂Java 突破程序员基本功的16课》第三章 常见的 Java 集合的实现细节
  2. HashMap在Java1.7与1.8中的区别

评论

发表评论 点击刷新验证码

提示

该功能暂未开放