Map對映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(...));

LinkedHashMap

get()

get(Object 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。

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

從table的角度看，新的entry需要插入到對應的bucket裡，當有雜湊衝突時，採用頭插法將新的entry插入到衝突連結串列的頭部。

從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()方法類似。

注意，這裡的刪除也有兩重含義:

從table的角度看，需要將該entry從對應的bucket裡刪除，如果對應的衝突連結串列不空，需要修改衝突連結串列的相應參照。

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

LinkedHashMap經典用法

LinkedHashMap除了可以保證迭代順序外࿰c;還有一個非常有用的用法: 可以輕鬆實現一個採用了FIFO替換策略的快取。具體說來，LinkedHashMap有一個子類方法

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

該方法的作用是告訴Map是否要刪除“最老”的Entry，所謂最老就是當前Map中最早插入的Entry，如果該方法返回true，最老的那個元素就會被刪除。在每次插入新元素的之後LinkedHashMap會自動詢問removeEldestEntry()是否要刪除最老的元素。這樣只需要在子類中過載該方法，當元素個數超過一定數量時讓removeEldestEntry()返回true，就能夠實現一個固定大小的FIFO策略的快取。範例程式碼如下:

/** 一個固定大小的FIFO替換策略的快取 */
class FIFOCache<K, V> extends LinkedHashMap<K, V>{
    private final int cacheSize;
    public FIFOCache(int cacheSize){
        this.cacheSize = cacheSize;
    }
    // 當Entry個數超過cacheSize時，刪除最老的Entry
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
       return size() > cacheSize;
    }
}

以上就是Map對映LinkedHashSet與LinkedHashMap範例解析的詳細內容，更多關於Map對映LinkedHashSet與LinkedHashMap的資料請關注it145.com其它相關文章！