Map 幾個常用方法的比較

一、containsValue(value)的差別

在 Map 體系中有提供判斷某個值是否存在的方法 — containsValue(value)，下面分别是 HashMap 和 LinkedHashMap 的兩個方法。

1、HashMap#containsValue(value)

public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();
    HashMapEntry[] tab = table;
    for (int i = ; i < tab.length ; i++)
        for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}
           

2、LinkedHashMap#containsValue(value)

從下面的源碼可以知道，LinkedHashMap#containsValue 方法跟 HashMap 的實作還有點差別的，它周遊的是雙向連結清單，這樣的效率就要 HashMap 周遊 table 數組，然後還有對 table 數組的每一個元素對應的連結清單（也就是整個 hash 表）進行周遊要高。因為 HashMap 的實作是雙重 for 循環判斷的，而雙向連結清單隻需要一個 for 即可完成判斷。

hash表是由數組+單向連結清單組成，而由于使用hash算法，可能會導緻散列不均勻，甚至數組的有些項是沒有元素的（沒有hash出對應的散列值），而LinkedHashMap的雙向連結清單呢，是不存在空項的，是以LinkedHashMap的containsValue比HashMap的containsValue效率要好一些。

public boolean containsValue(Object value) {
    // Overridden to take advantage of faster iterator
    if (value==null) {
        for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
            if (e.value==null)
                return true;
    } else {
        for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
            if (value.equals(e.value))
                return true;
    }
    return false;
}
           

二、keySet() 和 entrySet 哪個周遊比較快？

1.HashMap#keySet()

示例代碼

Set<String> keys = map.keySet();
Iterator<String> iter = keys.iterator();
while(iter.hasNext()){
    String key = iter.next();
    String value = map.get(key);
    System.out.println("key = "+key+";value = "+value);
}
           

源碼分析

周遊 KeySet 集合最終會調用 iterator(） 擷取疊代器對象，然後周遊疊代器 Iterator 對象的 next() 方法擷取到每一個 key 值。

public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
}

//周遊 KeySet 集合核心方法就是 iterator() 方法了
private final class KeySet extends AbstractSet<K> {

    public Iterator<K> iterator() {
        //周遊的核心方法
        return newKeyIterator();
    }
    ...
}


Iterator<K> newKeyIterator()   {
    return new KeyIterator();
}

private final class KeyIterator extends HashIterator<K> {
    public K next() {
        //周遊代碼都會執行 next() 擷取到 Map.Entry 對象
        //在這裡可以看到它是先擷取 Map.Entry 然後在擷取 Entry 中對應的 key ，因為擷取 key 集合之後，還要周遊 key 集合擷取到對應的 value 值，多了一步循環判斷的操作，是以效率要比直接擷取 EntrySet 低下。
        return nextEntry().getKey();
    }
}
           

2.HashMap#entrySet()

示例代碼：

for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println("key:" + entry.getKey() + ";value:" + entry.getValue());
}
           

源碼分析

entrySet 方法擷取到的存儲 Map.Entry 的 Set 集合，在方法 next() 中擷取到的 Map.Entry 對象，那麼相對于 keySet 先擷取 key 集合然後再周遊擷取 value 的方法， entrySet 一次性就擷取 Entry 對象這種方式的效率會更好一些。

public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            //核心方法
            return newEntryIterator();
        }
}

Iterator<Map.Entry<K,V>> newEntryIterator()   {
    return new EntryIterator();
}

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}

//最後擷取的就是一個個 Map.Entry 對象
final Entry<K,V> nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    HashMapEntry<K,V> e = next;
    if (e == null)
        throw new NoSuchElementException();
    if ((next = e.next) == null) {
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
            ;
    }
    current = e;
    return e;
}
           

三、remove /replace /put元素的效率

這裡隻分析 remove 方法

1、LinkedHashMap#remove(key)

因為 LinkedHashMap 沒有實作 remove 方法是以去父類 Hashmap 檢視。根據 key 移除某個對象，我們參考 LinkedHashMap 是如何實作的，因為 LinkedHashMap 的移除操作是基于 HashMap 實作，隻要弄懂了 LinkedHashMap 的移除操作就明白了 HashMap 的移除操作了。

對于 HashMap 結構而言，其内部都是有數組+連結清單組成，每一個存儲的機關但是一個個的 Entry 對象，但是 LinkedHashMap 的 Entry 還添加了 after 和 before 屬性，表示前後兩個 Entry ，這種方式構成了雙向連結清單，也就是說在移除操作過程中處理要移除 hash 表的 Entry 對象，還要移除 雙向連結清單的 Entry 對象，這就說明了 LinedHashMap 在移除資料方面效率比 HashMap 要低。

public V remove(Object key) {
    //根據 key 移除哈希表 table 對應的 Entry 對象
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.getValue());
}

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == ) {
        return null;
    }
    int hash = (key == null) ?  : sun.misc.Hashing.singleWordWangJenkinsHash(key);
    int i = indexFor(hash, table.length);
    HashMapEntry<K,V> prev = table[i];
    HashMapEntry<K,V> e = prev;
    while (e != null) {
        HashMapEntry<K,V> next = e.next;
        Object k;
        //找到需要移除的 Entry 對象了，然後從哈希表中移除這個 Entry 對象。
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            //找到需要移除的 Entry 對象了。前面已經從哈希表移除了，但是雙向連結清單中維護這該對象。目前的 Entry 對象實際就是 LinkedHashMap.LinkedHashMapEntry 對象。如果目前對象是 HashMap 的話，recoreRemoval内部是一個空實作。
            //是以會調用 LinkedHashMapEntry.recoreRemoval(this)方法
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
    return e;
}

//LinkedHashMapEntry 的源碼
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {

    //recordRemoval() 被調用之後 remove()方法被調用
    private void remove() {
        before.after = after;
        after.before = before;
    }

    ...
    //當 HashMap 的 Entry 被移除了之後，該方法會被調用
    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}