JS简单实现(FIFO 、LRU、LFU)缓存淘汰算法

FIFO 、LRU、LFU缓存算法算是比较简单的，它们的区别是当缓存空间满的时候，其对数据淘汰策略不同而已，这里的话我就选择了JavaScript来进行演示FIFO 、LRU、LFU的实现。希望能帮助大家更好的理解。

1. FIFO 算法实现

FIFO (First Input First Output)可以说是最简单的一种缓存算法，通过设置缓存上限，当达到了缓存上限的时候，按照先进先出的策略进行淘汰，再增加进新的 key-value。

实现的可以创建一个map对象来保存键值信息

然后创建keys的数组用来进行淘汰判断

代码示例:

var FIFOCache = function (limit) {
    this.limit = limit || 10;
    this.map = {};
    this.keys = [];
};

实现get函数其实很简单，通过map返回对应值就行

代码示例:

FIFOCache.prototype.get = function (key) { 
    return this.map[key];
};

在set函数中,先keys长度是否达到限制

没达到限制直接追加

如果达到限制判断key是否已经存在，存在将key删除，否则默认删除keys的第一个数据与对应map中的值

代码示例:

FIFOCache.prototype.set = function (key,value) { 
    if (this.keys.length >= this.limit) {
        let i = this.keys.indexOf(key);
        if (i >= 0)
            this.keys.splice(i, 1);
        else
            delete this.map[this.keys.shift()];
    }
    this.keys.push(key);
    this.map[key] = value;
};

2. LRU 算法实现

LRU（Least recently used）算法算是最常见的缓存淘汰算法，根据数据的历史访问记录来进行淘汰数据，其核心思想是如果数据最近被访问过，那么将来被访问的几率也更高。

如果你搜索java的LRU实现，很多都是通过LinkedHashMap来实现的。我这里就照着网上搜索的相关原理通过js来实现一下。

这里稍微注意的是淘汰的方向，有的是淘汰数组最前的，有的是淘汰最后的。可最后的效果都差不多，这里的话我就以淘汰首位的数据来举例编写。

开始的代码跟上面的FIFO实现差不多

代码示例:

var LRUCache = function (capacity) {
    this.limit = limit || 2;
    this.map = {};
    this.keys = [];
};

实现get函数一样是通过map返回对应值，不过需要这里多了一个update函数，用来切换key位置，将最新访问的数据置到最后。

代码示例:

LRUCache.prototype.get = function (key) {
    let r = -1;
    if (typeof this.map[key] != "undefined") {
        r = this.map[key];
        this.update(key);
    }
    return r;
};

LRUCache.prototype.update = function (key) {
    let idx = this.keys.indexOf(key);
    if (idx != this.keys.length - 1) {
        // 删除之前位置
        this.keys.splice(idx, 1);
        // 重新插入到最后
        this.keys.push(key);
    }
};

set函数判断map中key是否存在，存在直接修改值并更新key在keys中的位置

如果不存在，判断keys是否已满，满则删除首位数据，然后将最新数据追加到末位

代码示例:

LRUCache.prototype.set = function (key, value) {
    if(typeof key=="undefined"||typeof value=="undefined") throw new Error('key or value is undefined');
    if (typeof this.map[key] != "undefined") {
        this.update(key);
        this.map[key] = value;
    } else {
        // 判断容量是否满
        if (this.keys.length == this.limit) {
            // 淘汰首位
            delete this.map[this.keys[0]];
            this.keys.splice(0, 1);
        }
        // 插入新值
        this.keys.push(key);
        this.map[key] = value;
    }
};

以下是通过Map实现代码参考：

var LRUCache = function (capacity) {
    this.cache = new Map();
    this.capacity = capacity;
};
LRUCache.prototype.get = function (key) {
    let cache = this.cache;
    if (cache.has(key)) {
        let temp = cache.get(key);
        cache.delete(key);
        cache.set(key, temp);
        return temp;
    } else {
        return -1;
    }
};
LRUCache.prototype.put = function (key, value) {
    let cache = this.cache;
    if (cache.has(key)) {
        cache.delete(key);
    } else if (cache.size >= this.capacity) {
        cache.delete(cache.keys().next().value);
    }
    cache.set(key, value);
};

3. LFU 算法实现

LFU（Least Frequently Used ）也是一种常见的缓存算法。当空间满时，通过访问次数，淘汰问次数最小的数据。

如果访问次数全部一样则默认淘汰最初添加的数据

根据需求，定义一个freqMap用来保存访问频率数据

代码示例:

var LFUCache = function (capacity) {
    this.limit = capacity;
    this.map = {};
    this.freqMap = {};
};

get函数跟上面的LRU算法的差不多，不过这里this.map里所保存的对象格式为

{
    value:"value", // 存值
    freq:1//<== 频率
}

代码示例:

LFUCache.prototype.get = function (key) {
    let r = -1;
    if (typeof this.map[key] != "undefined") {
        let o = this.map[key];
        r = o.value;
        //更新频率记录
        this.updateL(key, o);
    }
    return r;
};

所以更新频率的时候通过对象保存的freq字段从频率记录this.freqMap中寻找，删除原始记录后重新追加到新的记录

代码示例:

LFUCache.prototype.updateL = function (key, obj) {
    let freq = obj.freq;
    let arr = this.freqMap[freq];
    // 删除原频率记录
    this.freqMap[freq].splice(arr.indexOf(key), 1);
    // 清理
    if (this.freqMap[freq].length == 0) delete this.freqMap[freq];
    // 跟新频率
    freq = obj.freq = obj.freq + 1;
    if (!this.freqMap[freq]) this.freqMap[freq] = [];
    this.freqMap[freq].push(key);
};

set函数判断逻辑跟LRU的差不多，区别在容量满的时候,默认取freqMap中第一个索引对应的keys数组中第一个key，删除key对应的数据

代码示例:

LFUCache.prototype.set = function (key, value) {
    if (this.limit <= 0) return;
    if(typeof key=="undefined"||typeof value=="undefined") throw new Error('key or value is undefined');
    // 存在则直接更新
    if (typeof this.map[key] == "undefined") {
        // 获取频率 key
        // 判断容量是否满
        if (Object.keys(this.map).length == this.limit) {
            let fkeys = Object.keys(this.freqMap);
            let freq = fkeys[0];
            // 获取key集合
            let keys = this.freqMap[freq];
            // 淘汰首位
            delete this.map[keys.shift()]; 
            // delete this.map[keys[0]];
            // keys.splice(0, 1);
            // 清理
            if (this.freqMap[freq].length == 0) delete this.freqMap[freq];
        }
        // 频率记录是否存在
        if (!this.freqMap[1]) this.freqMap[1] = [];
        // 插入新值
        this.freqMap[1].push(key);
        this.map[key] = {
            value: value,
            freq: 1 // 默认的频率
        };
    } else {
        this.map[key].value = value;
        //更新频率记录
        this.updateL(key, this.map[key]);
    }
};