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

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

緩存淘汰算法

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

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

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

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

FIFO

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

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

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

LRU

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

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

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

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方法，如果緩存滿了，則把鏈表頭部第一個節(jié)點和對應(yīng)的數(shù)據(jù)刪除。

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

運行結(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)然，這個不是面試官想要的，也不是我們想要的。我們可以使用雙向鏈表和哈希表進行實現(xiàn)，哈希表用于存儲對應(yīng)的數(shù)據(jù)，雙向鏈表用于數(shù)據(jù)被使用的時間先后順序。

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

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

packageone.more;

importjava.util.HashMap;

importjava.util.Map;

publicclassLruCacheK,V{

*頭結(jié)點

privateNodehead;

*尾結(jié)點

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é)點移動到隊尾

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

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

map.remove(removeHead().key);

//放入隊尾節(jié)點

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é)點

tail.next=newNode;

newNode.pre=tail;

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

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;

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

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

我們可以使用雙哈希表進行實現(xiàn)，一個哈希表用于存儲對應(yīng)的數(shù)據(jù)，另一個哈希表用于存儲數(shù)據(jù)被使用次數(shù)和對應(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ù)頻率和對應(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){

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

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