Java實(shí)現(xiàn)常用緩存淘汰算法-FIFO、LRU、LFU

第Java實(shí)現(xiàn)常用緩存淘汰算法:FIFO、LRU、LFU目錄緩存淘汰算法FIFOLRULFU總結(jié)

緩存淘汰算法

在高并發(fā)、高性能的質(zhì)量要求不斷提高時(shí)，我們首先會(huì)想到的就是利用緩存予以應(yīng)對(duì)。

第一次請(qǐng)求時(shí)把計(jì)算好的結(jié)果存放在緩存中，下次遇到同樣的請(qǐng)求時(shí)，把之前保存在緩存中的數(shù)據(jù)直接拿來使用。

但是，緩存的空間一般都是有限，不可能把所有的結(jié)果全部保存下來。那么，當(dāng)緩存空間全部被占滿再有新的數(shù)據(jù)需要被保存，就要決定刪除原來的哪些數(shù)據(jù)。如何做這樣決定需要使用緩存淘汰算法。

常用的緩存淘汰算法有：FIFO、LRU、LFU，下面我們就逐一介紹一下。

FIFO

FIFO，F(xiàn)irstInFirstOut，先進(jìn)先出算法。判斷被存儲(chǔ)的時(shí)間，離目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰。簡(jiǎn)單地說，先存入緩存的數(shù)據(jù)，先被淘汰。

最早存入緩存的數(shù)據(jù)，其不再被使用的可能性比剛存入緩存的可能性大。建立一個(gè)FIFO隊(duì)列，記錄所有在緩存中的數(shù)據(jù)。當(dāng)一條數(shù)據(jù)被存入緩存時(shí)，就把它插在隊(duì)尾上。需要被淘汰的數(shù)據(jù)一直在隊(duì)列頭。這種算法只是在按線性順序訪問數(shù)據(jù)時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問的數(shù)據(jù)，往往在緩存中也停留得最久，結(jié)果它們卻因變“老”而不得不被淘汰出去。

FIFO算法用隊(duì)列實(shí)現(xiàn)就可以了，這里就不做代碼實(shí)現(xiàn)了。

LRU

LRU，LeastRecentlyUsed，最近最少使用算法。判斷最近被使用的時(shí)間，目前最遠(yuǎn)的數(shù)據(jù)優(yōu)先被淘汰。簡(jiǎn)單地說，LRU的淘汰規(guī)則是基于訪問時(shí)間。

如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒有被使用到，那么可以認(rèn)為在將來它被使用的可能性也很小。因此，當(dāng)緩存空間滿時(shí)，最久沒有使用的數(shù)據(jù)最先被淘汰。

在Java中，其實(shí)LinkedHashMap已經(jīng)實(shí)現(xiàn)了LRU緩存淘汰算法，需要在構(gòu)造函數(shù)第三個(gè)參數(shù)傳入true，表示按照時(shí)間順序訪問?？梢灾苯永^承LinkedHashMap來實(shí)現(xiàn)。

packageone.more;

importjava.util.LinkedHashMap;

importjava.util.Map;

publicclassLruCacheK,VextendsLinkedHashMapK,V{

*容量限制

privateintcapacity;

LruCache(intcapacity){

//初始大小，0.75是裝載因子，true是表示按照訪問時(shí)間排序

super(capacity,0.75f,true);

//緩存最大容量

this.capacity=capacity;

*重寫removeEldestEntry方法，如果緩存滿了，則把鏈表頭部第一個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的數(shù)據(jù)刪除。

@Override

protectedbooleanremoveEldestEntry(Map.EntryK,Veldest){

returnsize()capacity;

我寫一個(gè)簡(jiǎn)單的程序測(cè)試一下：

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);

運(yùn)行結(jié)果如下：

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}

當(dāng)然，這個(gè)不是面試官想要的，也不是我們想要的。我們可以使用雙向鏈表和哈希表進(jìn)行實(shí)現(xiàn)，哈希表用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)，雙向鏈表用于數(shù)據(jù)被使用的時(shí)間先后順序。

在訪問數(shù)據(jù)時(shí)，如果數(shù)據(jù)已存在緩存中，則把該數(shù)據(jù)的對(duì)應(yīng)節(jié)點(diǎn)移到鏈表尾部。如此操作，在鏈表頭部的節(jié)點(diǎn)則是最近最少使用的數(shù)據(jù)。

當(dāng)需要添加新的數(shù)據(jù)到緩存時(shí)，如果該數(shù)據(jù)已存在緩存中，則把該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)移到鏈表尾部；如果不存在，則新建一個(gè)對(duì)應(yīng)的節(jié)點(diǎn)，放到鏈表尾部；如果緩存滿了，則把鏈表頭部第一個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的數(shù)據(jù)刪除。

packageone.more;

importjava.util.HashMap;

importjava.util.Map;

publicclassLruCacheK,V{

*頭結(jié)點(diǎn)

privateNodehead;

*尾結(jié)點(diǎn)

privateNodetail;

*容量限制

privateintcapacity;

*key和數(shù)據(jù)的映射

privateMapK,Nodemap;

LruCache(intcapacity){

this.capacity=capacity;

this.map=newHashMap();

publicVput(Kkey,Vvalue){

Nodenode=map.get(key);

//數(shù)據(jù)存在，將節(jié)點(diǎn)移動(dòng)到隊(duì)尾

if(node!=null){

VoldValue=node.value;

//更新數(shù)據(jù)

node.value=value;

moveToTail(node);

returnoldValue;

}else{

NodenewNode=newNode(key,value);

//數(shù)據(jù)不存在，判斷鏈表是否滿

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

//如果滿，則刪除隊(duì)首節(jié)點(diǎn)，更新哈希表

map.remove(removeHead().key);

//放入隊(duì)尾節(jié)點(diǎn)

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{

//連接新節(jié)點(diǎn)

tail.next=newNode;

newNode.pre=tail;

//更新尾節(jié)點(diǎn)指針為新節(jié)點(diǎn)

tail=newNode;

privatevoidmoveToTail(Nodenode){

if(tail==node){

return;

if(head==node){

head=node.next;

head.pre=null;

}else{

//調(diào)整雙向鏈表指針

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;

再次運(yùn)行測(cè)試程序，結(jié)果如下：

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，最不經(jīng)常使用算法，在一段時(shí)間內(nèi)，數(shù)據(jù)被使用次數(shù)最少的，優(yōu)先被淘汰。簡(jiǎn)單地說，LFU的淘汰規(guī)則是基于訪問次數(shù)。

如果一個(gè)數(shù)據(jù)在最近一段時(shí)間很少被使用到，那么可以認(rèn)為在將來它被使用的可能性也很小。因此，當(dāng)空間滿時(shí)，最小頻率使用的數(shù)據(jù)最先被淘汰。

我們可以使用雙哈希表進(jìn)行實(shí)現(xiàn)，一個(gè)哈希表用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)，另一個(gè)哈希表用于存儲(chǔ)數(shù)據(jù)被使用次數(shù)和對(duì)應(yīng)的數(shù)據(jù)。

packageone.more;

importjava.util.Comparator;

importjava.util.HashMap;

importjava.util.LinkedList;

importjava.util.List;

importjava.util.Map;

importjava.util.stream.Collectors;

publicclassLfuCacheK,V{

*容量限制

privateintcapacity;

*當(dāng)前最小使用次數(shù)

privateintminUsedCount;

*key和數(shù)據(jù)的映射

privateMapK,Nodemap;

*數(shù)據(jù)頻率和對(duì)應(yīng)數(shù)據(jù)組成的鏈表

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;

//增加數(shù)據(jù)的訪問頻率

addUsedCount(node);

returnnode.value;

publicVput(Kkey,Vvalue){

Nodenode=map.get(key);

if(node!=null){

//如果存在則增加該數(shù)據(jù)的訪問頻次

VoldValue=node.value;

node.value=value;

addUsedCount(node);

returnoldValue;

}else{

//數(shù)據(jù)不存在，判斷鏈表是否滿

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

//如果滿，則刪除隊(duì)首節(jié)點(diǎn)，更新哈希表

ListNodelist=usedCountMap.get(minUsedCount);

NodedelNode=list.get(0);

list.remove(delNode);

map.remove(delNode.key);

//新增數(shù)據(jù)并放到數(shù)據(jù)頻率為1的數(shù)據(jù)鏈表中

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);

//更新最小數(shù)據(jù)頻率

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