深入源碼分析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()內部類的源碼:

// 內部類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對象，這樣就可以減低性能開銷。