如何实现LRU缓存算法

一、什么是 LRU 缓存算法

LRU 缓存算法（Least Recently Used）是一种常用的缓存淘汰算法，它的基本思想是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，先剔除在最近最久未被使用的数据，从而为新数据腾出空间。

二、LRU 缓存算法的实现原理

LRU 缓存算法的实现原理是维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的，当有一个新的数据被访问时，从链表头开始顺序遍历链表，如果此数据已经存在，则将此结点移到链表头；如果不存在，则将此结点插入到链表的头部，如果缓存已满，则删除链表的尾结点。

三、LRU 缓存算法的实现代码

LRU 缓存算法的实现代码如下：

12345678910111213141516171819202122232425

class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.pre = None

class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.head = Node(None, None)
self.tail = Node(None, None)
self.head.next = self.tail
self.tail.pre = self.head
self.dict = {}

def get(self, key):
if key not in self.dict:
return -1
node = self.dict[key]
self.remove(node)
self.add(node)
return node.value

def put(self, key, value):
if key in self.dict:
self.remove(self.dict[key])
node = Node(key, value)
self.add(node)
self.dict[key] = node
if len(self.dict) > self.capacity:
node = self.tail.pre
self.remove(node)
del self.dict[node.key]

def add(self, node):
node.pre = self.head
node.next = self.head.next
self.head.next.pre = node
self.head.next = node

def remove(self, node):
node.pre.next = node.next
node.next.pre = node.pre

四、总结

总的来说，LRU 缓存算法是一种常用的缓存淘汰算法，它的基本原理是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。实现 LRU 缓存算法的原理是维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。可以通过上述代码实现 LRU 缓存算法。