如何在Java中实现LRU缓存算法

原创女爷i 2024-12-07 21:27 4阅读 0赞

LRU（Least Recently Used，最近最少使用）是一种常用的缓存淘汰策略。在Java中，可以通过以下步骤来实现一个简单的LRU缓存：

1. 创建一个Cache类，作为缓存的容器。

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

public class LRUCache {
    private int capacity; // 缓存容量
    private Map<Integer, Node> cacheMap; // 树形结构存储键值对

public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>(capacity);
    }

// 主方法，插入和删除操作
    public void put(int key, int value) {
        if (cacheMap.size() >= capacity) {
            // 超过容量的元素将被移除（淘汰）
            cacheMap.removeLastEntry();
        }
        
        Node newNode = new Node(key, value);
        cacheMap.put(key, newNode);
    }

public void remove(int key) {
        if (cacheMap.containsKey(key)) {
            Node node = cacheMap.get(key);
            
            // 移除节点，同时移除键值对
            cacheMap.remove(node.getKey());
        }
    }

// 取值操作
    public int get(int key) {
        return cacheMap.getOrDefault(key, new Node(-1, -1))).getValue();
    }
}
```

2. 创建Node类，用于存储缓存的键值对。

```java
class Node {
    private int key;
    private int value;
    private Node prev;
    private Node next;

public Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }

// 获取键值对
    public int getKey() {
        return key;
    }

public int getValue() {
        return value;
    }
}
```

3. 在主方法中，可以测试LRU缓存的插入、删除和获取功能。

```java
public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(5); // 创建一个容量为5的缓存

// 插入元素
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.put(4, 4);

// 打印缓存
        for (Map.Entry<Integer, Node>> entry : cache.cacheMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue().getValue());
        }

// 删除元素
        cache.remove(3);

// 再次打印缓存，可以发现3已经被移除
        for (Map.Entry<Integer, Node>> entry : cache.cacheMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue().getValue());
        }

// 获取元素
        int retrievedValue = cache.get(2);
        System.out.println("Retrieved value for key 2: " + retrievedValue);
    }
}
```

这样，你就实现了一个简单的LRU缓存算法。这个实现可能不完全符合LRU的最优性能，但足够理解基本原理。对于更复杂的需求，你可能需要使用现成的缓存库，如Guava、JCache等。