LRU,全程Least Recently Used,即最近最久未使用算法,用于操作系统的页面置换算法,以及一些常见的框架。其原理实质就是当需要淘汰数据时,会选择那些最近没有使用过的数据进行淘汰,换句话说,当某数据被访问时,就把其移动到淘汰队列的队首(也就是最不会被淘汰的位置)
基于这样的原则,我们就可以着手实现了。不过Java已经为我们提供了一个现成的模板,我们站在巨人的肩膀上,可以参考一下Java是如何实现LRU功能的
在LinkedHashMap中,有一个很少用到的构造函数:
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } 复制代码
其中 accessOrder
这一属性,在其他的构造函数中是默认为 false
的,如果我们通过该构造函数将其设为 true
之后,就实现了LRU功能,下面的程序简单了做了下演示:
public static void main(String[] args) { int cacheSize = 3; // 最大容量 = (缓存大小 / 负载因子)+ 1,保证不会触发自动扩容 LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>( (int)(cacheSize/ 0.75f) + 1, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > cacheSize; } }; cache.put("1", "a"); cache.put("2", "b"); cache.put("3", "c"); // head => "1" => "2" => "3" => null // put已存在的值,和get方法是一样的效果 cache.put("1", "a"); // head => "2" => "3" => "1" => null; cache.put("4", "d"); // head => "3" => "1" => "4" => null; for (String key: cache.keySet()) { System.out.println(key); } } 复制代码
其实还有很重要的一点,就是需要重写 removeEldestEntry()
这一方法,默认是返回 false
的,当返回 true
时,会移除最久没有使用的节点,所以我们要做的,就是当容量达到缓存限制时,移除LRU算法判定的最近最久未使用节点
可以看到,我们依次插入节点1、2、3后,如果此时再插入节点4,就会导致 removeEldestEntry()
返回为 true
,然后移除队首节点,即节点1。但是我们这里由于中间重复插入了一次节点1,所以会判断节点1是“经常访问的节点”,所以节点1被提到链表最后,队首节点就变成了节点2,当容量超过限制时,会把节点2移除
探索LinkedHashMap中LRU的实现原理,我们就要追溯到HashMap中的 putVal
方法,这个方法最后触发了一个回调函数:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ... if (e != null) { // existing mapping for key // ... afterNodeAccess(e); return oldValue; } } afterNodeInsertion(evict); return null; } 复制代码
putVal()
方法在插入后会触发方法的回调,有两种情况:
afterNodeAccess(e) afterNodeInsertion(evict)
其中,变量e是“撞车”的节点,变量evict在子类不重写 put()
方法的情况下是默认为 true
的,所以我们就把它当作常量来看
然后我们回到,LinkedHashMap中,来看这个两个钩子方法(HashMap中这两个方法实现均为空):
void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; // 以下情况满足时,调用removeNode移除最久未使用的节点: // 1. evict为true // 2. 头结点不为空 // 3. 符合移除条件:removeEldestEntry返回true if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; // 开启LRU模式,且访问的节点不是尾节点,则将被访问的节点置于链表尾 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; } } 复制代码
显而易见, afterNodeInsertion
负责在 插入
之后判断是否需要移除最近最久未使用的节点(即链表头节点), afterNodeAccess
负责在 访问
某节点之后,将该节点移动到链表尾
在 afterNodeAccess
中,因为要考虑到各种特殊情况,而且是一个带有头尾节点的双向链表,所以情况判断比较复杂,实际上就是将指定节点移动到队尾,如果自己想实现一个类似的功能可以不做的这么复杂
一般来说,如果想做一个LRU算法实现的话,LinkedHashMap就能满足需要了。要是想自己实现的话,这里提供一个实现的思路: