用java写出：LRU

LRU（Least Recently Used）是一种缓存淘汰算法，它会优先淘汰最近最少使用的缓存。下面是用Java实现LRU算法的代码：

import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> cache;
    private Node<K, V> head;
    private Node<K, V> tail;

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

    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            return null;
        }
        refresh(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            if (cache.size() == capacity) {
                cache.remove(tail.key);
                remove(tail);
            }
            node = new Node<>(key, value);
            cache.put(key, node);
            add(node);
        } else {
            node.value = value;
            refresh(node);
        }
    }

    private void add(Node<K, V> node) {
        if (head == null) {
            head = node;
            tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    private void remove(Node<K, V> node) {
        if (node == head) {
            head = head.next;
        } else if (node == tail) {
            tail = tail.prev;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    private void refresh(Node<K, V> node) {
        remove(node);
        add(node);
    }

    private static class Node<K, V> {
        private final K key;
        private V value;
        private Node<K, V> prev;
        private Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

使用方法：

LRUCache<Integer, String> cache = new LRUCache<>(2);
cache.put(1, "one");
cache.put(2, "two");
System.out.println(cache.get(1)); // 输出：one
cache.put(3, "three");
System.out.println(cache.get(2)); // 输出：null
cache.put(4, "four");
System.out.println(cache.get(1)); // 输出：null
System.out.println(cache.get(3)); // 输出：three
System.out.println(cache.get(4)); // 输出：four

上面的代码中，LRUCache类封装了一个双向链表和一个哈希表。哈希表用来存储键值对，双向链表用来维护缓存中的元素顺序。在get方法中，如果缓存中不存在指定的键，则返回null；否则，将与该键对应的节点移到链表头部，并返回节点的值。在put方法中，如果缓存已满，则删除链表尾部的节点，并从哈希表中删除对应的键值对；否则，将新节点添加到链表头部，并在哈希表中存储新的键值对。在refresh方法中，先将节点从链表中删除，然后再将其添加到链表头部，以保证链表中最近访问的节点总是在链表头部。