你还在滥用缓存吗？

介绍一种如何控制缓存体积的缓存淘汰机制：LRU (最近最少使用) 缓存机制。

一、背景介绍

缓存在前端和后端日常开发场景中使用的非常多，使用得当可以很大程度上优化代码执行速度，减少不必要的重复计算。

但是在某些数据量很大或者运行时间长的场景下，滥用缓存可能导致缓存数量庞大，内存无法释放，导致运行卡顿等问题。

因此，针对这种情况建立一套缓存淘汰机制，设置最大缓存数量，达到最大缓存数量时将使用较少的缓存删掉，以此控制缓存占用的空间。

二、LeetCode题目

• LeetCode 146. LRU 缓存机制
• 

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

实现 LRUCache 类：

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

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

示例：

输入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
复制代码

输出

[null, null, null, 1, null, -1, null, -1, 3, 4]
复制代码

解释

const lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
复制代码

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• 最多调用 3 * 104 次 get 和 put

三、思路

1. 使用数组实现，在数组中存储缓存值，每次获取和设置缓存都需要遍历一遍数组，时间复杂度是O(n)；
2. 使用hashMap + 双向链表实现，获取操作直接从map中取，设置和获取操作可能伴随链表节点的衔接变化操作，获取和设置缓存时间复杂度都是O(1)；

四、解法

1. 使用数组实现

• 获取和设置缓存时间复杂度都是O(n)；

/**
 * @class LRU (最近最少使用) 缓存
 * @desc 使用数组实现，时间复杂度O(n)
 * @param {number} capacity 缓存的最大容量
 */
 class LRUCache {
    constructor(capacity) {
        // 缓存的最大容量
        this.capacity = capacity;
        // 缓存列表
        this.list = [];
    }
    /**
     * 获取缓存，未命中缓存返回-1
     * @param {number} key 缓存的唯一标识
     * @return {number} 缓存值
     */
    get(key) {
        const node = this._moveToHead(key);
        return node ? node.value : -1;
    }
    /**
     * 增加缓存
     * @param {number} key 缓存的唯一标识
     * @param {number} value 缓存的值
     * @return {void} 无返回值
     */
    put(key, value) {
        const node = this._moveToHead(key, value);
        if (!node) {
            if (this.list.length === this.capacity) {
                this.list.shift();
            }
            this.list.push({key, value});
        }
    }
    /**
     * 移动节点到头部
     * @param {number} key 缓存的唯一标识
     * @param {number} value 缓存的值
     * @return {Node | null} 匹配到的节点
     */
    _moveToHead(key, value) {
        for (let i = 0; i < this.list.length; i ++) {
            const item = this.list[i];
            if (item.key === key) {
                const node = this.list.splice(i, 1)[0];
                if (value !== undefined) {
                    node.value = value;
                }
                this.list.push(node);
                return node;
            }
        }
        return null;
    }
}

/****************** 以下是测试代码 *****************************************/

const cache = new LRUCache(3);

cache.put(1, 1);
console.log(cache.list.map(e => e.value));
cache.put(2, 2);
console.log(cache.list.map(e => e.value));
cache.put(3, 3);
console.log(cache.list.map(e => e.value));
console.log(cache.get(3));
console.log(cache.list.map(e => e.value));
console.log(cache.get(1));
console.log(cache.list.map(e => e.value));
console.log(cache.get(2));
console.log(cache.list.map(e => e.value));
cache.put(1, 1);
console.log(cache.list.map(e => e.value));
cache.put(4, 4);
console.log(cache.list.map(e => e.value));
cache.put(4, 4);
console.log(cache.list.map(e => e.value));
console.log(cache.get(5));
console.log(cache.list.map(e => e.value));

复制代码

2. hashMap + 双向链表实现

• 获取和设置缓存时间复杂度都是O(1)；

/**
 * @class LRU (最近最少使用) 缓存
 * @param {number} capacity 缓存的最大容量
 */
class LRUCache {
    constructor(capacity) {
        // 缓存的最大容量
        this.capacity = capacity;
        // 缓存的当前存储数量
        this.count = 0;
        // 缓存链表头部
        this.head = null;
        // 缓存链表尾部
        this.tail = null;
        // 缓存映射
        this.map = {};
    }
    /**
     * 获取缓存，未命中缓存返回-1
     * @param {number} key 缓存的唯一标识
     * @return {number} 缓存值
     */
    get(key) {
        let node = this.map[key];
        if (node) {
            this._moveToHead(node);
            return node.value;
        }
        return -1;
    }
    /**
     * 增加缓存
     * @param {number} key 缓存的唯一标识
     * @param {number} value 缓存的值
     * @return {void} 无返回值
     */
    put(key, value) {
        let node = this.map[key];
        if (node) {
            node.value = value;
            this._moveToHead(node);
        } else {
            node = { key, value, pre: null, next: this.head };
            // 第一个节点同时设置为头和尾
            if (this.count === 0) {
                this.head = this.tail = node;
            }
            // 如果缓存节点数量达到最大容量，则需要先删尾节点，然后在头部添加
            if (this.count === this.capacity) {
                delete this.map[this.tail.key];
                this._delTail();
            } else {
                this.count++;
            }
            this._setHead(node);
        }
        this.map[key] = node; // 设置缓存映射
    }
    /**
     * 移动节点到尾部
     * @param {Node} node 当前节点
     * @return {void} 无返回值
     */
    _moveToHead(node) {
        // 如果命中头节点就不必移动了
        if (this.head.key === node.key) {
            return;
        }
        // 如果命中尾节点，需要手动设置尾节点为前一个节点
        if (this.tail.key === node.key && node.pre) {
            this.tail = node.pre;
        }
        // 先删链表中当前的节点，然后在头部添加
        node.pre && (node.pre.next = node.next);
        node.next && (node.next.pre = node.pre);
        // 在头部增加当前节点
        node.pre = null;
        node.next = this.head;
        this._setHead(node);
    }
    /**
     * 设置头节点
     * @param {Node} node 当前节点
     * @return {void} 无返回值
     */
    _setHead(node) {
        this.head.pre = node;
        this.head = node;
    }
    /**
     * 删除尾节点
     * @return {void} 无返回值
     */
    _delTail() {
        this.tail.pre && (this.tail.pre.next = null);
        this.tail = this.tail.pre;
    }
}



/****************** 以下是测试代码 *****************************************/

// 输出链表数组
function logLinkList(node) {
    let tail = node;
    let list = [tail];
    while(tail.next) {
        list.push(tail.next);
        tail = tail.next;
    }
    return list;
}


const cache = new LRUCache(3);

cache.put(1, 1);
console.log(logLinkList(cache.head).map(e => e.value));
cache.put(2, 2);
console.log(logLinkList(cache.head).map(e => e.value));
cache.put(3, 3);
console.log(logLinkList(cache.head).map(e => e.value));
console.log(cache.get(3));
console.log(logLinkList(cache.head).map(e => e.value));
console.log(cache.get(1));
console.log(logLinkList(cache.head).map(e => e.value));
console.log(cache.get(2));
console.log(logLinkList(cache.head).map(e => e.value));
cache.put(1, 1);
console.log(logLinkList(cache.head).map(e => e.value));
cache.put(4, 4);
console.log(logLinkList(cache.head).map(e => e.value));
cache.put(4, 4);
console.log(logLinkList(cache.head).map(e => e.value));


复制代码