面试官：来了，老弟，LRU缓存实现一下?

我：直接LinkedHashMap就好了。

面试官：不要用现有的实现，自己实现一个。

我：…..

面试官：回去等消息吧….

大家好，我是程序员学长，今天我们来聊一聊LRU缓存问题。

Tips: LRU在计算机软件中无处不在，希望大家一定要了解透彻。

  1. 设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
  2. 1. set(key, value)：将记录(key, value)插入该结构
  3. 2. get(key)：返回key对应的value值

根据问题描述，我们可以知道LRU包含两种操作，即Set和Get操作。

对于Set操作来说，分为两种情况。

  1. 缓存中已经存在。把缓存中的该元素移动到缓存头部。
  2. 如果缓存中不存在。把该元素添加到缓存头部。如果此时缓存的大小超过限制的大小，需要删除缓存中末尾的元素。

对于Get操作来着，也分为两种情况。

  1. 缓存中存在。把缓存中的该元素移动到缓存头部。并返回对应的value值。
  2. 缓存中不存在。直接返回-1。

综上所述：对于一个LRU缓存结构来说，主要需要支持以下三种操作。

  1. 查找一个元素。
  2. 在缓存末尾删除一个元素。
  3. 在缓存头部添加一个元素。

所以，我们最容易想到的就是使用一个链表来实现LRU缓存。

我们可以维护一个有序的单链表，越靠近链表尾部的结点是越早访问的。

当我们进行Set操作时，我们从链表头开始顺序遍历。遍历的结果有两种情况。

  1. 如果此数据之前就已经被缓存在链表中，我们遍历得到这个数据对应的结点，然后将其从这个位置移动到链表的头部。
  2. 如果此数据不在链表中，又会分为两种情况。如果此时缓存链表没有满，我们直接将该结点插入链表头部。如果此时缓存链表已经满了，我们从链表尾部删除一个结点，然后将新的数据结点插入到链表头部。

当我们进行Get操作时，我们从链表头开始顺序遍历。遍历的结果有两种情况。

  1. 如果此数据之前就已经被缓存在链表中，我们遍历得到这个数据对应的结点，然后将其从这个位置移动到链表的头部。
  2. 如果此数据之前不在缓存中，我们直接返回-1。

下面我们来看一下代码如何实现。

  1. class LinkedNode:
  2.     def __init__(self, key=0, value=0):
  3.         self.key = key
  4.         self.value = value
  5.         self.next = None
  7. class LRUCache():
  8.     def __init__(self, capacity: int):
  9.         # 使用伪头部节点
  10.         self.capacity=capacity
  11.         self.head = LinkedNode()
  12.         self.head.next=None
  13.         self.size = 0
  15.     def get(self, key: int) -> int:
  17.         cur=self.head.next
  18.         pre=self.head
  20.         while cur!=None:
  21.             if cur.key==key:
  22.                 pre.next = cur.next
  23.                 cur.next = self.head.next
  24.                 self.head.next = cur
  25.                 break
  26.             pre=pre.next
  27.             cur=cur.next
  29.         if cur!=None:
  30.             return cur.value
  31.         else:
  32.             return -1
  34.     def put(self, key: int, value: int) -> None:
  36.         cur = self.head.next
  37.         pre = self.head
  38.         
  39.         #缓存没有元素，直接添加
  40.         if cur==None:
  41.             node = LinkedNode()
  42.             node.key = key
  43.             node.value = value
  44.             self.head.next = node
  45.             self.size = self.size + 1
  46.             return
  48.         #缓存有元素，判断是否存在于缓存中
  49.         while cur!=None:
  50.             #表示已经存在
  51.             if cur.key == key:
  52.                 #把该元素反正链表头部
  53.                 cur.value=value
  54.                 pre.next = cur.next
  55.                 cur.next = self.head.next
  56.                 self.head.next = cur
  57.                 break
  59.             #代表当前元素时最后一个元素
  60.             if cur.next==None:
  61.                 #如果此时缓存已经满了，淘汰最后一个元素
  62.                 if self.size==self.capacity:
  63.                     pre.next=None
  64.                     self.size=self.size-1
  65.                 node=LinkedNode()
  66.                 node.key=key
  67.                 node.value=value
  68.                 node.next=self.head.next
  69.                 self.head.next=node
  70.                 self.size=self.size+1
  71.                 break
  72.                 
  73.             pre = pre.next
  74.             cur=cur.next

这样我们就用链表实现了一个LRU缓存，我们接下来分析一下缓存访问的时间复杂度。对于Set来说，不管缓存有没有满，我们都需要遍历一遍链表，所以时间复杂度是O(n)。对于Get操作来说，也是需要遍历一遍链表，所以时间复杂度也是O(n)。

​从上面的分析，我们可以看到。如果用单链表来实现LRU，不论是Set还是Get操作，都需要遍历一遍链表，来查找当前元素是否在缓存中，时间复杂度为O（n），那我们可以优化吗？我们知道，使用hash表，我们查找元素的时间复杂度可以减低到O（1）,如果我们可以用hash表，来替代上述的查找操作，那不就可以减低时间复杂度吗?根据这个逻辑，所以我们采用hash表和链表的组合方式来实现一个高效的LRU缓存。

  1. class LinkedNode:
  2.     def __init__(self, key=0, value=0):
  3.         self.key = key
  4.         self.value = value
  5.         self.prev = None
  6.         self.next = None
  8. class LRUCache:
  9.     def __init__(self, capacity: int):
  10.         self.cache = dict()
  11.         self.head = LinkedNode()
  12.         self.tail = LinkedNode()
  13.         self.head.next = self.tail
  14.         self.tail.prev = self.head
  15.         self.capacity = capacity
  16.         self.size = 0
  18.     def get(self, key: int):
  19.         #如果key不存在，直接返回-1
  20.         if key not in self.cache:
  21.             return -1
  22.         #通过hash表定位位置，然后删除，省去遍历查找过程
  23.         node = self.cache[key]
  24.         self.moveHead(node)
  25.         return node.value
  27.     def put(self, key: int, value: int) -> None:
  28.         if key not in self.cache:
  29.             # 如果key不存在，创建一个新的节点
  30.             node = LinkedNode(key, value)
  31.             # 添加进哈希表
  32.             self.cache[key] = node
  33.             self.addHead(node)
  34.             self.size += 1
  35.             if self.size > self.capacity:
  36.                 # 如果超出容量，删除双向链表的尾部节点
  37.                 removed = self.removeTail()
  38.                 # 删除哈希表中对应的项
  39.                 self.cache.pop(removed.key)
  40.                 self.size -= 1
  41.         else:
  42.             node = self.cache[key]
  43.             node.value = value
  44.             self.moveHead(node)
  46.     def addHead(self, node):
  47.         node.prev = self.head
  48.         node.next = self.head.next
  49.         self.head.next.prev = node
  50.         self.head.next = node
  52.     def removeNode(self, node):
  53.         node.prev.next = node.next
  54.         node.next.prev = node.prev
  56.     def moveHead(self, node):
  57.         self.removeNode(node)
  58.         self.addHead(node)
  60.     def removeTail(self):
  61.         node = self.tail.prev
  62.         self.removeNode(node)
  63.         return node

LRU缓存不论在工作中还是面试中，我们都会经常碰到。希望这篇文章能对你有所帮助。

今天，我们就聊到这里。更多有趣知识，请关注公众号【程序员学长】。我给你准备了上百本学习资料，包括python、java、数据结构和算法等。如果需要，请关注公众号【程序员学长】，回复【资料】，即可得。

你知道的越多，你的思维也就越开阔，我们下期再见。

版权声明：本文为laohanshuibi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/laohanshuibi/p/15225912.html