146. LRU Cache

https://leetcode.com/problems/lru-cache/description/

这题很好其实，我看它是hard，一直没碰。
很经典的一个Cache工具了，我们的项目中也有用到，输入登录密码那儿。
我做这题一直在思考该用什么数据结构好。依次想到了数组(滑动窗口)、链表、stack等等；但一方面效率低，肯定做不到O(1)，另一方面实现起来也困难。
这件事其实就是put的时候把entry放到优先级最高的slot，get的时候把已有的元素抽出来，挪到优先级最高的slot。我一开始想能不能用栈，但是栈只能从栈顶取数据；后来又想到链表，也是同样的问题。然后我想到能不能直接put的时候就在map里调整顺序，但是普通hashmap顺序是根据hashcode来的，所以就想到了LinkedHashMap。我暂时不理解LinkedHashMap的原理，明天要看一下。写代码的时候又遇到问题，我不知道怎么移除LinkedHashMap的第一条数据。。似乎没这个API。总不能把entry读出来赋值到另一个map吧。。然后我在网上查了用法，查的时候才发现原来LRUCache常用的方式就是LinkedHashMap，而且LinkedHashMap好像本身就有get的时候更新的机制。另外，提供了移除最老Entry的API: 覆写removeEldestEntry方法。。但是leetcode由于是包外调用，Entry是protected的，所以没法编译。
明天看看题解吧。

下面是我初次写的代码，思路就是用LinkedHashMap，但是leetcode并不能AC，因为Entry是protected的。

    public Map<Integer, Integer> mMap = new LinkedHashMap<Integer, Integer>() {
        @Override
        public boolean removeEldestEntry(Entry eldest) {
            return size() > mCapacity;
        }
    };
    private int mCapacity;


    public LRUCache(int capacity) {
        mCapacity = capacity;
    }

    public int get(int key) {
        if (mMap.containsKey(key)) {
            int val = mMap.get(key);
            mMap.remove(key);
            mMap.put(key, val);
            return val;
        }
        return -1;
    }

    public void put(int key, int value) {
        //map.remove()的参数不是index，而是key
//      if (mMap.size() >= mCapacity) {
//          mMap.keySet().remove(0);
//      }
        mMap.put(key, value);
    }

我查了一下，其实LinkedHashMap有两种模式，一种是普通模式，就是有序地插入；第二种就直接帮你实现了LRUCache的功能，只要把它的第三个构造参数写成true，那就开启了accessOrder模式，如果覆写removeEldestEntry，会自动根据它的条件移除LEAST USED的元素：

    import java.util.LinkedHashMap;
    public class LRUCache {
        private LinkedHashMap<Integer, Integer> map;
        private final int CAPACITY;
        public LRUCache(int capacity) {
            CAPACITY = capacity;
            map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > CAPACITY;
                }
            };
        }
        public int get(int key) {
            return map.getOrDefault(key, -1);
        }
        public void set(int key, int value) {
            map.put(key, value);
        }
    }

这种是偷懒方法了，还没有理解为什么LinkedHashMap可以保存顺序。所以我摘抄一段高票答案的解法，就可以懂得LinkedHashMap的原理了，其实是利用双向链表：

class DLinkedNode {
    int key;
    int value;
    DLinkedNode pre;
    DLinkedNode post;
}

/**
 * Always add the new node right after head;
 * 把新的Node加入到链表开头
 */
private void addNode(DLinkedNode node){
    node.pre = head;
    node.post = head.post;
    head.post.pre = node;
    head.post = node;
}

/**
 * Remove an existing node from the linked list.
 * 从链表移除一个Node。这个操作是O(1)的，因为给的是Node的地址
 */
private void removeNode(DLinkedNode node){
    DLinkedNode pre = node.pre;
    DLinkedNode post = node.post;
    
    pre.post = post;
    post.pre = pre;
}

/**
 * Move certain node in between to the head.
 * 把中间的Node移动到链表开头
 */
private void moveToHead(DLinkedNode node){
    this.removeNode(node);
    this.addNode(node);
}

// pop the current tail. 
private DLinkedNode popTail(){
    DLinkedNode res = tail.pre;
    this.removeNode(res);
    return res;
}

private Hashtable<Integer, DLinkedNode> 
    cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
    this.count = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    head.pre = null;
    
    tail = new DLinkedNode();
    tail.post = null;
    
    head.post = tail;
    tail.pre = head;
}

public int get(int key) {
    
    DLinkedNode node = cache.get(key);
    if(node == null){
        return -1; // should raise exception here.
    }
    
    // move the accessed node to the head;
    this.moveToHead(node);
    
    return node.value;
}


public void set(int key, int value) {
    DLinkedNode node = cache.get(key);
    if(node == null){
        DLinkedNode newNode = new DLinkedNode();
        newNode.key = key;
        newNode.value = value;
        this.cache.put(key, newNode);
        this.addNode(newNode);
        
        ++count;
        
        if(count > capacity){
            // pop the tail
            DLinkedNode tail = this.popTail();
            this.cache.remove(tail.key);
            --count;
        }
    }else{
        // update the value.
        node.value = value;
        this.moveToHead(node);
    }
    
}

方案是以把value存储成一个双向链表的结点，当做Hashtable的value，Hashtable<Integer, DLinkedNode>()；用链表的意义是可以有序，用双向链表的意义是可以O(1)地插入和删除。这段程序我没有动手写，所以我有个疑惑是，这个Node里定义的key这个成员变量~~是不是没有意义的？因为看起来，get只是通过传入的key来get。~~仔细看了下，在超出容量后的是要用到这个node里的key的，用来在Hashtable中移除对应的Entry。

----20180507UPDATE----
模仿上面的思路，用JavaScript实现了LruCache，放在了Github上。

关联阅读：SoftReference和LRUCache
ref:
https://www.cnblogs.com/whoislcj/p/5552421.html
https://www.cnblogs.com/hubingxu/archive/2012/02/21/2361281.html