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
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!