歡迎光臨
每天分享高質量文章

Map 大家族的那點事兒 ( 6 ) :LinkedHashMap

(點選上方公眾號,可快速關註)


來源:SylvanasSun’s Blog ,

sylvanassun.github.io/2018/03/16/2018-03-16-map_family/

LinkedHashMap繼承HashMap並實現了Map介面,同時具有可預測的迭代順序(按照插入順序排序)。它與HashMap的不同之處在於,維護了一條貫穿其全部Entry的雙向連結串列(因為額外維護了連結串列的關係,效能上要略差於HashMap,不過集合檢視的遍歷時間與元素數量成正比,而HashMap是與buckets陣列的長度成正比的),可以認為它是散串列與連結串列的結合。

/**

 * The head (eldest) of the doubly linked list.

 */

transient LinkedHashMap.Entry head;

/**

 * The tail (youngest) of the doubly linked list.

 */

transient LinkedHashMap.Entry tail;

/**

 * 迭代順序樣式的標記位,如果為true,採用訪問排序,否則,採用插入順序

 * 預設插入順序(建構式中預設設定為false)

 */

final boolean accessOrder;

/**

 * Constructs an empty insertion-ordered LinkedHashMap instance

 * with the default initial capacity (16) and load factor (0.75).

 */

public LinkedHashMap() {

    super();

    accessOrder = false;

}

LinkedHashMap的Entry實現也繼承自HashMap,只不過多了指向前後的兩個指標。

/**

 * HashMap.Node subclass for normal LinkedHashMap entries.

 */

static class Entry extends HashMap.Node {

    Entry before, after;

    Entry(int hash, K key, V value, Node next) {

        super(hash, key, value, next);

    }

}

你也可以透過建構式來構造一個迭代順序為訪問順序(accessOrder設為true)的LinkedHashMap,這個訪問順序指的是按照最近被訪問的Entry的順序進行排序(從最近最少訪問到最近最多訪問)。基於這點可以簡單實現一個採用LRU(Least Recently Used)策略的快取。

public LinkedHashMap(int initialCapacity,

                     float loadFactor,

                     boolean accessOrder) {

    super(initialCapacity, loadFactor);

    this.accessOrder = accessOrder;

}

LinkedHashMap復用了HashMap的大部分程式碼,所以它的查詢實現是非常簡單的,唯一稍微複雜點的操作是保證訪問順序。

public V get(Object key) {

    Node e;

    if ((e = getNode(hash(key), key)) == null)

        return null;

    if (accessOrder)

        afterNodeAccess(e);

    return e.value;

}

還記得這些afterNodeXXXX命名格式的函式嗎?我們之前已經在HashMap中見識過了,這些函式在HashMap中只是一個空實現,是專門用來讓LinkedHashMap重寫實現的hook函式。

   // 在HashMap.removeNode()的末尾處呼叫

   // 將e從LinkedHashMap的雙向連結串列中刪除

   void afterNodeRemoval(Node e) { // unlink

       LinkedHashMap.Entry p =

           (LinkedHashMap.Entry)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()的末尾處呼叫

   // evict是一個樣式標記,如果為false代表buckets陣列處於建立樣式

   // HashMap.put()函式對此標記設定為true

   void afterNodeInsertion(boolean evict) { // possibly remove eldest

       LinkedHashMap.Entry first;

       // LinkedHashMap.removeEldestEntry()永遠傳回false

       // 避免了最年長元素被刪除的可能(就像一個普通的Map一樣)

       if (evict && (first = head) != null && removeEldestEntry(first)) {

           K key = first.key;

           removeNode(hash(key), key, null, false, true);

       }

   }

   // HashMap.get()沒有呼叫此函式,所以LinkedHashMap重寫了get()

// get()與put()都會呼叫afterNodeAccess()來保證訪問順序

   // 將e移動到tail,代表最近訪問到的節點

   void afterNodeAccess(Node e) { // move node to last

       LinkedHashMap.Entry last;

       if (accessOrder && (last = tail) != e) {

           LinkedHashMap.Entry p =

               (LinkedHashMap.Entry)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()預設永遠傳回false,這時它的行為與普通的Map無異。如果你把removeEldestEntry()重寫為永遠傳回true,那麼就有可能使LinkedHashMap處於一個永遠為空的狀態(每次put()或者putAll()都會刪除頭節點)。

一個比較合理的實現示例:

protected boolean removeEldestEntry(Map.Entry eldest){

    return size() > MAX_SIZE;

}

LinkedHashMap重寫了newNode()等函式,以初始化或連線節點到它內部的雙向連結串列:

// 連結節點p到連結串列尾部(或初始化連結串列)

private void linkNodeLast(LinkedHashMap.Entry p) {

    LinkedHashMap.Entry last = tail;

    tail = p;

    if (last == null)

        head = p;

    else {

        p.before = last;

        last.after = p;

    }

}

// 用dst替換掉src

private void transferLinks(LinkedHashMap.Entry src,

                           LinkedHashMap.Entry dst) {

    LinkedHashMap.Entry b = dst.before = src.before;

    LinkedHashMap.Entry a = dst.after = src.after;

    // src是頭節點

    if (b == null)

        head = dst;

    else

        b.after = dst;

    // src是尾節點

    if (a == null)

        tail = dst;

    else

        a.before = dst;

}   

Node newNode(int hash, K key, V value, Node e) {

    LinkedHashMap.Entry p =

        new LinkedHashMap.Entry(hash, key, value, e);

    linkNodeLast(p);

    return p;

}

Node replacementNode(Node p, Node next) {

    LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;

    LinkedHashMap.Entry t =

        new LinkedHashMap.Entry(q.hash, q.key, q.value, next);

    transferLinks(q, t);

    return t;

}

TreeNode newTreeNode(int hash, K key, V value, Node next) {

    TreeNode p = new TreeNode(hash, key, value, next);

    linkNodeLast(p);

    return p;

}

TreeNode replacementTreeNode(Node p, Node next) {

    LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;

    TreeNode t = new TreeNode(q.hash, q.key, q.value, next);

    transferLinks(q, t);

    return t;

}

遍歷LinkedHashMap所需要的時間與Entry數量成正比,這是因為迭代器直接對雙向連結串列進行迭代,而連結串列中只會含有Entry節點。迭代的順序是從頭節點開始一直到尾節點,插入操作會將新節點連結到尾部,所以保證了插入順序,而訪問順序會透過afterNodeAccess()來保證,訪問次數越多的節點越接近尾部。

abstract class LinkedHashIterator {

    LinkedHashMap.Entry next;

    LinkedHashMap.Entry current;

    int expectedModCount;

    LinkedHashIterator() {

        next = head;

        expectedModCount = modCount;

        current = null;

    }

    public final boolean hasNext() {

        return next != null;

    }

    final LinkedHashMap.Entry nextNode() {

        LinkedHashMap.Entry 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 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 {

    public final K next() { return nextNode().getKey(); }

}

final class LinkedValueIterator extends LinkedHashIterator

    implements Iterator {

    public final V next() { return nextNode().value; }

}

final class LinkedEntryIterator extends LinkedHashIterator

    implements Iterator> {

    public final Map.Entry next() { return nextNode(); }

}

系列


【關於投稿】


如果大家有原創好文投稿,請直接給公號傳送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章連結

② 示例:
【投稿】《不要自稱是程式員,我十多年的 IT 職場總結》:http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~



看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,提升Java技能

贊(0)

分享創造快樂