算法--LRU缓存实现

**LRU 缓存实现**
================###什么是 LRU 缓存？

LRU（Least Recently Used）缓存是一种常见的缓存策略，用于优化数据访问。它通过淘汰最近最少使用的项来维持固定大小的缓存。

### 为什么需要 LRU 缓存？

在实际应用中，缓存可以显著提高系统性能和减少延迟。然而，如果缓存过大或未经管理，可能会导致内存泄漏、缓存击穿等问题。LRU 缓存可以帮助我们有效地利用缓存空间，并避免这些问题。

### LRU 缓存实现下面是 LRU 缓存的基本实现：

####1. 使用链表或哈希表作为缓存结构我们可以使用链表或哈希表作为缓存结构。链表更适合于顺序访问，而哈希表则更适合于随机访问。

####2. 维护一个访问时间戳每次访问缓存时，我们需要维护一个访问时间戳，以便在淘汰项时可以确定最近最少使用的项。

####3. 实现淘汰策略当缓存达到最大大小或新项被添加时，我们需要实现淘汰策略，淘汰最近最少使用的项。

### Python 实现示例

import timeclass LRUCache:
 def __init__(self, capacity):
 self.capacity = capacity self.cache = {} # 使用哈希表作为缓存结构 self.timestamp = {} # 维护访问时间戳 def get(self, key):
 if key in self.cache:
 value = self.cache[key]
 self.timestamp[key] = time.time() # 更新访问时间戳 return value else:
 return -1 def put(self, key, value):
 if key in self.cache:
 del self.cache[key]
 del self.timestamp[key]
 elif len(self.cache) >= self.capacity:
 lru_key = min(self.timestamp, key=self.timestamp.get)
 del self.cache[lru_key]
 del self.timestamp[lru_key]

 self.cache[key] = value self.timestamp[key] = time.time()

# 测试示例cache = LRUCache(2) # 创建缓存，最大大小为2cache.put('key1', 'value1')
cache.put('key2', 'value2')

print(cache.get('key1')) # 输出: value1cache.put('key3', 'value3') # 淘汰 key2print(cache.get('key2')) # 输出: -1

javaimport java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache {
 private final int capacity;
 private final Map cache = new LinkedHashMap(16,0.75f, true) {
 @Override protected boolean removeEldestEntry(Map.Entry eldest) {
 return size() > capacity;
 }
 };

 public LRUCache(int capacity) {
 this.capacity = capacity;
 }

 public String get(String key) {
 return cache.get(key);
 }

 public void put(String key, String value) {
 cache.put(key, value);
 }

 // 测试示例 public static void main(String[] args) {
 LRUCache cache = new LRUCache(2);

 cache.put("key1", "value1");
 cache.put("key2", "value2");

 System.out.println(cache.get("key1")); // 输出: value1 cache.put("key3", "value3"); // 淘汰 key2 System.out.println(cache.get("key2")); // 输出: null }
}