java LRU(Least Recently Used )详解及实例代码
javaLRU(LeastRecentlyUsed)详解
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.Entry<K,V>eldest){
returnfalse;
}
LRU缓存LinkedHashMap(inheritance)实现
采用inheritance方式实现比较简单，而且实现了Map接口，在多线程环境使用时可以使用Collections.synchronizedMap()方法实现线程安全操作
packagecn.lzrabbit.structure.lru;
importjava.util.LinkedHashMap;
importjava.util.Map;
/**
*Createdbyliuzhaoon14-5-15.
*/
publicclassLRUCache2<K,V>extendsLinkedHashMap<K,V>{
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.Entry<K,V>entry:entrySet()){
sb.append(String.format("%s:%s",entry.getKey(),entry.getValue()));
}
returnsb.toString();
}
}
这样算是比较标准的实现吧，实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦
finalintcacheSize=100;
Map<String,String>map=newLinkedHashMap<String,String>((int)Math.ceil(cacheSize/0.75f)+1,0.75f,true){
@Override
protectedbooleanremoveEldestEntry(Map.Entry<String,String>eldest){
returnsize()>cacheSize;
}
};
LRU缓存LinkedHashMap(delegation)实现
delegation方式实现更加优雅一些，但是由于没有实现Map接口，所以线程同步就需要自己搞定了
packagecn.lzrabbit.structure.lru;
importjava.util.LinkedHashMap;
importjava.util.Map;
importjava.util.Set;
/**
*Createdbyliuzhaoon14-5-13.
*/
publicclassLRUCache3<K,V>{
privatefinalintMAX_CACHE_SIZE;
privatefinalfloatDEFAULT_LOAD_FACTOR=0.75f;
LinkedHashMap<K,V>map;
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<Map.Entry<K,V>>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<K,V>{
privatefinalintMAX_CACHE_SIZE;
privateEntryfirst;
privateEntrylast;
privateHashMap<K,Entry<K,V>>hashMap;
publicLRUCache1(intcacheSize){
MAX_CACHE_SIZE=cacheSize;
hashMap=newHashMap<K,Entry<K,V>>();
}
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){
Entry<K,V>entry=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;
}
}
privateEntry<K,V>getEntry(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<K,V>{
publicEntrypre;
publicEntrynext;
publicKkey;
publicVvalue;
}
}
LinkedHashMap的FIFO实现
FIFO是FirstInputFirstOutput的缩写，也就是常说的先入先出，默认情况下LinkedHashMap就是按照添加顺序保存，我们只需重写下removeEldestEntry方法即可轻松实现一个FIFO缓存，简化版的实现代码如下
finalintcacheSize=5;
LinkedHashMap<Integer,String>lru=newLinkedHashMap<Integer,String>(){
@Override
protectedbooleanremoveEldestEntry(Map.Entry<Integer,String>eldest){
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链表实现===========================");
LRUCache1<Integer,String>lru=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();
}
static<T>voidlruCache2(){
System.out.println();
System.out.println("===========================LRULinkedHashMap(inheritance)实现===========================");
LRUCache2<Integer,String>lru=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)实现===========================");
LRUCache3<Integer,String>lru=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;
LinkedHashMap<Integer,String>lru=newLinkedHashMap<Integer,String>(){
@Override
protectedbooleanremoveEldestEntry(Map.Entry<Integer,String>eldest){
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
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！