详解Java实现LRU缓存

2023-07-19 10:41:04 84

LRU是LeastRecentlyUsed的缩写，翻译过来就是“最近最少使用”，LRU缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉，比如我们缓存10000条数据，当数据小于10000时可以随意添加，当超过10000时就需要把新的数据添加进来，同时要把过期数据删除，以确保我们最大缓存10000条，那怎么确定删除哪条过期数据呢，采用LRU算法实现的话就是将最老的数据删掉，废话不多说，下面来说下Java版的LRU缓存实现

Java里面实现LRU缓存通常有两种选择，一种是使用LinkedHashMap，一种是自己设计数据结构，使用链表+HashMap

LRUCache的LinkedHashMap实现

LinkedHashMap自身已经实现了顺序存储，默认情况下是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据，我们使用LinkedHashMap实现LRU缓存的方法就是对LinkedHashMap实现简单的扩展，扩展方式有两种，一种是inheritance，一种是delegation，具体使用什么方式看个人喜好

//LinkedHashMap的一个构造函数，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
publicLinkedHashMap(intinitialCapacity,floatloadFactor,booleanaccessOrder){
super(initialCapacity,loadFactor);
this.accessOrder=accessOrder;
}

//LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
//我们要做的就是重写这个方法，当满足一定条件时删除老数据
protectedbooleanremoveEldestEntry(Map.Entryeldest){
returnfalse;
}

LRU缓存LinkedHashMap(inheritance)实现

采用inheritance方式实现比较简单，而且实现了Map接口，在多线程环境使用时可以使用Collections.synchronizedMap()方法实现线程安全操作

packagecn.lzrabbit.structure.lru;

importjava.util.LinkedHashMap;
importjava.util.Map;

/**
*Createdbyliuzhaoon14-5-15.
*/
publicclassLRUCache2extendsLinkedHashMap{
privatefinalintMAX_CACHE_SIZE;

publicLRUCache2(intcacheSize){
super((int)Math.ceil(cacheSize/0.75)+1,0.75f,true);
MAX_CACHE_SIZE=cacheSize;
}

@Override
protectedbooleanremoveEldestEntry(Map.Entryeldest){
returnsize()>MAX_CACHE_SIZE;
}

@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
for(Map.Entryentry:entrySet()){
sb.append(String.format("%s:%s",entry.getKey(),entry.getValue()));
}
returnsb.toString();
}
}

这样算是比较标准的实现吧，实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦

finalintcacheSize=100;
Mapmap=newLinkedHashMap((int)Math.ceil(cacheSize/0.75f)+1,0.75f,true){
@Override
protectedbooleanremoveEldestEntry(Map.Entryeldest){
returnsize()>cacheSize;
}
};

LRU缓存LinkedHashMap(delegation)实现

delegation方式实现更加优雅一些，但是由于没有实现Map接口，所以线程同步就需要自己搞定了

packagecn.lzrabbit.structure.lru;

importjava.util.LinkedHashMap;
importjava.util.Map;
importjava.util.Set;

/**
*Createdbyliuzhaoon14-5-13.
*/
publicclassLRUCache3{

privatefinalintMAX_CACHE_SIZE;
privatefinalfloatDEFAULT_LOAD_FACTOR=0.75f;
LinkedHashMapmap;

publicLRUCache3(intcacheSize){
MAX_CACHE_SIZE=cacheSize;
//根据cacheSize和加载因子计算hashmap的capactiy，+1确保当达到cacheSize上限时不会触发hashmap的扩容，
intcapacity=(int)Math.ceil(MAX_CACHE_SIZE/DEFAULT_LOAD_FACTOR)+1;
map=newLinkedHashMap(capacity,DEFAULT_LOAD_FACTOR,true){
@Override
protectedbooleanremoveEldestEntry(Map.Entryeldest){
returnsize()>MAX_CACHE_SIZE;
}
};
}

publicsynchronizedvoidput(Kkey,Vvalue){
map.put(key,value);
}

publicsynchronizedVget(Kkey){
returnmap.get(key);
}

publicsynchronizedvoidremove(Kkey){
map.remove(key);
}

publicsynchronizedSet>getAll(){
returnmap.entrySet();
}

publicsynchronizedintsize(){
returnmap.size();
}

publicsynchronizedvoidclear(){
map.clear();
}

@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
for(Map.Entryentry:map.entrySet()){
sb.append(String.format("%s:%s",entry.getKey(),entry.getValue()));
}
returnsb.toString();
}
}

LRUCache的链表+HashMap实现

注：此实现为非线程安全，若在多线程环境下使用需要在相关方法上添加synchronized以实现线程安全操作

packagecn.lzrabbit.structure.lru;


importjava.util.HashMap;

/**
*Createdbyliuzhaoon14-5-12.
*/
publicclassLRUCache1{

privatefinalintMAX_CACHE_SIZE;
privateEntryfirst;
privateEntrylast;

privateHashMap>hashMap;

publicLRUCache1(intcacheSize){
MAX_CACHE_SIZE=cacheSize;
hashMap=newHashMap>();
}

publicvoidput(Kkey,Vvalue){
Entryentry=getEntry(key);
if(entry==null){
if(hashMap.size()>=MAX_CACHE_SIZE){
hashMap.remove(last.key);
removeLast();
}
entry=newEntry();
entry.key=key;
}
entry.value=value;
moveToFirst(entry);
hashMap.put(key,entry);
}

publicVget(Kkey){
Entryentry=getEntry(key);
if(entry==null)returnnull;
moveToFirst(entry);
returnentry.value;
}

publicvoidremove(Kkey){
Entryentry=getEntry(key);
if(entry!=null){
if(entry.pre!=null)entry.pre.next=entry.next;
if(entry.next!=null)entry.next.pre=entry.pre;
if(entry==first)first=entry.next;
if(entry==last)last=entry.pre;
}
hashMap.remove(key);
}

privatevoidmoveToFirst(Entryentry){
if(entry==first)return;
if(entry.pre!=null)entry.pre.next=entry.next;
if(entry.next!=null)entry.next.pre=entry.pre;
if(entry==last)last=last.pre;

if(first==null||last==null){
first=last=entry;
return;
}

entry.next=first;
first.pre=entry;
first=entry;
entry.pre=null;
}

privatevoidremoveLast(){
if(last!=null){
last=last.pre;
if(last==null)first=null;
elselast.next=null;
}
}


privateEntrygetEntry(Kkey){
returnhashMap.get(key);
}

@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
Entryentry=first;
while(entry!=null){
sb.append(String.format("%s:%s",entry.key,entry.value));
entry=entry.next;
}
returnsb.toString();
}

classEntry{
publicEntrypre;
publicEntrynext;
publicKkey;
publicVvalue;
}
}

LinkedHashMap的FIFO实现

FIFO是FirstInputFirstOutput的缩写，也就是常说的先入先出，默认情况下LinkedHashMap就是按照添加顺序保存，我们只需重写下removeEldestEntry方法即可轻松实现一个FIFO缓存，简化版的实现代码如下

finalintcacheSize=5;
LinkedHashMaplru=newLinkedHashMap(){
@Override
protectedbooleanremoveEldestEntry(Map.Entryeldest){
returnsize()>cacheSize;
}
};

调用示例

测试代码

packagecn.lzrabbit.structure.lru;

importcn.lzrabbit.ITest;

importjava.util.LinkedHashMap;
importjava.util.Map;

/**
*Createdbyliuzhaoon14-5-15.
*/
publicclassLRUCacheTest{

publicstaticvoidmain(String[]args)throwsException{
System.out.println("start...");

lruCache1();
lruCache2();
lruCache3();
lruCache4();

System.out.println("over...");
}


staticvoidlruCache1(){
System.out.println();
System.out.println("===========================LRU链表实现===========================");
LRUCache1lru=newLRUCache1(5);
lru.put(1,"11");
lru.put(2,"11");
lru.put(3,"11");
lru.put(4,"11");
lru.put(5,"11");
System.out.println(lru.toString());
lru.put(6,"66");
lru.get(2);
lru.put(7,"77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}


staticvoidlruCache2(){
System.out.println();
System.out.println("===========================LRULinkedHashMap(inheritance)实现===========================");
LRUCache2lru=newLRUCache2(5);
lru.put(1,"11");
lru.put(2,"11");
lru.put(3,"11");
lru.put(4,"11");
lru.put(5,"11");
System.out.println(lru.toString());
lru.put(6,"66");
lru.get(2);
lru.put(7,"77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}

staticvoidlruCache3(){
System.out.println();
System.out.println("===========================LRULinkedHashMap(delegation)实现===========================");
LRUCache3lru=newLRUCache3(5);
lru.put(1,"11");
lru.put(2,"11");
lru.put(3,"11");
lru.put(4,"11");
lru.put(5,"11");
System.out.println(lru.toString());
lru.put(6,"66");
lru.get(2);
lru.put(7,"77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}

staticvoidlruCache4(){
System.out.println();
System.out.println("===========================FIFOLinkedHashMap默认实现===========================");
finalintcacheSize=5;
LinkedHashMaplru=newLinkedHashMap(){
@Override
protectedbooleanremoveEldestEntry(Map.Entryeldest){
returnsize()>cacheSize;
}
};
lru.put(1,"11");
lru.put(2,"11");
lru.put(3,"11");
lru.put(4,"11");
lru.put(5,"11");
System.out.println(lru.toString());
lru.put(6,"66");
lru.get(2);
lru.put(7,"77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}

}

运行结果

"C:\ProgramFiles(x86)\Java\jdk1.6.0_10\bin\java"-Didea.launcher.port=7535"-Didea.launcher.bin.path=C:\ProgramFiles(x86)\JetBrains\IntelliJIDEA13.0.2\bin"-Dfile.encoding=UTF-8-classpath"C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\charsets.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\deploy.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\javaws.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\jce.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\jsse.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\management-agent.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\plugin.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\resources.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\rt.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\ext\localedata.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;C:\ProgramFiles(x86)\Java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;D:\SVN\projects\Java\Java.Algorithm\target\test-classes;D:\SVN\projects\Java\Java.Algorithm\target\classes;C:\ProgramFiles(x86)\JetBrains\IntelliJIDEA13.0.2\lib\idea_rt.jar"com.intellij.rt.execution.application.AppMainMain
start...

===========================LRU链表实现===========================
5:114:113:112:111:11
4:117:772:116:665:11


===========================LRULinkedHashMap(inheritance)实现===========================
1:112:113:114:115:11
5:116:662:117:774:11


===========================LRULinkedHashMap(delegation)实现===========================
1:112:113:114:115:11
5:116:662:117:774:11


===========================FIFOLinkedHashMap默认实现===========================
{1=11,2=11,3=11,4=11,5=11}
{3=11,4=11,5=11,6=66,7=77}

over...

Processfinishedwithexitcode0

到此这篇关于详解Java实现LRU缓存的文章就介绍到这了,更多相关Java实现LRU缓存内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！

详解Java实现LRU缓存

热门推荐

随机推荐