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
网友评论