什么是LRU算法
LRU算法的全称Least Recently Used。即最近最少使用。
LRU算法是内存管理的一种页面置换算法，对于在内存中但是又不用的数据块叫做LRU，操作系统会将那些数据数据LRU而将其移除内存腾出空间来加载其他数据（以上来自百度百科）。
LRU算法的实现
LRU算法通常是基于双向链表来实现的，下面我们一起看一下双向链表是如何实现LRU算法的。
image.png
如上图所示，我们定义了一个双向链表。对链表中元素的操作不外乎四种：get，put，remove，update。其中remove操作，删除链表中的一个元素，不会影响链表中现有的排序情况，而update和put操作可以看作是同一种操作。所以我们主要看get，put操作对链表中元素的影响。
image.png
image.png
以上我们看到当在双向链表中发生get和put操作时，链表内元素的变化情况。下面再来看一下基于LinkedHashMap的LRU算法是如何实现的。
基于LinkedHashMap的LRU算法实现
LinkedHashMap中LRU算法的实现主要依赖的几个方法。
- afterNodeInsertion(boolean evict)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// first = head 这一步是关键，从if的判断条件中可以看出，在链表的头结点head存在的情况下，会将head赋值给first，然后交给removeEldestEntry(first)执行
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 该方法移除的是链表的头结点
removeNode(hash(key), key, null, false, true);
}
}
- afterNodeAccess(Node<K,V> e)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 执行移动操作的前提是accessOrder和要移动的元素e != tail，这是为什么呢，刚开始看到这样的代码我也疑惑，说好的移动到链表的头部呢？挠头
if (accessOrder && (last = tail) != e) {
// 下面的代码就是我们熟知的双向链表中元素的移动操作了。
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
- removeEldestEntry(Map.Entry<K,V> eldest)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
// 默认返回false，也就是不移除最老的元素，我们需要重新改写该方法，在当前容量大于预设的最大容量时，移除最老元素。
return false;
}
介绍完几个关键方法之后，我们来从整体的角度看一下这几个方法在整个流程中的作用。
image.png
image.png
Demo
public class LruCache {
private Map<Object, Object> cache;
LruCache(int size) {
// 初始化LinkedHashMap三个参数，容量，负载引子，accessOrder
this.cache = new LinkedHashMap<Object, Object>(size, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
// 比较当前LinkedHashMap中的节点数量与允许存放最大数量的比较
return super.size() > size;
}
};
}
public Object put(Object key, Object value) {
return cache.put(key, value);
}
public Object get(Object key) {
return cache.get(key);
}
}
