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

快捷導(dǎo)航

徹底弄懂Redis的LRU淘汰策略

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

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

Redis的淘汰策略

為什么要有淘汰策略呢？

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

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

LRU算法簡介

LRU是 Least Recently Used 的縮寫，即 最近最少使用 ，是一種常見的頁面置換算法。

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

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

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

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

有序；
如果應(yīng)用開滿3個了，要淘汰最不常用的應(yīng)用，每次新訪問應(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)圖

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

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

巧用LinkedHashMap

我們查看Java的 LinkedHashMap 使用說明。

LinkedHashMap使用說明

翻譯：這種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) ，主要看第三個參數(shù)：

order參數(shù)

true -> access-order // false -> insertion-order 即按照訪問時間排序，還是按照插入的時間來排序

// 構(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 方法：什么時候移除最年長的元素。

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

手寫LRU

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

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

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

DoubleLinkedList示意圖

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

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

通過上邊的示意圖，我們可以得知 節(jié)點(diǎn) 應(yīng)該要儲存的內(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對象

DoubleLinkedList初始化示意圖

還是通過上邊的示意圖，我們可以得知 DoubleLinkedList對象 應(yīng)該要儲存的內(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;
}

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

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

第四步：LRU對象屬性

cacheSize

private int cacheSize;

map

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

doubleLinkedList

DoubleLinkedList<Integer, String> doubleLinkedList;

第五步：LRU對象的方法

構(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);
    }
}

第六步：測試

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));
}