什么是 LRU

LRU（Least Recently Used）即最近最少使用缓存，
在做性能优化的时候会经常用到使用到缓存，用以空间换时间的方式来达到性能优化目标。
最常用到的缓存库就是 lru-cache， 前端 SSR 框架 nuxt 就是使用 lru-cache 来实现其页面缓存、组件缓存和接口缓存的功能，以降低服务器 cpu 的负载提高 SSR 页面的并发数。

LRU 实现

先来看看 LRU 需要达到什么样的要求。

  1. 需要给定一个数据结构的长度，不能无限制的缓存数据；
  2. LRU 实例提供一个 get 方法，可通过关键字 key 获取缓存中数据，若没有则返回 -1；
  3. LRU 实例提供一个 put 方法，变更数据值，若数据存在则修改，不存在则插入一条新数据，插入时超过数据长度则删除最久未使用的关键字。
  4. get、put的时间复杂度必须是 O(1)

    基础数据结构选型

    问题一

    对于一个优秀的前端工程师来说，想要实现 1、2、3 的要求是很容易的，用纯数组就可以实现上述 3 点的需求，但是在时间复杂度的要求上达不到，用数组的话，不管是 get 还是 put 方法的时间复杂度都为 O(n)
    这里就不详细展开数组的实现了， 为什么时间复杂度为 O(n) ？？？
    所以为了实现对存储结构操作的，这里选择双向链表来时现缓存数据的存储。

    问题二

    在选择双向链表后又出现了一个新问题, 众所周知，对链表插入与删除时间复杂度为 O(1), 但是链表的查找时间复杂度却为 O(n),在实现 get 的过程中肯定会使用到查询操作。为了解决查询的时间复杂度问题，自然就想到了 Map 数据结构。es6 的 Map 数据结构是查询的时间复杂度正是为O(1)。

这里肯定又有小朋友问啦：用 Map 为什么不直接用对象呢，这多方便？
其实这里使用对象也是可以实现一些简单的需求的，如果 key 为 number 或者为 string，只需要操作时转化一下即可，也能实现需求。但是需要 key 类型更复杂的场景，直接使用对象时达不到 LRU 的要求的
这里通过 双向链表，Map 的数据结构的组合来实现 LRU，使用双向链表存储数据，使用Map标记链表中 key 的位置这样就可以很容易实现 LRUCache 的数据结构。
因为要实现 O(1) 的时间复杂度，首先想到的就是使用 es6 的 Map 数据结构来实现。

  1. /**
  2.  * @param {number} capacity
  3.  */
  4. var LRUCache = function(capacity) {
  5.     this.map = new Map();
  6.     this.capacity = capacity;
  7. };
  9. /** 
  10.  * @param {number} key
  11.  * @return {number}
  12.  */
  13. LRUCache.prototype.get = function(key) {
  14.     if(this.map.has(key)){
  15.         let value = this.map.get(key);
  16.         this.map.delete(key); // 删除后，再 set ，相当于更新到 map 最后一位
  17.         this.map.set(key, value);
  18.         return value
  19.     } else {
  20.         return -1
  21.     }
  22. };
  24. /** 
  25.  * @param {number} key 
  26.  * @param {number} value
  27.  * @return {void}
  28.  */
  29. LRUCache.prototype.put = function(key, value) {
  30.     // 如果已有，那就要更新，即要先删了再进行后面的 set
  31.     if(this.map.has(key)){
  32.         this.map.delete(key);
  33.     }
  34.     this.map.set(key, value);
  35.     // put 后判断是否超载
  36.     if(this.map.size > this.capacity){
  37.         this.map.delete(this.map.keys().next().value);
  38.     }
  40. };
  42. /**
  43.  * Your LRUCache object will be instantiated and called as such:
  44.  * var obj = new LRUCache(capacity)
  45.  * var param_1 = obj.get(key)
  46.  * obj.put(key,value)
  47.  */

简单用 Typescript 实现一下

  1. class LinkNode {
  2.   key: number
  3.   value: number
  4.   _prev: LinkNode | null
  5.   _next: LinkNode | null
  6.   constructor(key: number, val: number) {
  7.     this.key = key
  8.     this.value = val
  9.     this._prev = null
  10.     this._next = null
  11.   }
  12. }
  14. class LRUCache {
  15.   head: LinkNode | null
  16.   tail: LinkNode | null
  17.   size: number
  18.   map: Map<number, LinkNode>
  19.   constructor(capacity: number) {
  20.     this.size = capacity
  21.     this.map = new Map()
  22.     this.head = null
  23.     this.tail = null
  24.   }
  26.   get(key: number): number {
  27.     // 在 map 中查找是否存在有这条数据
  28.     if (this.map.has(key)) {
  29.       let node = this.map.get(key) as LinkNode
  30.       let _prev = node._prev
  31.       let _next = node._next
  33.       // 判断是否为头节点，若为头节点则不需要对链表作任何操作，直接返回值，若部位头肩点，需要操作链表达到最近缓存的操作
  34.       if (_prev) {
  35.         // 不为节点需要将该节点移动到头节点的位置
  37.         // 当前节点是尾部节点的情况
  38.         if (!_next) {
  39.           this.tail = _prev
  40.         } else {
  41.           _next._prev = _prev // 等价于 node._next._prev = node._prev
  42.         }
  44.         // 1. 链表操作，移除 node 节点
  45.         _prev._next = _next // 等价于 node._prev._next = node._next
  47.         // 2. 将 node 节点放到链表头部
  48.         node._prev = null
  50.         if (this.head) {
  51.           node._next = this.head
  52.           this.head._prev = node
  53.         }
  54.         this.head = node
  55.       }
  57.       // 返回想要查找的数据值
  58.       return node.value
  59.     }
  61.     return -1
  62.   }
  64.   put(key: number, value: number): void {
  65.     // put 功能包括两部分，修改和新增
  67.     if (this.map.has(key)) {
  68.       // 修改
  69.       let node = this.map.get(key) as LinkNode
  70.       node.value = value
  71.       let _prev = node._prev
  72.       let _next = node._next
  74.       if (_prev) {
  75.         if (!_next) {
  76.           this.tail = _prev
  77.         } else {
  78.           _next._prev = _prev // 等价于 node._next._prev = node._prev
  79.         }
  81.         // 非头部节需要把节点提到链表头部
  82.         _prev._next = _next
  83.         node._next = this.head
  84.         node._prev = null
  85.         this.head && (this.head._prev = node)
  86.         this.head = node
  87.       }
  88.     } else {
  89.       let node = new LinkNode(key, value)
  90.       this.map.set(key, node)
  92.       if (this.head) {
  93.         node._next = this.head
  94.         this.head._prev = node
  95.         this.head = node
  96.       } else {
  97.         this.head = this.tail = node
  98.       }
  100.       // 新增数据的场景
  101.       if (this.map.size > this.size) {
  102.         let _tail = this.tail as LinkNode
  103.         this.map.delete(_tail.key)
  105.         this.tail = _tail._prev
  107.         if (this.tail) {
  108.           this.tail._next = null
  109.         }
  111.         if (this.head.key === _tail.key) {
  112.           this.head = null
  113.         }
  114.       }
  115.     }
  116.   }
  117. }