手写最简单的LRU算法

作者:低调的干货君更新于： 2020-09-18 14:43:04

1 什么是LRU

LRU(Least recently used)最近最少使用，它的核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。因此 LRU 算法会根据数据的历史访问记录来进行排序，如果空间不足，就会淘汰掉最近最少使用的数据。

2 LRU 实现原理

由于 LRU 算法会将最近使用的数据优先级上升，因此需要数据结构支持排序，链表非常合适。

为什么不考虑数组呢?

由于 LRU 算法，一般都会应用在访问比较频繁的场景，因此，对数据的移动会频繁，而数组一旦移动，需要将移动到值的位置后面的所有数据的位置全部改变，效率比较低，不推荐使用。

3 双向链表之LinkedHashMap

前面我们分析到 LRU 的算法实现，可以使用链表实现，java 中 LinkedHashMap 就是一个双向链表。

LinkedHashMap是HashMap的子类，在HashMap数据结构的基础上，还维护着一个双向链表链接所有entry，这个链表定义了迭代顺序，通常是数据插入的顺序。

我们来看看LinkedHashMap的源码：

从源码中的定义可以看到，accessOrder 属性可以指定遍历 LinkedHashMap 的顺序，true 表示按照访问顺序，false 表示按照插入顺序，默认为 false。

由于LRU对访问顺序敏感，因此使用true来简单验证一下：

1. public class LRUTest { 
2.     public static void main(String[] args) { 
3.         LinkedHashMap map = new LinkedHashMap<>(16, 0.75f, true); 
4.         map.put("a", 1); 
5.         map.put("b", 2); 
6.         map.put("c", 3); 
7.         System.out.println("before get " + map); 
8.         map.get("a"); 
9.         System.out.println("after get" + map); 
10.     }} 

运行结果如下：

1. before get {a=1, b=2, c=3} 
2. after get{b=2, c=3, a=1} 

可以看到通过 accessOrder = true，可以让 LinkedHashMap 按照访问顺序进行排序。

那么 LinkedHashMap 是怎么做的呢?

我们看下get方法

1. public V get(Object key) { 
2.     Node e; 
3.     // 获取node 
4.     if ((e = getNode(hash(key), key)) == null) 
5.         return null; 
6.     // 如果 accessOrder = true，则执行afterNodeAccess方法 
7.     if (accessOrder) 
8.         afterNodeAccess(e); 
9.     return e.value; 
10. } 

再看下afterNodeAccess方法，发现进行移动节点，到此移动节点的原理我们了解了

1. void afterNodeAccess(Node e) { // move node to last 
2.    LinkedHashMap.Entry last; 
3.    if (accessOrder && (last = tail) != e) { 
4.        LinkedHashMap.Entry p =            (LinkedHashMap.Entry)e, b = p.before, a = p.after;        p.after = null;        if (b == null) 
5.            head = a;        else 
6.            b.after = a;        if (a != null) 
7.            a.before = b;        else 
8.            last = b; 
9.        if (last == null) 
10.            head = p;        else { 
11.            p.before = last; 
12.            last.after = p;        }        tail = p;        ++modCount;    }} 

目前，如果使用 LinkedHashMap 做LRU，还有一个问题困扰着我们，就是如果容量有限，该如何淘汰旧数据?

我们回过头看看 put 方法

1. public V put(K key, V value) { 
2.     return putVal(hash(key), key, value, false, true); 
3. } 
4. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 
5.     Node[] tab; Node p; int n, i; 
6.     if ((tab = table) == null || (n = tab.length) == 0) 
7.         n = (tab = resize()).length; 
8.     if ((p = tab[i = (n - 1) & hash]) == null) 
9.         tab[i] = newNode(hash, key, value, null); 
10.     else { 
11.         Node e; K k; 
12.         if (p.hash == hash && 
13.             ((k = p.key) == key || (key != null && key.equals(k)))) 
14.             e = p; 
15.         else if (p instanceof TreeNode) 
16.             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 
17.         else { 
18.             for (int binCount = 0; ; ++binCount) { 
19.                 if ((e = p.next) == null) { 
20.                     p.next = newNode(hash, key, value, null); 
21.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
22.                         treeifyBin(tab, hash); 
23.                     break; 
24.                 } 
25.                 if (e.hash == hash && 
26.                     ((k = e.key) == key || (key != null && key.equals(k)))) 
27.                     break; 
28.                 p = e; 
29.             } 
30.         } 
31.         if (e != null) { // existing mapping for key 
32.             V oldValue = e.value; 
33.             if (!onlyIfAbsent || oldValue == null) 
34.                 e.value = value; 
35.             afterNodeAccess(e); 
36.             return oldValue; 
37.         } 
38.     } 
39.     ++modCount; 
40.     if (++size > threshold) 
41.         resize(); 
42.     afterNodeInsertion(evict); 
43.     return null; 
44. } 
45. void afterNodeInsertion(boolean evict) { // possibly remove eldest 
46.     LinkedHashMap.Entry first; 
47.     if (evict && (first = head) != null && removeEldestEntry(first)) { 
48.         K key = first.key; 
49.         removeNode(hash(key), key, null, false, true); 
50.     } 
51. } 

从put方法中逐步看下来，最终我们发现，如果 removeEldestEntry(first) 方法返回true，则会移除 head，这样就淘汰了最近都没使用的数据。完全符合LRU。

4 最简单的LRU实现

根据上面分析，我们可以如下实现一个最简单的LRU

1. public class LRUCache extends LinkedHashMap { 
2.       private int cacheSize; 
3.     public LRUCache(int cacheSize) { 
4.       // 注意：此处需要让 accessOrder = true 
5.       super(cacheSize, 0.75f, true); 
6.       this.cacheSize = cacheSize; 
7.   } 
8.   /** 
9.    * 判断元素个数是否超过缓存的容量，超过需要移除 
10.    */ 
11.   @Override 
12.   protected boolean removeEldestEntry(Map.Entry eldest) { 
13.       return size() > cacheSize; 
14.   } 
15. }