public class LRUCache {
    private int size;
    private int cap;
    private HashMap<Integer, Node> map = new HashMap<>();
    private Node first;
    private Node last;

    public LRUCache(int cap) {
        this.cap = cap;
    }

    public void put(int k, int v) {
        if (map.containsKey(k)) {
            //已包含、更新
            Node node = map.get(k);
            node.value = v;
            //删除原节点
            if (node.next == null) {
                //尾
                //do nothing
                return;
            } else if (node.pre == null) {
                //头
                first = first.next;
                first.pre = null;
            } else {
                //中间
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            //放到队尾
            last.next = node;
            node.pre = last;
            last = node;
            node.next = null;
        } else {
            //不包含、插入
            Node node = new Node(k, v);
            map.put(k, node);
            if (last == null) {
                last = node;
                first = node;
            } else {
                //放到队尾
                last.next = node;
                node.pre = last;
                last = node;
            }

            size++;
            if (size > cap) {
                //满了，淘汰头
                map.remove(first.key);
                first = first.next;
                first.pre = null;
                size--;
            }
        }
    }

    public Integer get(int k) {
        Node node = map.get(k);
        if (node == null) {
            return -1;
        } else {
            //删除原节点
            if (node.next == null) {
                //尾
                //do nothing
                return node.value;
            } else if (node.pre == null) {
                //头
                first = first.next;
                first.pre = null;
            } else {
                //中间
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            //放到队尾
            last.next = node;
            node.pre = last;
            last = node;
            node.next = null;
        }
        return node.value;
    }

    class Node {
        Integer key;
        Integer value;
        Node pre;
        Node next;

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

主要思路

• 使用HashMap实现get的O(1)。没有HashMap也可以实现，但是每次需要遍历整个列表。
• 使用双向链表实现put的O(1)，维护node使用顺序。最久未使用的放在队头，最近使用的放在队尾，当容量达到设定的阈值，淘汰队头。
• get、put时，将node移动到队尾。

TODO：

• 代码有冗余，还有简化的空间
• 为了适应leetcode题目要求（https://leetcode-cn.com/problems/lru-cache-lcci/），使用了Integer作为了cache的泛型，实际可以用Object替换。

欣赏一下Leetcode耗时最短的写法

class LRUCache {

    ListNode head;
    ListNode tail;
    Map<Integer, ListNode> map;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if(!map.containsKey(key))
            return -1;
        ListNode node = map.get(key);
        moveToTail(node);
        return node.val;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)) {
            ListNode node = map.get(key);
            node.val = value;
            moveToTail(node);
        } else {
            if(map.size() == capacity) {
                map.remove(head.next.key);
                head.next.next.pre = head;
                head.next = head.next.next;
            }
            ListNode node = new ListNode(key, value);
            tail.pre.next = node;
            node.pre = tail.pre;
            node.next = tail;
            tail.pre = node;
            map.put(key, node);
        }
    }

    private void moveToTail(ListNode node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre.next = node;
        tail.pre = node;
    }
}

class ListNode {
    int val;
    int key;
    ListNode pre;
    ListNode next;
    ListNode(int key, int val) {
        this.val = val;
        this.key = key;
    }
}