LRU缓存淘汰算法分析与实现

概述

记录一下LRU缓存淘汰算法的实现。

原理

LRU（Least recently used，最近最少使用）缓存算法根据数据最近被访问的情况来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

介绍

下图中，介绍了一个缓存空间为5的缓存队列，当访问数据的顺序是:1,2,3,4,5,6,7,6,4,0时空间中数据的变化过程。

可以发现:

1. 当缓存空间未满时，数据一直往新的空间写；
2. 当缓存满，并且缓存中没有需要访问的数据时，最先进入缓存的数据被淘汰掉；
3. 当缓存满，并且缓存中有需要访问的数据时，做了一个数据交换，把访问的数据拿出来，其余数据往下压，最后把访问的数据放到顶部
   在这里，可能有疑问，就是把“数据交换”于“数据完全新增和删除”有什么区别呢？答案是性能，前者是移动指针，后者是更新整个内存空间，后者所花费的系统开销远比前者大得多。

实现

看了算法的介绍，我们想到的数据结构就是链表了。

• 双向链表的数据结构

 /** * 双向链表数据结构 */ private class NodePair{ NodePair frontNode; NodePair postNode; int data; }

• 逆序查找链表

 /** * 根据数据逆序查找链表中是否有此节点，有，则把该点提出来，放到current的位置 * 当匹配到的时候，返回true * @param data */ public boolean searchNode(int data){ boolean flag = false; NodePair tempNode = current; //不匹配，即没找到，则继续查找 while(tempNode.frontNode != null || tempNode.data != data){ tempNode = tempNode.frontNode; } //这个判读表示匹配到了 if(tempNode.data == data){ tempNode.frontNode.postNode = tempNode.postNode; tempNode.postNode.frontNode = tempNode.frontNode; current = tempNode; flag = true; } return flag; }

• 空间满了，并且缓存中没有待访问的数据，删除最下面的节点，再新增一个节点，相当于重新赋值最下面的节点，如图
  

红线表示，head将要指向倒数第二个点了，即，倒数第二个点要变成现在最底下的点了。

 /** * 给head节点重新赋值操作 * 实现细节是： * 0.倒数第二个点（head的下一个点）的frontNode引用指向null * 1.给head所指节点重新赋值 * 2.current节点的frontNode引用指向head * 3.把current节点指向head * 4.把head指向head的下一个节点（即，倒数第二个点） */ public void resetHeadNode(int data){ NodePair secondNode = head.postNode; head.postNode.frontNode = null; head.data = data; head.frontNode = current; head.postNode = null; current.postNode = head; current = head; head = secondNode; }

• 缓存满了，查找缓存中是否有待访问数据，有的话，同时把有的数据放到current指针所指位置。

 /** * 根据数据逆序查找链表中是否有此节点，有，则把该点提出来，放到current的位置 * 当匹配到的时候，返回true * @param data */ public boolean searchNode(int data){ boolean flag = false; NodePair tempNode = current; //不匹配，即没找到，则继续查找 while(tempNode.frontNode != null || tempNode.data != data){ tempNode = tempNode.frontNode; } //这个判读表示匹配到了 if(tempNode.data == data){ tempNode.frontNode.postNode = tempNode.postNode; tempNode.postNode.frontNode = tempNode.frontNode; current = tempNode; flag = true; } return flag; }

• 新增节点

 /** * 往LRU缓存中插入数据 * @param data */ public void addNode(int data){ //缓存未满，不需要删除，直接插入 if(length <= size){ NodePair tempNode = new NodePair(); tempNode.frontNode = current; tempNode.postNode = null; tempNode.data = data; current = tempNode; length++; } //缓存满了，查找缓存中有没有数据 else{ if(!searchNode(data)){ //缓存中没有，需要给head节点重新赋值 resetHeadNode(data); } } }

LRU算法的缺点

如果有几个不符合“如果数据最近被访问过，那么将来被访问的几率也更高”的规律时，会破坏缓存，导致性能下降。

总结

写算法时，通过画图，写步骤，先产生一个清晰的思路，然后一步步去做实现刚才思考的步骤。