在Java中,可以使用LinkedList类来实现LRU(最近最少使用)缓存淘汰算法。以下是一个示例代码实现:
import java.util.LinkedList;
public class LRUCache {
private int capacity;
private LinkedList<Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new LinkedList<>();
}
public int get(int key) {
if (cache.contains(key)) {
// 移除已存在的key,并将其添加到链表头部
cache.remove((Integer) key);
cache.addFirst(key);
return key;
} else {
return -1;
}
}
public void put(int key) {
if (cache.contains(key)) {
// 如果key已存在,移除旧位置,将其添加到链表头部
cache.remove((Integer) key);
cache.addFirst(key);
} else {
if (cache.size() >= capacity) {
// 如果缓存已满,删除链表尾部的元素
cache.removeLast();
}
cache.addFirst(key);
}
}
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(3);
lruCache.put(1);
lruCache.put(2);
lruCache.put(3);
lruCache.put(4);
System.out.println(lruCache.get(2)); // 输出-1
System.out.println(lruCache.get(1)); // 输出1
lruCache.put(5);
System.out.println(lruCache.get(3)); // 输出-1
System.out.println(lruCache.get(4)); // 输出4
System.out.println(lruCache.get(5)); // 输出5
}
}
在LRUCache类中,我们使用容量变量capacity和链表cache来实现LRU缓存。链表的头部代表最新使用的元素,尾部代表最久未使用的元素。
get方法用于获取缓存中的元素。如果元素存在,我们将其从链表中移除并添加到头部,然后返回该元素。如果元素不存在,返回-1。
put方法用于存储元素到缓存中。首先判断元素是否已经存在于缓存中,如果存在,将其从链表中移除并添加到头部。如果不存在,判断当前缓存是否已满,如果已满,删除链表尾部元素,然后将新的元素添加到头部。
在示例中,我们创建了一个容量为3的LRUCache对象。依次放入1、2、3、4,并尝试再次获取2、1、3、4、5元素。根据LRU缓存淘汰算法,获取结果符合预期的缓存淘汰顺序及结果。