LRU原理
我们仔细想一下这个问题会发现好像没有那么简单，显然我们不能通过数组来实现这个缓存。因为数组的查询速度是很慢的，不可能做到。其次我们用HashMap好像也不行，因为虽然查询的速度可以做到
，但是我们没办法做到更新最近使用的时间，并且快速找出最远更新的数据。
如果是在面试当中被问到想到这里的时候，可能很多人都已经束手无策了。但是先别着急，我们冷静下来想想会发现问题其实并没有那么模糊。首先HashMap是一定要用的，因为只有HashMap才可以做到时间内的读写，其他的数据结构几乎都不可行。但是只有HashMap解决不了更新以及淘汰的问题，必须要配合其他数据结构进行。这个数据结构需要能够做到快速地插入和删除，其实我这么一说已经很明显了，只有一个数据结构可以做到，就是链表。
链表有一个问题是我们想要查询链表当中的某一个节点需要的时间，这也是我们无法接受的。但这个问题并非无法解决，实际上解决也很简单，我们只需要把链表当中的节点作为HashMap中的value进行储存即可，最后得到的系统架构如下：
对于缓存来说其实只有两种功能，第一种功能就是查找，第二种是更新。
查找
查找会分为两种情况，第一种是没查到，这种没什么好说的，直接返回空即可。如果能查到节点，在我们返回结果的同时，我们需要将查到的节点在链表当中移动位置。我们假设越靠近链表头部表示数据越旧，越靠近链表尾部数据越新，那么当我们查找结束之后，我们需要把节点移动到链表的尾部。
移动可以通过两个步骤来完成，第一个步骤是在链表上删除该节点，第二个步骤是插入到尾部：
更新
更新也同样分为两种情况，第一种情况就是更新的key已经在HashMap当中了，那么我们只需要更新它对应的Value，并且将它移动到链表尾部。对应的操作和上面的查找是一样的，只不过多了一个更新HashMap的步骤，这没什么好说的，大家应该都能想明白。
第二种情况就是要更新的值在链表当中不存在，这也会有两种情况，第一个情况是缓存当中的数量还没有达到限制，那么我们直接添加在链表结尾即可。第二种情况是链表现在已经满了，我们需要移除掉一个元素才可以放入新的数据。这个时候我们需要删除链表的第一个元素，不仅仅是链表当中删除就可以了，还需要在HashMap当中也删除对应的值，否则还是会占据一份内存。
因为我们要进行链表到HashMap的反向删除操作，所以链表当中的节点上也需要记录下Key值，否则的话删除就没办法了。删除之后再加入新的节点，这个都很简单：
我们理顺了整个过程之后来看代码：
class Node:
def __init__(self, key, val, prev=None, succ=None):
self.key = key
self.val = val
# 前驱
self.prev = prev
# 后继
self.succ = succ
def __repr__(self):
return str(self.val)
class LinkedList:
def __init__(self):
self.head = Node(None, 'header')
self.tail = Node(None, 'tail')
self.head.succ = self.tail
self.tail.prev = self.head
def append(self, node):
# 将node节点添加在链表尾部
prev = self.tail.prev
node.prev = prev
node.succ = prev.succ
prev.succ = node
node.succ.prev = node
def delete(self, node):
# 删除节点
prev = node.prev
succ = node.succ
succ.prev, prev.succ = prev, succ
def get_head(self):
# 返回第一个节点
return self.head.succ
class LRU:
def __init__(self, cap=100):
# cap即capacity，容量
self.cap = cap
self.cache = {}
self.linked_list = LinkedList()
def get(self, key):
if key not in self.cache:
return None
self.put_recently(key)
return self.cache[key]
def put_recently(self, key):
# 把节点更新到链表尾部
node = self.cache[key]
self.linked_list.delete(node)
self.linked_list.append(node)
def put(self, key, value):
# 能查到的话先删除原数据再更新
if key in self.cache:
self.linked_list.delete(self.cache[key])
self.cache[key] = Node(key, value)
self.linked_list.append(self.cache[key])
return
if len(self.cache) >= self.cap:
# 如果容量已经满了，删除最旧的节点
node = self.linked_list.get_head()
self.linked_list.delete(node)
del self.cache[node.key]
u = Node(key, value)
self.linked_list.append(u)
self.cache[key] = u
在这种实现当中我们没有用除了dict之外的其他任何工具，连LinkedList都是自己实现的。实际上在Python语言当中有一个数据结构叫做OrderedDict，它是一个字典，但是它当中的元素都是有序的。我们利用OrderedDict来实现LRU就非常非常简单，代码量也要少得多。
我们来看代码：
class LRU(OrderedDict):
def __init__(self, cap=128, /, *args, **kwds):
self.cap = cap
super().__init__(*args, **kwds)
def __getitem__(self, key):
# 查询函数
value = super().__getitem__(key)
# 把节点移动到末尾
self.move_to_end(key)
return value
def __setitem__(self, key, value):
# 更新函数
super().__setitem__(key, value)
if len(self) > self.cap:
oldest = next(iter(self))
del self[oldest]
在上面一种实现当中由于只用了一个数据结构，所以整个代码要简洁许多。使用起来也更加方便，直接像是dict一样使用方括号进行查询以及更新就可以了。不过在其他语言当中可能没有OrderedDict这种数据结构，这就需要我们自己来编码实现了。
好了，今天的文章就到这里。衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、关注、转发）
本文使用 mdnice 排版
- END -