總體介紹

如果你已看過(guò)前面關(guān)于HashSet和HashMap，以及TreeSet和TreeMap的講解，一定能夠想到本文將要講解的LinkedHashSet和LinkedHashMap其實(shí)也是一回事。LinkedHashSet和LinkedHashMap在Java里也有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝，也就是說(shuō)LinkedHashSet里面有一個(gè)LinkedHashMap(適配器模式)。因此本文將重點(diǎn)分析LinkedHashMap。

LinkedHashMap實(shí)現(xiàn)了Map接口，即允許放入key為null的元素，也允許插入value為null的元素。從名字上可以看出該容器是linked list和HashMap的混合體，也就是說(shuō)它同時(shí)滿足HashMap和linked list的某些特性。可將LinkedHashMap看作采用linked list增強(qiáng)的HashMap。

事實(shí)上LinkedHashMap是HashMap的直接子類(lèi)，二者唯一的區(qū)別是LinkedHashMap在HashMap的基礎(chǔ)上，采用雙向鏈表(doubly-linked list)的形式將所有entry連接起來(lái)，這樣是為保證元素的迭代順序跟插入順序相同。上圖給出了LinkedHashMap的結(jié)構(gòu)圖，主體部分跟HashMap完全一樣，多了header指向雙向鏈表的頭部(是一個(gè)啞元)，該雙向鏈表的迭代順序就是entry的插入順序。

除了可以保迭代歷順序，這種結(jié)構(gòu)還有一個(gè)好處 : 迭代LinkedHashMap時(shí)不需要像HashMap那樣遍歷整個(gè)table，而只需要直接遍歷header指向的雙向鏈表即可，也就是說(shuō)LinkedHashMap的迭代時(shí)間就只跟entry的個(gè)數(shù)相關(guān)，而跟table的大小無(wú)關(guān)。

有兩個(gè)參數(shù)可以影響LinkedHashMap的性能: 初始容量(inital capacity)和負(fù)載系數(shù)(load factor)。初始容量指定了初始table的大小，負(fù)載系數(shù)用來(lái)指定自動(dòng)擴(kuò)容的臨界值。當(dāng)entry的數(shù)量超過(guò)capacity*load_factor時(shí)，容器將自動(dòng)擴(kuò)容并重新哈希。對(duì)于插入元素較多的場(chǎng)景，將初始容量設(shè)大可以減少重新哈希的次數(shù)。

將對(duì)象放入到LinkedHashMap或LinkedHashSet中時(shí)，有兩個(gè)方法需要特別關(guān)心: hashCode()和equals()。hashCode()方法決定了對(duì)象會(huì)被放到哪個(gè)bucket里，當(dāng)多個(gè)對(duì)象的哈希值沖突時(shí)，equals()方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”。所以，如果要將自定義的對(duì)象放入到LinkedHashMap或LinkedHashSet中，需要@Override hashCode()和equals()方法。

通過(guò)如下方式可以得到一個(gè)跟源Map 迭代順序一樣的LinkedHashMap:

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

出于性能原因，LinkedHashMap是非同步的(not synchronized)，如果需要在多線程環(huán)境使用，需要程序員手動(dòng)同步；或者通過(guò)如下方式將LinkedHashMap包裝成(wrapped)同步的:

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

LinkedHashMap

get()

get(Object key)方法根據(jù)指定的key值返回對(duì)應(yīng)的value。該方法跟HashMap.get()方法的流程幾乎完全一樣

put()

put(K key, V value)方法是將指定的key, value對(duì)添加到map里。
該方法首先會(huì)對(duì)map做一次查找，看是否包含該元組，如果已經(jīng)包含則直接返回，查找過(guò)程類(lèi)似于get()方法；如果沒(méi)有找到，則會(huì)通過(guò)addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

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

從table的角度看，新的entry需要插入到對(duì)應(yīng)的bucket里，當(dāng)有哈希沖突時(shí)，采用頭插法將新的entry插入到?jīng)_突鏈表的頭部。

從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);// 自動(dòng)擴(kuò)容，并重新哈希
        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就成為雙向鏈表中的最后一個(gè)元素。addBefore()的源碼如下:

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

上述代碼只是簡(jiǎn)單修改相關(guān)entry的引用而已。

remove()

remove(Object key)的作用是刪除key值對(duì)應(yīng)的entry，該方法的具體邏輯是在removeEntryForKey(Object key)里實(shí)現(xiàn)的。

removeEntryForKey()方法會(huì)首先找到key值對(duì)應(yīng)的entry，然后刪除該entry(修改鏈表的相應(yīng)引用)。查找過(guò)程跟get()方法類(lèi)似。

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

從table的角度看，需要將該entry從對(duì)應(yīng)的bucket里刪除，如果對(duì)應(yīng)的沖突鏈表不空，需要修改沖突鏈表的相應(yīng)引用。

從header的角度來(lái)看，需要將該entry從雙向鏈表中刪除，同時(shí)修改鏈表中前面以及后面元素的相應(yīng)引用。

removeEntryForKey()對(duì)應(yīng)的源碼如下: 

// LinkedHashMap.removeEntryForKey()，刪除key值對(duì)應(yīng)的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];// 得到?jīng)_突鏈表
    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)))) {// 找到要?jiǎng)h除的entry
            modCount++; size--;
            // 1. 將e從對(duì)應(yīng)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

前面已經(jīng)說(shuō)過(guò)LinkedHashSet是對(duì)LinkedHashMap的簡(jiǎn)單包裝，對(duì)LinkedHashSet的函數(shù)調(diào)用都會(huì)轉(zhuǎn)換成合適的LinkedHashMap方法，因此LinkedHashSet的實(shí)現(xiàn)非常簡(jiǎn)單，這里不再贅述。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ......
    // LinkedHashSet里面有一個(gè)LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
	......
    public boolean add(E e) {
        //簡(jiǎn)單的方法轉(zhuǎn)換
        return map.put(e, PRESENT)==null;
    }
    ......
}

LinkedHashMap經(jīng)典用法

LinkedHashMap除了可以保證迭代順序外?c;還有一個(gè)非常有用的用法: 可以輕松實(shí)現(xiàn)一個(gè)采用了FIFO替換策略的緩存。具體說(shuō)來(lái)，LinkedHashMap有一個(gè)子類(lèi)方法

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

該方法的作用是告訴Map是否要?jiǎng)h除“最老”的Entry，所謂最老就是當(dāng)前Map中最早插入的Entry，如果該方法返回true，最老的那個(gè)元素就會(huì)被刪除。在每次插入新元素的之后LinkedHashMap會(huì)自動(dòng)詢(xún)問(wèn)removeEldestEntry()是否要?jiǎng)h除最老的元素。這樣只需要在子類(lèi)中重載該方法，當(dāng)元素個(gè)數(shù)超過(guò)一定數(shù)量時(shí)讓removeEldestEntry()返回true，就能夠?qū)崿F(xiàn)一個(gè)固定大小的FIFO策略的緩存。示例代碼如下:

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

以上就是Map映射LinkedHashSet與LinkedHashMap示例解析的詳細(xì)內(nèi)容，更多關(guān)于Map映射LinkedHashSet與LinkedHashMap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論