用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)$的操作。