Java用LinkedList实现LRU缓存的数据结构和算法

LRU是什么？大家都不陌生，具体怎么实现还没实现过，今天就来实现一下。

一、什么是 LRU 缓存？

LRU（Least Recently Used，最近最少使用）缓存是一种缓存淘汰策略，用于管理缓存中的数据。

当缓存容量有限时，它决定了哪些数据应该被移除。LRU 缓存的核心思想是：当缓存满时，移除最久没有被访问过的数据（即最近最少使用的数据）。

二、为什么需要 LRU 缓存？

在现代应用中，尤其是高性能系统，通常需要处理大量的用户请求。为了提高系统的响应速度，许多应用会使用缓存来存储常用数据，避免频繁地进行计算或访问慢速存储（如数据库或文件系统）。

但是，由于缓存的大小通常有限，缓存中无法存储所有可能的数据，所以需要制定一些策略来决定哪些数据应该保留，哪些应该被移除。

LRU（最近最少使用）就是其中一种非常有效的策略。当缓存空间已满时，LRU 会移除最近最少使用的数据，保留那些最近被访问过的数据。

三、LRU 缓存的工作原理

LRU 缓存的工作原理可以通过两个主要的操作来描述：插入（Put） 和 查询（Get）。

1、插入数据（Put 操作）

当将一个新数据（key 和 value）插入缓存时，如果缓存容量没有满，直接插入并将该数据标记为最近访问。

如果缓存已满，需要移除最久未使用的数据。LRU 缓存会移除双向链表尾部的节点（最久未使用的），并将新数据插入到链表头部（表示最新使用）。

2、查询数据（Get 操作）

当查询一个数据时，首先通过哈希表查找该数据是否存在。

如果数据存在，则返回值，并将该数据标记为最近访问，通过将其移到链表头部来更新其访问顺序。

如果数据不存在，则返回一个空值或失败标志（如 -1）。

3、缓存满时的处理

如果缓存已经满了，当插入新数据时，LRU 缓存会选择移除双向链表的尾部节点（即最久没有被访问的节点），然后将新的数据插入到头部。

这个移除尾部节点的操作和插入头部节点的操作都可以在 O(1) 时间复杂度内完成，从而保持高效的缓存管理。

四、LRU 缓存的设计理念

LRU 缓存的设计理念是基于时间局部性和空间局部性：

时间局部性：如果某个数据被访问过，那么很有可能在不久的将来它还会被访问。这种访问模式非常常见，尤其是在计算机程序中。如果某个数据最近被频繁访问，那么它很可能是热点数据，应该保留在缓存中。

空间局部性：某些数据结构或缓存中，访问某个数据往往会访问到相邻的数据。因此，LRU 策略也考虑了数据的邻近性，尽量保留一部分数据，并且删除一些长期未被使用的部分。

LRU 缓存结合了哈希表和双向链表的优点，能够在 O(1) 时间内完成数据的插入、删除和查询操作。因此，它在高性能系统中非常适用。

五、LRU 缓存应用示例

这段代码实现了一个 LRU (Least Recently Used) Cache（最近最少使用缓存），用于模拟一个具有固定容量的缓存系统，缓存中存储的是键值对（key-value）。在该缓存中，当达到容量限制时，会自动移除最久未使用的项。

import java.util.HashMap;

import java.util.LinkedList;

/**

* 最近最少使用数据结构

* @param <K>

* @param <V>

*

*/

class LRUCache<K, V> {

// 最大容量

private final int capacity;

// 最近访问的索引

private LinkedList<K> cacheList;

// 存储key对应value的集合

private HashMap<K, V> cacheMap;

public LRUCache(int capacity) {

this.capacity = capacity;

this.cacheList = new LinkedList<>();

this.cacheMap = new HashMap<>();

}

// 获取缓存中的值

public V get(K key) {

if (!cacheMap.containsKey(key)) {

System.out.println("null");

return null; // 如果key不存在，返回null

}

// 如果key存在，将其移到链表头部（表示最近使用）

cacheList.remove(key);

cacheList.addFirst(key);

System.out.println(cacheMap.get(key));

return cacheMap.get(key);

}

// 插入新的值

public void put(K key, V value) {

// 如果key已经存在，更新值并移到链表头部

if (cacheMap.containsKey(key)) {

cacheList.remove(key);

} else if (cacheList.size() == capacity) {

// 如果缓存已满，移除链表尾部（最久未使用的）

K oldestKey = cacheList.removeLast();

cacheMap.remove(oldestKey);

}

// 添加新的值到链表头部并更新HashMap

cacheList.addFirst(key);

cacheMap.put(key, value);

}

// 打印当前缓存状态

public void printCache() {

for (K key : cacheList) {

System.out.print(key + ":" + cacheMap.get(key) + " ");

}

System.out.println();

//System.out.println(cacheList);

}

}

// 测试 LRUCache

public class LRUCacheExample{

public static void main(String[] args) {

LRUCache<Integer, String> cache = new LRUCache<>(3);

cache.put(1, "A");

cache.printCache(); // 输出: 1:A

cache.put(2, "B");

cache.printCache(); // 输出: 2:B 1:A

cache.get(1); // 使用key 1,返回A

cache.printCache(); // 输出: 1:A 2:B

cache.put(3, "C"); // 插入新元素

cache.printCache(); // 输出:3:C 1:A 2:B

cache.get(2); // 使用key 2,返回B

cache.printCache(); // 输出: 2:B 3:C 1:A

cache.put(4, "D"); // 插入新元素，容量已满，移除key 1

cache.printCache(); // 输出: 4:D 2:B 3:C

cache.get(1); // 使用key 3，返回null

cache.printCache(); // 输出: 4:D 2:B 3:C

}

}

代码解读：

1、 LRUCache 类

该类包含了实现LRU缓存所需要的主要数据结构和方法。它通过两个核心的数据结构来管理缓存：

cacheList：一个 LinkedList<K> 用于维护缓存中的键的顺序。这个链表的头部代表最近使用的元素，尾部代表最久未使用的元素。

cacheMap：一个 HashMap<K, V> 用于存储键值对，提供快速的O(1)查找操作。

2、主要成员变量：

capacity：表示缓存的最大容量。

cacheList：用于记录最近使用的元素顺序。

cacheMap：用于存储键值对。

3、构造函数 LRUCache(int capacity)

构造函数初始化了缓存的最大容量 capacity，并创建了一个空的 LinkedList（用于记录元素访问顺序）和一个空的 HashMap（用于存储键值对）。

4、方法：get(K key)

该方法尝试从缓存中获取 key 对应的值。

如果 key 不存在于 cacheMap 中，返回 null。

如果 key 存在，先将该 key 从 cacheList 中移除，然后再将其添加到链表的头部，表示该元素被最近访问过。这样，链表的顺序就会反映出最近的使用顺序。

最后，返回缓存中的值。

5、 方法：put(K key, V value)

该方法用于插入新的键值对到缓存中。

如果 key 已经存在于缓存中，则更新它的值并将其移到链表头部。

如果 key 不存在且缓存未满，则将其直接插入到链表头部，并添加到 cacheMap 中。

如果缓存已满，需要移除链表尾部（即最久未使用的项），然后再插入新的键值对。

6、方法：printCache()

该方法用于打印当前缓存中的所有键值对，按照链表中的顺序（即最近使用的顺序）输出。

7、main方法

在 main 方法中，创建了一个容量为 3 的 LRUCache 实例，并通过多个操作测试了缓存的行为：

插入元素，检查缓存的状态。

获取元素，检查元素的顺序是否更新。

当缓存已满时，插入新元素，检查最久未使用的元素是否被移除。

8、具体测试过程：

插入元素 (1, "A")，打印缓存状态。

插入元素 (2, "B")，打印缓存状态。

访问元素 1，将其移动到链表头部，打印缓存状态。

插入元素 (3, "C")，打印缓存状态。

访问元素 2，将其移动到链表头部，打印缓存状态。

插入元素 (4, "D")，因为缓存已满，移除最久未使用的元素 1，打印缓存状态。

尝试访问元素 1，因为 1 已被移除，打印 null，并打印缓存状态。

运行结果：

1:A

2:B 1:A

1:A 2:B

3:C 1:A 2:B

2:B 3:C 1:A

4:D 2:B 3:C

null

4:D 2:B 3:C

该代码实现了一个简单的 LRU 缓存，它通过一个 LinkedList 来跟踪元素的使用顺序，通过一个 HashMap 来实现 O(1) 的快速访问。当缓存容量满时，最久未使用的元素会被自动移除。

六、为什么使用双向链表和哈希表？

LRU 缓存通常使用双向链表和哈希表的组合来实现高效的缓存管理：

哈希表：用于 O(1) 时间复杂度下查找数据。

双向链表：用于 O(1) 时间复杂度下移动节点（将节点移动到链表头部），以及移除最久未访问的节点（从链表尾部移除）。

哈希表提供快速的查找，而双向链表保证了在 O(1) 时间内对节点的插入、删除和更新操作。

最后总结

LRU 缓存是一个非常常用的缓存策略，它通过维护一个双向链表和哈希表的结合，能够在常数时间内完成插入、删除和查询操作，从而高效地管理有限的缓存空间，减少了缓存失效和频繁的数据重新加载，适用于高性能、高并发的系统。