Java中自定義LRU緩存詳解

更新時間：2023年09月21日 10:45:52 作者：曉之木初

這篇文章主要介紹了Java中自定義LRU緩存詳解,基于LRU算法的緩存系統(tǒng),可以在達(dá)到緩存容量上限時,清理最近最少使用的數(shù)據(jù),為新的數(shù)據(jù)的插入騰出空間,需要的朋友可以參考下

1. LRU算法

在計算機(jī)領(lǐng)域，LRU算法的應(yīng)用非常多，最常見的就是LRU緩存
LRU：Least Recently USed，最近最少使用
英文和中文存在差異，如果只看中文，貌似RLU更合適
基于LRU算法的緩存系統(tǒng)，可以在達(dá)到緩存容量上限時，清理最近最少使用的數(shù)據(jù)，為新的數(shù)據(jù)的插入騰出空間
leetcode上，也有對應(yīng)的LRU緩存算法題：146. LRU 緩存機(jī)制
?？蜕?，螞蟻金服的面試題庫，LRU緩存也赫然在列
題目要求大概如下：
- 設(shè)計和實現(xiàn)一個LRU算法的緩存數(shù)據(jù)結(jié)構(gòu)。需要實現(xiàn)兩個操作：get和set
- 獲取數(shù)據(jù) get(key) ：如果關(guān)鍵字 (key) 存在于緩存中，則獲取關(guān)鍵字的值（總是正數(shù)），否則返回 -1。
- 寫入數(shù)據(jù) put(key, value) ：
  - 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；
  - 如果關(guān)鍵字不存在，則插入該組<key, value>。
  - 當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

2. 繼承LinkedHashMap實現(xiàn)LRU緩存

通過對LinkedHashMap的學(xué)習(xí)，我們了解到：

與HashMap不同，LinkedHashMap作為鏈表形式的哈希表，支持元素的插入順序或訪問順序

使用訪問順序時，通過重寫removeEldestEntry()方法，可以刪除最近最少使用的鍵值對

因此，可以通過繼承LinkedHashMap、重寫removeEldestEntry() 方法，實現(xiàn)LRU緩存

import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    public LRUCache(int capacity) {
        // true表示按訪順序存儲鍵值對，最近訪問的在尾部，最近最少訪問在頭部
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
    public int get(int key) {
        // 根據(jù)題目要求，不存在key時，不能直接返回null值，而是需要返回默認(rèn)值-1
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
}

3. 自定義LRU緩存

如果在面試時，碰到該題，應(yīng)該先和面試官確認(rèn)，是否能使用現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)去實現(xiàn)
如果面試官明確要求說，需要自己去實現(xiàn)LRU緩存，不能使用現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)，那么時候展現(xiàn)你的實力了

最原始的想法：

既然LinkedHashMap都是雙向鏈表 + HashMap實現(xiàn)的，那我自己定義一個雙向鏈表實現(xiàn)類似的功能

class DLinkedNode{
    private int key;
    private int val;
    private DLinkNode prev;
    private DLinkNode next;
}

基于雙向鏈表，可以在 O ( 1 ) O(1) O(1)的時間內(nèi)快速增加、刪除節(jié)點
但在確定節(jié)點位置時，需要從頭到尾遍歷鏈表
就算使用雙指針左右開弓，在定位節(jié)點時，依然存在很大的開銷

思路進(jìn)階

借助HashMap，以O(shè) ( 1 ) O(1)O(1)的時間復(fù)雜度快速get或put數(shù)據(jù)
同時，規(guī)定：最近訪問的節(jié)點放在鏈表的頭部，最近最少訪問的節(jié)點放在鏈表的尾部
如果頭部或尾部直接存儲數(shù)據(jù)，則在實現(xiàn)時需要考慮節(jié)點是否為頭節(jié)點或尾結(jié)點的情況
因此，直接創(chuàng)建dummy的head和tail節(jié)點，以減少編寫代碼的工作量

最終的代碼實現(xiàn)

通過上述分析，代碼如下

import java.util.HashMap;
public class LRUCache{
    private HashMap<Integer, DLinkedNode> map;
    private DLinkedNode head;
    private DLinkedNode tail;
    private int capacity;
    private int size;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        // 初始化帶dummy節(jié)點的雙向鏈表
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        DLinkedNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 被訪問，需要從當(dāng)前位置移動到頭部
        if (head.next != node){
            removeNode(node);
            insertToHead(node);
        }
        return node.val;
    }
    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        // 如果存在，直接更新值
        if (node != null) {
            node.val = value;
            // 被訪問，需要從當(dāng)前位置移動到頭部
            if (head.next != node) {
                removeNode(node);
                insertToHead(node);
            }
        } else {
            // 插入前，先判斷是否需要騰出空間
            if (size == capacity) {
                // 從鏈表中刪除尾結(jié)點
                DLinkedNode last = tail.prev;
                removeNode(last);
                // 從map中移除記錄
                map.remove(last.key);
                size--;
            }
            // 新建節(jié)點并插入
            DLinkedNode newNode = new DLinkedNode(key, value);
            insertToHead(newNode);
            map.put(key, newNode);
            size++;
        }
    }
    // 插入節(jié)點一定是在頭部
    public void insertToHead(DLinkedNode node) {
        // 分別建立與head.next和head的關(guān)聯(lián)
        DLinkedNode next = head.next;
        node.next = next;
        next.prev = node;
        head.next = node;
        node.prev = head;
    }
    // 刪除指定節(jié)點
    public void removeNode(DLinkedNode node) {
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
        // 斷開引用，幫助GC
        node.prev = null;
        node.next = null;
    }
}
class DLinkedNode{
     int key;
     int val;
     DLinkedNode prev;
     DLinkedNode next;
    public DLinkedNode() {
    }
    public DLinkedNode(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

幾點注意事項：