Java实现常用缓存淘汰算法-FIFO、LRU、LFU

第Java实现常用缓存淘汰算法:FIFO、LRU、LFU目录缓存淘汰算法FIFOLRULFU总结

缓存淘汰算法

在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。

第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。

但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。

常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。

FIFO

FIFO，FirstInFirstOut，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰。简单地说，先存入缓存的数据，先被淘汰。

最早存入缓存的数据，其不再被使用的可能性比刚存入缓存的可能性大。建立一个FIFO队列，记录所有在缓存中的数据。当一条数据被存入缓存时，就把它插在队尾上。需要被淘汰的数据一直在队列头。这种算法只是在按线性顺序访问数据时才是理想的，否则效率不高。因为那些常被访问的数据，往往在缓存中也停留得最久，结果它们却因变“老”而不得不被淘汰出去。

FIFO算法用队列实现就可以了，这里就不做代码实现了。

LRU

LRU，LeastRecentlyUsed，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰。简单地说，LRU的淘汰规则是基于访问时间。

如果一个数据在最近一段时间没有被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当缓存空间满时，最久没有使用的数据最先被淘汰。

在Java中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造函数第三个参数传入true，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。

packageone.more;

importjava.util.LinkedHashMap;

importjava.util.Map;

publicclassLruCacheK,VextendsLinkedHashMapK,V{

*容量限制

privateintcapacity;

LruCache(intcapacity){

//初始大小，0.75是装载因子，true是表示按照访问时间排序

super(capacity,0.75f,true);

//缓存最大容量

this.capacity=capacity;

*重写removeEldestEntry方法，如果缓存满了，则把链表头部第一个节点和对应的数据删除。

@Override

protectedbooleanremoveEldestEntry(Map.EntryK,Veldest){

returnsize()capacity;

我写一个简单的程序测试一下：

packageone.more;

publicclassTestApp{

publicstaticvoidmain(String[]args){

LruCacheString,Stringcache=newLruCache(3);

cache.put("keyA","valueA");

System.out.println("putkeyA");

System.out.println(cache);

System.out.println("=========================");

cache.put("keyB","valueB");

System.out.println("putkeyB");

System.out.println(cache);

System.out.println("=========================");

cache.put("keyC","valueC");

System.out.println("putkeyC");

System.out.println(cache);

System.out.println("=========================");

cache.get("keyA");

System.out.println("getkeyA");

System.out.println(cache);

System.out.println("=========================");

cache.put("keyD","valueD");

System.out.println("putkeyD");

System.out.println(cache);

运行结果如下：

putkeyA

{keyA=valueA}

=========================

putkeyB

{keyA=valueA,keyB=valueB}

=========================

putkeyC

{keyA=valueA,keyB=valueB,keyC=valueC}

=========================

getkeyA

{keyB=valueB,keyC=valueC,keyA=valueA}

=========================

putkeyD

{keyC=valueC,keyA=valueA,keyD=valueD}

当然，这个不是面试官想要的，也不是我们想要的。我们可以使用双向链表和哈希表进行实现，哈希表用于存储对应的数据，双向链表用于数据被使用的时间先后顺序。

在访问数据时，如果数据已存在缓存中，则把该数据的对应节点移到链表尾部。如此操作，在链表头部的节点则是最近最少使用的数据。

当需要添加新的数据到缓存时，如果该数据已存在缓存中，则把该数据对应的节点移到链表尾部；如果不存在，则新建一个对应的节点，放到链表尾部；如果缓存满了，则把链表头部第一个节点和对应的数据删除。

packageone.more;

importjava.util.HashMap;

importjava.util.Map;

publicclassLruCacheK,V{

*头结点

privateNodehead;

*尾结点

privateNodetail;

*容量限制

privateintcapacity;

*key和数据的映射

privateMapK,Nodemap;

LruCache(intcapacity){

this.capacity=capacity;

this.map=newHashMap();

publicVput(Kkey,Vvalue){

Nodenode=map.get(key);

//数据存在，将节点移动到队尾

if(node!=null){

VoldValue=node.value;

//更新数据

node.value=value;

moveToTail(node);

returnoldValue;

}else{

NodenewNode=newNode(key,value);

//数据不存在，判断链表是否满

if(map.size()==capacity){

//如果满，则删除队首节点，更新哈希表

map.remove(removeHead().key);

//放入队尾节点

addToTail(newNode);

map.put(key,newNode);

returnnull;

publicVget(Kkey){

Nodenode=map.get(key);

if(node!=null){

moveToTail(node);

returnnode.value;

returnnull;

@Override

publicStringtoString(){

StringBuildersb=newStringBuilder();

sb.append("LruCache{");

Nodecurr=this.head;

while(curr!=null){

if(curr!=this.head){

sb.append(',').append('');

sb.append(curr.key);

sb.append('=');

sb.append(curr.value);

curr=curr.next;

returnsb.append('}').toString();

privatevoidaddToTail(NodenewNode){

if(newNode==null){

return;

if(head==null){

head=newNode;

tail=newNode;

}else{

//连接新节点

tail.next=newNode;

newNode.pre=tail;

//更新尾节点指针为新节点

tail=newNode;

privatevoidmoveToTail(Nodenode){

if(tail==node){

return;

if(head==node){

head=node.next;

head.pre=null;

}else{

//调整双向链表指针

node.pre.next=node.next;

node.next.pre=node.pre;

node.pre=tail;

node.next=null;

tail.next=node;

tail=node;

privateNoderemoveHead(){

if(head==null){

returnnull;

Noderes=head;

if(head==tail){

head=null;

tail=null;

}else{

head=res.next;

head.pre=null;

res.next=null;

returnres;

classNode{

Kkey;

Vvalue;

Nodepre;

Nodenext;

Node(Kkey,Vvalue){

this.key=key;

this.value=value;

再次运行测试程序，结果如下：

putkeyA

LruCache{keyA=valueA}

=========================

putkeyB

LruCache{keyA=valueA,keyB=valueB}

=========================

putkeyC

LruCache{keyA=valueA,keyB=valueB,keyC=valueC}

=========================

getkeyA

LruCache{keyB=valueB,keyC=valueC,keyA=valueA}

=========================

putkeyD

LruCache{keyC=valueC,keyA=valueA,keyD=valueD}

LFU

LFU，LeastFrequentlyUsed，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰。简单地说，LFU的淘汰规则是基于访问次数。

如果一个数据在最近一段时间很少被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当空间满时，最小频率使用的数据最先被淘汰。

我们可以使用双哈希表进行实现，一个哈希表用于存储对应的数据，另一个哈希表用于存储数据被使用次数和对应的数据。

packageone.more;

importjava.util.Comparator;

importjava.util.HashMap;

importjava.util.LinkedList;

importjava.util.List;

importjava.util.Map;

importjava.util.stream.Collectors;

publicclassLfuCacheK,V{

*容量限制

privateintcapacity;

*当前最小使用次数

privateintminUsedCount;

*key和数据的映射

privateMapK,Nodemap;

*数据频率和对应数据组成的链表

privateMapInteger,ListNodeusedCountMap;

publicLfuCache(intcapacity){

this.capacity=capacity;

this.minUsedCount=1;

this.map=newHashMap();

this.usedCountMap=newHashMap();

publicVget(Kkey){

Nodenode=map.get(key);

if(node==null){

returnnull;

//增加数据的访问频率

addUsedCount(node);

returnnode.value;

publicVput(Kkey,Vvalue){

Nodenode=map.get(key);

if(node!=null){

//如果存在则增加该数据的访问频次

VoldValue=node.value;

node.value=value;

addUsedCount(node);

returnoldValue;

}else{

//数据不存在，判断链表是否满

if(map.size()==capacity){

//如果满，则删除队首节点，更新哈希表

ListNodelist=usedCountMap.get(minUsedCount);

NodedelNode=list.get(0);

list.remove(delNode);

map.remove(delNode.key);

//新增数据并放到数据频率为1的数据链表中

NodenewNode=newNode(key,value);

map.put(key,newNode);

ListNodelist=usedCountMap.get(1);

if(list==null){

list=newLinkedList();

usedCountMap.put(1,list);

list.add(newNode);

minUsedCount=1;

returnnull;

@Override

publicStringtoString(){

StringBuildersb=newStringBuilder();

sb.append("LfuCache{");

ListIntegerusedCountList=this.usedCountMap.keySet().stream().collect(Collectors.toList());

usedCountList.sort(CparingInt(i-i));

intcount=0;

for(intusedCount:usedCountList){

ListNodelist=this.usedCountMap.get(usedCount);

if(list==null){

continue;

for(Nodenode:list){

if(count0){

sb.append(',').append('');

sb.append(node.key);

sb.append('=');

sb.append(node.value);

sb.append("(UsedCount:");

sb.append(node.usedCount);

sb.append(')');

count++;

returnsb.append('}').toString();

privatevoidaddUsedCount(Nodenode){

ListNodeoldList=usedCountMap.get(node.usedCount);

oldList.remove(node);

//更新最小数据频率

if(minUsedCount==node.usedCountoldList.isEmpty()){

minUsedCount++;

node.usedCount++;

ListNodeset=usedCountMap.get(node.usedCount);

if(set==null){

set=newLinkedList();

usedCountMap.put(node.usedCount,set);

set.add(node);

classNode{

Kkey;

Vvalue;

intusedCount=1;

Node(Kkey,Vvalue){

this.key=key;

this.valu