每日算法 — 使用java实现LRU缓存：哈希表与双向链表的高效协作

LRU（Least Recently Used，最近最少使用）缓存是一种经典的数据结构，广泛应用于操作系统内存管理、数据库缓冲池、分布式缓存（如Redis的淘汰策略）以及Web应用的本地缓存等场景。其核心思想是：当缓存容量满时，优先淘汰最久未被访问的数据，以保留近期活跃的数据。

本文将用Java从零实现一个完整的LRU缓存，深入讲解哈希表实现O(1)查找与双向链表维护访问顺序的核心机制，并扩展至线程安全版本。

一、为什么需要LRU缓存

在计算机系统中，内存访问速度远快于磁盘或网络。缓存通过将热点数据保留在内存中，显著降低后续访问的延迟。但内存容量有限，当缓存满时必须决定淘汰哪些数据。

常见的缓存淘汰策略包括：

LRU基于时间局部性原理：如果一个数据最近被访问过，那么它在未来被访问的概率也更高。这一假设在绝大多数实际场景中成立。

二、LRU的核心设计思路

要实现一个高效的LRU缓存，需要同时满足两个操作都在O(1)时间复杂度：

1. get(key)：查找某个key对应的value
2. put(key, value)：插入或更新一个键值对，并在容量满时淘汰最久未使用的数据

单一数据结构无法满足这两个需求：
– 哈希表：get和put都是O(1)，但无法记录访问顺序
– 链表：可以维护顺序，但查找需要O(n)

解决方案：哈希表 + 双向链表的强强联合

• 哈希表（HashMap）：存储key到链表节点的映射，实现O(1)查找
• 双向链表（Doubly Linked List）：按访问时间顺序存储节点，头部为最近访问，尾部为最久未访问，实现O(1)的移动和删除

三、数据结构定义

3.1 双向链表节点

/**
 * 双向链表节点，同时存储key和value
 * 存储key的目的是在淘汰尾部节点时，能通过key从哈希表中删除对应映射
 */
class Node {
    int key;
    int value;
    Node prev;
    Node next;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

3.2 链表操作封装

为了简化LRUCache的实现，我们将链表操作（添加到头部、删除节点、移动节点到头部）封装在独立方法中。

/**
 * LRU缓存核心实现
 * 时间复杂度：get和put均为O(1)
 * 空间复杂度：O(capacity)
 */
public class LRUCache {

    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head; // 伪头部：最近使用的节点
    private final Node tail; // 伪尾部：最久未使用的节点
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        // 使用伪头部和伪尾部简化边界判断
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }
}

四、核心操作实现

4.1 移动到头部（标记为最近使用）

/**
 * 将节点移动到链表头部（标记为最近使用）
 * 步骤：先删除原位置，再插入头部
 */
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;
}

4.2 淘汰尾部节点（移除最久未使用）

/**
 * 删除链表尾部节点（最久未使用），并返回该节点
 * 用于容量满时淘汰数据
 */
private Node removeTail() {
    Node node = tail.prev;
    removeNode(node);
    return node;
}

4.3 get操作：O(1)查找与更新

/**
 * 获取key对应的value
 * 如果key存在，将其移动到链表头部（标记为最近使用），返回value
 * 如果key不存在，返回-1
 */
public int get(int key) {
    Node node = cache.get(key);
    if (node == null) {
        return -1; // key不存在
    }
    // 访问过，移动到头部
    moveToHead(node);
    return node.value;
}

4.4 put操作：插入、更新与淘汰

/**
 * 插入或更新键值对
 * 如果key已存在，更新value并移动到头部
 * 如果key不存在，创建新节点插入头部；若容量满，先淘汰尾部节点
 */
public void put(int key, int value) {
    Node node = cache.get(key);
    if (node != null) {
        // key已存在，更新value并移动到头部
        node.value = value;
        moveToHead(node);
        return;
    }

    // key不存在，创建新节点
    Node newNode = new Node(key, value);
    cache.put(key, newNode);
    addToHead(newNode);
    size++;

    // 超出容量，淘汰尾部节点
    if (size > capacity) {
        Node tailNode = removeTail();
        cache.remove(tailNode.key);
        size--;
    }
}

五、完整Java代码

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存实现（哈希表 + 双向链表）
 * get和put操作时间复杂度均为O(1)
 */
public class LRUCache {

    /**
     * 双向链表节点
     */
    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 int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

    /**
     * 获取key对应的value，不存在返回-1
     * 每次get都会将该节点提升为最近使用
     */
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    /**
     * 插入或更新键值对
     */
    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }

        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        addToHead(newNode);
        size++;

        if (size > capacity) {
            Node tailNode = removeTail();
            cache.remove(tailNode.key);
            size--;
        }
    }

    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 void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }

    /**
     * 打印当前缓存状态（调试用）
     */
    public void printCache() {
        System.out.print("Cache[head->tail]: ");
        Node cur = head.next;
        while (cur != tail) {
            System.out.print("(" + cur.key + "=" + cur.value + ") ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 主程序：演示LRU缓存的工作过程
     */
    public static void main(String[] args) {
        System.out.println("=== LRU缓存演示（容量=3） ===\n");

        LRUCache cache = new LRUCache(3);

        // 步骤1：依次插入1, 2, 3
        System.out.println("插入 (1=10), (2=20), (3=30)");
        cache.put(1, 10);
        cache.put(2, 20);
        cache.put(3, 30);
        cache.printCache(); // 3, 2, 1

        // 步骤2：访问key=1，将其提升到最近使用
        System.out.println("\nget(1) = " + cache.get(1));
        cache.printCache(); // 1, 3, 2

        // 步骤3：插入4，超出容量，淘汰最久未使用的2
        System.out.println("\n插入 (4=40)，容量满，淘汰key=2");
        cache.put(4, 40);
        cache.printCache(); // 4, 1, 3

        // 步骤4：访问3，提升到最近使用
        System.out.println("\nget(3) = " + cache.get(3));
        cache.printCache(); // 3, 4, 1

        // 步骤5：插入5，淘汰最久未使用的1
        System.out.println("\n插入 (5=50)，淘汰key=1");
        cache.put(5, 50);
        cache.printCache(); // 5, 3, 4

        // 步骤6：访问不存在的key
        System.out.println("\nget(2) = " + cache.get(2) + " (已被淘汰)");

        // 步骤7：更新已有key的值
        System.out.println("\n更新 (3=300)");
        cache.put(3, 300);
        cache.printCache(); // 3, 5, 4

        System.out.println("\n=== 演示结束 ===");
    }
}

六、Java标准库的LinkedHashMap方案

Java标准库中的LinkedHashMap已经内置了LRU支持，只需重写removeEldestEntry方法即可：

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

/**
 * 基于LinkedHashMap的LRU缓存实现
 * 代码更简洁，但理解底层原理对面试至关重要
 */
public 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;
    }

    /**
     * 当插入新元素后，如果此方法返回true，则删除最老的元素
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    public static void main(String[] args) {
        LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3); // 淘汰key=2
        System.out.println(cache.get(2)); // -1
        System.out.println(cache.get(3)); // 3
    }
}

虽然LinkedHashMap方案简洁，但面试和工程深入理解时，手写哈希表+双向链表的版本更能展示对数据结构的掌控力。

七、线程安全扩展

在多线程环境中，需要对get和put方法加锁。可以使用synchronized或ReentrantReadWriteLock优化读多写少的场景：

import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 线程安全的LRU缓存
 * 使用读写锁优化并发性能：允许多个线程同时读，写操作独占
 */
public class ConcurrentLRUCache {

    private final LRUCache cache;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final ReentrantReadWriteLock.ReadLock readLock = lock.readLock();
    private final ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock();

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

    public int get(int key) {
        readLock.lock();
        try {
            return cache.get(key);
        } finally {
            readLock.unlock();
        }
    }

    public void put(int key, int value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }
}

八、复杂度分析

九、实际应用场景

• 数据库连接池：缓存最近使用的数据库连接，避免频繁创建和销毁
• 图片/资源缓存：Android的LruCache就是基于此原理
• DNS缓存：操作系统缓存最近解析的域名，加速后续访问
• CPU缓存行：硬件层面的LRU近似算法管理缓存行替换
• Redis：支持allkeys-lru淘汰策略，在内存满时自动淘汰冷数据

十、总结

LRU缓存是数据结构与算法结合的完美典范：

1. 哈希表提供O(1)的键值查找能力，是”快速定位”的基石
2. 双向链表提供O(1)的顺序维护能力，是”有序管理”的基石
3. 两者的配合使得LRU的两个核心操作都在常数时间内完成

掌握LRU缓存的实现，不仅能应对各类算法面试，更能帮助你在实际工程中设计出高效的缓存系统。从LinkedHashMap的简洁方案到手写双向链表的底层方案，建议先理解后者，再使用前者提升开发效率。