极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。
山月训练营之面试直通车 服务上线了,从准备简历、八股文准备、项目经历准备、面试、面经、面经解答、主观问题答复、谈薪再到入职的一条龙服务。

# 使用 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 做数据保存
  • 自建双向链表做元素使用频率保存及空间大小控制

Author

回答者: 4may-mcx (opens new window)

数组存 key + map

class LRUCache {
  _stack = [];
  _map = {};

  constructor(len = 10) {
    this._len = len;
  }

  put(key, value) {
    if (this._stack.includes(key)) {
      this.update(key, value);
      return;
    }
    // 如果超过缓存的大小,那就删除数组中的最后一个值
    if (this._stack.length >= this._len) {
      const delKey = this._stack[this._len - 1];
      this.delete(delKey);
    }
    this.set(key, value);
  }

  set(key, value) {
    this._stack.unshift(key);
    this._map[key] = value;
  }

  get(key) {
    if (this._map[key]) {
      this.update(key);
      return this._map[key];
    }
    return -1;
  }

  update(key, value) {
    const index = this._stack.indexOf(key);
    this._stack.splice(index, 1);
    this._stack.unshift(key);
    if (value) {
      this._map[key] = value;
    }
  }

  delete(key) {
    delete this._map[key];
    this._stack.pop();
  }
}

export default LRUCache;

Author

回答者: iamphc (opens new window)

function Node(key, val) {
  this.prev = null;
  this.next = null;
  this.key = key;
  this.val = val;
}
function DoubleList() {
  this._node = new Node(null, null);
  this.size = 0;
  // 插入到头部
  this.addFirst = (node) => {
    // 找到头节点
    while (this._node) {
      this._node = this._node.prev;
    }
    // 处理头节点
    this._node.prev = node;
    node.next = this._node;
    // 找到尾节点
    while (this._node) {
      this._node = this._node.next;
    }
    // 处理尾节点
    this._node.prev.next = null;
    this._node.prev = null;
    this.size++;
  };
  // 移除一个节点
  this.remove = (node) => {
    if (!this.size) return -1;
    const prev = node.prev;
    const next = node.next;
    if (prev) {
      node.prev.next = node.next;
    }
    if (next) {
      node.next.prev = node.prev;
    }
    this.size--;
  };
  // 移除最后一个节点,并返回该节点
  this.removeLast = () => {
    if (!this.size) return -1;
    while (this._node) {
      this._node = this._node.next;
    }
    this.remove(this._node);
    return this._node;
  };
}
function LRUcache(limit) {
  this._limit = limit;
  this._doubleList = new DoubleList();
  this._map = new Map();
  // 获取key对应的节点,并将节点提前
  this.get = (key) => {
    if (!this._map.has(key)) return -1;
    const node = this._map.get(key);
    this._doubleList.addFirst(node);
    return node;
  };
  // 插入节点,并将节点提前
  this.put = (key, val) => {
    const node = new Node(key, val);
    if (this._map.has(key)) {
      this._doubleList.remove(this._map.get(key));
    }
    if (this._doubleList.size === this._limit) {
      const lastNode = this._doubleList.removeLast();
      this._map.delete(lastNode.key);
    }
    this._doubleList.addFirst(node);
    this._map.set(key, node);
  };
}
Last Updated: 2/13/2023, 10:50:25 AM