LRU 缓存机制

本是古典何须时尚 2022-12-27 08:22 164阅读 0赞

> leetcode 146题 \[medium\]  
> 中：[LRU 缓存机制][LRU]  
> 英：[LRU Cache][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

##### 1. 思路 #####

1.  使用双向链表，链表头为下一次需要剔除出缓存的数据，尾部为最近操作过的数据。（使得put为O(1)的时间复杂度）
    
     *  LRU未满，直接尾部添加新元素
     *  LRU满，删除头节点，尾部新增新数据
2.  使用原生对象(hash)，键值对使得**数据键**与**链表节点**一一对应（使得get为O(1)的时间复杂度）
    
     *  访问LRU，借助hash获取到相应的链表结点，借助链表的双向指针更新链表数据顺序

##### 2. 时间复杂度：O(1) get, put 均为 O(1) #####

##### 3. 空间复杂度：O(n) n为缓存大小 #####

1.  双向链表
2.  原生对象

##### 4. 实现 #####

/** * 双向链表结点 * @param {any} data: 列表结点数据 * @param {ListNode|null} pre: 前指针 * @param {ListNode|null} next: 后指针 */
    var ListNode = function(data, pre=null, next=null){ 
        this.val = data;
        this.pre = pre;
        this.next = next;
    }
    
    /** * @param {number} capacity */
    var LRUCache = function(capacity) { 
        // 大小
        this.currSize = 0;
        this.capacity = capacity;
        // 双向链表记录数据（{key, value}）
        this.headNode = null;
        this.tailNode = null;
        // 对象字典记录：键为数据key，值为其双向链表结点
        this.dict = { };
    };
    
    /** * @param {number} key * @return {number} */
    LRUCache.prototype.get = function(key) { 
        // key in this.dict
        if(key in this.dict){ 
            let node = this.dict[key];
            // node 不是 this.tailNode 时，需要更新位置
            if(node !== this.tailNode){ 
                // pre 存在
                // node 从原位置 “出来”
                if(node.pre){ 
                    // 更新 2 指针
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                // pre 不存在，说明 node 为 this.headNode
                else{ 
                    this.headNode = node.next;
                    this.headNode.pre = null;
                }
                // node 进入新位置（this.tailNode）
                this.tailNode.next = node;
                node.pre = this.tailNode;
                this.tailNode = node;
                this.tailNode.next = null;
            }
            return node.val.value;
        }
        // key not in this.dict
        else return -1;
    };
    
    /** * @param {number} key * @param {number} value * @return {void} */
    LRUCache.prototype.put = function(key, value) { 
        // key in this.dict
        if(key in this.dict){ 
            // 更新数据
            let node = this.dict[key];
            node.val.value = value;
            // 不是tailNode，需要更新位置
            if(this.tailNode !== node){ 
                // node 从原位置 “出来”
                // node 有 pre
                if(node.pre){ 
                    // 更新 2 指针位置
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                }
                // node 无 pre, 说明node是headNode
                else{ 
                    this.headNode = node.next;
                    this.headNode.pre = null;
                }
                // node 进入新位置（结尾）
                this.tailNode.next = node;
                node.pre = this.tailNode;
                this.tailNode = node;
                this.tailNode.next = null;
            }
        }
        // key not in this.dict
        else{ 
            // LRU 满，先剔除headNode
            if (this.currSize >= this.capacity){ 
                delete this.dict[this.headNode.val.key];
                this.headNode = this.headNode.next;
                this.headNode && (this.headNode.pre = null);    // capacity为1时，this.headNode可能为null
                this.currSize--;
            }
    
            // LRU 为空
            if(this.currSize === 0){ 
                this.dict[key] = this.headNode = this.tailNode = new ListNode({ 'key': key, 'value': value});
            }
            // LRU 不为空
            else{ 
                this.dict[key] = this.tailNode.next = new ListNode({ 'key': key, 'value': value}, this.tailNode);
                this.tailNode = this.dict[key];
            }
            // 更新 currSize
            this.currSize++;
        }
    };
    
    /** * Your LRUCache object will be instantiated and called as such: * var obj = new LRUCache(capacity) * var param_1 = obj.get(key) * obj.put(key,value) */

[LRU]: https://leetcode-cn.com/problems/lru-cache/
[LRU Cache]: https://leetcode.com/problems/lru-cache/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/c01a66f9cc8045859028cb8a9f89c58e.png