Java 容器源碼分析之 LinkedHashMap

同 HashMap 一樣，LinkedHashMap 也是對 Map 接口的一種基于連結清單和哈希表的實作。實際上， LinkedHashMap 是 HashMap 的子類，其擴充了 HashMap 增加了雙向連結清單的實作。相較于 HashMap 的疊代器中混亂的通路順序，LinkedHashMap 可以提供可以預測的疊代通路，即按照插入序 (insertion-order) 或通路序 (access-order) 來對哈希表中的元素進行疊代。

1
2
3

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

從類聲明中可以看到，LinkedHashMap 确實是繼承了 HashMap，因而 HashMap 中的一些基本操作，如哈希計算、擴容、查找等，在 LinkedHashMap 中都和父類 HashMap 是一緻的。

但是，和 HashMap 有所差別的是，LinkedHashMap 支援按插入序 (insertion-order) 或通路序 (access-order) 來通路其中的元素。所謂插入順序，就是 Entry 被添加到 Map 中的順序，更新一個 Key 關聯的 Value 并不會對插入順序造成影響；而通路順序則是對所有 Entry 按照最近通路 (least-recently) 到最遠通路 (most-recently) 進行排序，讀寫都會影響到通路順序，但是對疊代器 (entrySet(), keySet(), values()) 的通路不會影響到通路順序。通路序的特性使得可以很容易通過 LinkedHashMap 來實作一個 LRU(least-recently-used) Cache，後面會給出一個簡單的例子。

之是以 LinkedHashMap 能夠支援插入序或通路序的周遊，是因為 LinkedHashMap 在 HashMap 的基礎上增加了雙向連結清單的實作，下面會結合 JDK 8 的源碼進行簡要的分析。

底層結構

LinkedHashMap 是 HashMap 的子類，因而 HashMap 中的成員在 LinkedHashMap 中也存在，如底層的 table 數組等，這裡就不再說明了。我們重點關注一下 LinkedHashMap 中節點發生的變化。

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
//LinkedHashMap.Entey 繼承自 HashMap.Node， 
//而 HashMap.TreeNode 又繼承了 LinkedHashMap.Entey 
static class Entry<K,V> extends HashMap.Node<K,V> {
    //在父類的基礎上增加了before 和 after
    //父類中存在 next
    //雙向連結清單的連接配接通過before 和 after，哈希表中所有的元素可看作一個雙向連結清單
    //桶内單向連結清單的連接配接通過 next
    Entry<K,V> before, after;
    //構造方法
    Entry(int hash, K key, V value, Node<K,V> next) {
        //父類構造方法
        super(hash, key, value, next);
    }
}

private static final long serialVersionUID = 3801124242820219131L;

/**
 * The head (eldest) of the doubly linked list.
 */
//head成員為雙向連結清單的頭
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
//tail成員為雙向連結清單的尾
transient LinkedHashMap.Entry<K,V> tail;

/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
//疊代順序， true 使用最近被通路的順序， false為插入順序
//the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)， well-suited to building LRU caches
final boolean accessOrder;

為了實作雙向連結清單，LinkedHashMap 的節點在父類的基礎上增加了 before/after 引用，并且使用 head 和 tail 分别儲存雙向連結清單的頭和尾。同時，增加了一個辨別來儲存 LinkedHashMap 的疊代順序是插入序還是通路序。

由于父類 HashMap 的節點中存在 next 引用，可以将每個桶中的元素都當作一個單連結清單看待；LinkedHashMap 的每個桶中當然也保留了這個單連結清單關系，不過這個關系由父類進行管理，LinkedHashMap 中隻會對雙向連結清單的關系進行管理。LinkedHashMap 中所有的元素都被串聯在一個雙向連結清單中。

雙向連結清單

為了簡化對雙向連結清單的操作，LinkedHashMap 中提供了 linkNodeLast 和 transferLinks 方法，分别如下：

// link at the end of list
// 将新節點 p 連結到雙向連結清單的末尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        //為空，則為頭節點
        head = p;
    else {
        //修改before 和 after的指向
        p.before = last;
        last.after = p;
    }
}

// apply src's links to dst
// 将src的連結應用到dst中，就是用dst替換src在雙向連結清單中的位置
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                           LinkedHashMap.Entry<K,V> dst) {
    //修改dst的前驅和後繼指向
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    //将雙向連結清單中原來指向src的連結改為指向dst
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

LinkedHashMap 重寫了父類建立節點的方法，在建立節點之後調用 linkNodeLast 方法将新添加的節點連結到雙向連結清單的末尾：

//覆寫父類方法
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;
}

//覆寫父類方法
//建立TreeNode
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;
}

我們知道，HashMap 中單個桶中的元素可能會在單連結清單和紅黑樹之間進行轉換，LinkedHashMap 中當然也是一樣，不過在轉換時還要調用 transferLinks 來改變雙向連結清單中的連接配接關系：

//覆寫父類方法
// For conversion from TreeNodes to plain nodes
// 将節點由 TreeNode 轉換為 普通節點
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; //TreeNode
    //根據TreeNode的資訊建立新的普通節點
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    //将雙向連結清單中的TreeNode替換為新的普通節點
    transferLinks(q, t);
    return t;
}

//覆寫父類方法
// For treeifyBin
// 将節點由普通節點轉換為TreeNode
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 中，所有的 Entry 都被串聯在一個雙向連結清單中。從上一節的代碼中可以看到，每次在建立一個節點時都會将建立的節點連結到雙向連結清單的末尾。這樣從雙向連結清單的尾部向頭部周遊就可以保證插入順序了，頭部節點是最早添加的節點，而尾部節點則是最近添加的節點。那麼，通路順序要怎麼實作呢？

之前我們在分析 HashMap 的源碼的時候，在添加及更新、查找、删除等操作中可以看到 afterNodeAccess、afterNodeInsertion、afterNodeRemoval 等幾個方法的調用，不過在 HashMap 中這幾個方法中沒有任何操作。實際上，這幾個方法就是供 LinkedHashMap 的重寫的，我們不妨看一下在 HashMap 中這幾個方法的聲明：

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

在 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;
}

//插入節點的回調函數
//構造函數中調用，evict為false
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //first是頭元素，也是最老的元素
    //在插入序中，就是最先插入的元素
    //在通路序中，就是最遠被通路的元素
    //這裡removeEldestEntry(first)始終傳回true，即不删除最老的元素
    //如果是一個容量固定的cache，可調整removeEldestEntry(first)的實作
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        //不是構造方法中
        //頭元素不為空
        //要删除最老的元素
        //在LinkedHashMap的實作中，不會進入這裡
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

//通路節點的回調函數
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //如果是通路序，且目前節點并不是尾節點
    //将該節點置為雙向連結清單的尾部
    if (accessOrder && (last = tail) != e) {
        //p 目前節點， b 前驅結點， a 後繼結點
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null; //設為尾節點，則沒有後繼
        if (b == null)
            head = a; //p是頭節點，調整後其後繼結點變為頭節點
        else
            b.after = a;//p不是頭節點，前驅和後繼結點相連
        if (a != null)
            a.before = b;
        else
            last = b;//應該不會出現這種情況，p是尾節點
        if (last == null)
            head = p;
        else {
            //将p置于尾節點之後
            p.before = last;
            last.after = p;
        }
        tail = p;//調整tail指向
        ++modCount;//結構性改變
    }
}

在插入節點、删除節點和通路節點後會調用相應的回調函數。可以看到，在

afterNodeAccess

方法中，如果該 LinkedHashMap 是通路序，且目前通路的節點不是尾部節點，則該節點會被置為雙連結清單的尾節點。即，在通路序下，最近通路的節點會是尾節點，頭節點則是最遠通路的節點。

在

afterNodeInsertion

中，如果

removeEldestEntry(first)

節點傳回 true，則會将頭部節點删除。如果想要實作一個固定容量的 Map，可以在繼承 LinkedHashMap 後重寫

removeEldestEntry

方法。在 LinkedHashMap 中，該方法始終傳回 false。

//傳回false
//是否移除最老的Entry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

在 HashMap 中，在 putVal 和 removeNode 中都調用了相應的回調函數，而 get 則沒有，因而在 LinkedHahsMap 中進行了重寫：

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

周遊及疊代器

因為 LinkeHashMap 的所有的節點都在一個雙向連結清單中，因而可以通過該雙向連結清單來周遊所有的 Entry。而在 HashMap 中，要周遊所有的 Entry，則要依次周遊所有桶中的單連結清單。相比較而言，從時間複雜度的角度來看，LinkedHashMap 的複雜度為 O(size())，而 HashMap 則為 O(capacity + size())。

//因為所有的節點都被串聯在雙向連結清單中，疊代器在疊代時可以利用雙向連結清單的連結關系進行
//雙向連結清單的順序是按照插入序或通路序排列的
//相比于HashMap中的疊代，LinkedHashMap更為高效，O(size())
//HashMapde 疊代，O(capacity + size())
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;
    }
}

可以看到，在周遊所有節點時是通過節點的 after 引用進行的。這樣，可以雙連結清單的頭部周遊到到雙連結清單的尾部，就不用像 HahsMap 那樣通路空槽了。

containsValue

和

internalWriteEntries

中也使用了雙向連結清單進行周遊。

public boolean containsValue(Object value) {
    //使用雙向連結清單進行周遊
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

//覆寫父類方法
//序列化，Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    //調整元素的周遊方式，使用雙連結清單周遊
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        s.writeObject(e.key);
        s.writeObject(e.value);
    }
}

使用 LinkedHashMap 實作 LRU Cache

LinkedHashMap 的通路序可以友善地用來實作一個 LRU Cache。在通路序模式下，尾部節點是最近一次被通路的節點 (least-recently)，而頭部節點則是最遠通路 (most-recently) 的節點。因而在決定失效緩存的時候，将頭部節點移除即可。

但是，由于連結清單是無界的，但緩存往往是資源受限的，如何确定何時移除最遠通路的緩存呢？前面分析過，在

afterNodeInsertion

中，會調用

removeEldestEntry

來決定是否将最老的節點移除，因而我們可以使用 LinkedHashMap 的子類，并重寫

removeEldestEntry

方法，當 Enrty 的數量超過緩存的容量是傳回 true 即可。

下面給出基于 LinkedHashMap 實作的 LRU Cache 的代碼：

public class CacheImpl<K,V> {
    private Map<K, V> cache;
    private int capacity;

    public enum POLICY {
        LRU, FIFO
    }

    public CacheImpl(int cap, POLICY policy) {
        this.capacity = cap;
        cache = new LinkedHashMap<K, V>(cap, 0.75f, policy.equals(POLICY.LRU)){
            //超出容量就删除最老的值
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }

    public V get(K key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        return null;
    }

    public void set(K key, V val) {
        cache.put(key, val);
    }

    public void printKV() {
        System.out.println("key value in cache");
        for (Map.Entry<K,V> entry : cache.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }

    public static void main(String[] args) {
        CacheImpl<Integer, String> cache = new CacheImpl(5, POLICY.LRU);

        cache.set(1, "first");
        cache.set(2, "second");
        cache.set(3, "third");
        cache.set(4, "fourth");
        cache.set(5, "fifth");
        cache.printKV();

        cache.get(1);
        cache.get(2);
        cache.printKV();

        cache.set(6, "sixth");
        cache.printKV();
    }
}

小結

本文對 JDK 8 中的

LinkedHashMap

的源碼及實作進行了簡單的分析。LinkedHashMap 繼承自 HashMap，并在其基本結構上增加了雙向連結清單的實作，因而 LinkedHashMap 在記憶體占用上要比 HashMap 高出許多。LinkedHashMap 仍然沿用了 HashMap 中基于桶數組、桶内單連結清單和紅黑樹結構的哈希表，在哈希計算、定位、擴容等方面都和 HashMAp 是一緻的。LinkedHashMap 同樣支援為 null 的鍵和值。

由于增加了雙向連結清單将所有的 Entry 串在一起，LinkedHashMap 的一個重要的特點就是支援按照插入順序或通路順序來周遊所有的 Entry，這一點和 HashMap 的亂序周遊很不相同。在一些對順序有要求的場合，就需要使用 LinkedHashMap 來替代 HashMap。

由于雙向連結清單的緣故，在周遊時可以直接在雙向連結清單上進行，因而周遊時間複雜度和容量無關，隻和目前 Entry 數量有關。這點相比于 HashMap 要更加高效一些。

熬夜不易,點選請老王喝杯烈酒！！！！！！！

Java 容器源碼分析之 LinkedHashMap

底層結構

雙向連結清單

如何維護插入序和通路序？

周遊及疊代器

使用 LinkedHashMap 實作 LRU Cache

小結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method