如何使用 LinkedHashMap 實現 LRU 快取？

2022 年 12 月 1 日
筆記
演算法

本文已收錄到 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

小彭的 Android 交流群 02 群

Tags: 演算法