问题

如何设计实现LRU缓存？且Set() 和 Get() 的复杂度为O(1)。

解答

LRU，全称Least Recently Used，最近最少使用缓存。

在设计数据结构时，需要能够保持顺序，且是最近使用过的时间顺序被记录，这样每个item的相对位置代表了最近使用的顺序。满足这样考虑的结构可以是链表或者数组，不过链表更有利于Insert和Delete的操纵。

此外，需要记录链表的head和tail，从而方便进行移动到tail或者删除head的操作：
head.next作为最近最少使用的item，tail.prev为最近使用过的item，

在set时，如果超出capacity，则删除head.next，同时将要插入的item放入tail.prev,
在get时，如果存在，只需把item更新到tail.prev即可。

这样set与get均为O(1)时间的操作（HashMap Get/Set + LinkedList Insert/Delete)，空间复杂度为O(n), n为capacity。

public class LRUCache {
    private class Node {
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> hm = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    // @param capacity, an integer
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    // @return an integer
    public int get(int key) {
        if (!hm.containsKey(key)) {
            return -1;
        }
        Node current = hm.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        moveToTail(current);

        return hm.get(key).value;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        if (get(key) != -1) {
            hm.get(key).value = value;
            return;
        }
        if (hm.size() == capacity) {
            hm.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);
        hm.put(key, insert);
        moveToTail(insert);
    }

    private void moveToTail(Node current) {
        current.next = tail;
        tail.prev.next = current;
        current.prev = tail.prev;
        tail.prev = current;
    }
}