146.|146. LRU Cache 146.LRUCache

https://leetcode.com/problems/lru-cache/description/
【146.|146. LRU Cache】这题很好其实，我看它是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 mMap = new LinkedHashMap() { @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 map; private final int CAPACITY; public LRUCache(int capacity) { CAPACITY = capacity; map = new LinkedHashMap(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 cache = new Hashtable(); 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 = https://www.it610.com/article/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 = https://www.it610.com/article/value; this.moveToHead(node); }}

方案是以把value存储成一个双向链表的结点，当做Hashtable的value，Hashtable()；用链表的意义是可以有序，用双向链表的意义是可以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