LRU cache实现

[Genluo]

这是一种常见的缓存算法，是计算机系统中一种常见的内存交换（页面置换）算法，我关注这个算法的原因主要是因为在个人项目中使用同构，进行服务器端渲染，为了提高服务器的性能，通过缓存渲染之后的页面来提升服务器的性能，其中使用到的缓存算法就是LRU（最近最久未使用），正巧做的一个算法设计题目也是设计一个LRU缓存机制，这次就根据算法题为例，实现一个LRU缓存

设计原则

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

实现思路

首先应该确定使用什么数据结构来实现，利用hashMap和双向链表实现这个算法，当访问一个节点的时候，如果此节点在链表中，则将此节点移动到链表的首节点，如果此节点不在链表中，则将生成新的节点插入到链表中，如果链表中满了的化，则直接删除链表最后一个节点，产生新的节点，插入到链表首部，通过这种方式可以保证时间复杂度在o(1)之内完成

具体实现

/**
 * @param {number} capacity 容量
 * @description{O（1）时间复杂度内完成对应的操作}
 * @description {对应的数据结构是hashMap和数组}
 */
// { key, value, next, last}
var LRUCache = function(capacity) {
    this.maxCapcity = capacity; // 最大容量
    this.head = null; // 指向链表头结点
    this.hashMap = {}; // 作为hashMap的实现
    this.currentCapcity = 0;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.hashMap[key]) {
        return -1;
    }
    // 将链表和hashMap结合起来处理
    const { last , next } = this.hashMap[key];
    if (last) {
        last.next = next;
    }
    if (next) {
        next.last = last;
    }
    this.hashMap[key].last = null;
    this.hashMap[key].next = null;
    if (this.head !== this.hashMap[key]) {
        this.hashMap[key].next = this.head;
        this.head.last = this.hashMap[key];
        this.head = this.hashMap[key];
    }
    return this.hashMap[key].value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.hashMap[key]) {
        // 重新设置
        this.hashMap[key].value = value;
        this.get(key);
        return;
    }
    if (this.currentCapcity >= this.maxCapcity) {
        // 删除老元素
        let head = this.head;
        while(head.next) {
            head = head.next;
        }
        const { key, last, } = head;
        this.hashMap[key] = null;
        // 处理链表
        if (last) {
            last.next = null;
        }
        this.currentCapcity--;
    }
    // 增加新的元素
    this.hashMap[key] = {
        key,
        value,
        next: null,
        last: null,
    }
    this.hashMap[key].next = this.head;
    if (this.head) {
        this.head.last = this.hashMap[key];
    }
    this.head = this.hashMap[key];
    this.currentCapcity++;
};

相关资料

• 设计并实现一个LRU Cache