Java中自定義LRU緩存詳解

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

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

1. LRU算法

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

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

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

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

使用訪問(wèn)順序時(shí)，通過(guò)重寫(xiě)removeEldestEntry()方法，可以刪除最近最少使用的鍵值對(duì)

因此，可以通過(guò)繼承LinkedHashMap、重寫(xiě)removeEldestEntry() 方法，實(shí)現(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表示按訪順序存儲(chǔ)鍵值對(duì)，最近訪問(wèn)的在尾部，最近最少訪問(wèn)在頭部
        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時(shí)，不能直接返回null值，而是需要返回默認(rèn)值-1
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
}

3. 自定義LRU緩存

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

最原始的想法：

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

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

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

思路進(jìn)階

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

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

通過(guò)上述分析，代碼如下

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é)點(diǎn)的雙向鏈表
        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;
        }
        // 被訪問(wèn)，需要從當(dāng)前位置移動(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;
            // 被訪問(wèn)，需要從當(dāng)前位置移動(dòng)到頭部
            if (head.next != node) {
                removeNode(node);
                insertToHead(node);
            }
        } else {
            // 插入前，先判斷是否需要騰出空間
            if (size == capacity) {
                // 從鏈表中刪除尾結(jié)點(diǎn)
                DLinkedNode last = tail.prev;
                removeNode(last);
                // 從map中移除記錄
                map.remove(last.key);
                size--;
            }
            // 新建節(jié)點(diǎn)并插入
            DLinkedNode newNode = new DLinkedNode(key, value);
            insertToHead(newNode);
            map.put(key, newNode);
            size++;
        }
    }
    // 插入節(jié)點(diǎn)一定是在頭部
    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é)點(diǎn)
    public void removeNode(DLinkedNode node) {
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
        // 斷開(kāi)引用，幫助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;
    }
}

幾點(diǎn)注意事項(xiàng)：

節(jié)點(diǎn)移動(dòng)到頭部情況：get時(shí)，節(jié)點(diǎn)被訪問(wèn)；put時(shí)，節(jié)點(diǎn)的值被更新。put時(shí)的情況，容易被忽略
新增節(jié)點(diǎn)時(shí)，按照題目要求是先刪除最久未使用的節(jié)點(diǎn)，并非先插入再刪除
注意雙向鏈表和HashMap的聯(lián)動(dòng)，刪除或新增節(jié)點(diǎn)，HashMap中也要?jiǎng)h除或新增記錄

到此這篇關(guān)于Java中自定義LRU緩存詳解的文章就介紹到這了,更多相關(guān)Java的LRU緩存內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: