本文已收錄到 AndroidFamily，技術和職場問題，請關注公衆号 [彭旭銳] 提問。

大家好，我是小彭。

在上一篇文章裡，我們聊到了 HashMap 的實作原理和源碼分析，在源碼分析的過程中，我們發現一些 LinkedHashMap 相關的源碼，當時沒有展開，現在它來了。

那麼，LinkedHashMap 與 HashMap 有什麼差別呢？其實，LinkedHashMap 的使用場景非常明确 —— LRU 緩存。今天，我們就來讨論 LinkedHashMap 是如何實作 LRU 緩存的。

本文源碼基于 Java 8 LinkedHashMap。

小彭的 Android 交流群 02 群已經建立啦~

思維導圖：

1. 認識 LRU 緩存淘汰算法

1.1 什麼是緩存淘汰算法？

緩存是提高資料讀取性能的通用技術，在硬體和軟體設計中被廣泛使用，例如 CPU 緩存、Glide 記憶體緩存，資料庫緩存等。由于緩存空間不可能無限大，當緩存容量占滿時，就需要利用某種政策将部分資料換出緩存，這就是緩存的替換政策 / 淘汰問題。常見緩存淘汰政策有：

1、随機政策：使用一個随機數生成器随機地選擇要被淘汰的資料塊；
2、FIFO 先進先出政策：記錄各個資料塊的通路時間，最早通路的資料最先被淘汰；
3、LRU （Least Recently Used）最近最少政策：記錄各個資料塊的通路 “時間戳” ，最近最久未使用的資料最先被淘汰。與前 2 種政策相比，LRU 政策平均緩存命中率更高，這是因為 LRU 政策利用了 “局部性原理”：最近被通路過的資料，将來被通路的幾率較大，最近很久未通路的資料，将來通路的幾率也較小；
4、LFU （Least Frequently Used）最不經常使用政策：與 LRU 相比，LFU 更加注重使用的 “頻率” 。LFU 會記錄每個資料塊的通路次數，最少通路次數的資料最先被淘汰。但是有些資料在開始時使用次數很高，以後不再使用，這些資料就會長時間污染緩存。可以定期将計數器右移一位，形成指數衰減。

FIFO 與 LRU 政策

1.2 向外看：LRU 的變型

其實，在标準的 LRU 算法上還有一些變型實作，這是因為 LRU 算法本身也存在一些不足。例如，當資料中熱點資料較多時，LRU 能夠保證較高的命中率。但是當有偶發的批量的非熱點資料産生時，就會将熱點資料寄出緩存，使得緩存被污染。是以，LRU 也有一些變型：

LRU-K：提供兩個 LRU 隊列，一個是通路計數隊列，一個是标準的 LRU 隊列，兩個隊列都按照 LRU 規則淘汰資料。當通路一個資料時，資料先進入通路計數隊列，當資料通路次數超過 K 次後，才會進入标準 LRU 隊列。标準的 LRU 算法相當于 LRU-1；
Two Queue：相當于 LRU-2 的變型，将通路計數隊列替換為 FIFO 隊列淘汰資料資料。當通路一個資料時，資料先進入 FIFO 隊列，當第 2 次通路資料時，才會進入标準 LRU 隊列；
Multi Queue：在 LRU-K 的基礎上增加更多隊列，提供多個級别的緩沖。

小彭在 Redis 和 Vue 中有看到這些 LRU 變型的應用，在 Android 領域的架構中還沒有看到具體應用，你知道的話可以提醒我。

1.3 如何實作 LRU 緩存淘汰算法？

這一小節，我們嘗試找到 LRU 緩存淘汰算法的實作方案。經過總結，我們可以定義一個緩存系統的基本操作：

操作 1 - 添加資料：先查詢資料是否存在，不存在則添加資料，存在則更新資料，并嘗試淘汰資料；
操作 2 - 删除資料：先查詢資料是否存在，存在則删除資料；
操作 3 - 查詢資料：如果資料不存在則傳回 null；
操作 4 - 淘汰資料：添加資料時如果容量已滿，則根據緩存淘汰政策一個資料。

我們發現，前 3 個操作都有 “查詢” 操作，是以緩存系統的性能主要取決于查找資料和淘汰資料是否高效。下面，我們用遞推的思路推導 LRU 緩存的實作方案，主要分為 3 種方案：

方案 1 - 基于時間戳的數組：在每個資料塊中記錄最近通路的時間戳，當資料被通路（添加、更新或查詢）時，将資料的時間戳更新到目前時間。當數組空間已滿時，則掃描數組淘汰時間戳最小的資料。查找資料：需要周遊整個數組找到目标資料，時間複雜度為 O(n)；淘汰資料：需要周遊整個數組找到時間戳最小的資料，且在移除數組元素時需要搬運資料，整體時間複雜度為 O(n)。
方案 2 - 基于雙向連結清單：不再直接維護時間戳，而是利用連結清單的順序隐式維護時間戳的先後順序。當資料被通路（添加、更新或查詢）時，将資料插入到連結清單頭部。當空間已滿時，直接淘汰連結清單的尾節點。查詢資料：需要周遊整個連結清單找到目标資料，時間複雜度為 O(n)；淘汰資料：直接淘汰連結清單尾節點，時間複雜度為 O(1)。
方案 3 - 基于雙向連結清單 + 散清單：使用雙向連結清單可以将淘汰資料的時間複雜度降低為 O(1)，但是查詢資料的時間複雜度還是 O(n)，我們可以在雙向連結清單的基礎上增加散清單，将查詢操作的時間複雜度降低為 O(1)。查詢資料：通過散清單定位資料，時間複雜度為 O(1)；淘汰資料：直接淘汰連結清單尾節點，時間複雜度為 O(1)。

方案 3 這種資料結構就叫 “哈希連結清單或鍊式哈希表”，我更傾向于稱為哈希連結清單，因為當這兩個資料結構相結合時，我們更看重的是它作為連結清單的排序能力。

我們今天要讨論的 Java LinkedHashMap 就是基于哈希連結清單的資料結構。

2. 認識 LinkedHashMap 哈希連結清單

2.1 說一下 LinkedHashMap 的特點

需要注意：LinkedHashMap 中的 “Linked” 實際上是指雙向連結清單，并不是指解決散列沖突中的分離連結清單法。

1、LinkedHashMap 是繼承于 HashMap 實作的哈希連結清單，它同時具備雙向連結清單和散清單的特點。事實上，LinkedHashMap 繼承了 HashMap 的主要功能，并通過 HashMap 預留的 Hook 點維護雙向連結清單的邏輯。1.1 當 LinkedHashMap 作為散清單時，主要展現出 O(1) 時間複雜度的查詢效率；1.2 當 LinkedHashMap 作為雙向連結清單時，主要展現出有序的特性。
2、LinkedHashMap 支援 2 種排序模式，這是通過構造器參數 accessOrder 标記位控制的，表示是否按照通路順序排序，預設為 false 按照插入順序。2.1 插入順序（預設）：按照資料添加到 LinkedHashMap 的順序排序，即 FIFO 政策；2.2 通路順序：按照資料被通路（包括插入、更新、查詢）的順序排序，即 LRU 政策。
3、在有序性的基礎上，LinkedHashMap 提供了維護了淘汰資料能力，并開放了淘汰判斷的接口 removeEldestEntry()。在每次添加資料時，會回調 removeEldestEntry() 接口，開發者可以重寫這個接口決定是否移除最早的節點（在 FIFO 政策中是最早添加的節點，在 LRU 政策中是最早未通路的節點）；
4、與 HashMap 相同，LinkedHashMap 也不考慮線程同步，也會存線上程安全問題。可以使用 Collections.synchronizedMap 包裝類，其原理也是在所有方法上增加 synchronized 關鍵字。

2.2 說一下 HashMap 和 LinkedHashMap 的差別？

事實上，HashMap 和 LinkedHashMap 并不是平行的關系，而是繼承的關系，LinkedHashMap 是繼承于 HashMap 實作的哈希連結清單。

兩者主要的差別在于有序性： LinkedHashMap 會維護資料的插入順序或通路順序，而且封裝了淘汰資料的能力。在疊代器周遊時，HashMap 會按照數組順序周遊桶節點，從開發者的視角看是無序的。而是按照雙向連結清單的順序從 head 節點開始周遊，從開發者的視角是可以感覺到的插入順序或通路順序。

LinkedHashMap 示意圖

3. HashMap 預留的 Hook 點

LinkedHashMap 繼承于 HashMap，在後者的基礎上通過雙向連結清單維護節點的插入順序或通路順序。是以，我們先回顧下 HashMap 為 LinkedHashMap 預留的 Hook 點：

afterNodeAccess：在節點被通路時回調；
afterNodeInsertion：在節點被插入時回調，其中有參數 evict 标記是否淘汰最早的節點。在初始化、反序列化或克隆等構造過程中，evict 預設為 false，表示在構造過程中不淘汰。
afterNodeRemoval：在節點被移除時回調。

HashMap.java

// 節點通路回調
void afterNodeAccess(Node<K,V> p) { }
// 節點插入回調
// evict：是否淘汰最早的節點
void afterNodeInsertion(boolean evict) { }
// 節點移除回調
void afterNodeRemoval(Node<K,V> p) { }

除此了這 3 個空方法外，LinkedHashMap 也重寫了部分 HashMap 的方法，在其中插入雙連結清單的維護邏輯，也相當于 Hook 點。在 HashMap 的添加、擷取、移除方法中，與 LinkedHashMap 有關的 Hook 點如下：

3.1 HashMap 的添加方法中的 Hook 點

LinkedHashMap 直接複用 HashMap 的添加方法，也支援批量添加：

HashMap#put：逐個添加或更新鍵值對；
HashMap#putAll：批量添加或更新鍵值對。

不管是逐個添加還是批量添加，最終都會先通過 hash 函數計算鍵（Key）的散列值，再通過 HashMap#putVal 添加或更新鍵值對，這些都是 HashMap 的行為。關鍵的地方在于：LinkedHashMap 在 HashMap#putVal 的 Hook 點中加入了雙線連結清單的邏輯。區分 2 種情況：

添加資料：如果資料不存在散清單中，則調用 newNode() 或 newTreeNode() 建立節點，并回調 afterNodeInsertion()；
更新資料：如果資料存在散清單中，則更新 Value，并回調 afterNodeAccess()。

HashMap.java

// 添加或更新鍵值對
public V put(K key, V value) {
    return putVal(hash(key) /*計算散列值*/, key, value, false, true);
}

// hash：Key 的散列值（經過擾動）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n;
    int i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash：散列值轉數組下标
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 省略周遊桶的代碼，具體分析見 HashMap 源碼講解

        // 1.1 如果節點不存在，則新增節點
        p.next = newNode(hash, key, value, null);
        // 2.1 如果節點存在更新節點 Value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 2.2 Hook：通路節點回調
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 擴容
    if (++size > threshold)
        resize();
    // 1.2 Hook：新增節點回調
    afterNodeInsertion(evict);
    return null;
}

HashMap#put 示意圖

3.2 HashMap 的擷取方法中的 Hook 點

LinkedHashMap 重寫了 HashMap#get 方法，在 HashMap 版本的基礎上，增加了 afterNodeAccess() 回調。

HashMap.java

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

LinkedHashMap.java

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // Hook：節點通路回調
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return defaultValue;
    // Hook：節點通路回調
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

HashMap#get 示意圖

3.3 HashMap 的移除方法中的 Hook 點

LinkedHashMap 直接複用 HashMap 的移除方法，在移除節點後，增加 afterNodeRemoval() 回調。

HashMap.java

// 移除節點
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key)/*計算散列值*/, key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
    boolean matchValue, boolean movable) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, index;
    // (n - 1) & hash：散列值轉數組下标
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 省略周遊桶的代碼，具體分析見 HashMap 源碼講解
        // 删除 node 節點
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            // 省略删除節點的代碼，具體分析見 HashMap 源碼講解
            ++modCount;
            --size;
            // Hook：删除節點回調
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

HashMap#remove 示意圖

4. LinkedHashMap 源碼分析

這一節，我們來分析 LinkedHashMap 中主要流程的源碼。

4.1 LinkedHashMap 的屬性

LinkedHashMap 繼承于 HashMap，并且新增 head 和 tail 指針指向連結清單的頭尾節點（與 LinkedList 類似的頭尾節點）；
LinkedHashMap 的雙連結清單節點 Entry 繼承于 HashMap 的單連結清單節點 Node，而 HashMap 的紅黑樹節點 TreeNode 繼承于 LinkedHashMap 的雙連結清單節點 Entry。

節點繼承關系

LinkedHashMap.java

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    // 頭指針
    transient LinkedHashMap.Entry<K,V> head;
    // 尾指針
    transient LinkedHashMap.Entry<K,V> tail;
    // 是否按照通路順序排序
    final boolean accessOrder;

    // 雙向連結清單節點
    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);
        }
    }
}

LinkedList.java

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 頭指針（// LinkedList 中也有類似的頭尾節點）
    transient Node<E> first;
    // 尾指針
    transient Node<E> last;

    // 雙向連結清單節點
    private static class Node<E> {
        // 節點資料
        // （類型擦除後：Object item;）
        E item;
        // 前驅指針
        Node<E> next;
        // 後繼指針
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

LinkedHashMap 的屬性很好了解的，不出意外的話又有小朋友出來舉手提問了：

‍♀️疑問 1：HashMap.TreeNode 和 LinkedHashMap.Entry 的繼承順序是不是反了？

我的了解是作者希望簡化節點類型，是以采用了非正常的做法（不愧是标準庫）。由于 Java 是單繼承的，如果按照正常的做法讓 HashMap.TreeNode 直接繼承 HashMap.Node，那麼在 LinkedHashMap 中就需要區分 LinkedHashMap.Entry 和 LinkedHashMap.TreeEntry，再使用接口統一兩種類型。

正常實作

4.2 LinkedHashMap 的構造方法

LinkedHashMap 有 5 個構造方法，作用與 HashMap 的構造方法基本一緻，差別隻在于對 accessOrder 字段的初始化。

// 帶初始容量和裝載因子的構造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 帶初始容量的構造方法
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

// 無參構造方法
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 帶 Map 的構造方法
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

// 帶初始容量、裝載因子和 accessOrder 的構造方法
// 是否按照通路順序排序，為 true 表示按照通路順序排序，預設為 false
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

4.3 LinkedHashMap 如何維護雙連結清單

現在，我們看下 LinkedHashMap 是如何維護雙連結清單的。其實，我們将上一節所有的 Hook 點彙總，會發現這些 Hook 點正好組成了 LinkedHashMap 雙向連結清單的行為：

添加資料：将資料連結到雙向連結清單的尾節點，時間複雜度為 O(1)；
通路資料（包括添加、查詢、更新）：将資料移動到雙向連結清單的尾節點，亦相當于先移除再添加到尾節點，時間複雜度為 O(1)；
删除資料：将資料從雙向連結清單中移除，時間複雜度為 O(1)；
淘汰資料：直接淘汰雙向連結清單的頭節點，時間複雜度為 O(1)。

LinkedHashMap.java

// -> 1.1 如果節點不存在，則新增節點
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);
    // 添加到雙向連結清單尾部，等價于 LinkedList#linkLast
    linkNodeLast(p);
    return p;
}

// -> 1.1 如果節點不存在，則新增節點
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);
    // 添加到雙向連結清單尾部，等價于 LinkedList#linkLast
    linkNodeLast(p);
    return p;
}

// 添加到雙向連結清單尾部，等價于 LinkedList#linkLast
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        // last 為 null 說明首個添加的元素，需要修改 first 指針
        head = p;
    else {
        // 将新節點的前驅指針指向 last 
        p.before = last;
        // 将 last 的 next 指針指向新節點
        last.after = p;
    }
}

// 節點插入回調
// evict：是否淘汰最早的節點
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry：是否淘汰最早的節點，即是否淘汰頭節點（由子類實作）
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        // 移除 first 節點，騰出緩存空間
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

// 移除節點回調
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 指針
        head = a;
    else
        // 修正前驅節點的後繼指針，指向被删除節點的後繼節點
        b.after = a;
    if (a == null)
        // 删除的是尾節點，則修正 tail 指針
        tail = b;
    else
        // 修正後繼節點的前驅指針，指向被删除節點的前驅節點
        a.before = b;
}

// 節點通路回調
void afterNodeAccess(Node<K,V> e) { // move node to last
    // 先将節點 e 移除，再添加到連結清單尾部
    LinkedHashMap.Entry<K,V> last;
    // accessOrder：是否按照通路順序排序，為 false 則保留插入順序
    if (accessOrder && (last = tail) != e) {
        // 這兩個 if 語句塊就是 afterNodeRemoval 的邏輯
        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 語句塊就是 linkNodeLast 的邏輯
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

// 淘汰判斷接口，由子類實作
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

4.4 LinkedHashMap 的疊代器

與 HashMap 類似，LinkedHashMap 也提供了 3 個疊代器：

LinkedEntryIterator：鍵值對疊代器
LinkedKeyIterator：鍵疊代器
LinkedValueIterator：值疊代器

差別在于 LinkedHashMap 自己實作了 LinkedHashIterator。在疊代器周遊時，HashMap 會按照數組順序周遊桶節點，從開發者的視角看是無序的。而 LinkedHashMap 是按照雙向連結清單的順序從 head 節點開始周遊，從開發者的視角是可以感覺到的插入順序或通路順序。

LinkedHashMap.java

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

4.5 LinkedHashMap 的序列化過程

與 HashMap 相同，LinkedHashMap 也重寫了 JDK 序列化的邏輯，并保留了 HashMap 中序列化的主體結構。LinkedHashMap 隻是重寫了 internalWriteEntries()，按照雙向連結清單的順序進行序列化，這樣在反序列化時就能夠恢複雙向連結清單順序。

HashMap.java

// 序列化過程
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    int buckets = capacity();
    s.defaultWriteObject();
    // 寫入容量
    s.writeInt(buckets);
    // 寫入有效元素個數
    s.writeInt(size);
    // 寫入有效元素
    internalWriteEntries(s);
}

// 不關心鍵值對所在的桶，在反序列化會重新映射
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    Node<K,V>[] tab;
    if (size > 0 && (tab = table) != null) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                s.writeObject(e.key);
                s.writeObject(e.value);
            }
        }
    }
}

LinkedHashMap.java

// 重寫：按照雙向連結清單順序寫入
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);
    }
}

5. 基于 LinkedHashMap 實作 LRU 緩存

這一節，我們來實作一個簡單的 LRU 緩存。了解了 LinkedHashMap 維護插入順序和通路順序的原理後，相信你已經知道如何實作 LRU 緩存了。

首先，我們已經知道，LinkedHashMap 支援 2 種排序模式，這是通過構造器參數 accessOrder 标記位控制的。是以，這裡我們需要将 accessOrder 設定為 true 表示使用 LRU 模式的通路順序排序。
其次，我們不需要實作淘汰資料的邏輯，隻需要重寫淘汰判斷接口 removeEldestEntry()，當緩存數量大于緩存容量時傳回 true，表示移除最早的節點。

MaxSizeLruCacheDemo.java

public class MaxSizeLruCacheDemo extends LinkedHashMap {

    private int maxElements;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
        // 超出容量
        return size() > maxElements;
    }
}

6. 總結

1、LRU 是一種緩存淘汰算法，與其他淘汰算法相比，LRU 算法利用了 “局部性原理”，緩存的平均命中率更高；
2、使用雙向連結清單 + 散清單實作的 LRU，在添加、查詢、移除和淘汰資料的時間複雜度都是 O(1)，這種資料結構也叫哈希連結清單；查詢資料：通過散清單定位資料，時間複雜度為 O(1)；淘汰資料：直接淘汰連結清單尾節點，時間複雜度為 O(1)。
3、使用 LinkedHashMap 時，主要關注 2 個 API：accessOrder 标記位： LinkedHashMap 同時實作了 FIFO 和 LRU 兩種淘汰政策，預設為 FIFO 排序，可以使用 accessOrder 标記位修改排序模式。removeEldestEntry() 接口：每次添加資料時，LinkedHashMap 會回調 removeEldestEntry() 接口。開發者可以重寫 removeEldestEntry() 接口決定是否移除最早的節點（在 FIFO 政策中是最早添加的節點，在 LRU 政策中是最久未通路的節點）。
4、Android 的 LruCache 記憶體緩存和 DiskLruCache 磁盤緩存中，都直接複用了 LinkedHashMap 的 LRU 能力。

今天，我們分析了 LinkedHashMap 的實作原理。在下篇文章裡，我們來分析 LRU 的具體實作應用，例如 Android 标準庫中的 LruCache 記憶體緩存。

可以思考一個問題，LinkedHashMap 是非線程安全的，Android 的 LruCache 是如何解決線程安全問題的？請關注小彭說 · Android 開源元件專欄。

參考資料

資料結構與算法分析 · Java 語言描述（第 5 章 · 散列）—— [美] Mark Allen Weiss 著
算法導論（第 11 章 · 散清單）—— [美] Thomas H. Cormen 等著
資料結構與算法之美（第 6、18~22 講） —— 王争著，極客時間出品
LinkedHashMap 源碼詳細分析（JDK1.8）—— 田小波著
LRU 算法及其優化政策——算法篇 —— 豆豉辣椒炒臘肉著
緩沖池(buffer pool)，這次徹底懂了！ —— 58 沈劍著
LeetCode 146. LRU 緩存 —— LeetCode
Cache replacement policies —— Wikipedia

如何使用 LinkedHashMap 實作 LRU 緩存？

1. 認識 LRU 緩存淘汰算法

1.1 什麼是緩存淘汰算法？

1.2 向外看：LRU 的變型

1.3 如何實作 LRU 緩存淘汰算法？

2. 認識 LinkedHashMap 哈希連結清單

2.1 說一下 LinkedHashMap 的特點

2.2 說一下 HashMap 和 LinkedHashMap 的差別？

3. HashMap 預留的 Hook 點

3.1 HashMap 的添加方法中的 Hook 點

3.2 HashMap 的擷取方法中的 Hook 點

3.3 HashMap 的移除方法中的 Hook 點

4. LinkedHashMap 源碼分析

4.1 LinkedHashMap 的屬性

4.2 LinkedHashMap 的構造方法

4.3 LinkedHashMap 如何維護雙連結清單

4.4 LinkedHashMap 的疊代器

4.5 LinkedHashMap 的序列化過程

5. 基于 LinkedHashMap 實作 LRU 緩存

6. 總結

參考資料

繼續閱讀

LinkedHashSet源碼閱讀回顧

Java常見面試題：什麼是值傳遞？許多人可能仍不清楚值傳遞的概念。盡管他們知道如何使用引用傳遞，但他們可能不了解其實際原

如何使用EV代碼簽名證書，注冊Windows硬體開發中心帳戶？

關于統招專升本的這些資訊表，你一定要知道它們如何使用，掌握這些表的資訊及使用方法，也是成功上岸的重要組成部分。#惠衆專升

中視訊計劃的釋出入口。你知道中視訊夥伴計劃正确的釋出入口嗎？隻有從正确的釋出入口釋出作品，才能獲得西瓜平台、抖音平台和今

緩存注解大揭秘：SpringCloud中如何使用緩存注解？

如何使用人工智能來做事：AI實用指南

如何使用 PSEXEC 在遠端計算機上運作指令

如何使用Golang的Gin架構渲染HTML頁面

LeetCode-Linked List Cycle II

如何使用NS遊戲機？現在教你如何進入學習軟體。·首先打開NS遊戲機，設定開機選項。更多設定中包含學習軟體，若未找到，請先

如何使用 OFFICE 365 保留政策

如何使用PyTorch建構Transformer模型實作語言生成任務

如何使用Transformer模型實作語言分類任務

php源碼安裝，如何使用源碼的方式安裝PHP環境

LinkedHashMap的簡單用法