LRU：Least Recently Used，最少最近使用算法。

算法描述

leetcode 146 [LRU缓存机制] 有关于这个数据结构的设计的描述，下面我直接copy一下，实现LRUCache类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字

注意：put & get方法的都需要是O(1) 的时间复杂度

  1. LRUCache lRUCache = new LRUCache(2);
  2. lRUCache.put(1, 1); // 缓存是 cache = [1=>1]
  3. lRUCache.put(2, 2); // 缓存是 cache = [2=>2, 1=>1]
  4. lRUCache.get(1);    // 返回 1,访问了1就会将1提到队列前头 cache = [1=>1, 2=>2],
  6. lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 cache = [3=>3, 1=>1]
  7. lRUCache.get(2);    // 返回 -1 (未找到)
  8. lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 cache = [4=>4, 3=>3]
  10. lRUCache.get(1);    // 返回 -1 (未找到)
  11. lRUCache.get(3);    // 返回 3 cache = [3=>3, 4=>4]
  12. lRUCache.get(4);    // 返回 4 cache = [4=>4, 3=>3]

算法设计

上面我们知道有一个条件是put & get方法的时间复杂度要是O(1)，那么构建的cache缓存需要满足以下条件
1、cache中的元素，应该是有时序的，来区分哪些是最近访问的/较久未访问的数据，容量满的时候还需要删掉末尾的元素腾出空间。
2、在cache需要快速找到某个key是否存在并且获得对应的value O(1)，这个点我们很容易想到hashMap。
3、每次访问cache中的某个key，需要将这个元素变成队列最开头的位置，也就是说cache要支持在任意位置快速的删除/插入元素 O(1)
我们知道hashMap查找快，但是数据没有固定顺序；链表有顺序，插入删除快，但查找慢。结合一下基本就满足了我们上面的需求，一般也是采用这个结构实现的即哈希链表：LinkedHashMap

image.png
注意这里用到的是双向链表，关于这个为什么是双链表不是单链表

代码实现：双向链表+hashMap

双向链表部分

  1. /*
  2.  * 双链表Node
  3.  */
  4. class DoubleLinkedListNode {
  5.   public key: number;
  6.   public value: number;
  7.   public next: any = null;
  8.   public prev: any = null;
  10.   constructor(key: number, value: number) {
  11.     this.key = key;
  12.     this.value = value;
  13.   }
  14. }
  16. class DoubleLinkedList {
  17.   // 链表头节点, Number.POSITIVE_INFINITY -> 正无穷大
  18.   public head = new DoubleLinkedListNode(
  19.     Number.POSITIVE_INFINITY,
  20.     Number.POSITIVE_INFINITY
  21.   );
  22.   // 链表尾节点, Number.NEGATIVE_INFINITY -> 负无穷大
  23.   public tail = new DoubleLinkedListNode(
  24.     Number.NEGATIVE_INFINITY,
  25.     Number.NEGATIVE_INFINITY
  26.   );
  27.   private size: number = 0; //链表长度
  29.   constructor() {
  30.     this.head.next = this.tail;
  31.     this.tail.prev = this.head;
  32.   }
  34.   public addFirstNode(node: DoubleLinkedListNode): any {
  35.     // node链起来
  36.     node.prev = this.head;
  37.     node.next = this.head.next;
  38.     // 处理node
  39.     this.head.next.prev = node;
  40.     this.head.next = node;
  41.     // size ++
  42.     this.size += 1;
  43.   }
  45.   public remove(node: any): void {
  46.     node.prev.next = node.next;
  47.     node.next.prev = node.prev;
  48.     // size --
  49.     this.size -= 1;
  50.   }
  52.   public removeLastNode() {
  53.     // 空链表上，其实这里也可以通过size判断
  54.     if (this.head.next === this.tail) return null;
  55.     const last = this.tail.prev;
  56.     this.remove(last);
  57.     return last;
  58.   }
  60.   public getSize(): number {
  61.     return this.size;
  62.   }
  63. }

LRUCache实现部分

  1. class LRUCache {
  2.   private hashMap = new Map();
  3.   private cache: DoubleLinkedList = new DoubleLinkedList();
  4.   private capacity: number; //容量
  6.   constructor(capacity: number) {
  7.     this.capacity = capacity;
  8.   }
  10.   // key访问提升到最近使用
  11.   private getRecently(key: number): void {
  12.     const node: DoubleLinkedListNode = this.hashMap.get(key);
  13.     // 移除node
  14.     this.cache.remove(node);
  15.     // 放到队头
  16.     this.cache.addFirstNode(node);
  17.   }
  19.   // 移除最久未使用的元素
  20.   private removeLastRecently(): void {
  21.     const lastNode: any = this.cache.removeLastNode();
  22.     // map中也要删掉改元素哦
  23.     this.hashMap.delete(lastNode?.key);
  24.   }
  26.   // 添加最近使用的元素
  27.   private addRecently(key: number, value: number): void {
  28.     const node: DoubleLinkedListNode = new DoubleLinkedListNode(key, value);
  29.     this.cache.addFirstNode(node);
  30.     this.hashMap.set(key, node);
  31.   }
  33.   /*
  34.    * 判断hashMap是否有该元素
  35.    * 没有: 返回 -1
  36.    * 有: 将元素提升到链表头，返回对应的元素
  37.    */
  38.   public get(key: number) {
  39.     if (this.hashMap.has(key)) {
  40.       this.getRecently(key);
  41.       return this.hashMap.get(key).value;
  42.     } else {
  43.       return -1;
  44.     }
  45.   }
  47.   /*
  48.    * 判断是否超过容器的极限了
  49.    * 有: 将链表最后一个元素移除，后再将该元素放在链表头
  50.    * 没有: 放到链表头
  51.    */
  52.   public put(key: number, value: number) {
  53.     if (this.cache.getSize() === this.capacity) {
  54.       this.removeLastRecently();
  55.     }
  56.     this.addRecently(key, value);
  57.     console.log("map", this.hashMap);
  58.   }
  59. }

验证部分的代码

  1. const lRUCache = new LRUCache(2);
  2. console.log("-----");
  3. lRUCache.put(1, 1); // 缓存是 {1=1}
  4. lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  5. console.log("-----");
  6. lRUCache.get(1); // 返回 1
  7. lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  8. console.log("-----");
  9. lRUCache.get(2); // 返回 -1 (未找到)
  10. lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  11. console.log("-----");
  12. lRUCache.get(1); // 返回 -1 (未找到)
  13. lRUCache.get(3); // 返回 3
  14. lRUCache.get(4); // 返回 4

代码实现：迭代器+hashMap

ES6中的Map本身是可迭代的，并且key有序，这样我们可以利用这个特性替代双向链表的功能
image.png

  1. /*
  2.  * map的key是一个有序(迭代器)
  3.  * 可以替代LinkedListHashMap的功能
  4.  */
  6. class LRUCacheMap<T, U> {
  7.   private cache: Map<T, U> = new Map();
  8.   private capacity: number;
  10.   constructor(capacity: number) {
  11.     this.capacity = capacity;
  12.   }
  14.   /*
  15.    * 判断cache是否有该元素
  16.    * 没有: 返回 null
  17.    * 有: 将元素提升到链表头，返回对应的元素
  18.    */
  19.   public get(key: T): U | null {
  20.     if (this.cache.get(key)) {
  21.       // 先删除该元素，再提升到头部
  22.       const value: U = this.cache.get(key) as U;
  23.       this.cache.delete(key);
  24.       this.cache.set(key, value);
  25.       return value;
  26.     } else {
  27.       return null;
  28.     }
  29.   }
  31.   // 获取map中最久没有访问一个元素(最先插入)
  32.   private getFirstKey() {
  33.     const keys = this.cache.keys();
  34.     return keys.next().value;
  35.   }
  37.   /*
  38.    * 判断是否超过容器的极限了
  39.    * 有: 将map最后一个元素移除，后再将该元素放在链表头
  40.    * 没有: 放到链表头
  41.    */
  42.   public put(key: T, value: U) {
  43.     // 已经存在的删除: map的key如果是引用类型并不会被覆盖的
  44.     if (this.cache.has(key)) {
  45.       this.cache.delete(key);
  46.     }
  47.     if (this.capacity === this.cache.size) {
  48.       const lastKey = this.getFirstKey();
  49.       this.cache.delete(lastKey);
  50.     }
  51.     this.cache.set(key, value);
  52.   }
  54.   toString() {
  55.     console.table(this.cache);
  56.   }
  57. }
  1. const lruCacheMap = new LRUCacheMap(4);
  2. lruCacheMap.put(2, 2); // 入 2，剩余容量3
  3. lruCacheMap.put(3, 3); // 入 3，剩余容量2
  4. lruCacheMap.put(4, 4); // 入 4，剩余容量1
  5. lruCacheMap.put(5, 5); // 入 5，已满  从头至尾  2-3-4-5
  6. lruCacheMap.toString();
  7. lruCacheMap.put(4, 4); // 入4，已存在 ——> 置队尾   2-3-5-4
  8. lruCacheMap.toString();
  9. lruCacheMap.put(1, 1); // 入1，不存在 ——> 删除队首 插入1  3-5-4-1
  10. lruCacheMap.toString();
  11. lruCacheMap.get(3); // 获取3，刷新3——> 置队尾  5-4-1-3
  12. lruCacheMap.toString();