用Java写一个LRU算法

好的，我可以回答这个问题。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 int capacity;

    public LRUCache(int capacity) {
        // 第三个参数设置为true，表示使用访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(2);
        cache.put("a", 1);
        cache.put("b", 2);
        System.out.println(cache); // {a=1, b=2}
        cache.put("c", 3);
        System.out.println(cache); // {b=2, c=3}
        cache.get("b");
        System.out.println(cache); // {c=3, b=2}
        cache.put("d", 4);
        System.out.println(cache); // {b=2, d=4}
    }
}

这里使用了Java内置的LinkedHashMap作为缓存数据结构，重写了removeEldestEntry方法判断是否需要移除最久未使用的元素。在LRUCache的构造函数中，通过传入accessOrder参数为true，表示使用访问顺序排序，即最近被访问的元素排在最前面。当缓存已满需要移除元素时，LinkedHashMap会自动删除最近最少使用的元素，从而实现了LRU策略。