基于LinkedHashMap实现LRU Cache以及手写LRU

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> oldestEntry){
        return size() > capacity;
    }
}

（1） super(chcheSize, 0.75f, true)， 第三个参数必须是true，表示按照访问顺序控制LinkedHashMap元素顺序，默认是false按照插入顺序排序。ture情况下访问元素后该元素会被放到末尾，因此头部都是最近最久没有访问的元素；

（2）removeEldestEntry是否删除eldestEntry

用双向链表加Map可以自己实现lru

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;


    public LRUCache(int capacity){
        super(capacity,0.75f,true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> oldestEntry){
        return size() > capacity;
    }

    //put可以不写，但是get要写，否则不存在的时候返回的是null而不是-1，不符合题目要求，实际上是可以不写的
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    

    /*
    private int capacity;
    private DoubleLinkedList linkedList;
    private Map<Integer, Node> map;


    public LRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Invalid capacity");
        }
        this.capacity = capacity;
        this.linkedList = new DoubleLinkedList();
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        Node node = map.get(key);
        linkedList.remove(node);
        linkedList.add(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            linkedList.remove(map.get(key));
        }

        if (this.capacity == linkedList.size()) {
            Node oldestNode = linkedList.peek();
            linkedList.remove(oldestNode);
            map.remove(oldestNode.key);
        }
        Node node = new Node(key, value);
        linkedList.add(node);
        map.put(key, node);
    }

    private class Node {
        private int key;
        private int value;
        private Node prev = null;
        private Node next = null;


        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private class DoubleLinkedList {
        private int size;
        private Node dummyHead;
        private Node dummyTail;

        DoubleLinkedList() {
            this.size = 0;
            this.dummyHead = new Node(0, 0);
            this.dummyTail = new Node(0, 0);

            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }

        int size() {
            return this.size;
        }

        Node peek() {
            return this.size == 0 ? null : dummyHead.next;
        }

        void add(Node node) {
            node.next = dummyTail;
            node.prev = dummyTail.prev;
            dummyTail.prev.next = node;
            dummyTail.prev = node;
            size++;
        }

        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }
    }
    */
}