LRU 缓存

**LRU 缓存**

LRU (Least Recently Used) 缓存是一种常见的缓存策略，用于优化系统性能。它通过淘汱最近使用过的数据来释放内存空间，从而避免了由于内存不足导致的性能下降。

**什么是 LRU 缓存**

LRU 缓存是一种基于时间序列的缓存策略，它根据数据的访问顺序来决定哪些数据需要被淘汱。具体来说，LRU 缓存会将最近使用过的数据放在缓存中，而将最久未使用过的数据从缓存中移除。

**如何实现 LRU 缓存**

实现 LRU 缓存有多种方法，我们可以使用以下几种方式：

1. **链表法**：我们可以使用一个双向链表来实现 LRU 缓存。每个节点代表一个缓存项，链表的头部指向最近使用过的数据，而链表的尾部指向最久未使用过的数据。
2. **哈希表法**：我们可以使用一个哈希表来实现 LRU 缓存。每个键值对代表一个缓存项，哈希表中的键是缓存项的 ID，而哈希表中的值是缓存项本身。

下面，我们将使用链表法和哈希表法两种方式分别实现 LRU 缓存。

**链表法**

class Node:
 def __init__(self, key, value):
 self.key = key self.value = value self.prev = None self.next = Noneclass LRUCache:
 def __init__(self, capacity):
 self.capacity = capacity self.cache = {}
 self.head = Node(0,0)
 self.tail = Node(0,0)
 self.head.next = self.tail self.tail.prev = self.head def get(self, key):
 if key in self.cache:
 node = self.cache[key]
 self._remove(node)
 self._add(node)
 return node.value else:
 return -1 def put(self, key, value):
 if key in self.cache:
 self._remove(self.cache[key])
 new_node = Node(key, value)
 self._add(new_node)
 self.cache[key] = new_node if len(self.cache) > self.capacity:
 node = self.head.next self._remove(node)
 del self.cache[node.key]

 def _remove(self, node):
 prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _add(self, node):
 prev_node = self.tail.prev prev_node.next = node self.tail.prev = node node.prev = prev_node node.next = self.tail

class LRUCache:
 def __init__(self, capacity):
 self.capacity = capacity self.cache = {}
 self.order = []

 def get(self, key):
 if key in self.cache:
 value = self.cache[key]
 self.order.remove(key)
 self.order.append(key)
 return value else:
 return -1 def put(self, key, value):
 if key in self.cache:
 del self.cache[key]
 self.order.remove(key)
 elif len(self.cache) >= self.capacity:
 lru_key = self.order.pop(0)
 del self.cache[lru_key]
 self.cache[key] = value self.order.append(key)

cache = LRUCache(2)

cache.put(1,1)
cache.put(2,2)
print(cache.get(1)) # returns1cache.put(3,3) # evicts key2print(cache.get(2)) # returns -1 (not found)
cache.put(4,4) # evicts key1print(cache.get(1)) # returns -1 (not found)
print(cache.get(3)) # returns3print(cache.get(4)) # returns4