import java.util.HashMap;import java.util.Map;/** * 双链表加哈希实现最近最少使用算法 */public class LRUCache {    public static void main(String[] args) {        LRUCache lruCache = new LRUCache(3);        lruCache.put(1, 1);        lruCache.put(2, 2);        lruCache.put(3, 3);        System.out.println(lruCache.map.keySet());        lruCache.put(4, 4);        System.out.println(lruCache.map.keySet());        lruCache.put(3, 3);        System.out.println(lruCache.map.keySet());        lruCache.put(3, 3);        System.out.println(lruCache.map.keySet());        lruCache.put(3, 3);        System.out.println(lruCache.map.keySet());        lruCache.put(5, 5);        System.out.println(lruCache.map.keySet());    }    private int capacity;    private Map<Integer, Node<Integer, Integer>> map;    private DoubleLinkedList<Integer, Integer> linkedList;    public LRUCache(int capacity) {        this.capacity = capacity;        map = new HashMap<>();        linkedList = new DoubleLinkedList<>();    }    public int get(int key) {        if (map.containsKey(key)) {            Node<Integer, Integer> node = map.get(key);            linkedList.removeNode(node);            linkedList.addHead(node);            return node.val;        }        return -1;    }    public void put(int key, int value) {        //更新        if (map.containsKey(key)) {            Node<Integer, Integer> node = map.get(key);            node.val = value;            linkedList.removeNode(node);            linkedList.addHead(node);        }        //新增        else {            if (map.size() == this.capacity) {                Node<Integer, Integer> node = linkedList.last();                linkedList.removeNode(node);                map.remove(node.key);            }            Node<Integer, Integer> node = new Node<>(key, value);            linkedList.addHead(node);            map.put(key, node);        }    }}class Node<K, V> {    K key;    V val;    Node<K, V> prev;    Node<K, V> next;    public Node() {    }    public Node(K key, V val) {        this.key = key;        this.val = val;    }}class DoubleLinkedList<K, V> {    Node<K, V> head;    Node<K, V> tail;    public DoubleLinkedList() {        head = new Node<>();        tail = new Node<>();        head.next = tail;        tail.prev = head;    }    public void addHead(Node<K, V> node) {        node.prev = head;        node.next = head.next;        head.next.prev = node;        head.next = node;    }    public void removeNode(Node<K, V> node) {        node.prev.next = node.next;        node.next.prev = node.prev;        node.next = null;        node.prev = null;    }    public Node<K, V> last() {        return tail.prev;    }}

import java.util.LinkedHashMap;import java.util.Map;/** * 最近最少使用 */public class SimpleLRUCache<K, V> extends LinkedHashMap<K, V> {    public static void main(String[] args) {        SimpleLRUCache<Integer, String> lruCache = new SimpleLRUCache<>(3);        lruCache.put(1, "A");        lruCache.put(2, "B");        lruCache.put(3, "C");        System.out.println(lruCache.keySet());        lruCache.put(4, "D");        System.out.println(lruCache.keySet());        lruCache.put(3, "C");        System.out.println(lruCache.keySet());        lruCache.put(3, "C");        System.out.println(lruCache.keySet());        lruCache.put(3, "C");        System.out.println(lruCache.keySet());        lruCache.put(5, "D");        System.out.println(lruCache.keySet());    }    private int capacity;    public SimpleLRUCache(int capacity) {        super(capacity, 0.75f, true);//true访问顺序  false插入顺序        this.capacity = capacity;    }    @Override    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {        return super.size() > capacity;    }}