一天一道算法题（24）：LRU缓存机制

146. LRU 缓存

文章目录

• • [146. LRU 缓存](https://leetcode.cn/problems/lru-cache/)
  • 思路
  • • Java代码
    • Python代码
    • Golang代码
    • 注意
  • 结语

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

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

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

思路

• 三种语言实现一下这道题目，分别是Java，Python，Golang。我将带着你一步一步思考，按照第一次见到这个题目的方式层层递进地解析这道题目的算法实现，一边思考一边看，收获非凡。

• 首先我们要理清楚这道题目在设计的时候我们需要知道哪些量。我们要存一个键值对，同时要管理每一对键值对的优先级，当缓存满了的时候，把最久未使用的键值对删除。题目还要求put和get必须达到O(1)级别的时间复杂度，难度还是很大的。

• 我们先从O(1)查找这条思路出发。O(1)查找只有两个数据结构可以满足，就是数组和哈希表。但是数组的查找是通过下标索引查找，如果我们要用数组存储key-value对，key本身必须是整数，而且最好还是连续紧凑的整数，否则就会浪费大量空间。更麻烦的是，我们的key不一定都是整数（比如可能是字符串），即使都是整数，用数组存也会产生巨大的内存空洞。那能不能用数组存value，然后另外建立一个映射关系把key转换成数组下标呢？当然可以，这就是哈希表做的事情。但我们如果先走这条路，就等于绕了一圈最后还是回到哈希表，反而多维护了一个映射层，内存开销更大。

• 所以我们直接使用哈希表来作为存储key-value的数据结构，一步到位。这里我们就实现了get的O(1)级别查找。但注意，get的O(1)搞定了，为什么没有说同时实现了put的O(1)呢？ 因为我们还缺少一个关键机制：优先级管理。

• 我们引入哈希表只是解决了存储和查找的问题，但哈希表本身不记录顺序。 所以我们要想一个办法来记录每一个键值对的优先级。一开始我想把哈希表的"值"设置为一个"结构体"（或类），在这个结构体里面存两个值：一个是原本的value，另一个是记录优先级的变量。比如可以用时间戳，但每次获取本地时间在算法题里不太合适；也可以用计数器模拟时间，每次get或put都让计数器加一，在更新或创建键值对时把当前计数存进去。虽然理论上可行，但这样的代价是：当缓存满了需要删除最旧元素时，我们必须O(n)遍历所有键值对才能找到计数器最小的那个，这不符合O(1)的要求。

• 那我们换一种思路。 如果不用计数器，能不能按照访问顺序天然地排列键值对呢？这其实就是链表要做的事情。如果用头插法，每次新节点或刚访问过的节点都插入到head后面，那么越靠近head的节点就是越新的，越靠近tail的节点就是越旧的，优先级顺序就这样被链表天然维护了。当链表长度达到缓存容量时，我们直接删除tail前面的节点（即最久未使用的节点），然后新节点头插即可。这里有一个关键点：单链表中删除任意节点需要O(n)时间，所以我们用双向链表，这样删除操作就是O(1)。

• 此时存储数据的不再是独立的变量或结构体，而是链表的节点。 我们把哈希表的"值"设置为链表的指针。这样就完美结合了哈希表和双向链表的优势：通过哈希表实现O(1)查找，通过链表维护优先级顺序。当我们调用get时，先在哈希表中查找key，如果不存在返回-1；如果存在，直接通过指针找到链表节点，访问value，同时把该节点移到head后面更新优先级（因为它刚刚被访问了）。当我们调用put时，如果key已存在，就修改value，然后把该节点移到head后面；如果key不存在，就创建新节点，头插到head后面，同时存入哈希表。每次插入后检查是否超过容量，如果超过就删除tail前面的节点，并从哈希表中移除对应的key。这样就实现了O(1)时间复杂度的put和get操作。空间复杂度方面，哈希表和链表各存一份数据，物理上是O(2n)，但大O记法忽略常数系数，记为O(n)。

• 代码展示

Java代码

• class LRUCache extends LinkedHashMap<Integer, Integer>{
  private int capacity;

  public LRUCache(int capacity) {
  super(capacity, 0.75F, true);
  this.capacity = capacity;
  }

  public int get(int key) {
  return super.getOrDefault(key, –1);
  }

  public void put(int key, int value) {
  super.put(key, value);
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  return size() > capacity;
  }
  }

  作者：力扣官方题解
  链接：https://leetcode.cn/problems/lru–cache/solutions/259678/lruhuan–cun–ji–zhi–by–leetcode–solution/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Python代码

• class LRUCache(collections.OrderedDict):

  def __init__(self, capacity: int):
  super().__init__()
  self.capacity = capacity

  def get(self, key: int) –> int:
  if key not in self:
  return –1
  self.move_to_end(key)
  return self[key]

  def put(self, key: int, value: int) –> None:
  if key in self:
  self.move_to_end(key)
  self[key] = value
  if len(self) > self.capacity:
  self.popitem(last=False)

  作者：力扣官方题解
  链接：https://leetcode.cn/problems/lru–cache/solutions/259678/lruhuan–cun–ji–zhi–by–leetcode–solution/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Golang代码

• type Node struct {
  key int
  val int
  prev *Node
  next *Node
  }

  type LRUCache struct {
  capacity int
  size int
  cache map[int]*Node
  head *Node
  tail *Node
  }

  func Constructor(capacity int) LRUCache {
  head := &Node{}
  tail := &Node{}
  head.next = tail
  tail.prev = head
  return LRUCache{
  capacity: capacity,
  cache: make(map[int]*Node),
  head: head,
  tail: tail,
  }
  }

  func (this *LRUCache) moveToTail(node *Node) {
  node.prev.next = node.next
  node.next.prev = node.prev

  node.prev = this.tail.prev
  node.next = this.tail
  this.tail.prev.next = node
  this.tail.prev = node
  }

  func (this *LRUCache) addToTail(node *Node) {
  node.prev = this.tail.prev
  node.next = this.tail
  this.tail.prev.next = node
  this.tail.prev = node
  this.cache[node.key] = node
  this.size++
  }

  func (this *LRUCache) removeHead() {
  if this.head.next == this.tail {
  return
  }
  node := this.head.next
  this.head.next = node.next
  node.next.prev = this.head
  delete(this.cache, node.key)
  this.size—
  }

  func (this *LRUCache) Get(key int) int {
  node, ok := this.cache[key]
  if !ok {
  return –1
  }
  this.moveToTail(node)
  return node.val
  }

  func (this *LRUCache) Put(key int, value int) {
  if node, ok := this.cache[key]; ok {
  node.val = value
  this.moveToTail(node)
  return
  }
  if this.size == this.capacity {
  this.removeHead()
  }
  newNode := &Node{key: key, val: value}
  this.addToTail(newNode)
  }

注意

• 这里我必须提醒一句，在 Golang 中，GC（垃圾回收）机制的判断标准是：如果一块内存地址不再被任何变量或数据结构引用，它才会被回收。在我们的 LRU 实现中，当缓存满了需要删除尾节点时，我们确实把节点从双向链表中移除了，但这个节点的地址还存储在 map 里面——map 仍然持有这个 key 和对应的指针。这时候 GC 看到 map 还在引用这块内存，就认为它还在使用中，不会回收它。也就是说，虽然我们从链表中删除了尾节点，但如果不做额外处理，这块内存就永远无法被释放，这就发生了内存泄漏。随着不断的删除和插入，map 中会积累大量已经不在链表中的"僵尸节点"，内存占用只增不减，最终可能导致 OOM（Out Of Memory）。所以，在删除尾节点的时候，我们一定要使用 Golang 的 delete 内置函数，从 map 中删除对应的 key，这样 map 不再引用该节点，链表中也没有引用，GC 就能正常回收这块内存，保证程序的健壮性。

结语

本文是 《算法题目解析系列》 的第 [24] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。