题解 | #设计LRU缓存结构#

对于这个题目，我有一个问题无法从题目描述中得知。那就是，get操作失败时返回-1，这个值是否需要缓存。按我的理解来说，即使是查找不到结果，也是需要缓存的。查找不到结果，也是一种结果。

话说回来，利用map保存数据，每一个数据是一个节点：

interface IItem {
	key: any,
    value: any,
    prevKey: any,
    nextKey: any
}

利用双向链表来保存位置，并且使用headKey和tailKey保存最新的最旧的缓存数据的key。

相比起利用 map 的有序性直接读取指针来更新缓存的新旧属性，性能上双向链表是否更好？无论如何使用 map 的 keys() 或 entriy() 方法都将会创建一个新的可迭代对象。但是双向链表代码量更多，我写的阅读性不好，每一个 value 都需要更多的空间存储几个属性。

整体代码如下：

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
function LRU(operators, k) {
  // write code here
  const hash = new Map();
  const result = [];
  let headKey = null;
  let tailKey = null;

  const deleteItem = (key) => {
    if (hash.has(key)) {
      const prevKey = hash.get(key).prevKey;
      const nextKey = hash.get(key).nextKey;
      if (prevKey) {
        const prevItem = hash.get(prevKey);
        hash.set(prevKey, {
          ...prevItem,
          nextKey,
        });
      } else {
        // delete head
        headKey = hash.get(key).nextKey;
      }
      if (nextKey) {
        const nextItem = hash.get(nextKey);
        hash.set(nextKey, {
          ...nextItem,
          prevKey,
        });
      } else {
        // delete tail
        tailKey = hash.get(key).prevKey;
      }
      hash.delete(key);
      if (hash.size === 0) {
        headKey = null;
        tailKey = null;
      }
    }
  };

  const put = (key, value) => {
    // update cache
    if (hash.size === 0) {
      // init head
      headKey = key;
      tailKey = key;
      hash.set(key, {
        key,
        value,
        prevKey: null,
        nextKey: null,
      });
    } else {
      deleteItem(key);
      if (tailKey) {
        const tailItem = hash.get(tailKey);
        hash.set(tailKey, {
          ...tailItem,
          nextKey: key,
        });
        hash.set(key, {
          key,
          value,
          nextKey: null,
          prevKey: tailKey,
        });
        tailKey = key;
      } else {
        put(key, value);
      }
    }
  };

  const get = (key, value = -1) => {
    if (hash.has(key)) {
      result.push(hash.get(key).value);
      // update cache
      put(key, hash.get(key).value);
    } else {
      result.push(value);
      
    }
  };

  const checkMaxSize = () => {
    if (hash.size > k) {
      const headItem = hash.get(headKey);
      const newHeadKey = headItem.nextKey;
      const newHeadItem = hash.get(newHeadKey);
      // delete head and update headKey
      hash.delete(headKey);
      headKey = newHeadKey;
      hash.set(newHeadKey, {
        ...newHeadItem,
        prevKey: null,
      });
    }
  };

  operators.forEach((operator) => {
    const action = operator[0];
    const key = operator[1];
    const value = operator[2];
    const fcObject = {
      1: put,
      2: get,
    };
    // 调用目标方法
    // check max size
    fcObject[action](key, value);
    checkMaxSize();
  });
  return result;
}

module.exports = {
    LRU : LRU
};