美文网首页
实现LRU缓存淘汰算法

实现LRU缓存淘汰算法

作者: 随风_d6a2 | 来源:发表于2022-01-10 21:31 被阅读0次

    LRU就是一种缓存淘汰策略。

    计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。那么,什么样的数据,我们判定为「有用的」的数据呢?

    LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。

    算法描述

    运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制

    实现 LRUCache 类:

    • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
    • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
    • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

    注意哦,get 和 put 方法必须都是 O(1) 的时间复杂度!

    示例

    /* 缓存容量为 2 */
    LRUCache cache = new LRUCache(2);
    // 你可以把 cache 理解成一个队列
    // 假设左边是队头,右边是队尾
    // 最近使用的排在队头,久未使用的排在队尾
    // 圆括号表示键值对 (key, val)
    
    cache.put(1, 1);
    // cache = [(1, 1)]
    cache.put(2, 2);
    // cache = [(2, 2), (1, 1)]
    cache.get(1);       // 返回 1
    // cache = [(1, 1), (2, 2)]
    // 解释:因为最近访问了键 1,所以提前至队头
    // 返回键 1 对应的值 1
    cache.put(3, 3);
    // cache = [(3, 3), (1, 1)]
    // 解释:缓存容量已满,需要删除内容空出位置
    // 优先删除久未使用的数据,也就是队尾的数据
    // 然后把新的数据插入队头
    cache.get(2);       // 返回 -1 (未找到)
    // cache = [(3, 3), (1, 1)]
    // 解释:cache 中不存在键为 2 的数据
    cache.put(1, 4);    
    // cache = [(1, 4), (3, 3)]
    // 解释:键 1 已存在,把原始值 1 覆盖为 4
    // 不要忘了也要将键值对提前到队头
    
    

    算法设计

    分析上面的操作过程,要让 put 和 get 方法的时间复杂度为 O(1),我们可以总结出 cache 这个数据结构必要的条件:查找快,插入快,删除快,有顺序之分。

    因为显然 cache 必须有顺序之分,以区分最近使用的和久未使用的数据;而且我们要在 cache 中查找键是否已存在;如果容量满了要删除最后一个数据;每次访问还要把数据插入到队头。

    那么,什么数据结构同时符合上述条件呢?哈希表查找快,但是数据无固定顺序;链表有顺序之分,插入删除快,但是查找慢。所以结合一下,形成一种新的数据结构:哈希链表。

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

    LRU 缓存算法的核心数据结构就是哈希链表:双向链表和哈希表的结合体。这个数据结构长这样:

    image

    思想很简单,就是借助哈希表赋予了链表快速查找的特性嘛:可以快速查找某个 key 是否存在缓存(链表)中,同时可以快速删除、添加节点。回想刚才的例子,这种数据结构是不是完美解决了 LRU 缓存的需求?

    代码实现

    • 首先定义双端链表类(包括数据和记录前驱/后继节点的指针
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode next;
    
        public DLinkedNode() {};
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    
    • 双向链表需要提供一些接口api,便于我们操作,主要就是链表的一些操作,画图理解!
    private void addFirst(DLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }
    
    private void moveToFirst(DLinkedNode node) {
        remove(node);
        addFirst(node);
    }
    
    private void remove(DLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    
    // 删除尾结点,并返回头节点
    private DLinkedNode removeLast() {
        DLinkedNode ans = tail.pre;
        remove(ans);
        return ans;
    }
    
    private int getSize() {
        return size;
    }
    
    
    • 确定LRU缓存类的成员变量(链表长度、缓存容量和map映射等)和构造函数。注意:定义虚拟头尾结点便于在头部插入元素或者寻找尾部元素!并在构造函数初始化。
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
    
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
    
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }
    
    
    • 核心代码:get和put方法,都是先根据key获取这个映射,根据映射节点的情况(有无)进行操作。注意:
      • get和put都在使用,所以数据要提前!
      • put操作如果改变了双端链表长度(不是仅改变值),需要先判断是否达到最大容量!
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 将该数据移到双端队列头部
        moveToFirst(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node != null) {
            // 如果存在key,先修改值,然后移动到头部
            node.value = value;
            moveToFirst(node);
        } else {
            // 如果key存在,先考虑是否超过容量限制
            if (capacity == cache.size()) {
                // 删除尾结点和hash表中对应的映射!
                DLinkedNode tail = removeLast();
                cache.remove(tail.key);
                --size;
            }
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 建立映射,并更新双向链表头部
            cache.put(key, newNode);
            addFirst(newNode);
            ++size;
        }
    }
    
    

    完整代码如下:

    class LRUCache {
    
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode pre;
            DLinkedNode next;
    
            public DLinkedNode() {};
            public DLinkedNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    
        private Map<Integer, DLinkedNode> cache = new HashMap<>();
        private int size;
        private int capacity;
        // 虚拟头尾结点便于在头部插入元素或者寻找尾部元素!
        private DLinkedNode head, tail;
    
        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.pre = head;
        }
    
        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 将该数据移到双端队列头部
            moveToFirst(node);
            return node.value;
        }
    
        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node != null) {
                // 如果存在key,先修改值,然后移动到头部
                node.value = value;
                moveToFirst(node);
            } else {
                // 如果key存在,先考虑是否超过容量限制
                if (capacity == cache.size()) {
                    // 删除尾结点和hash表中对应的映射!
                    DLinkedNode tail = removeLast();
                    cache.remove(tail.key);
                    --size;
                }
                DLinkedNode newNode = new DLinkedNode(key, value);
                // 建立映射,并更新双向链表头部
                cache.put(key, newNode);
                addFirst(newNode);
                ++size;
            }
        }
    
        private void addFirst(DLinkedNode node) {
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }
    
        private void moveToFirst(DLinkedNode node) {
            remove(node);
            addFirst(node);
        }
    
        private void remove(DLinkedNode node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
    
        // 删除尾结点,并返回头节点
        private DLinkedNode removeLast() {
            DLinkedNode ans = tail.pre;
            remove(ans);
            return ans;
        }
    
        private int getSize() {
            return size;
        }
    }
    
    

    总结与补充

    • LRU缓存机制的核心:双向链表(保证元素有序,且能快速的插入和删除)+hash表(可以快速查询)
    • 为什么使用双向链表?因为:对于删除操作,使用双向链表,我们可以在O(1)的时间复杂度下,找到被删除节点的前节点。
    • 为什么要在链表中同时存键值,而不是只存值?因为:当缓存容量满了之后,我们不仅要在双向链表中删除最后一个节点(即最久没有使用的节点),还要把cache中映射到该节点的key删除,这个key只能有Node得到(即hash表不能通过值得到键)。

    作者:_code_x
    链接:https://www.jianshu.com/p/b7fed77324b9
    来源:简书
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    相关文章

      网友评论

          本文标题:实现LRU缓存淘汰算法

          本文链接:https://www.haomeiwen.com/subject/bgjvcrtx.html