java lru linkedlist

admin 2026年02月06日 04:30 102 0

Java中基于LinkedList实现LRU缓存，核心思想是通过双向链表维护节点访问顺序，HashMap存储键与节点的映射以实现O(1)访问，当访问节点时，将其移至链表头部；插入新节点时，若容量已满，移除链表尾部节点（最少使用），LinkedList的快速插入删除特性结合HashMap的键值查找，确保get和put操作均能在常数时间内完成，高效满足LRU缓存的核心需求。

Java中基于LinkedList与HashMap的LRU缓存实现与优化

LRU缓存：从概念到需求

在计算机系统中,缓存是提升性能的核心手段之一，当高速存储（如CPU缓存、内存）容量有限时，必须采用一种策略来决定哪些数据应保留在缓存中，哪些数据在容量不足时应被淘汰。LRU（Least Recently Used，最近最少使用）算法是应用最广泛的淘汰策略之一，其核心假设是：最近被访问的数据在未来更有可能被再次访问，当缓存满载时，LRU策略会优先淘汰最久未被使用的数据。

LRU缓存的应用场景广泛,包括但不限于：数据库查询缓存、操作系统页面置换算法、分布式系统中的数据分片缓存、浏览器“前进/后退”历史记录管理、热门商品推荐系统等，这些场景都需要高效地管理缓存数据，在有限的内存空间内最大化命中率，在Java中，实现一个高性能LRU缓存的核心挑战在于：如何同时满足对get（访问）和put（添加/更新）操作的快速响应（时间复杂度O(1)），并动态维护数据的“最近使用”访问顺序，本文将深入探讨如何利用LinkedList（双向链表）和HashMap协同工作，构建一个高效、健壮的LRU缓存实现，并分析其优化思路。

LRU缓存的核心设计思路

一个合格的LRU缓存必须满足两个核心性能需求：

快速访问定位：根据给定的key，必须能在O(1)时间内找到对应的value。
高效顺序维护：每次数据被访问（无论是get成功还是put新数据/更新数据）时，该数据需要被标记为“最近使用”；当缓存容量达到上限时，必须能快速定位并淘汰“最久未使用”的数据。

单独使用LinkedList或HashMap均无法完美满足上述需求：

LinkedList（双向链表）：支持在头部（O(1)）插入和在尾部（O(1)）删除操作，非常适合维护顺序，其查找操作需要遍历整个链表，时间复杂度为O(n)，无法满足快速访问的要求。
HashMap：基于哈希表实现，能提供O(1)平均时间复杂度的key-value查找，完美解决了快速访问问题，但它本身是无序的，无法直接维护数据的访问时间顺序。

组合使用HashMap与LinkedList成为解决此问题的经典方案：

HashMap：存储key到链表节点（ListNode）的映射，利用其O(1)的查找能力，快速定位到链表中对应的节点。
LinkedList：双向链表存储所有缓存节点，节点按照“最近使用”到“最久未使用”的顺序排列：链表头部（head.next）代表最近访问的节点，链表尾部（tail.prev）代表最久未使用的节点，每次访问节点时，将其移动到链表头部；淘汰时则移除尾部节点。

这种组合巧妙地利用了两种数据结构的优势：HashMap提供快速索引，LinkedList维护访问顺序，共同实现了LRU缓存所需的高效操作。

基于Java的LRU缓存实现

定义双向链表节点（`ListNode`）

我们需要一个自定义的双向链表节点类,每个节点除了存储键值对（key, value）外，还需包含指向前驱节点（prev）和后继节点（next）的引用，特别地，key字段是必需的，因为当需要从链表中移除一个节点（尤其是淘汰尾部节点时）时，需要通过该key从HashMap中删除对应的映射关系。

/**
 * 双向链表节点类
 * @param  键类型
 * @param  值类型
 */
class ListNode<K, V> {
    K key;
    V value;
    ListNode<K, V> prev;  // 前驱节点
    ListNode<K, V> next;  // 后继节点
public ListNode(K key, V value) {
    this.key = key;
    this.value = value;
}

实现LRUCache核心类

定义LRUCache类，它包含以下核心组件：

int capacity：缓存的固定容量上限。
int size：当前缓存中存储的键值对数量。
ListNode<K, V> head / ListNode<K, V> tail：双向链表的**虚拟头节点**和**虚拟尾节点**，使用虚拟头尾节点可以极大地简化链表头部插入、尾部删除以及节点移除时的边界条件判断（无需单独处理链表为空或只有一个节点的情况）。
Map<K, ListNode<K, V>> cache：HashMap，用于存储key到链表节点的映射，实现O(1)的节点查找。

核心方法包括：

get(K key)：获取指定key对应的value，如果key存在，则将该节点标记为“最近使用”（移动到链表头部）并返回value；如果key不存在，返回null。
put(K key, V value)：添加或更新键值对，如果key已存在，则更新其value并标记为“最近使用”（移动到头部）；如果key不存在，则创建新节点添加到链表头部并更新HashMap，同时检查缓存是否已满（size > capacity），若满则淘汰链表尾部（最久未使用）的节点及其HashMap映射。
私有辅助方法：
- addToHead(ListNode<K, V> node)：将指定节点添加到链表头部（紧邻虚拟头节点之后）。
- removeNode(ListNode<K, V> node)：从链表中移除指定节点（不涉及HashMap操作）。
- removeTail()：移除链表尾部节点（紧邻虚拟尾节点之前的节点），并返回该被移除的节点（