面试官（手撕LRU缓存了解一下#2021年底大盘点#） _面试

归志宁无五亩园，读书本意在元元。这篇文章主要讲述面试官：手撕LRU缓存了解一下#2021年底大盘点#相关的知识，希望能为你提供帮助。
大家好，我是程序员学长~
关注公众号【程序员学长】，回复【电子书】，免费获得上百本计算机经典书籍
面试官：来了，老弟，LRU缓存实现一下?
我：直接LinkedHashMap就好了。
面试官：不要用现有的实现，自己实现一个。
我：.....
面试官：回去等消息吧....
大家好，我是程序员学长，今天我们来聊一聊LRU缓存的问题。
Tips: LRU在计算机软件中无处不在，希望大家一定要了解透彻。
问题描述

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

分析问题
根据问题描述，我们可以知道LRU缓存中包含两种操作，即Set和Get操作。
对于Set操作来说，分为两种情况。

如果缓存中已经存在。把缓存中对应的该元素移动到缓存头部。
如果缓存中不存在。把该元素添加到缓存头部。此时如果缓存的大小超过限制的大小，需要删除缓存中末尾的元素。
对于Get操作来说，也分为两种情况。
如果缓存中存在。把缓存中的该元素移动到缓存头部，并返回对应的value值。
如果缓存中不存在。直接返回-1。
综上所述：对于一个LRU缓存来说，主要包含以下三种操作。
查找一个元素。
在缓存末尾删除一个元素。
在缓存头部添加一个元素。
所以，我们最容易想到的就是使用一个链表来实现LRU缓存。我们可以维护一个有序的单链表，越靠近链表尾部的结点是越早访问的。当我们进行Set操作时，我们从链表头开始顺序遍历。遍历的结果有两种情况。
如果此数据已经在链表中，我们遍历得到这个数据对应的结点，然后将其从这个位置移动到链表的头部。
如果此数据不在链表中，又会分为两种情况。如果此时链表没有满，我们直接将该结点插入到链表头部。如果此时链表已经满了，我们从链表尾部删除一个结点，然后将新的数据结点插入到链表头部。
当我们进行Get操作时，我们从链表头开始顺序遍历。遍历的结果有两种情况。
如果此数据在链表中。我们遍历得到这个数据对应的结点，然后将其从这个位置移动到链表的头部，并返回这个结点对应的value。
如果此数据不在链表中。我们直接返回-1。

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

class LinkedNode: def __init__(self, key=0, value=https://www.songbingjia.com/android/0): self.key = key self.value = value self.next = Noneclass LRUCache(): def __init__(self, capacity: int): # 使用伪头部节点 self.capacity=capacity self.head = LinkedNode() self.head.next=None self.size = 0def get(self, key: int) -> int:cur=self.head.next pre=self.headwhile cur!=None: if cur.key==key: pre.next = cur.next cur.next = self.head.next self.head.next = cur break pre=pre.next cur=cur.nextif cur!=None: return cur.value else: return -1def put(self, key: int, value: int) -> None:cur = self.head.next pre = self.head#缓存没有元素，直接添加 if cur==None: node = LinkedNode() node.key = key node.value = value self.head.next = node self.size = self.size + 1 return#缓存有元素，判断是否存在于缓存中 while cur!=None: #表示已经存在 if cur.key == key: #把该元素反正链表头部 cur.value=value pre.next = cur.next cur.next = self.head.next self.head.next = cur break#代表当前元素时最后一个元素 if cur.next==None: #如果此时缓存已经满了，淘汰最后一个元素 if self.size==self.capacity: pre.next=None self.size=self.size-1 node=LinkedNode() node.key=key node.value=value node.next=self.head.next self.head.next=node self.size=self.size+1 breakpre = pre.next cur=cur.next

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

class LinkedNode: def __init__(self, key=0, value=https://www.songbingjia.com/android/0): self.key = key self.value = value self.prev = None self.next = Noneclass LRUCache: def __init__(self, capacity: int): self.cache = dict() self.head = LinkedNode() self.tail = LinkedNode() self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.size = 0def get(self, key: int): #如果key不存在，直接返回-1 if key not in self.cache: return -1 #通过hash表定位位置，然后删除，省去遍历查找过程 node = self.cache[key] self.moveHead(node) return node.valuedef put(self, key: int, value: int) -> None: if key not in self.cache: # 如果key不存在，创建一个新的节点 node = LinkedNode(key, value) # 添加进哈希表 self.cache[key] = node self.addHead(node) self.size += 1 if self.size > self.capacity: # 如果超出容量，删除双向链表的尾部节点 removed = self.removeTail() # 删除哈希表中对应的项 self.cache.pop(removed.key) self.size -= 1 else: node = self.cache[key] node.value = value self.moveHead(node)def addHead(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = nodedef removeNode(self, node): node.prev.next = node.next node.next.prev = node.prevdef moveHead(self, node): self.removeNode(node) self.addHead(node)def removeTail(self): node = self.tail.prev self.removeNode(node) return node

总结
LRU缓存不论在工作中还是面试中，我们都会经常碰到。希望这篇文章能对你有所帮助。
当散列表遇上链表
今天，我们就聊到这里。更多有趣知识，请关注公众号【程序员学长】。
【面试官（手撕LRU缓存了解一下#2021年底大盘点#）】你知道的越多，你的思维也就越开阔，我们下期再见。