Leetcode: LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

难度：90。这是一道非常综合的题目，主要应用在操作系统的资源管理中。

按照题目要求，要实现get和set功能，为了满足get功能：随机访问的需求(lookup)我们首先想到的一般是用数组，如果用链表会有O(n)的访问时间。然而他又有另一个条件就是要维护least used的队列，也就是说经常用的放在前面，用的少的放在后面。这样当资源超过cache的容积的时候就可以把用得最少的资源删掉。这就要求我们要对节点有好的删除和插入操作，这个要求又会让我们想到用链表，其删除插入是O(1)，而数组的删除和插入是O(n)复杂度的。

lookup, insert operations in O(1) leads to use HashMap.

Hashtable也是一个不错的选择，本来它的insert, delete, lookup操作amortized代价都是O(1), 但是，这里delete无法O(1). 这是因为这里困难的是得找到合乎条件的节点去删除，需要花时间在search这个Least Recently Used节点。想过用一种方法，if we use a time stamp on each entry, deleting the one with oldest access time stamp, But it will take O(n) time cost. 所以，如果只用HashMap, 删除最老的节点需要O(n).

那么我们能不能维护一个数据结构使得访问操作和插入删除操作都是O(1)复杂度的呢？答案是肯定的。这个数据结构比较复杂，是用一个hash表加上一个双向链表来实现。

这里为什么使用Doubly linkd list 而不使用 Linked list的原因是：

当访问一个节点后，我们需要将他从原来的list中删除，然后将它插入到头节点处，删除过程中需要将其前后节点连接起来，单链表做不到。

查询：

• 根据键值查询hashmap，若命中，则返回节点，否则返回null。
• 从双向链表中删除命中的节点，将其重新插入到表头。
• 所有操作的复杂度均为O(1)。

插入：

• 将新的节点关联到Hashmap
• 如果Cache满了，删除双向链表的尾节点，同时删除Hashmap对应的记录
• 将新的节点插入到双向链表中头部

更新：

• 和查询相似

删除：

• 从双向链表和Hashmap中同时删除对应的记录。

通过hash表访问结点我们可以认为是O(1)的操作（假设hash函数足够好），然后双向链表的插入删除操作也是O(1)的操作。如此我们便实现了用O(1)时间来完成所有LRU cache的操作。空间上就是对于每一个资源有一个hash表的的项以及一个对应的结点（包含前后指针和资源的<key, value>）。代码如下：

public class LRUCache {
    class Node {
        Node prev, next;
        int key;
        int value;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    int capacity;
    int num;
    Node first, last;
    HashMap<Integer, Node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.num = 0;
        this.first = null;
        this.last = null;
        this.map = new HashMap<Integer, Node>();
    }
    
    public int get(int key) {
        Node n = map.get(key);
        if (n == null) { //no find the key
            return -1;
        }
        int val = n.value;
        shiftToLast(n);
        return val; //return the value of the key node
    }
    
    public void set(int key, int value) {
        Node n = map.get(key);
        if (n != null) { //find the node, need to change its value and put to last
            shiftToLast(n);
            n.value = value; //change the value
        }
        else { //not find the node, need to create one, put to the last
            Node newNode = new Node(key, value);

            if (num >= capacity) { //no capacity, need to delete first Node
                map.remove(first.key);
                first = first.next;
                if (first != null) first.prev = null;
                else last = null;
                num--;
            }
            if (num == 0) {
                first = newNode;
                last = newNode;
            }
            else {
                newNode.next = null;
                newNode.prev = last;
                last.next = newNode;
                last = last.next;
            }
            num++;
            map.put(key, newNode);
        }
    }
    
        
    public void shiftToLast(Node n) {
        if (n != last) {  //find the key, and the node is not the last, need to put the node to the last of the LinkedList
            if (n == first) {  //delete the node from its original place, when the node is the first
                first.next.prev = null;
                first = first.next;
            }
            else {  //delete the node from its original place, when the node is neither the first nor the last
                n.next.prev = n.prev;
                n.prev.next = n.next;
            }
            n.next = last.next; //put the node to the last of the Linkedlist
            n.prev = last;
            last.next = n;
            last = n;
        }
    }
}

 关于set()函数还有另一版写法，看哪个好理解

    public void set(int key, int value) {
        if (map.containsKey(key)) { // key exist, change the value of the corresponding node
            CacheNode targetNode = map.get(key);
            if (targetNode != last) { //if target node is not the last node, put it to the last
                if (targetNode != first) { //if target node is not the first node, normal operation
                    targetNode.prev.next = targetNode.next;
                    targetNode.next.prev = targetNode.prev;
                }
                else { // if target node is the first node, special operation
                    targetNode.next.prev = targetNode.prev;
                    first = targetNode.next;
                }
                targetNode.next = last.next;
                last.next = targetNode;
                targetNode.prev = last;
                last = last.next;
            }
            targetNode.val = value;
        }
        else { // key not exist, add the value to the LRUCache
            CacheNode newNode = new CacheNode(key, value);
            if (curnum < Capacity) { // LRU Capacity not reached, can add the node the LRU without deletion
                if (last == null) { // LRU is initially empty, newNode is the first node added
                    last = newNode;
                    first = newNode;
                }
                else { // LRU is not initially empty, add newNode to the last
                    newNode.next = last.next;
                    last.next = newNode;
                    newNode.prev = last;
                    last = last.next;
                }
                curnum++;
                map.put(key, newNode);
            }
            else { // curnum >= Capacity, LRU Capacity reached, deletes first node before adding newNode
                if (first != null) { // Capacity is not 0, it Capacity is 0, do nothing, directly go to next if()
                    if (first == last) { // only one node in the LRU
                        map.remove(first.key);
                        first = null;
                        last = null;
                    }
                    else { //more than one node in the LRU, delete first node
                        first.next.prev = first.prev;
                        map.remove(first.key);
                        first = first.next;
                    }
                    curnum = Math.max(0, curnum-1);
                }
                if (curnum < Capacity) { //after deleting the firstNode, add the newNode to last.next
                    if (last == null) { // LRU is initially empty, newNode is the first node added
                        last = newNode;
                        first = newNode;
                    }
                    else { // LRU is not initially empty, add newNode to the last
                        newNode.next = last.next;
                        last.next = newNode;
                        newNode.prev = last;
                        last = last.next;
                    }
                    curnum++;
                    map.put(key, newNode);
                }
            }
        }
    }