深入源码分析Map与List的关系

前面通过观察源码分析了Map和Set的相似之处，当把Map中的key-value对当成单独的集合元素来等待时，Map和Set也就统一起来了。接下来依然把Map的key-value对分开来对待，从另外一个角度来看，其实我们也可以把Map和List统一起来。Map的values（）方法:Map集合是一个关联数值，它包含两组值: 一组是所有key组成的集合，key值不允许重复，而且Map不会保存key加入的顺序。因此这些key可以组成一个Set集合。另外一组是value组成的集合，因为Map集合的value完全可以重复，所以这些value可以组成一个List集合。我们知道Map集合的keySet（）方法可以返回一个Set集合。但Map的values（）方法并未返回一个List集合:

HashMap<String , Double> scores = new HashMap<String , Double>（）;scores.put（"java" , 89.0）;scores.put（"Android" , 83.0）;scores.put（"Spring" , 80.0）;System.out.println（scores.values（））;System.out.println（scores.values（）.getClass（））;TreeMap<String , Double> health = new TreeMap<String , Double>（）;health.put（"Linux" , 173.0）;health.put（"Git" , 71.2）;System.out.println（health.values（））;System.out.println（health.values（）.getClass（））;

输出:[ 89.0,83.0,80.0 ]class java.util.HashMap$Values[ 71.2,173.0 ]class java.utill.TreeMap$Values可以看出，HashMap和TreeMap两个集合的values（）方法返回值确实是包含Map中所有value的集合。但他们不是正在的List对象，而分别是HashMap$Value对象和TreeMap$Value对象。观看values（）方法源码:

/*** 返回此映射所包含的值的 Collection 视图。* 该 collection 受映射的支持，所以对映射的更改将反映在该 collection 中，* 反之亦然。如果在对 collection 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），* 则迭代结果是不确定的。该 collection 支持元素的移除，* 通过 Iterator.remove、Collection.remove、removeAll、retainAll 和 clear 操作* 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。*/public Collection<V> values（） {Collection<V> vs = values;return （vs ！= null ？ vs : （values = new Values（）））;}

当程序第一次调用这两个Map对象的values（）方法时，它们会新建一个Values（）对象，并将Values（）对象赋值给values实例变量。当程序下次调用values（）方法时，将直接以values实例变量作为返回值。观察HashMap的Values（）内部类的源码:

// 内部类Valuesprivate final class Values extends AbstractCollection<V> {public Iterator<V> iterator（） {//返回newValueIterator（）方法的返回值return newValueIterator（）;}public int size（） {//返回外部类size实例变量的返回值return size;}public boolean contains（Object o） {//返回外部类实例的 containsValue（o）的返回值作为本方法的返回值return containsValue（o）;}public void clear（） {//调用其外部类实例的clear（）方法HashMap.this.clear（）;}}

注意Values集合类，它虽然继承了AbstractCollection抽象类，但它并非是一个真正的Collection集合。因为它并未实现add（Object e）方法，而且该抽象类也没有实现add（Object e）方法，也就是说，这个Values集合对象并没有真正盛称任何java对象。Values内部类的inerator（）方法返回一个ValueIterator（）类。public final Iterator<V> iterator（） { return new ValueIterator（）; }ValueIterator类的实现非常简单，它是通过调用HashMap的nextNode（）方法来实现的。

final class ValueIterator extends HashIteratorimplements Iterator<V> {public final V next（） { return nextNode（）.value; }}

现在我们可以发现，HashMap的values（）方法表明上返回了一个Values集合对象。但这个集合对象并不能添加元素。它的主要功能是用于遍历HashMap里的所以Value，而遍历Value则主要依赖于HashIterator的nextNode（）方法来实现。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（）对象

 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（） {TreeMap.this.clear（）;}}

其中执行的successor（Entry

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;}}

归纳后我们可以发现:不管是HashMap和TreeMap，它们的values（）方法都可以返回其所有value组成的Collection集合–按照通俗的理解，这个Collection集合应该是一个List集合。因为Map的多个Value允许重复。但实际上，HashMap，TreeMap的values（）方法的实现更巧妙。这两个Map对象的values（）方法返回的是一个不存储元素的Collection集合，当程序遍历该Collection时，实际就是Map对象的value。HashMap和TreeMap并没有把value重新组合成一个包含元素的Collection对象，这样就可以减低性能开销。本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-10/1363633.htm<！-- Baidu Button BEGIN -->