欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論