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

偏执的太偏执、 2022-08-21 09:42 5阅读 0赞

前面通过观察源码分析了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()内部类的源码:

// 内部类Values  
        private 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 HashIterator  implements 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对象，这样就可以减低性能开销。