LRU算法 学习笔记

LRU算法是一种常见的页面置换算法，选择内存中最近最久未使用的页面予以淘汰，也就是根据数据的历史访问记录来淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

一般LRU实现使用链表维护，实现LRU算法的步骤有三步：

• 新数据从链表头部插入
• 当缓存命中时，此数据移动到链表头部
• 当链表满时，将链表尾部的数据丢弃

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。实现代价是命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

如何使用JS实现？

使用数组模拟链表（后面要用Map替换掉降低复杂度），提供两个方法，一个用于加入某个kv值，但需要判断链表是否已满，这里我使用set标识，还有一种方法用于设定某个值被命中，也就是标记它为最新使用，我使用hit标识。hit方法需要根据值来找键，普通的数据结构需要O(n)的时间满足这个操作，但可以使用JavaScript ES6提供的Map，就可以降低为O(1)，它既能保持键值对还能记住插入顺序。

那么提供一个数据结构：

let LRUCache = function (capacity) {
    this.capacity = capacity;
    this.cache = new Map();
}

LRUCache.prototype.set = function (key, value) {
    if (this.cache.has(key)) {
        // 如果cache里已经有这个值了，那就做一次更新，相当于做了一次hit
        this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
        // 这里要打算往cache里加入新值，但需要提前判断容量，如果容量不够，就需要删除尾部
        this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
}

LRUCache.prototype.hit = function (key) {
    if (this.cache.has(key)) {
        // hit的原理是先删除再新加入
        this.cache.delete(key);
        this.cache.set(key, this.cache.get(key));
        return 1; // 表示命中成功，return啥随便你自己定
    }
    return -1; // 表示命中了个寂寞，return啥还是随便你自己定
}

可以用来解决LRU问题。

扩展LRU算法，详情参考：https://www.jianshu.com/p/d533d8a66795

打赏