什么是LRU缓存？

LRU缓存（Least Recently Used）是一种常用的缓存淘汰算法，它根据数据的使用时间来决定哪些数据需要被移除。这种算法假设最近使用的数据会在未来一段时间内继续被使用，而很久没有使用的数据则可能在未来很长时间内不会被使用。

实现

LRU淘汰机制的基本原理是，当缓存已满，需要插入新的数据时，它会选择最近最少使用的数据进行移除，从而为新数据留出空间。

public class LRU<K, V> {
    //容量
    private int capacity;
    private HashMap<K, Node<K, V>> cache;
    //双向链表
    private LinkedList<Node<K, V>> list;

    public LRU(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        list = new LinkedList<>();
    }

    //获取数据
    public V get(K key){
        if (!cache.containsKey(key)) {
            return null;
        }
        Node<K, V> node = cache.get(key);
        //将数据放入头部
        list.remove(node);
        list.addFirst(node);
        return node.value;
    }

     //添加数据
    public void put(K key , V value){
        if(cache.containsKey(key)){
            Node<K, V> node = cache.get(key);
            node.value = value;
            list.remove(node);
            list.addFirst(node);
            return;
        }
        //容量已满，删除最后的数据
        if(capacity == cache.size()){
            cache.remove(list.peekLast().key);
            list.pollLast();
        }
        Node<K, V> node = new Node<>(key, value);
        cache.put(key, node);
        list.addFirst(node);
    }

    private class Node<K, V>{
        private K key;
        private V value;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}