实现LRU缓存机制

[LuckyWinty]

实现一个LRU过期算法的KV cache, 所有KV过期间隔相同, 满足如下性质:

1. 最多存储n对KV;
2. 如果大于n个, 则随意剔除一个已经过期的KV;
3. 如果没有过期的KV, 则按照LRU的规则剔除一个KV;
4. 查询时如果已经过期, 则返回空;

[LuckyWinty]

class LRUCache {
    constructor(capacity,intervalTime){
        this.cache = new Map();
        this.capacity = capacity;
        this.intervalTime = intervalTime;
    }
    get(key){
        if(!this.cache.has(key)){
            return null
        }
        const tempValue = this.cache.get(key)
        this.cache.delete(key);
        if(Date.now() - tempValue.time > this.intervalTime){
            return null
        }
        this.cache.set(key, {value: tempValue.value, time: Date.now()})
        return tempValue.value
    }
    put(key, value){
        if(this.cache.has(key)){
            this.cache.delete(key)
        }
        if(this.cache.size >= capacity){ //满了
            const keys = this.cache.keys()
            this.cache.delete(keys.next().value)
        }
        this.cache.set(key, {value,time:Date.now()})
    }
}

巧妙地利用了Map结构的key是有序的这个特点。普通Object的key是无序的。

[sinbadmaster]

this.cache.set(key,tempValue) 这次设定之后再次获取这个key的数据不是就已经已没有time了吗？ @LuckyWinty 应该更新一下时间再set回去

[SherryQueen]

交个作业

function LRU(max, timeout) {
  const map = new Map();

  const isTimeout = key => {
    const value = map.get(key);
    if (!value) return true;
    return Date.now() - value.time > timeout;
  };

  return {
    get: key => {
      if (!map.has(key)) return null;
      if (isTimeout(key)) {
        map.delete(key);
        return null;
      }

      return map.get(key).value;
    },

    put: (key, value) => {
      if (map.has(key)) map.delete(key);
      if (map.size === max) {
        // * Map 是有序的, 故最长时间未被访问的值会被第一个迭代到
        map.delete(map.keys().next().value);
      }
      map.set(key, { value, time: Date.now() });
    },
  };
}