最近最少使用缓存(LRU Cache)

#LRU Cache

• LRU(Least Recently Used) 即: 最近最少使用。
• LRU Cache，一种缓存淘汰策略，在有限的内存空间内，只缓存最近使用的数据，超过有限内存空间的数据将会被删除。

#场景

• LRU，一个在产品业务中很有用的算法，常适用于缓存服务、部分业务场景、底层的内存管理等。

#代码实现

• 分析
  • 哈希表: 用来映射每个键到链表中的节点
  • 双向链表: 高效地在任意位置插入和删除节点
  • 从头部添加节点到链表，从尾部删除节点（删除的同时从哈希表里面删除对应的key），再次访问的节点，需要把节点移动到链表的头部。
  • 哨兵节点（dummy node），初始的prev、next指向自己。随节点插入，next指向链表第一个节点，prev指向链表最后一个节点。
• 时间复杂度: O(1)、空间复杂度: O(min(putCount, capacity))

#JS 实现

• Playground

class Node {
  constructor(key = 0, value = 0) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.dummy = new Node();
    this.dummy.prev = this.dummy;
    this.dummy.next = this.dummy;
    this.keyNodeMap = new Map();
  }

  moveToFront(node) {
    node.prev = this.dummy;
    node.next = this.dummy.next;
    node.prev.next = node;
    node.next.prev = node;
  }

  get(key) {
    if (!this.keyNodeMap.has(key)) {
      return null;
    }

    const node = this.keyNodeMap.get(key);
    this.remove(node);
    this.moveToFront(node);
    return node;
  }

  remove(node) {
    node.prev.next = node.next;
    nodex.next.prev = node.prev;
  }

  put(key, value) {
    let node = this.get(key);
    if (node) {
      // 存在 -> 更新value
      node.value = value;
      return;
    }
    node = new Node(); // 不存在 -> 新增
    this.keyNodeMap.set(key, node);
    this.moveToFront(node);

    if (this.keyNodeMap.size > this.capacity) {
      // 空间不足 -> 删除最后一个节点
      const lastNode = this.dummy.prev;
      this.keyNodeMap.delete(lastNode.key);
      this.remove(lastNode);
    }
  }
}

#GO实现

• Playground

package main

import (
    "container/list"
    "fmt"
)

type entry struct {
  key, value int
}

type LRUCache struct {
  capacity int
  list *list.List
  keyNodeMap map[int]*list.Element
}

func Constructor(capacity int) LRUCache {
  return LRUCache{capacity, list.New(), map[int]*list.Element{}}
}

func (c *LRUCache) Get(key int) int {
  node := c.keyNodeMap[key]
  if node == nil {
    return -1
  }

  c.list.MoveToFront(node)
  return node.Value.(entry).value
}

func (c *LRUCache) Put(key, value int) {
  if node := c.keyNodeMap[key]; node != nil { // 存在 -> 更新value
    node.Value = entry{key, value}
    c.list.MoveToFront(node)
    return
  }
  c.keyNodeMap[key] = c.list.PushFront(entry{key, value}) // 不存在 -> 新增

  if len(c.keyNodeMap) > c.capacity {  //  // 空间不足 -> 删除最后一个节点
    delete(c.keyNodeMap, c.list.Remove(c.list.Back()).(entry).key)
  }
}

func main() {
    cache := Constructor(2)
    cache.Put(1, 1)
    cache.Put(2, 2)
    fmt.Println(cache.Get(1))   // 1
    cache.Put(3, 3)             // put 3, remove 2
    fmt.Println(cache.Get(2))   // -1
    cache.Put(4, 4)             // put 4, remove 2
    fmt.Println(cache.Get(1))   // -1
    fmt.Println(cache.Get(3))   // 3
    fmt.Println(cache.Get(4))   // 4
}

#题解

leetcode-solution

#扩展

• 页面置换算法(Page-Replacement Algorithms)
  • 最佳（OPT）
  • 先进先出（FIFO）
  • 最少使用（LFU）