腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

徹底弄懂Redis的LRU淘汰策略

更新時(shí)間：2022年01月20日 09:43:09 作者：柒柒Java

本文主要介紹了LRU淘汰策略以及實(shí)現(xiàn)一個(gè)LRU算法，文章會(huì)結(jié)合圖解循序漸進(jìn)的講解，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

Redis的淘汰策略

為什么要有淘汰策略呢？

因?yàn)榇鎯?chǔ)內(nèi)存的空間是有限的，所以需要有淘汰的策略。

Redis的清理內(nèi)存淘汰策略有哪些呢？

LRU算法簡(jiǎn)介

LRU是 Least Recently Used 的縮寫(xiě)，即 最近最少使用 ，是一種常見(jiàn)的頁(yè)面置換算法。

我們手機(jī)的后臺(tái)窗口（蘋(píng)果手機(jī)雙擊Home的效果），他總是會(huì)把最近常用的窗口放在最前邊，而最不常用的應(yīng)用窗口，就排列在后邊了，如果再加上只能放置N個(gè)應(yīng)用窗口的限制，淘汰最不常用的最近最少用的應(yīng)用窗口，那就是一個(gè)活生生的 LRU 。

實(shí)現(xiàn)思想推導(dǎo)

手機(jī)應(yīng)用案例

從上邊的示意圖，我們可以分析出這么幾個(gè)點(diǎn)：

有序；
如果應(yīng)用開(kāi)滿3個(gè)了，要淘汰最不常用的應(yīng)用，每次新訪問(wèn)應(yīng)用，需要把數(shù)據(jù)插入隊(duì)頭（按照業(yè)務(wù)可以設(shè)定左右哪一邊是隊(duì)頭）；
O(1)復(fù)雜度是我們查找數(shù)據(jù)的追求，我們什么結(jié)構(gòu)能夠?qū)崿F(xiàn)快速的O(1)查找呢？

推導(dǎo)圖

通過(guò)上邊的推導(dǎo)，我們就能得出， LRU 算法核心是 HashMap + DoubleLinkedList 。

思想搞明白了，我們接下來(lái)編碼實(shí)現(xiàn)。

巧用LinkedHashMap

我們查看Java的 LinkedHashMap 使用說(shuō)明。

LinkedHashMap使用說(shuō)明

翻譯：這種Map結(jié)構(gòu)很適合構(gòu)建LRU緩存。

繼承 LinkedHashMap 實(shí)現(xiàn) LRU 算法：

public class LRUDemo<K, V> extends LinkedHashMap<K, V> {
    private int capacity;
 
    public LRUDemo(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return super.size() > capacity;
    }
 
    public static void main(String[] args) {
        LRUDemo lruDemo = new LRUDemo(3);
        lruDemo.put(1, "a");
        lruDemo.put(2, "b");
        lruDemo.put(3, "c");
        System.out.println(lruDemo.keySet());
 
        lruDemo.put(4, "d");
        lruDemo.put(5, "e");
        System.out.println(lruDemo.keySet());
    }
}

重點(diǎn)講解：

構(gòu)造方法： super(capacity, 0.75F, true) ，主要看第三個(gè)參數(shù)：

order參數(shù)

true -> access-order // false -> insertion-order 即按照訪問(wèn)時(shí)間排序，還是按照插入的時(shí)間來(lái)排序

// 構(gòu)造方法改成false
super(capacity, 0.75F, false);
// 使用示例
public static void main(String[] args) {
  LRUDemo lruDemo = new LRUDemo(3);
  lruDemo.put(1, "a");
  lruDemo.put(2, "b");
  lruDemo.put(3, "c");
  System.out.println(lruDemo.keySet());
 
  lruDemo.put(1, "y");
  // 構(gòu)造方法order=true，輸出：[2,3,1]，
  // 構(gòu)造方法order=false，輸出：[1,2,3]，
  System.out.println(lruDemo.keySet());
}

removeEldestEntry 方法：什么時(shí)候移除最年長(zhǎng)的元素。

通過(guò)上面，相信大家對(duì) LRU 算法有所理解了，接下來(lái)我們不依賴JDK的 LinkedHashMap ，通過(guò)我們自己的理解，動(dòng)手實(shí)現(xiàn)一個(gè) LRU 算法，讓我們的 LRU 算法刻入我們的大腦。

手寫(xiě)LRU

上邊的推導(dǎo)圖中可以看出，我們用 HashMap 來(lái)做具體的數(shù)據(jù)儲(chǔ)存，但是我們還需要構(gòu)造一個(gè) DoubleLinkedList 對(duì)象（結(jié)構(gòu)體）來(lái)儲(chǔ)存 HashMap 的具體 key 順序關(guān)系。

第一步：構(gòu)建DoubleLinkedList對(duì)象

所以我們現(xiàn)在 第一步 ，就是構(gòu)建一個(gè) DoubleLinkedList 對(duì)象：

DoubleLinkedList示意圖

我們可以從 HashMap 源碼中找一些靈感，他們都是使用一個(gè) Node 靜態(tài)內(nèi)部類來(lái)儲(chǔ)存節(jié)點(diǎn)的值。

第二步：構(gòu)建節(jié)點(diǎn)

通過(guò)上邊的示意圖，我們可以得知 節(jié)點(diǎn) 應(yīng)該要儲(chǔ)存的內(nèi)容：

key
value
prev節(jié)點(diǎn)
next節(jié)點(diǎn)

翻譯成代碼：

class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;
 
    public Node() {
        this.prev = this.next = null;
    }
 
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.prev = this.next = null;
    }
}

第三步：初始化DoubleLinkedList對(duì)象

DoubleLinkedList初始化示意圖

還是通過(guò)上邊的示意圖，我們可以得知 DoubleLinkedList對(duì)象 應(yīng)該要儲(chǔ)存的內(nèi)容：

頭節(jié)點(diǎn)
尾節(jié)點(diǎn)

翻譯成代碼：

class DoubleLinkedList<K, V> {
    Node<K, V> head;
    Node<K, V> tail;
 
    // 構(gòu)造方法
    public DoubleLinkedList(){
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.prev = head;
    }
}

從頭添加節(jié)點(diǎn)

翻譯成代碼：

public void addHead(Node<K, V> node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}

刪除節(jié)點(diǎn)

翻譯成代碼：

public void removeNode(Node<K, V> node) {
    node.next.prev = node.prev;
    node.prev.next = node.next;
    node.prev = null;
    node.next = null;
}

獲取最后一個(gè)節(jié)點(diǎn)

public Node getLast() {
    return tail.prev;
}

第四步：LRU對(duì)象屬性

cacheSize

private int cacheSize;

map

Map<Integer, Node<Integer, String>> map;

doubleLinkedList

DoubleLinkedList<Integer, String> doubleLinkedList;

第五步：LRU對(duì)象的方法

構(gòu)造方法

public LRUDemo(int cacheSize) {
    this.cacheSize = cacheSize;
    map = new HashMap<>();
    doubleLinkedList = new DoubleLinkedList<>();
}

refreshNode刷新節(jié)點(diǎn)

public void refreshNode(Node node) {
    doubleLinkedList.removeNode(node);
    doubleLinkedList.addHead(node);
}

get節(jié)點(diǎn)

public String get(int key) {
    if (!map.containsKey(key)) {
        return "";
    }
 
    Node<Integer, String> node = map.get(key);
    refreshNode(node);
    return node.value;
}

put節(jié)點(diǎn)

public void put(int key, String value) {
    if (map.containsKey(key)) {
        Node<Integer, String> node = map.get(key);
        node.value = value;
        map.put(key, node);
 
        refreshNode(node);
    } else {
        if (map.size() == cacheSize) {
            Node lastNode = doubleLinkedList.getLast();
            map.remove(lastNode.key);
            doubleLinkedList.removeNode(lastNode);
        }
 
        Node<Integer, String> newNode = new Node<>(key, value);
        map.put(key, newNode);
        doubleLinkedList.addHead(newNode);
    }
}

第六步：測(cè)試

public static void main(String[] args) {
    LRUDemo lruDemo = new LRUDemo(3);
    lruDemo.put(1, "美團(tuán)");
    lruDemo.put(2, "微信");
    lruDemo.put(3, "抖音");
    lruDemo.put(4, "微博");
    System.out.println(lruDemo.map.keySet());
 
    System.out.println(lruDemo.get(2));
}