极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。
每天晚上九点 B站讲解前端工程化直播,并解答相关问题。

# 使用 js 实现一个 lru cache

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 251 (opens new window)

Author

回答者: mrrs878 (opens new window)

可以借助Map实现

class LRUCache {
  constructor(limit) {
    this.limit = limit;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.limit) {
      this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

// ["LRUCache","put","put","get","put","get","put","get","get","get"]
// [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
const lruCache = new LRUCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
const res1 = lruCache.get(1);
lruCache.put(3, 3);
const res2 = lruCache.get(2);
lruCache.put(4, 4);
const res3 = lruCache.get(1);
const res4 = lruCache.get(3);
const res5 = lruCache.get(4);

console.log(res1, res2, res3, res4, res5);
// 1 undefined undefined 3 4

LRU (最近最少使用) 缓存机制

  • 使用 Map 做数据保存
  • 自建双向链表做元素使用频率保存及空间大小控制
Last Updated: 11/27/2021, 10:11:48 AM