前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LRU缓存机制

LRU缓存机制

作者头像
木子星兮
发布2020-07-16 17:07:57
1K0
发布2020-07-16 17:07:57
举报
文章被收录于专栏:前端小码农

JavaScript实现LeetCode第146题:LRU缓存机制[1]

题目描述

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制[2]。它应该支持以下操作:获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

示例:

代码语言:javascript
复制
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

解题思路

思路:哈希表(Map) + 双向链表

这个问题可以用哈希表,辅以双向链表记录键值对的信息。所以可以在 O(1) 时间内完成 put 和 get 操作,同时也支持 O(1)) 删除第一个添加的节点。

使用双向链表的一个好处是不需要额外信息删除一个节点,同时可以在常数时间内从头部或尾部插入删除节点。一个需要注意的是,在双向链表实现中,这里使用一个伪头部和伪尾部标记界限,这样在更新的时候就不需要检查是否是 null 节点。

解题步骤:

  1. 使用Map记录缓存值,使用链表记录缓存操作顺序,最后操作的缓存放在链表头部,链表尾部就是最少操作的缓存
  2. 读取缓存时,更新缓存操作顺序,将缓存节点从链表中移除, 再将其添加到链表头部, 移除节点时要保证链表的连续性,为了在 O(1)时间完成该操作,需要使用双向链表
  3. 设置缓存时
    • 如果是已存在的缓存,则直接更新缓存值即可,并更新缓存操作的顺序;
    • 如果是不存在的缓存,则将缓存加到链表头部, 添加后如果缓存超出上限, 则将链表尾部的缓存清掉

解题方法

代码语言:javascript
复制
class DoubleLinkList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    /**
     * 链表头部插入
     * 1.如果头部和尾部都存在, 则直接在头部之前插入
     *     修改原来head的prev指向当前node, node的next指向原先的head, node的prev设置为null修改head为当前node
     * 2.如果头部或尾部不存在, 则设置当前node为head和tail
     *     node的next指向null, node的prev设置为nul
     */
    unshift(node) {
         
        if (this.head && this.tail) {
            node.prev = null;
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        } else {
            node.prev = node.next = null;
            this.head = this.tail = node;
        }

        this.length++;
        return node;
    /**
     * 链表尾部删除
     * 1.判断tail是否存在
     * 2.判断head和tail是否相等
     *    相等: this.head = this.tail = null;
     *    不相等: this.tail.prev.next = null; this.tail = this.tail.prev;
     */
    pop() {
        if (this.tail) {
            const node = this.tail;
            if (this.head === this.tail) {
                this.head = this.tail = null;
            } else {
                this.tail.prev.next = null;
                this.tail = this.tail.prev;
            }
            this.length--;
            return node;
        }
    }
    /**
     * 删除具体的某个节点
     * 1.node等于head
     * 2.node等于tail
     * 3.node即不等于head, 也不等于tail
     */
    remove(node) {
        if (node !== this.head && node !== this.tail) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        if (node === this.head) {
            this.head = this.head.next;
        }
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }
        this.length--;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.list = new DoubleLinkList();
        this.map = new Map();
    }

    get(key) {
        let node = this.map.get(key);
        if (node) {
            this.list.remove(node);
            this.list.unshift(node);
            return node.value;
        } else {
            return -1;
        }
    }

    put(key, value) {
        let node = this.map.get(key);
        if (node) {
            node.value = value;
            this.list.remove(node);
            this.list.unshift(node);
        } else {
            node = { key, value };
            this.list.unshift(node);
            this.map.set(key, node);
            if (this.list.length > this.capacity) {
                const tail = this.list.pop();
                this.map.delete(tail.key);
            }
        }
    }
}

复杂度分析

  • 时间复杂度:对于 put 和 get 都是 O(1)。
  • 空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity + 1 个元素。

参考资料

[1]LRU缓存机制: https://leetcode-cn.com/problems/lru-cache/

[2]LRU (最近最少使用) 缓存机制: https://baike.baidu.com/item/LRU

[3]官方题解: https://leetcode-cn.com/problems/lru-cache/solution/lru-huan-cun-ji-zhi-by-leetcode/

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 牧码的星星 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 解题思路
  • 解题方法
  • 复杂度分析
    • 参考资料
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档