詳解Java集合框架LinkedHashSet與LinkedHashMap源碼剖析（圖）

整體介紹

如果你看過前面關於HashSet和HashMap，以及TreeSet和TreeMap#的講解，一定能夠想到本文將要講解的LinkedHashSet和LinkedHashMap其實也是一回事。 LinkedHashSet和LinkedHashMap在Java裡也有著相同的實現，前者只是對後者做了一層包裝，也就是說LinkedHashSet裡面有一個LinkedHashMap（適配器模式）。因此本文將重點分析LinkedHashMap。

LinkedHashMap實作了Map接口，即允許放入key為null的元素，也允許插入value為null的元素。從名字上可以看出該容器是linked list和HashMap的混合體，也就是說它同時滿足HashMap和linked list的某些特性。 可將LinkedHashMap視為採用linked list增強的HashMap。

事實上LinkedHashMap是HashMap的直接子類，二者唯一的差別是LinkedHashMap在HashMap的基礎上，採用雙向鍊錶（doubly-linked list）的形式將所有entry連接起來，這樣是為保證元素的迭代順序跟插入順序相同。上圖給了LinkedHashMap的結構圖，主體部分跟HashMap完全一樣，多了header指向雙向鍊錶的頭部（是啞元） ，該雙向鍊錶的迭代順序就是entry的插入順序。

除了可以保迭代歷順序，這種結構還有一個好處：迭代LinkedHashMap時不需要像HashMap那樣遍歷整個table ，而只需要直接遍歷header指向的雙向鍊錶即可，也就是說LinkedHashMap的迭代時間就只跟entry的個數相關，而跟table的大小無關。

有兩個參數可以影響LinkedHashMap的效能：初始容量（inital capacity）和負載係數（load factor）。初始容量指定了初始table的大小，負載係數用來指定自動擴容的臨界值。當entry的數量超過capacity*load_factor時，容器將自動擴容並重新哈希。對於插入元素較多的場​​景，將初始容量設大可以減少重新哈希的次數。

將物件放入到LinkedHashMap或LinkedHashSet中時，有兩個方法需要特別關心：hashCode()和equals()。 hashCode()方法決定了物件會被放到哪個bucket裡，當多個物件的雜湊值衝突時，equals()方法決定了這些物件是否是「同一個物件」。所以，如果要將自訂的物件放入LinkedHashMap或LinkedHashSet中，需要*@Override*hashCode()和equals() 方法。

透過以下方式可以得到一個跟源Map迭代順序一樣的LinkedHashMap：

void foo(Map m) {
    Map copy = new LinkedHashMap(m);

}

出於效能原因，LinkedHashMap是非同步的（not synchronized），如果需要在多執行緒環境使用，需要程式設計師手動同步；或透過如下方式將LinkedHashMap包裝成（wrapped）同步的：

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

方法剖析

get( )

get(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> key)方法根據指定的key值傳回對應的value。這個方法跟HashMap.get()方法的流程幾乎完全一樣，讀者可自行參考前文，這裡不再贅述。

put()

put(K key, V value)方法是將指定的key, value對加入map 裡。方法首先會對map做一次查找，看是否包含該元組，如果已經包含則直接傳回，查找過程類似於get()方法；如果沒有找到，則會透過addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

注意，這裡的插入有兩重意義：

1. #從table的角度看，新的entry需要插入對應的bucket裡，當有雜湊衝突時，採用頭插法將新的entry插入到衝突鍊錶的頭部。

2. 从header的角度看，新的entry需要插入到双向链表的尾部。

addEntry()代码如下：

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容，并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addBefore()的代码如下：

// LinkedHashMap.Entry.addBefor()，将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

上述代码只是简单修改相关entry的引用而已。

remove()

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应引用）。查找过程跟get()方法类似。

注意，这里的删除也有两重含义：

1. 从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。

2. 从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。

removeEntryForKey()对应的代码如下：

// LinkedHashMap.removeEntryForKey()，删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {

    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，因此LinkedHashSet的实现非常简单，这里不再赘述。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }

}

以上是詳解Java集合框架LinkedHashSet與LinkedHashMap源碼剖析（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！