当前位置: article > 正文

面试必问：请手写淘汰算法LRU与LFU_redis的lru和ifu手写

作者：我家小花儿 | 2024-08-09 01:31:43

踩

redis的lru和ifu手写

从Redis看淘汰算法

虽然「Redis」有自己的过期策略来删除过期的数据（惰性删除和抽样删除）。这其中具体的删除原理本章不做详细介绍。但是也会存在Redis删不过来导致内存占满的情况。所以「Redis」使用了一些淘汰算法来处理这些来不及删除的数据。

下面我们来说说「LRU」淘汰算法。

LRU算法

定义

「LRU」算法中，需要有一个链表来存放数据，当某个元素被访问时，这个元素会被移动到表头。当空间满了，会剔除掉链表末尾的元素。

其核心就是保留最近使用的元素。

代码实现

我们来看看代码实现：


public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
 
    private int capacity;
 
    LRULinkedHashMap(int capacity) {
        // 初始大小，0.75是装载因子，true是表示按照访问时间排序
        super(capacity, 0.75f, true);
        //传入指定的缓存最大容量
        this.capacity = capacity;
    }
 
    /**
     * 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
 
    }
}

我们来写个单元测试测试下：


@org.junit.Test
public void test() {
    LRULinkedHashMap<String, Integer> map = new LRULinkedHashMap<>(4);
    map.put("A", 1);
    map.put("B", 2);
    map.put("C", 3);
 
    System.out.println(map);
    map.get("B");
    System.out.println(map);
    map.put("D",4);
    map.put("E",5);
    System.out.println(map);
}

测试结果：


{A=1, B=2, C=3}
{A=1, C=3, B=2}
{C=3, B=2, D=4, E=5}

利用LinkedHashMap的特性：访问的数据会排到最前面。

我们来图解上面代码：

❝
（1）我们创建一个容量为「4」的LinkedHashMap，并put初始值：A ->B -> C

（2）查询值「key」为「B」的值，「B」会重新排列到最前面。顺序为：A ->C -> B

（3）put新值「D」，顺序为：A ->C ->B ->D

（4）put新值「E」，最末尾的值「A」被淘汰。顺序为：C ->B ->D ->E
❞

LFU算法

定义

在「Redis」 4.0中引入了一个新的淘汰算法LFU，可以说是LRU的进阶版。

LFU算法规定的是按最近访问的频率进行淘汰，与LRU算法相比，LFU更精准的表示了一个「key」被访问的热度。

为甚么Redis要引入LFU算法呢？

如果一个「key」长时间没有没访问，只是刚刚被用户偶尔访问了一下。在LRU算法下，这个「key」是不容易被淘汰的。但如果是LFU算法，会追踪最近一段时间的访问频率。就是说在LFU算法下，只是最近偶尔被访问一次是不足以说明这个「key」是热点数据。

算法示意图：

如图，算法将访问次数最高的放在最前面，容量满后会删除末尾的元素。

代码实现


public class LFUCache {
 
    private Map<Integer, ListNode> map;
 
    /**
     * 访问次数哈希表，使用 ListNode[] 也可以，不过要占用很多空间
     */
    private Map<Integer, DoubleLinkedList> frequentMap;
 
    /**
     * 外部传入的容量大小
     */
    private Integer capacity;
 
    /**
     * 全局最高访问次数，删除最少使用访问次数的结点时会用到
     */
    private Integer minFrequent = 1;
 
 
    public LFUCache(int capacity) {
        map = new HashMap<Integer, ListNode>(capacity);
        frequentMap = new HashMap<Integer, DoubleLinkedList>();
        this.capacity = capacity;
    }
 
    /**
     * get 一次操作，访问次数就增加 1；
     * 从原来的链表调整到访问次数更高的链表的表头
     *
     * @param key
     * @return
     */
    public int get(int key) {
        // 测试测出来的，capacity 可能传 0
        if (capacity == 0) {
            return -1;
        }
 
        if (map.containsKey(key)) {
            // 获得结点类
            ListNode listNode = removeListNode(key);
 
            // 挂接到新的访问次数的双向链表的头部
            int frequent = listNode.frequent;
            addListNode2Head(frequent, listNode);
            return listNode.value;
        } else {
            return -1;
        }
    }
 
    /**
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
 
        // 如果 key 存在，就更新访问次数 + 1，更新值
        if (map.containsKey(key)) {
            ListNode listNode = removeListNode(key);
 
            // 更新 value
            listNode.value = value;
            int frequent = listNode.frequent;
            addListNode2Head(frequent, listNode);
            return;
        }
 
        // 如果 key 不存在
        // 1、如果满了，先删除访问次数最小的的末尾结点，再删除 map 里对应的 key
        if (map.size() == capacity) {
            // 1、从双链表里删除结点
            DoubleLinkedList doubleLinkedList = frequentMap.get(minFrequent);
            ListNode removeNode = doubleLinkedList.removeTail();
 
            // 2、删除 map 里对应的 key
            map.remove(removeNode.key);
        }
 
        // 2、再创建新结点放在访问次数为 1 的双向链表的前面
        ListNode newListNode = new ListNode(key, value);
        addListNode2Head(1, newListNode);
        map.put(key, newListNode);
 
        // 【注意】因为这个结点是刚刚创建的，最少访问次数一定为 1
        this.minFrequent = 1;
    }
 
    // 以下部分主要是结点类和双向链表的操作
 
    /**
     * 结点类，是双向链表的组成部分
     */
    private class ListNode {
        private int key;
        private int value;
        private int frequent = 1;
        private ListNode pre;
        private ListNode next;
 
        public ListNode() {
        }
 
        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
 
    /**
     * 双向链表
     */
    private class DoubleLinkedList {
        /**
         * 虚拟头结点，它无前驱结点
         */
        private ListNode dummyHead;
        /**
         * 虚拟尾结点，它无后继结点
         */
        private ListNode dummyTail;
 
        /**
         * 当前双向链表的有效结点数
         */
        private int count;
 
        public DoubleLinkedList() {
            // 虚拟头尾结点赋值多少无所谓
            this.dummyHead = new ListNode(-1, -1);
            this.dummyTail = new ListNode(-2, -2);
 
            dummyHead.next = dummyTail;
            dummyTail.pre = dummyHead;
            count = 0;
        }
 
        /**
         * 把一个结点类添加到双向链表的开头（头部是最新使用数据）
         *
         * @param addNode
         */
        public void addNode2Head(ListNode addNode) {
            ListNode oldHead = dummyHead.next;
            // 两侧结点指向它
            dummyHead.next = addNode;
            oldHead.pre = addNode;
            // 它的前驱和后继指向两侧结点
            addNode.pre = dummyHead;
            addNode.next = oldHead;
            count++;
        }
 
        /**
         * 把双向链表的末尾结点删除（尾部是最旧的数据，在缓存满的时候淘汰）
         *
         * @return
         */
        public ListNode removeTail() {
            ListNode oldTail = dummyTail.pre;
            ListNode newTail = oldTail.pre;
 
            // 两侧结点建立连接
            newTail.next = dummyTail;
            dummyTail.pre = newTail;
 
            // 它的两个属性切断连接
            oldTail.pre = null;
            oldTail.next = null;
 
            // 重要：删除一个结点，当前双向链表的结点个数少 1
            count--;
            return oldTail;
        }
    }
 
 
    /**
     * 将原来访问次数的结点，从双向链表里脱离出来
     *
     * @param key
     * @return
     */
    private ListNode removeListNode(int key) {
        // 获得结点类
        ListNode deleteNode = map.get(key);
 
        ListNode preNode = deleteNode.pre;
        ListNode nextNode = deleteNode.next;
        // 两侧结点建立连接
        preNode.next = nextNode;
        nextNode.pre = preNode;
        // 删除去原来两侧结点的连接
        deleteNode.pre = null;
        deleteNode.next = null;
 
        // 维护双链表结点数
        frequentMap.get(deleteNode.frequent).count--;
 
        // 【注意】维护 minFrequent
        // 如果当前结点正好在最小访问次数的链表上，并且移除以后结点数为 0，最小访问次数需要加 1
        if (deleteNode.frequent == minFrequent && frequentMap.get(deleteNode.frequent).count == 0) {
            minFrequent++;
        }
 
        // 访问次数加 1
        deleteNode.frequent++;
        return deleteNode;
    }
 
 
    /**
     * 把结点放在对应访问次数的双向链表的头部
     *
     * @param frequent
     * @param addNode
     */
    private void addListNode2Head(int frequent, ListNode addNode) {
        DoubleLinkedList doubleLinkedList;
 
        // 如果不存在，就初始化
        if (frequentMap.containsKey(frequent)) {
            doubleLinkedList = frequentMap.get(frequent);
        } else {
            doubleLinkedList = new DoubleLinkedList();
        }
 
        // 添加到 DoubleLinkedList 的表头
        doubleLinkedList.addNode2Head(addNode);
        frequentMap.put(frequent, doubleLinkedList);
    }
 
}

测试代码：


@Test
public void test() {
    LFUCache cache = new LFUCache(3);
 
    //tail ->  head
    // ①[1,2,3]
    cache.put(1, 1);
    cache.put(2, 2);
    cache.put(3, 3);
 
    // ②[2,3,1]
    int i = cache.get(1);
    int i1 = cache.get(1);
 
    // ③[3,2,1]
    cache.get(2);
    cache.put(4,4);
 
    // ④[4,1,2]
    System.out.println(cache.map.keySet());
}

运行结果：

我们来分析下：

❝
（1）设容量为「3」，最开始put值，「map」 （取的「key」）为[1，2，3]，初始每个元素访问计数为1；

（2）get获取两次「1」，「1」的计数为1+2=3次，map为[2，3，1]；

（3）get获取「2」一次，「2」的计数为1+1=2次，map为[3，2，1]；

（4）put值4，由于map容量达到上限，访问次数最少的「1」被淘汰。由于「4」的计数为1次，「4」排到最末尾。map值为[4，1，2]。
❞

总结

由上面可知。LRU算法和LFU算法有各自的特点，我们应该根据实际业务使用情况去使用。

往期推荐

扫码二维码，获取更多精彩。或微信搜Lvshen_9，可后台回复获取资料


1.回复"java" 获取java电子书；
 
2.回复"python"获取python电子书；
 
3.回复"算法"获取算法电子书；
 
4.回复"大数据"获取大数据电子书；
 
5.回复"spring"获取SpringBoot的学习视频。
 
6.回复"面试"获取一线大厂面试资料
 
7.回复"进阶之路"获取Java进阶之路的思维导图
 
8.回复"手册"获取阿里巴巴Java开发手册(嵩山终极版)
 
9.回复"总结"获取Java后端面试经验总结PDF版
 
10.回复"Redis"获取Redis命令手册，和Redis专项面试习题（PDF）

另：点击【我的福利】有更多惊喜哦。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】