LRU Cache

算法定义

LRU（Least Recently Used，最近最少使用）缓存是一种页面置换算法，用于管理有限的缓存空间。其核心思想是：当缓存空间满时，优先淘汰最近最少被访问的数据，为新数据腾出空间。这种策略基于 "最近被访问的数据在未来更可能被再次访问" 的局部性原理。

缓存（Cache）是一种存储临时数据的机制，目的是加快数据访问速度（内存访问速度远快于磁盘）。LRU 是缓存淘汰策略中最经典的一种。

算法思路

LRU Cache 的核心操作包括：

get(key)：获取键对应的值，若键存在则更新该键为 "最近使用" 状态
put(key, value)：插入或更新键值对，若键存在则更新值并标记为 "最近使用"；若键不存在且缓存满，则删除 "最近最少使用" 的键后插入新键值对

实现思路需满足：

快速访问数据（O (1) 时间复杂度）
快速插入新数据（O (1)）
快速删除最久未使用的数据（O (1)）
快速更新数据的访问状态（O (1)）

经典实现方案：

哈希表（HashMap）：用于快速定位键值对，O (1) 访问
双向链表：用于维护数据的访问顺序，头部为最近使用，尾部为最久未使用，O (1) 插入 / 删除

算法复杂度

get 操作：O (1) - 哈希表定位 + 链表节点移动
put 操作：O (1) - 哈希表操作 + 链表节点插入 / 删除
最坏时间复杂度：O (1) - 所有操作均为常数时间
平均时间复杂度：O(1)
空间复杂度：O (capacity) - 缓存容量固定，最多存储 capacity 个键值对

优点与缺点

优点：
- 实现相对简单，性能优异（所有操作 O (1)）
- 符合局部性原理，缓存命中率较高
- 适用于大多数访问模式具有局部性的场景
缺点：
- 对突发访问模式不友好（如周期性批量访问）
- 需要维护双向链表和哈希表，实现稍复杂
- 完全基于访问时间，未考虑数据的访问频率
- 缓存满时每次插入都可能触发淘汰操作

应用场景

数据库查询缓存（如 MySQL 的查询缓存）
浏览器缓存（页面资源缓存）
操作系统内存管理（页面置换）
分布式缓存（如 Redis 的 LRU 策略）
移动端图片缓存（避免重复加载）
计算结果缓存（重复计算的中间结果）

Java 实现及优化版本

import java.util.*;

// 1. 经典实现：双向链表 + 哈希表
class LRUCacheClassic {
    // 双向链表节点
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;  // 头节点（最近使用）
    private final Node tail;  // 尾节点（最久未使用）
    
    public LRUCacheClassic(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        
        // 哨兵节点，简化边界处理
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        
        // 存在则移动到头部（标记为最近使用）
        Node node = cache.get(key);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // 存在则更新值并移动到头部
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            // 不存在则创建新节点
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            
            // 超出容量则删除尾部节点（最久未使用）
            if (cache.size() > capacity) {
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
            }
        }
    }
    
    // 移动节点到头部
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    // 添加节点到头部
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    // 移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    // 移除尾部节点（最久未使用）
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

// 2. 优化版1：利用Java的LinkedHashMap（简化实现）
class LRUCacheLinkedHashMap extends LinkedHashMap<Integer, Integer> {
    private final int capacity;
    
    public LRUCacheLinkedHashMap(int capacity) {
        // accessOrder=true表示按访问顺序排序，false按插入顺序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    // 重写该方法，当size超过capacity时返回true，触发淘汰
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

// 3. 优化版2：并发安全实现（适合多线程环境）
class LRUCacheConcurrent {
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;
    private final Object lock = new Object();  // 用于同步
    
    public LRUCacheConcurrent(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        synchronized (lock) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            Node node = cache.get(key);
            moveToHead(node);
            return node.value;
        }
    }
    
    public void put(int key, int value) {
        synchronized (lock) {
            if (cache.containsKey(key)) {
                Node node = cache.get(key);
                node.value = value;
                moveToHead(node);
            } else {
                Node newNode = new Node(key, value);
                cache.put(key, newNode);
                addToHead(newNode);
                
                if (cache.size() > capacity) {
                    Node tailNode = removeTail();
                    cache.remove(tailNode.key);
                }
            }
        }
    }
    
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

// 4. 优化版3：支持过期时间的LRU（扩展功能）
class LRUCacheWithExpiry {
    private static class Node {
        int key;
        int value;
        long expiryTime;  // 过期时间戳（毫秒）
        Node prev;
        Node next;
        
        Node(int key, int value, long ttl) {
            this.key = key;
            this.value = value;
            this.expiryTime = System.currentTimeMillis() + ttl;
        }
        
        // 判断是否过期
        boolean isExpired() {
            return System.currentTimeMillis() > expiryTime;
        }
    }
    
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;
    
    public LRUCacheWithExpiry(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        head = new Node(0, 0, 0);
        tail = new Node(0, 0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        
        Node node = cache.get(key);
        // 检查是否过期
        if (node.isExpired()) {
            removeNode(node);
            cache.remove(key);
            return -1;
        }
        
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value, long ttl) {
        // ttl: time to live，存活时间（毫秒）
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            node.expiryTime = System.currentTimeMillis() + ttl;  // 更新过期时间
            moveToHead(node);
        } else {
            // 先清理过期节点
            evictExpired();
            
            Node newNode = new Node(key, value, ttl);
            cache.put(key, newNode);
            addToHead(newNode);
            
            if (cache.size() > capacity) {
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
            }
        }
    }
    
    // 清理所有过期节点
    private void evictExpired() {
        List<Node> toRemove = new ArrayList<>();
        Node curr = head.next;
        while (curr != tail) {
            if (curr.isExpired()) {
                toRemove.add(curr);
            }
            curr = curr.next;
        }
        
        for (Node node : toRemove) {
            removeNode(node);
            cache.remove(node.key);
        }
    }
    
    // 以下方法与基础版相同
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

// 测试类
public class LRUCacheDemo {
    public static void main(String[] args) {
        // 测试经典实现
        LRUCacheClassic classicCache = new LRUCacheClassic(2);
        classicCache.put(1, 1);
        classicCache.put(2, 2);
        System.out.println(classicCache.get(1));  // 1
        classicCache.put(3, 3);                  // 淘汰2
        System.out.println(classicCache.get(2));  // -1
        classicCache.put(4, 4);                  // 淘汰1
        System.out.println(classicCache.get(1));  // -1
        System.out.println(classicCache.get(3));  // 3
        System.out.println(classicCache.get(4));  // 4
        
        // 测试LinkedHashMap实现
        LRUCacheLinkedHashMap linkedCache = new LRUCacheLinkedHashMap(2);
        linkedCache.put(1, 1);
        linkedCache.put(2, 2);
        System.out.println(linkedCache.get(1));  // 1
        linkedCache.put(3, 3);
        System.out.println(linkedCache.get(2));  // -1
    }
}

各版本优化说明

经典实现（双向链表 + 哈希表）：最基础的实现方式，手动维护双向链表和哈希表，通过哨兵节点（head/tail）简化边界处理，保证所有操作 O (1) 时间复杂度，适合理解 LRU 核心原理。
LinkedHashMap 实现：利用 Java 内置的LinkedHashMap（访问顺序模式）简化实现，通过重写removeEldestEntry方法自动淘汰最久未使用元素，代码量减少 70% 以上，适合生产环境快速开发。
并发安全实现：在经典实现基础上添加同步锁（synchronized），保证多线程环境下的操作安全性，适合并发场景（如服务器缓存），缺点是会引入锁开销。
支持过期时间的 LRU：扩展节点结构添加过期时间戳，get/put时检查并清理过期节点，结合了 LRU 和 TTL（Time-To-Live）两种淘汰策略，适合需要数据自动过期的场景（如会话缓存）。

LRU Cache 是缓存设计中的基础算法，其核心价值在于平衡了缓存命中率和实现复杂度。在实际应用中，可根据场景选择不同实现：快速开发选LinkedHashMap版本，高性能场景选经典手动实现，多线程环境选并发安全版，需要过期策略则选扩展版。对于访问模式特殊的场景，还可考虑 LRU 的变体（如 LFU、ARC 等）。