牛逼,手写Redis的LRU淘汰策略「建议收藏」

牛逼,手写Redis的LRU淘汰策略「建议收藏」true -> access-order // false -> insertion-order即按照访问时间排序,还是按照插入的时

大家好,欢迎来到IT知识分享网。

牛逼,手写Redis的LRU淘汰策略「建议收藏」

LRU

Redis的淘汰策略

为什么要有淘汰策略呢?

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

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

牛逼,手写Redis的LRU淘汰策略「建议收藏」

Redis内存淘汰策略

LRU算法简介

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

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

牛逼,手写Redis的LRU淘汰策略「建议收藏」

手机后台应用窗口

实现思想推导

牛逼,手写Redis的LRU淘汰策略「建议收藏」

手机应用案例

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

  1. 有序;
  2. 如果应用开满3个了,要淘汰最不常用的应用,每次新访问应用,需要把数据插入队头(按照业务可以设定左右哪一边是队头);
  3. O(1)复杂度是我们查找数据的追求,我们什么结构能够实现快速的O(1)查找呢?
牛逼,手写Redis的LRU淘汰策略「建议收藏」

推导图

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

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

巧用LinkedHashMap

我们查看JavaLinkedHashMap使用说明。

牛逼,手写Redis的LRU淘汰策略「建议收藏」

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

IT知识分享网

重点讲解:

  1. 构造方法:super(capacity, 0.75F, true),主要看第三个参数:
    1. order参数
    2. 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());
      }

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

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

手写LRU

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

第一步:构建DoubleLinkedList对象

  1. 所以我们现在第一步,就是构建一个DoubleLinkedList对象:
牛逼,手写Redis的LRU淘汰策略「建议收藏」

DoubleLinkedList示意图

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

第二步:构建节点

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

  1. key
  2. value
  3. prev节点
  4. next节点

翻译成代码:

IT知识分享网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对象

牛逼,手写Redis的LRU淘汰策略「建议收藏」

DoubleLinkedList初始化示意图

还是通过上边的示意图,我们可以得知DoubleLinkedList对象应该要储存的内容:

  1. 头节点
  2. 尾节点

翻译成代码:

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

从头添加节点

牛逼,手写Redis的LRU淘汰策略「建议收藏」

从头添加节点

翻译成代码:

IT知识分享网public void addHead(Node<K, V> node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}

删除节点

牛逼,手写Redis的LRU淘汰策略「建议收藏」

删除节点

翻译成代码:

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算法到这里就写完啦,完整的代码可以从阅读原文的链接地址获取。

原文链接:https://mp.weixin.qq.com/s?__biz=MzkwNjMwMTgzMQ==&mid=2247491691&idx=1&sn=81bca6151094ac5dfe164ec34b512f82

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/6147.html

(0)
上一篇 2022-12-18 07:50
下一篇 2022-12-18 08:10

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信