lru是least recently used 的缩写，翻译过来就是“最近最少使用”，lru缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。
比如我们缓存10000条数据，当数据小于10000时可以随意添加，当超过10000时就需要把新的数据添加进来，同时要把过期数据删除，以确保我们最大缓存10000条，那怎么确定删除哪条过期数据呢，采用lru算法实现的话就是将最老的数据删掉。
下面来说下java版的lru缓存实现：（推荐：java视频教程）
java里面实现lru缓存通常有两种选择，一种是使用linkedhashmap，一种是自己设计数据结构，使用链表+hashmap
lru cache的linkedhashmap实现
linkedhashmap自身已经实现了顺序存储，默认情况下是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据。
我们使用linkedhashmap实现lru缓存的方法就是对linkedhashmap实现简单的扩展，扩展方式有两种，一种是inheritance，一种是delegation。
//linkedhashmap的一个构造函数，当参数accessorder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面public linkedhashmap(int initialcapacity, float loadfactor, boolean accessorder) { super(initialcapacity, loadfactor); this.accessorder = accessorder;}//linkedhashmap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据//我们要做的就是重写这个方法，当满足一定条件时删除老数据protected boolean removeeldestentry(map.entry<k,v> eldest) { return false;}
lru缓存linkedhashmap(inheritance)实现
采用inheritance方式实现比较简单，而且实现了map接口，在多线程环境使用时可以使用 collections.synchronizedmap()方法实现线程安全操作
package cn.lzrabbit.structure.lru;import java.util.linkedhashmap;import java.util.map;/** * created by liuzhao on 14-5-15. */public class lrucache2<k, v> extends linkedhashmap<k, v> { private final int max_cache_size; public lrucache2(int cachesize) { super((int) math.ceil(cachesize / 0.75) + 1, 0.75f, true); max_cache_size = cachesize; } @override protected boolean removeeldestentry(map.entry eldest) { return size() > max_cache_size; } @override public string tostring() { stringbuilder sb = new stringbuilder(); for (map.entry<k, v> entry : entryset()) { sb.append(string.format("%s:%s ", entry.getkey(), entry.getvalue())); } return sb.tostring(); }}
这样算是比较标准的实现吧，实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦
final int cachesize = 100;map<string, string> map = new linkedhashmap<string, string>((int) math.ceil(cachesize / 0.75f) + 1, 0.75f, true) { @override protected boolean removeeldestentry(map.entry<string, string> eldest) { return size() > cachesize; }};
lru缓存linkedhashmap(delegation)实现
delegation方式实现更加优雅一些，但是由于没有实现map接口，所以线程同步就需要自己搞定了
package cn.lzrabbit.structure.lru;import java.util.linkedhashmap;import java.util.map;import java.util.set;/** * created by liuzhao on 14-5-13. */public class lrucache3<k, v> { private final int max_cache_size; private final float default_load_factor = 0.75f; linkedhashmap<k, v> map; public lrucache3(int cachesize) { max_cache_size = cachesize; //根据cachesize和加载因子计算hashmap的capactiy，+1确保当达到cachesize上限时不会触发hashmap的扩容， int capacity = (int) math.ceil(max_cache_size / default_load_factor) + 1; map = new linkedhashmap(capacity, default_load_factor, true) { @override protected boolean removeeldestentry(map.entry eldest) { return size() > max_cache_size; } }; } public synchronized void put(k key, v value) { map.put(key, value); } public synchronized v get(k key) { return map.get(key); } public synchronized void remove(k key) { map.remove(key); } public synchronized set<map.entry<k, v>> getall() { return map.entryset(); } public synchronized int size() { return map.size(); } public synchronized void clear() { map.clear(); } @override public string tostring() { stringbuilder sb = new stringbuilder(); for (map.entry entry : map.entryset()) { sb.append(string.format("%s:%s ", entry.getkey(), entry.getvalue())); } return sb.tostring(); }}
lru cache的链表+hashmap实现
注：此实现为非线程安全，若在多线程环境下使用需要在相关方法上添加synchronized以实现线程安全操作
package cn.lzrabbit.structure.lru;import java.util.hashmap;/** * created by liuzhao on 14-5-12. */public class lrucache1<k, v> { private final int max_cache_size; private entry first; private entry last; private hashmap<k, entry<k, v>> hashmap; public lrucache1(int cachesize) { max_cache_size = cachesize; hashmap = new hashmap<k, entry<k, v>>(); } public void put(k key, v value) { entry entry = getentry(key); if (entry == null) { if (hashmap.size() >= max_cache_size) { hashmap.remove(last.key); removelast(); } entry = new entry(); entry.key = key; } entry.value = value; movetofirst(entry); hashmap.put(key, entry); } public v get(k key) { entry<k, v> entry = getentry(key); if (entry == null) return null; movetofirst(entry); return entry.value; } public void remove(k key) { entry entry = 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); } private void movetofirst(entry entry) { 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; } private void removelast() { if (last != null) { last = last.pre; if (last == null) first = null; else last.next = null; } } private entry<k, v> getentry(k key) { return hashmap.get(key); } @override public string tostring() { stringbuilder sb = new stringbuilder(); entry entry = first; while (entry != null) { sb.append(string.format("%s:%s ", entry.key, entry.value)); entry = entry.next; } return sb.tostring(); } class entry<k, v> { public entry pre; public entry next; public k key; public v value; }}
linkedhashmap的fifo实现
fifo是first input first output的缩写，也就是常说的先入先出，默认情况下linkedhashmap就是按照添加顺序保存，我们只需重写下removeeldestentry方法即可轻松实现一个fifo缓存，简化版的实现代码如下
final int cachesize = 5;linkedhashmap<integer, string> lru = new linkedhashmap<integer, string>() { @override protected boolean removeeldestentry(map.entry<integer, string> eldest) { return size() > cachesize; }};
调用示例
测试代码
package cn.lzrabbit.structure.lru;import cn.lzrabbit.itest;import java.util.linkedhashmap;import java.util.map;/** * created by liuzhao on 14-5-15. */public class lrucachetest { public static void main(string[] args) throws exception { system.out.println("start..."); lrucache1(); lrucache2(); lrucache3(); lrucache4(); system.out.println("over..."); } static void lrucache1() { system.out.println(); system.out.println("===========================lru 链表实现==========================="); lrucache1<integer, string> lru = new lrucache1(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> void lrucache2() { system.out.println(); system.out.println("===========================lru linkedhashmap(inheritance)实现==========================="); lrucache2<integer, string> lru = new lrucache2(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 void lrucache3() { system.out.println(); system.out.println("===========================lru linkedhashmap(delegation)实现==========================="); lrucache3<integer, string> lru = new lrucache3(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 void lrucache4() { system.out.println(); system.out.println("===========================fifo linkedhashmap默认实现==========================="); final int cachesize = 5; linkedhashmap<integer, string> lru = new linkedhashmap<integer, string>() { @override protected boolean removeeldestentry(map.entry<integer, string> eldest) { return size() > 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:\program files (x86)\java\jdk1.6.0_10\bin\java" -didea.launcher.port=7535 "-didea.launcher.bin.path=c:\program files (x86)\jetbrains\intellij idea 13.0.2\bin" -dfile.encoding=utf-8 -classpath "c:\program files (x86)\java\jdk1.6.0_10\jre\lib\charsets.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\deploy.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\javaws.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\jce.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\jsse.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\management-agent.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\plugin.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\resources.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\rt.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\localedata.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;c:\program files (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:\program files (x86)\jetbrains\intellij idea 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.appmain mainstart...===========================lru 链表实现===========================5:11 4:11 3:11 2:11 1:11 4:11 7:77 2:11 6:66 5:11 ===========================lru linkedhashmap(inheritance)实现===========================1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ===========================lru linkedhashmap(delegation)实现===========================1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ===========================fifo linkedhashmap默认实现==========================={1=11, 2=11, 3=11, 4=11, 5=11}{3=11, 4=11, 5=11, 6=66, 7=77}over...process finished with exit code 0
更多java知识请关注java基础教程栏目。
以上就是java中lru缓存实现的详细内容。