LRU & LFU

什么是 LRU

LRU （Least recently used：最近最少使用）算法在缓存写满的时候，会根据所有数据的访问记录，淘汰掉未来被访问几率最低的数据。也就是说该算法认为，最近被访问过的数据，在将来被访问的几率最大。

代码实现

核心原理：每次添加一个数据时，都去缓存（这里假设用队列的先进先出思想来模拟实现）中查找是否存在，如果存在就直接使用该缓存数据，同时把该缓存数据挪到队列的尾部，如果不存在，需要先判断当前缓存存放的数据是否已满，如果满了就先删除队列头部的数据，然后把新的数据添加进缓存中（队列的尾部）。

class LRUCache{
    constructor(capacity){
        this.capacity = capacity;
        this.cache = new Map();
    }
    get(key){
        if(!this.cache.has(key)) return -1;
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }
    set(key, value){
        if(this.cache.has(key)){
            this.cache.delete(key);
        }else{
            if(this.cache.size === this.capacity){
                // 获取到Map中第一个数据的key值，即最近最少访问的key，删之
                const delKey = this.cache.keys().next().value;
                this.cache.delete(delKey);
            }
        }
        this.cache.set(key, value);
    }
}

题目

LRU 缓存

参考

缓存文件置换机制
Cache replacement policies

什么是 LFU