如何实现一个 LRU

用双向链表+哈希。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
  this.cache = new DoubleList();
};
class Node {
  constructor(k, val) {
    this.k = k;
    this.val = val;
    this.pre = null;
    this.next = null;
  }
}
class DoubleList {
  constructor() {
    this.size = 0;
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.pre = this.head;
  }
  addLast(x) {
    const { head, tail } = this;
    x.pre = tail.pre;
    x.next = tail;
    tail.pre.next = x;
    tail.pre = x;
    this.size++;
  }
  remove(x) {
    x.pre.next = x.next;
    x.next.pre = x.pre;
    this.size--;
  }
  removeFirst() {
    const { head, tail } = this;
    if (head.next === tail) return null;
    let first = head.next;
    this.remove(first);
    return first;
  }
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  const { cache, map } = this;
  if (map.has(key)) {
    let x = map.get(key);
    cache.remove(x);
    cache.addLast(x);
    return map.get(key).val;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  const { cache, map, size } = this;
  const addRecently = function (key, value) {
    let x = new Node(key, value);
    cache.addLast(x);
    map.set(key, x);
  };
  if (map.has(key)) {
    let x = map.get(key);
    cache.remove(x);
    map.delete(key);
    addRecently(key, value);
  } else {
    if (cache.size === this.capacity) {
      let x = cache.removeFirst();
      map.delete(x.k);
    }
    addRecently(key, value);
  }
};

Map 的巧妙使用 map 放入数据是按顺序的，最新放入的数据在迭代器最后 而且 map 的 entries 方法，还有 keys 方法，会返回一个迭代器，迭代器调用 next 也是顺序返回，所以返回第一个的值就是最老的，找到并删除即可。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  const map = this.map;
  let val = map.get(key);
  if (val !== undefined) {
    map.delete(key);
    map.set(key, val);
    return val;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  const { map, capacity } = this;
  if (map.has(key)) map.delete(key);
  map.set(key, value);
  if (map.size > capacity) {
    map.delete(map.entries().next().value[0]);
  }
};