LruCache 是安卓开发中常用到的缓存技术，LRU 的全名是 Least Recently Used，表示最近最少使用算法，也就是说当内存快到达阈值时，若某个对象最近很少使用的，那么它就会被回收掉以释放内存。
使用
LruCache 的使用方法大致如下 ：
// LruCache 的声明初始化
int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
// 指定缓存的内存大小，一般为当前进程可用内存的 1/8 即可
int cacheSize = maxMemory / 8 ;
LruCache<String,Bitmap> cache = new LruCache<String,Bitmap>(cacheSize){
// 如何计算缓存的资源的内存大小
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight() / 1024 ;
}
// 当缓存对象被回收时执行的回调方法，以便释放一些资源之类的，默认为空
@Override
protected void entryRemoved(boolean evicted, String key, Bitmap oldValue, Bitmap newValue) {
super.entryRemoved(evicted, key, oldValue, newValue);
}
};
// LruCache 添加缓存对象
cache.put(key,bitmap) ;
// LruCache 获取缓存对象
cache.get(key);
LruCache 的声明和使用都比较简单，在它的内部就已经帮我们完成了缓存对象的移除和添加，而我们无需过多的考虑对象的释放问题。
原理分析
既然要缓存对象，必然要有个容器，LruCache 使用的是 LinkedHashMap，以强引用方式存储外界的缓存对象。
LinkedHashMap是一个双向的环形链表，链表中的每个节点都有指向前一个元素和后一个元素的引用。使用链表的好处就在于它的删除和添加操作更加的方便快捷。
而 LRU 的最近最少使用算法思想就体现在LinkedHashMap的元素顺序中了。
LinkedHashMap中的顺序当然是从头到尾的，而一个元素最近的使用情况当然也是从头到尾的一个渐变了。在 LruCache 中，默认是最近最少使用的元素位于链表的头部，而最近使用最多的元素则是位于链表的尾部。这样一来，从头到尾的一个渐变过程也就是一个元素使用最少到多的过程了。
当我们在进行每个get和put操作时，LinkedHashMap中的每个元素使用情况就要发生变化了，毕竟缓存容量是有限的，一些不幸的元素可能就因此而被垃圾回收了，以此来体现 LRU 的最近最少使用算法。
下面就分别介绍其get和put操作。
LruCache 的 get 操作
从 LruCache 中取出一个元素，显然，这个结果是可能为 null 的。
LruCache 使用get操作很简单，有就取出来，没有就返回个 null 。
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
而重点就在于LinkedHashMap的get方法了。
int hash = Collections.secondaryHash(key); // 计算 key 的 hash 值
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
LinkedHashMap的节点类是LinkedEntry，它继承自HashMapEntry，在其继承之上多了指向前后元素的引用。
所以，从上述代码可以看出，无非就是一个遍历，找到 key对应的元素就取出来，并且多了一个操作makeTail。
makeTail的操作又是干什么的呢？它可谓是实现最近最少算法的精髓了。
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e 将节点 e 的前节点和后节点进行连接，而将它自己给释放出来
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail 将节点 e 连接到链表的尾部
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
makeTail操作，将一个get的节点，从原本它在链表中的位置移到了整个链表中的尾部，使它的前节点是上一任的尾节点，而后节点则是头结点。
而在上面提到过，LinkedHashMap链表中元素的顺序正是完美的体现了最少最近算法的思想。
get得到的元素必然是最近使用最多的了，每次 get之后都将它移动到链表的尾部，也正是最近最少算法的体现了。
LruCache 的 put 操作
put操作则是向LinkedHashMap中放入一个元素，而缓存的容量又是有限的，这么一来，在有限的情况下，就会有元素被垃圾回收了。
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);
previous = map.put(key, value); // 若存在 key 相同的元素，则返回之前的，否则返回 null
if (previous != null) { // 存在 key 相同的元素
size -= safeSizeOf(key, previous);
}
}
// 移除最近最少使用的元素
trimToSize(maxSize);
当进行put操作时，若放入一个 key 存在的元素，则返回已经存在的对应的值。
同时，在每次put操作之后，都要进行容量的清除工作。
public void trimToSize(int maxSize) {
while (true) { // 死循环
K key;
V value;
synchronized (this) {
if (size <= maxSize) {
break;
}
Map.Entry<K, V> toEvict = map.eldest(); // 取出最老的元素
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
trimToSize的操作是一个死循环的操作，当size小于maxSize时，直接返回，否则从LinkedHashMap中移除最近最少使用的元素，也就是头节点后的元素。
以上就大致实现了 LRU 的最少最近算法。
同步锁相关操作
在 LruCache 的get和put操作中，都有用到的synchronized锁操作。
这是保证线程安全，因为在get和put方法中进行的都是复合操作，在并发条件下使用缓存时很容易出现脏数据，加上synchronized标识，则保证了操作的原子性，使得成为线程安全的操作。
参考
1、https://github.com/LittleFriendsGroup/AndroidSdkSourceAnalysis/blob/master/article/LruCache%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90.md
原创文章，转载请注明来源: Android LruCache实现分析