LinkedHashMap繼承HashMap并實(shí)現(xiàn)了Map接口，同時(shí)具有可預(yù)測(cè)的迭代順序（按照插入順序排序）。它與HashMap的不同之處在于，維護(hù)了一條貫穿其全部Entry的雙向鏈表（因?yàn)轭~外維護(hù)了鏈表的關(guān)系，性能上要略差于HashMap，不過(guò)集合視圖的遍歷時(shí)間與元素?cái)?shù)量成正比，而HashMap是與buckets數(shù)組的長(zhǎng)度成正比的），可以認(rèn)為它是散列表與鏈表的結(jié)合。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;
/**
 * 迭代順序模式的標(biāo)記位，如果為true，采用訪問(wèn)排序，否則，采用插入順序
 * 默認(rèn)插入順序（構(gòu)造函數(shù)中默認(rèn)設(shè)置為false）
 */
final boolean accessOrder;
/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

LinkedHashMap的Entry實(shí)現(xiàn)也繼承自HashMap，只不過(guò)多了指向前后的兩個(gè)指針。

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

你也可以通過(guò)構(gòu)造函數(shù)來(lái)構(gòu)造一個(gè)迭代順序?yàn)樵L問(wèn)順序（accessOrder設(shè)為true）的LinkedHashMap，這個(gè)訪問(wèn)順序指的是按照最近被訪問(wèn)的Entry的順序進(jìn)行排序（從最近最少訪問(wèn)到最近最多訪問(wèn)）。基于這點(diǎn)可以簡(jiǎn)單實(shí)現(xiàn)一個(gè)采用LRU（Least Recently Used）策略的緩存。

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

LinkedHashMap復(fù)用了HashMap的大部分代碼，所以它的查找實(shí)現(xiàn)是非常簡(jiǎn)單的，唯一稍微復(fù)雜點(diǎn)的操作是保證訪問(wèn)順序。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

還記得這些afterNodeXXXX命名格式的函數(shù)嗎？我們之前已經(jīng)在HashMap中見(jiàn)識(shí)過(guò)了，這些函數(shù)在HashMap中只是一個(gè)空實(shí)現(xiàn)，是專門(mén)用來(lái)讓LinkedHashMap重寫(xiě)實(shí)現(xiàn)的hook函數(shù)。

   // 在HashMap.removeNode()的末尾處調(diào)用
   // 將e從LinkedHashMap的雙向鏈表中刪除
   void afterNodeRemoval(Node<K,V> e) { // unlink
       LinkedHashMap.Entry<K,V> p =
           (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
       p.before = p.after = null;
       if (b == null)
           head = a;
       else
           b.after = a;
       if (a == null)
           tail = b;
       else
           a.before = b;
   }
   // 在HashMap.putVal()的末尾處調(diào)用
   // evict是一個(gè)模式標(biāo)記，如果為false代表buckets數(shù)組處于創(chuàng)建模式
   // HashMap.put()函數(shù)對(duì)此標(biāo)記設(shè)置為true
   void afterNodeInsertion(boolean evict) { // possibly remove eldest
       LinkedHashMap.Entry<K,V> first;
       // LinkedHashMap.removeEldestEntry()永遠(yuǎn)返回false
       // 避免了最年長(zhǎng)元素被刪除的可能（就像一個(gè)普通的Map一樣）
       if (evict && (first = head) != null && removeEldestEntry(first)) {
           K key = first.key;
           removeNode(hash(key), key, null, false, true);
       }
   }
   // HashMap.get()沒(méi)有調(diào)用此函數(shù)，所以LinkedHashMap重寫(xiě)了get()
// get()與put()都會(huì)調(diào)用afterNodeAccess()來(lái)保證訪問(wèn)順序
   // 將e移動(dòng)到tail，代表最近訪問(wèn)到的節(jié)點(diǎn)
   void afterNodeAccess(Node<K,V> e) { // move node to last
       LinkedHashMap.Entry<K,V> last;
       if (accessOrder && (last = tail) != e) {
           LinkedHashMap.Entry<K,V> p =
               (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
           p.after = null;
           if (b == null)
               head = a;
           else
               b.after = a;
           if (a != null)
               a.before = b;
           else
               last = b;
           if (last == null)
               head = p;
           else {
               p.before = last;
               last.after = p;
           }
           tail = p;
           ++modCount;
       }
   }

注意removeEldestEntry()默認(rèn)永遠(yuǎn)返回false，這時(shí)它的行為與普通的Map無(wú)異。如果你把removeEldestEntry()重寫(xiě)為永遠(yuǎn)返回true，那么就有可能使LinkedHashMap處于一個(gè)永遠(yuǎn)為空的狀態(tài)（每次put()或者putAll()都會(huì)刪除頭節(jié)點(diǎn)）。

一個(gè)比較合理的實(shí)現(xiàn)示例：

protected boolean removeEldestEntry(Map.Entry eldest){
    return size() > MAX_SIZE;
}

LinkedHashMap重寫(xiě)了newNode()等函數(shù)，以初始化或連接節(jié)點(diǎn)到它內(nèi)部的雙向鏈表：

// 鏈接節(jié)點(diǎn)p到鏈表尾部（或初始化鏈表）
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
// 用dst替換掉src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                           LinkedHashMap.Entry<K,V> dst) {
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    // src是頭節(jié)點(diǎn)
    if (b == null)
        head = dst;
    else
        b.after = dst;
    // src是尾節(jié)點(diǎn)
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}   
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
    linkNodeLast(p);
    return p;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

遍歷LinkedHashMap所需要的時(shí)間與Entry數(shù)量成正比，這是因?yàn)榈�代器直接�?duì)雙向鏈表進(jìn)行迭代，而鏈表中只會(huì)含有Entry節(jié)點(diǎn)。迭代的順序是從頭節(jié)點(diǎn)開(kāi)始一直到尾節(jié)點(diǎn)，插入操作會(huì)將新節(jié)點(diǎn)鏈接到尾部，所以保證了插入順序，而訪問(wèn)順序會(huì)通過(guò)afterNodeAccess()來(lái)保證，訪問(wèn)次數(shù)越多的節(jié)點(diǎn)越接近尾部。

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }
    public final boolean hasNext() {
        return next != null;
    }
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;
        return e;
    }
    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}
final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

 

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。