淘汰的英文

LRU算法缓存淘汰策略

LRU算法是什么？

按照英⽂的直接原义就是LeastRecentlyUd,最近最久未使⽤法，它是按照⼀个⾮常著名的计算机操作系统基础理论得来的：最近使⽤

的页⾯数据会在未来⼀段时期内仍然被使⽤,已经很久没有使⽤的页⾯很有可能在未来较长的⼀段时间内仍然不会被使⽤

基于这个思想,会存在⼀种缓存淘汰机制，每次从内存中找到最久未使⽤的数据然后置换出来，从⽽存⼊新的数据！它的主要衡量指标是使

⽤的时间，附加指标是使⽤的次数。

在计算机中⼤量使⽤了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使⽤的数据！因为，利⽤LRU我们可以

解决很多实际开发中的问题，并且很符合业务场景

LRU原理

可以⽤⼀个特殊的栈来保存当前正在使⽤的各个页⾯的页⾯号。当⼀个新的进程访问某页⾯时，便将该页⾯号压⼊栈顶，其他的页⾯号往栈

底移，如果内存不够，则将栈底的页⾯号移除。这样，栈顶始终是最新被访问的页⾯的编号，⽽栈底则是最近最久未访问的页⾯的页⾯号。

基于HashMap和双向链表的LRU

下⾯展⽰了，预设⼤⼩是3的，LRU存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展⽰HashMap部分的变化，仅仅

演⽰了上图LRU双向链表的变化。⽽且save()和get（）的时间复杂的都是O（1）我们对这个LRU缓存的操作序列如下：

save(“key1”,7)

save(“key2”,0)

save(“key3”,1)

save(“key4”,2)

get(“key2”)

save(“key5”,3)

get(“key2”)

save(“key6”,4)

相应的LRU双向链表部分变化如下

总结⼀下核⼼操作的步骤:

1，save(key,value)，⾸先在HashMap找到Key对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需

要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不⾜，则通过tail淘汰掉队尾的节点，同时在HashMap中移除Key。

2，get(key)，通过HashMap找到LRU链表节点，把节点插⼊到队头，返回缓存的值

Java代码的实现

classDLinkedNode{

Stringkey;

intvalue;

DLinkedNodepre;

DLinkedNodepost;

}

LRUCache

publicclassLRUCache{

privateHashtable

cache=newHashtable();

privateintcount;

privateintcapacity;

privateDLinkedNodehead,tail;

publicLRUCache(intcapacity){

=0;

ty=capacity;

head=newDLinkedNode();

=null;

tail=newDLinkedNode();

=null;

=tail;

=head;

}

publicintget(Stringkey){

DLinkedNodenode=(key);

if(node==null){

return-1;//shouldraiexceptionhere.

}

//movetheaccesdnodetothehead;

Head(node);

;

}

publicvoidt(Stringkey,intvalue){

DLinkedNodenode=(key);

if(node==null){

DLinkedNodenewNode=newDLinkedNode();

=key;

=value;

(key,newNode);

e(newNode);

++count;

if(count>capacity){

//popthetail

DLinkedNodetail=l();

();

--count;

}

}el{

//updatethevalue.

=value;

Head(node);

}

}

/**

*Alwaysaddthenewnoderightafterhead;

*/

privatevoidaddNode(DLinkedNodenode){

=head;

=;

=node;

=node;

}

/**

*Removeanexistingnodefromthelinkedlist.

*/

privatevoidremoveNode(DLinkedNodenode){

DLinkedNodepre=;

DLinkedNodepost=;

=post;

=pre;

}

/**

*Movecertainnodeinbetweentothehead.

*/

privatevoidmoveToHead(DLinkedNodenode){

Node(node);

e(node);

}

//popthecurrenttail.

privateDLinkedNodepopTail(){

DLinkedNoderes=;

Node(res);

returnres;

}

}