用Java写一个LRU算法
时间: 2023-04-05 19:03:16 浏览: 65
好的,我可以回答这个问题。LRU算法是一种缓存淘汰策略,它会优先淘汰最近最少使用的缓存数据。在Java中,可以使用LinkedHashMap来实现LRU算法,具体实现可以参考以下代码:
```
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
```
这个LRUCache类继承了LinkedHashMap,并重写了removeEldestEntry方法,当缓存数据超过容量时,会自动淘汰最近最少使用的数据。
相关问题
用Java写一个Lru算法
下面是一个简单的 Java 实现 LRU 算法的示例代码:
```
import java.util.*;
public class LRU {
private static final int MAX_SIZE = 5;
private Deque<Integer> deque;
private Map<Integer, Integer> map;
public LRU() {
deque = new LinkedList<>();
map = new HashMap<>();
}
public void put(int key, int value) {
if (map.containsKey(key)) {
deque.remove(key);
deque.offerFirst(key);
map.put(key, value);
} else {
if (deque.size() == MAX_SIZE) {
int removedKey = deque.removeLast();
map.remove(removedKey);
}
deque.offerFirst(key);
map.put(key, value);
}
}
public int get(int key) {
if (map.containsKey(key)) {
deque.remove(key);
deque.offerFirst(key);
return map.get(key);
}
return -1;
}
public static void main(String[] args) {
LRU lru = new LRU();
lru.put(1, 1);
lru.put(2, 2);
lru.put(3, 3);
lru.put(4, 4);
lru.put(5, 5);
System.out.println(lru.map);
lru.get(5);
lru.get(4);
System.out.println(lru.map);
lru.put(6, 6);
System.out.println(lru.map);
lru.put(7, 7);
System.out.println(lru.map);
}
}
```
这个实现中,我们使用双向链表来维护 LRU 缓存,并将键值对存储在一个哈希表中。每次插入元素时,我们检查是否存在此键,如果存在,则将其从链表中移除并重新插入到链表头部,否则,我们检查链表是否已满,如果已满,则删除链表中的最后一个元素,并从哈希表中删除相应键的映射。在获取元素时,我们从哈希表中获取值并调整节点的位置。
这个实现的时间复杂度为$O(1)$,因为在哈希表中查找键和在链表中移动节点都是$O(1)$的操作。
用Java写一个LRU置换算法
LRU(Least Recently Used)置换算法是一种常用的缓存置换算法,用于替换缓存中最近最少使用的页面。下面是Java代码实现LRU置换算法的示例:
```
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
System.out.println(cache);
cache.put("d", 4);
System.out.println(cache);
}
}
```
LRUCache类继承自LinkedHashMap,并重写了removeEldestEntry()方法,用于判断是否需要删除最老的元素。在LRUCache构造函数中,调用了父类构造函数,并传递了容量、负载因子、以及accessOrder参数。accessOrder参数为true时,表示采用访问顺序而不是插入顺序。
在main函数中,我们创建了一个容量为3的LRUCache对象,并插入了三个元素。输出cache对象时,会发现元素的顺序是访问的顺序。当插入第四个元素时,由于容量只有3个,最老的元素将被删除,即"a":1。最后再输出cache对象,可以看到"a":1已经被删除了。
这就是一个简单的LRU置换算法的Java实现,希望能解决您的问题。