实现一个LRU Cache
0x00 简介
Least Recently Used (LRU)是一种缓存替换策略。其实First In First Out (FIFO)、Last In First Out (LIFO)等都是缓存替换策略。基于LRU策略我们可以设计 LRU Cache。
LRU Cache在很多场景下都有应用，比如网易云音乐中的「最近播放」功能，把最近播放的100首单曲或歌单/专辑记录下来，这个「最近播放」的判断依据就是LRU。又比如很多项目里都有的「登录历史」，可以把最近登录的帐号记录下来。又比如图片缓存，什么时候清除内存中的图片(放弃引用，让gc做处理)？
Android 2.3（Level 9）时代，垃圾回收机制更倾向于回收 SoftReference 或 WeakReference 的对象。后来，又来到了 Android3.0，图片缓存在内容中，因为不知道要在是什么时候释放内存，没有策略，没用一种可以预见的场合去将其释放。这就造成了内存溢出。
我们知道SoftReference的策略是，只有当内存告急（即将 OOM）时，才会对只剩下Soft Reference 的变量进行回收，因此 SoftReference 比较适合用来做 Cache。但它的问题也很明显，无法提供足够的信息可以让 runtime决定什么时候清除引用的对象，也不知道是应该清除SoftReference还是增大Heap。所以Android建议使用LRU Cache。
Avoid Soft References for Cacheing
那本文的目的就在于实现一个有put和get功能的数据结构，名字叫LRUCache:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
0x01 使用什么数据结构
举网易云音乐那个例子，看起来其实很容易，只要把播放的新的音乐放到首位就行了。
是这样的，比如采用ArrayList，听一首新歌，把它add到list的首位，然后把末位的歌曲删除就行了。但问题是，如果这个音乐就在list里就会重复。所以必须要在add之前，先搜索list里是否有这首歌。如果采用list，搜索用的时间是O(n)。
这件事其实就是put的时候把entry放到优先级最高的slot，get的时候把已有的元素抽出来，挪到优先级最高的slot。
如何在O(1)时间实现put和get？
要用O(1)时间，那Array、Queue、Stack甚至LinkedList都做不到（LinkedList能做到快速put和get，但是必须知道对象的地址，这个地址需要用O(n)时间搜索）。
说道O(1)，很容易想到用HashMap。其实仔细想想，HashMap就是对链表的优化，针对链表不能快速定位对象所在位置的缺陷，把对象的地址用key的hash作为依据保存起来，这样get的复杂度就是O(1)了。
但HashMap有个缺陷，就是，HashMap的保存的key-value不是有序的，而是用散列的方法根据key的hash计算得到index分配到固定位置的。
怎么办，用LinkedHashMap吧。
0x02 LinkedHashMap
这里先不提它的原理是什么，要知道它是可以保持你put的顺序的就行了。
这样的话是不是直接记录一下Map的Size和Capacity就差不多搞定了？其实连这个也不要。。LinkedHashMap有两种模式，一种是普通模式，就是有序地插入；第二种就直接帮你实现了LRUCache的功能，只要把它的第三个构造参数写成true，那就开启了accessOrder模式，如果覆写removeEldestEntry，会自动根据它的条件移除LEAST USED的元素。于是，一个简单的LruCache就实现了！
public class LruCache {
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是怎么做到有序存储的？
0x03 模仿LinkedHashMap实现LruCache
前面说过，如果知道node的地址，链表的插入删除是O(1)的。具体来讲，我们需要的是一个双向链表（因为需要前一个node的地址），这样就可以保证在只知道当前节点的地址的情况下，在O(1)时间实现插入删除。
具体来讲，对于get方法，只需要利用一个HashMap（或是线程安全的HashTable）的get方法，get到了之后把包含key和value的node移动到双向链表的表头位置即可。
public int get(int key) {
DLinkedNode node = hashTable.get(key);
if (node == null) {
return -1; // should raise exception here.
}
// move the accessed node to the head;
this.moveToHead(node);
return node.value;
}
对于set方法，需要区分这个node是否已经在链表中。
如果不在链表中，需要：
- 创建一个node
- 把新的node加入到链表开头。
- 检查node数量是否超过了capacity，如果超过了，要把结尾的node删除。
如果node不在链表中，需要:
- 获取这个node，更新它的value（对于网易云音乐那种不改变值的情形来说，不需要value）。
- 移动node到表头。
public void set(int key, int value) {
DLinkedNode node = hashTable.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
hashTable.put(key, newNode);
addNode(newNode);
++count;
if (count > capacity) {
// pop the tail
DLinkedNode tail = popTail();
hashTable.remove(tail.key);
--count;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
基于这种想法，完整实现的LruCache如下：
public class LruCache {
private Hashtable<Integer, DLinkedNode> hashTable = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;
static class DLinkedNode {
int key;
int value;
DLinkedNode pre;
DLinkedNode post;
}
public LruCache(int capacity) {
count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
/**
* 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) {
removeNode(node);
addNode(node);
}
// pop the current tail.
private DLinkedNode popTail() {
DLinkedNode res = tail.pre;
removeNode(res);
return res;
}
public int get(int key) {
DLinkedNode node = hashTable.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 = hashTable.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
hashTable.put(key, newNode);
addNode(newNode);
++count;
if (count > capacity) {
// pop the tail
DLinkedNode tail = popTail();
hashTable.remove(tail.key);
--count;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
}
其实node仍然保存在Hashtable原来的bucket里面，只是我们另外用一个DoubleLinkedList把Node连接起来了。
0x04 总结
本文讲了LruCache和LinkedList的原理，实现了一个简单的LruCache。其实Android SDK中的LruCache的实现跟这个略有不同，比如它的put方法和get方法都用了同步锁:
public final V put(K key, V value) {
...
synchronized (this) {
...
// 计算双向链表中的node数量
size += safeSizeOf(key, value);
...
}
...
trimToSize(maxSize);
return previous;
}
那是因为LinkedHashMap是继承了LinkedHashMap而不是HashTable。
利用LruCache我们还可以实现DisLruCache，which，可以用来实现图片缓存之类的工具，比如：
mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {
@Override
protected int sizeOf(String key, Bitmap bitmap) {
//return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
return bitmap.getByteCount() / 1024;
}
};
不过这些都不重要了，我们已经知道什么是LruCache了，并且体会到了链表和Map的巧妙联系。
Ref:
https://www.jianshu.com/p/833adadc9eb6
by DrunkPaino
