Java 实现 LRU 算法的方法有多种，包括使用 LinkedHashMap、手动实现自定义数据结构和使用第三方库等。本文将介绍这些方法的实现细节，并给出相关代码示例。 我们将详细探讨 LinkedHashMap 的使用方式，并介绍如何手动实现自定义的数据结构。

一、使用 LinkedHashMap 实现 LRU 算法

1. LinkedHashMap 简介

LinkedHashMap 是 Java 提供的一个集合类，它继承了 HashMap，并保持了元素的插入顺序或者最近访问顺序。通过这种特性，我们可以轻松地实现 LRU 缓存。

2. 实现步骤

我们可以通过重写 LinkedHashMap 的 removeEldestEntry 方法来实现 LRU 缓存。当缓存中的元素个数超过指定的容量时，最久未使用的元素会被移除。

import java.util.LinkedHashMap;

import java.util.Map;

public class LRUCache extends LinkedHashMap {

private final int capacity;

public LRUCache(int capacity) {

super(capacity, 0.75f, true);

this.capacity = capacity;

}

@Override

protected boolean removeEldestEntry(Map.Entry eldest) {

return size() > capacity;

}

public static void main(String[] args) {

LRUCache cache = new LRUCache<>(3);

cache.put(1, "one");

cache.put(2, "two");

cache.put(3, "three");

System.out.println(cache); // {1=one, 2=two, 3=three}

cache.get(1);

cache.put(4, "four");

System.out.println(cache); // {2=two, 3=three, 1=one, 4=four}

}

}

3. 详细解释

在上面的代码中，我们创建了一个容量为 3 的 LRU 缓存。当缓存中的元素个数超过 3 时，最久未使用的元素将被自动移除。通过 super(capacity, 0.75f, true) 构造器，我们启用了访问顺序模式，这样最近访问的元素会被移到链表的末尾。

二、手动实现自定义数据结构

1. 自定义数据结构简介

有时我们可能需要更灵活的实现，或者 LinkedHashMap 无法满足我们的需求。这时，我们可以手动实现 LRU 缓存。我们将使用双向链表和哈希表来实现。

2. 实现步骤

双向链表用于维护元素的顺序，哈希表用于快速查找元素。

import java.util.HashMap;

import java.util.Map;

class Node {

K key;

V value;

Node prev;

Node next;

public Node(K key, V value) {

this.key = key;

this.value = value;

}

}

public class LRUCache {

private final int capacity;

private final Map> map;

private final Node head;

private final Node tail;

public LRUCache(int capacity) {

this.capacity = capacity;

this.map = new HashMap<>(capacity);

this.head = new Node<>(null, null);

this.tail = new Node<>(null, null);

head.next = tail;

tail.prev = head;

}

public V get(K key) {

Node node = map.get(key);

if (node == null) return null;

moveToHead(node);

return node.value;

}

public void put(K key, V value) {

Node node = map.get(key);

if (node == null) {

node = new Node<>(key, value);

map.put(key, node);

addNode(node);

if (map.size() > capacity) {

Node tail = popTail();

map.remove(tail.key);

}

} else {

node.value = value;

moveToHead(node);

}

}

private void addNode(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);

addNode(node);

}

private Node popTail() {

Node res = tail.prev;

removeNode(res);

return res;

}

public static void main(String[] args) {

LRUCache cache = new LRUCache<>(3);

cache.put(1, "one");

cache.put(2, "two");

cache.put(3, "three");

System.out.println(cache.get(1)); // one

cache.put(4, "four");

System.out.println(cache.get(2)); // null

}

}

3. 详细解释

在上面的代码中，我们创建了一个容量为 3 的 LRU 缓存。addNode 方法将新节点添加到链表的头部，removeNode 方法移除指定节点，moveToHead 方法将节点移到链表的头部，popTail 方法移除并返回链表的尾节点。

三、使用第三方库实现 LRU 算法

1. 第三方库简介

有许多第三方库提供了 LRU 缓存的实现，如 Guava 和 Caffeine。使用这些库可以简化我们的工作。

2. 使用 Guava 实现 LRU 缓存

Guava 是 Google 提供的一个 Java 库，它包含了一些常用的集合类和工具类。

import com.google.common.cache.Cache;

import com.google.common.cache.CacheBuilder;

import java.util.concurrent.TimeUnit;

public class LRUCache {

private final Cache cache;

public LRUCache(int capacity) {

this.cache = CacheBuilder.newBuilder()

.maximumSize(capacity)

.expireAfterAccess(10, TimeUnit.MINUTES)

.build();

}

public V get(K key) {

return cache.getIfPresent(key);

}

public void put(K key, V value) {

cache.put(key, value);

}

public static void main(String[] args) {

LRUCache cache = new LRUCache<>(3);

cache.put(1, "one");

cache.put(2, "two");

cache.put(3, "three");

System.out.println(cache.get(1)); // one

cache.put(4, "four");

System.out.println(cache.get(2)); // null

}

}

3. 使用 Caffeine 实现 LRU 缓存

Caffeine 是一个高性能的 Java 缓存库，它提供了类似 Guava 的 API。

import com.github.benmanes.caffeine.cache.Cache;

import com.github.benmanes.caffeine.cache.Caffeine;

import java.util.concurrent.TimeUnit;

public class LRUCache {

private final Cache cache;

public LRUCache(int capacity) {

this.cache = Caffeine.newBuilder()

.maximumSize(capacity)

.expireAfterAccess(10, TimeUnit.MINUTES)

.build();

}

public V get(K key) {

return cache.getIfPresent(key);

}

public void put(K key, V value) {

cache.put(key, value);

}

public static void main(String[] args) {

LRUCache cache = new LRUCache<>(3);

cache.put(1, "one");

cache.put(2, "two");

cache.put(3, "three");

System.out.println(cache.get(1)); // one

cache.put(4, "four");

System.out.println(cache.get(2)); // null

}

}

4. 详细解释

在上面的代码中，我们使用 Guava 和 Caffeine 库分别实现了一个容量为 3 的 LRU 缓存。通过 maximumSize 方法设置缓存的最大容量，通过 expireAfterAccess 方法设置缓存的过期时间。

四、总结

通过使用 LinkedHashMap、手动实现自定义数据结构和使用第三方库，我们可以在 Java 中轻松实现 LRU 算法。 每种方法都有其优缺点，开发者可以根据具体需求选择合适的方法。 LinkedHashMap 简单易用，适合大多数场景；自定义数据结构灵活性高，适合特殊需求；第三方库功能强大，适合复杂场景。 在实际开发中，我们应根据具体情况选择最合适的实现方式，确保系统的性能和稳定性。

相关问答FAQs：

1. 什么是LRU算法？LRU算法（Least Recently Used）是一种常用的缓存淘汰算法，它根据数据的访问顺序来决定哪些数据被保留在缓存中，哪些数据被淘汰。

2. Java中如何实现LRU算法？在Java中，可以通过LinkedHashMap来实现LRU算法。LinkedHashMap是HashMap的一个子类，它使用双向链表来维护插入顺序或者访问顺序。通过设置accessOrder参数为true，可以使LinkedHashMap按照访问顺序来排序，最近访问的元素会被放到链表尾部。

3. 如何使用Java实现一个简单的LRU缓存？可以通过继承LinkedHashMap来实现一个简单的LRU缓存。首先，需要重写LinkedHashMap的removeEldestEntry方法，当缓存大小超过指定阈值时，删除最近最少使用的元素。然后，可以通过使用LinkedHashMap的构造方法来指定缓存大小和accessOrder参数，从而实现一个基于LRU算法的缓存。

原创文章，作者：Edit2，如若转载，请注明出处：https://docs.pingcode.com/baike/176513