Java 自定义实现 LRU 缓存算法
LinkedHashMap继承自HashMap,内部提供了一个removeEldestEntry方法,该方法正是实现LRU策略的关键所在,且HashMap内部专门为LinkedHashMap提供了3个专用回调方法,afterNodeAccess、afterNodeInsertion、afterNodeRemoval,这3个方法的字面意思非常容易理解,就是节点访问后、节点插入后、节点删除后分别执行的行为。基于以上行为LinkedHashMap就可以实现一个LRUCache的功能了。
关于LinkedHashMap的eldest:eldest字面意思为最老的,LinkedHashMap中有个叫做accessOrder的字段,当accessOrder为true时表示LinkedHashMap内部节点按照访问次数排序,最老的节点也就是访问最少的节点。当accessOrder为false时表示LinkedHashMap内部节点按照插入顺序排序,最老的节点也就是最早插入的节点,该值默认为false。
代码实现
自己实现LRUCache只需覆盖removeEldestEntry这个方法即可,代码如下
private static class LRUCache<K, V> extends LinkedHashMap<K, V> { private static final long serialVersionUID = -9111855653176630846L; private static int MAX_ELEMENTS; public LRUCache(int initCap, int maxSize) throws IllegalArgumentException { super(initCap, 0.75f, true); if (maxSize < 0) throw new IllegalArgumentException(); MAX_ELEMENTS = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > MAX_ELEMENTS; } }
以上代码需要一个MAX_ELEMENTS变量限制最大存储节点个数,插入节点时判断 如果当前节点个数已经超过了这个值则会根据LRU策略将访问最少的那个节点删除,这里需要注意,默认LinkedHashMap保证的是插入顺序,也就是节点按照插入先后来排序的,所以就算删除也是删除最先插入的节点,但是我们在构造函数中传入了一个true,这个参数决定了LinkedHashMap内部的节点按照什么方式排序,参数为true时说明内部节点按照最近访问的时间排序,为false时说明按照插入顺序排序。至此已完成了一个简易的LRUCache实现。
注意
由于LinkedHahsMap本身实现不是线程安全的,也就是说这个LRUCache也不是线程安全的,如果想要能多线程访问的话,可以这样使用它:LRUCache cache = Collections.synchronizedMap(new LRUCache(10, 10))。这样cache就可以在多线程下执行get/put等操作了,但是,用这种方式得到的cache在多线程遍历时还是不安全的。所以不能在多线程下遍历cache,官方文档也建议在遍历synchronizedmap时使用map本身做同步。
Java实现简单的LRU缓存
应用程序经常需要在内存里缓存一些数据。Java里最常用的类是HashMap和Hashtable 。如果需要做一些更复杂的缓存,你可以使用JBoss Cache, OSCache或者EHCache。即使是使用其他的缓存系统,你可能仍然想要在本地用对象缓存一些数据,以便快速访问。在做这些缓存的时候经常会遇到一个令人讨厌的问题,就是要很小心的控制缓存大小以防止其占用过多内存的,如果缓存不停的增长就会影响程序的性能。
一个简单的解决方法就是给内存缓存设置一个最大的限制,采用LRU(最近最少使用)替换算法进行替换。这种方法可以对内存使用有个预期并且只在缓存里存储最近的使用过的数据。
自从JDK1.4,一种新的集合类LinkedHashMap被引入进来。LinkedHashMap有很多优点:
l 它能维持数据项的顺序。一个专门的构造函数(LinkedHashMap(Map<? extends K,? extends V> m) )可以实现遍历的顺序和插入的顺序可以保持一致。这个场景下用TreeMap就比较贵了。
l 它还有个removeEldestEntry(Map.Entry)方法,可以重写这个方法来表明替换的策略,这就是我们用来创建LRU缓存的主要方法。
Ok,下面是一段使用LinkedHashMap实现的LRU缓存:
import java.util.*; public class SimpleLRU { private static final int MAX_ENTRIES = 50; private Map mCache = new LinkedHashMap(MAX_ENTRIES, .75F, true) { protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } }; public SimpleLRU() { for(int i = 0; i < 100; i++) { String numberStr = String.valueOf(i); mCache.put(numberStr, numberStr); System.out.print("\rSize = " + mCache.size() + "\tCurrent value = " + i + "\tLast Value in cache = " + mCache.get(numberStr)); try { Thread.sleep(10); } catch(InterruptedException ex) { } } System.out.println(""); } public static void main(String[] args) { new SimpleLRU(); } }
这段代码创建了一个包含50个长度的简单的LRU缓存的实现。代码最神奇的部分就是在创建LinkedHashMap时,使用了true参数来表示维持访问顺序,并且重写了removeEldestEntry方法。运行程序,就可以看到cache size不断增加直到50,就不再增加,而开始替换最近最少使用的值。最后显示如下:
Size = 50 Current value = 99 Last Value in cache = 99
好了,现在你可以拿去胡作非为了,只要给他设置个最大值就不怕他增长个没完了。
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索内存
, 多线程
, 缓存
, 排序
, 代码
cache
lru缓存如何实现、java lru 缓存、lru算法java实现、lru java实现、java缓存实例,以便于您获取更多的相关知识。