文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

彻底弄懂Redis的LRU淘汰策略

2024-04-02 19:55

关注

今天我们这篇文章的目的是要 搞懂LRU淘汰策略 以及 实现一个LRU算法 。

文章会结合图解循序渐进的讲解,跟着我的思路慢慢来就能看懂,我们开始吧。

文章导读

Redis的淘汰策略

为什么要有淘汰策略呢?

因为存储内存的空间是有限的,所以需要有淘汰的策略。

Redis的清理内存淘汰策略有哪些呢?

LRU算法简介

LRU是 Least Recently Used 的缩写,即 最近最少使用 ,是一种常见的页面置换算法。

我们手机的后台窗口(苹果手机双击Home的效果),他总是会把最近常用的窗口放在最前边,而最不常用的应用窗口,就排列在后边了,如果再加上只能放置N个应用窗口的限制,淘汰最不常用的最近最少用的应用窗口,那就是一个活生生的 LRU 。

实现思想推导

手机应用案例

从上边的示意图,我们可以分析出这么几个点:

推导图

通过上边的推导,我们就能得出, LRU 算法核心是 HashMap + DoubleLinkedList 。

思想搞明白了,我们接下来编码实现。

巧用LinkedHashMap

我们查看Java的 LinkedHashMap 使用说明。

LinkedHashMap使用说明

翻译:这种Map结构很适合构建LRU缓存。

继承 LinkedHashMap 实现 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());
    }
}

重点讲解:

构造方法: super(capacity, 0.75F, true) ,主要看第三个参数:

order参数

true -> access-order // false -> insertion-order 即按照访问时间排序,还是按照插入的时间来排序

// 构造方法改成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");
  // 构造方法order=true,输出:[2,3,1],
  // 构造方法order=false,输出:[1,2,3],
  System.out.println(lruDemo.keySet());
}

removeEldestEntry 方法:什么时候移除最年长的元素。

通过上面,相信大家对 LRU 算法有所理解了,接下来我们不依赖JDK的 LinkedHashMap ,通过我们自己的理解,动手实现一个 LRU 算法,让我们的 LRU 算法刻入我们的大脑。

手写LRU

上边的推导图中可以看出,我们用 HashMap 来做具体的数据储存,但是我们还需要构造一个 DoubleLinkedList 对象(结构体)来储存 HashMap 的具体 key 顺序关系。

第一步:构建DoubleLinkedList对象

所以我们现在 第一步 ,就是构建一个 DoubleLinkedList 对象:

DoubleLinkedList示意图

我们可以从 HashMap 源码中找一些灵感,他们都是使用一个 Node 静态内部类来储存节点的值。

第二步:构建节点

通过上边的示意图,我们可以得知 节点 应该要储存的内容:

翻译成代码:

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对象 应该要储存的内容:

翻译成代码:

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

从头添加节点

从头添加节点

翻译成代码:

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

删除节点

删除节点

翻译成代码:

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

获取最后一个节点

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

第四步:LRU对象属性

cacheSize

private int cacheSize;

map

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

doubleLinkedList

DoubleLinkedList<Integer, String> doubleLinkedList;

第五步:LRU对象的方法

构造方法

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

refreshNode刷新节点

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

get节点

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

put节点

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, "美团");
    lruDemo.put(2, "微信");
    lruDemo.put(3, "抖音");
    lruDemo.put(4, "微博");
    System.out.println(lruDemo.map.keySet());
 
    System.out.println(lruDemo.get(2));
}

总结

LRU 算法到这里就写完啦,完整的代码可以从阅读原文的链接地址获取。

到此这篇关于彻底弄懂Redis的LRU淘汰策略的文章就介绍到这了,更多相关Redis LRU淘汰策略内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯