Java实现LRU缓存的实例详解

2023-09-26 13:20:05 56

Java实现LRU缓存的实例详解

1.Cache

Cache对于代码系统的加速与优化具有极大的作用，对于码农来说是一个很熟悉的概念。可以说，你在内存中new了一个一段空间（比方说数组，list）存放一些冗余的结果数据，并利用这些数据完成了以空间换时间的优化目的，你就已经使用了cache。

有服务级的缓存框架，如memcache，Redis等。其实，很多时候，我们在自己同一个服务内，或者单个进程内也需要缓存，例如，lucene就对搜索做了缓存，而无须依赖外界。那么，我们如何实现我们自己的缓存？还要带自动失效的，最好还是LRU（LeastRecentlyUsed）。

当你思考怎么去实现，你可能会想得很远。为了LRU，需要把刚使用的数据存入栈，或者纪录每个数据最近使用的时间，再来的定时扫描失效的线程….其实，Java本身就已经为我们提供了LRUCache很好的实现，即LinkedHashMap。

2.LinkedHashMap分析

很多没有去细究过其内部实现的人，只是将其当作一个普通的hashMap来对待。LinkedHashMap是一个双向链表，加上HashTable的实现。表现出来与普通HashMap的一个区别就是LinkedHashMap会记录存入其中的数据的顺序，并能按顺取出。
为了实现，一个hash表，自然应该先申请在一片连续的内存空间上。当需要存入数据的时候，根据相应的hash值存入。而LinkedHashMap在这个基础上，为每个entry设置了before与after属性，形了一个双向链表，记录了他们put进入的前后顺序。

不仅如此，每当通过get来获得某个元素后，get方法内部，会在最后通过afterNodeAccess方法来调整链表的指向:

voidafterNodeAccess(Nodee){//movenodetolast
LinkedHashMap.Entrylast;
if(accessOrder&&(last=tail)!=e){
LinkedHashMap.Entryp=
(LinkedHashMap.Entry)e,b=p.before,a=p.after;
p.after=null;
if(b==null)
head=a;
else
b.after=a;
if(a!=null)
a.before=b;
else
last=b;
if(last==null)
head=p;
else{
p.before=last;
last.after=p;
}
tail=p;
++modCount;
}
}

上述代码将Nodee移至了双向链表的未尾。而在方法afterNodeInsertion中，只要满足条件，便移除最老的数据,即链表的head。

voidafterNodeInsertion(booleanevict){//possiblyremoveeldest
LinkedHashMap.Entryfirst;
if(evict&&(first=head)!=null&&removeEldestEntry(first)){
Kkey=first.key;
removeNode(hash(key),key,null,false,true);
}
}

可见，当你为LinkedHashMap设置有限空间的时候，自然便完成了LRUCache的效果。当然还有一个前提，你必须重写一个方法removeEldestEntry,返回true。表示空间已满时，删除最老的。

@Override
publicbooleanremoveEldestEntry(Map.Entryeldest){
returnsize()>capacity;
}

3.线程安全的LRUCache

如此，我们就获得了一个LRU缓存利器，满足了我们大多场景下的需求。但还有一个问题，它不是线程安全的。在多线程的情况下，你有可能需要对某些Cache做同步处理。这时候，你再找，可以看到java有ConcurrentHashMap的实现，但并不存在ConcurrentLinkedHashMap这样的类。

当然这个问题也不大，我们可以对再有的LinkedHashMap，再作封装，对get，put,之类的方法加上同步操作。

目前，我们所用的处理，是直接采和google提供的guava包，这里面就提供了我们想要的ConcurrentLinkedHashMap。这样就可以很方便地实现一个线程安全。具体代码如下:

importjava.util.Set;

importcom.googlecode.concurrentlinkedhashmap.Weighers;
importcom.googlecode.concurrentlinkedhashmap.ConcurrentLinkedHashMap;
publicclassConcurrentLRUCache{
publicstaticfinalintDEFAULT_CONCURENCY_LEVEL=32;

privatefinalConcurrentLinkedHashMapmap;


publicConcurrentLRUCache(intcapacity){
this(capacity,DEFAULT_CONCURENCY_LEVEL);
}

publicConcurrentLRUCache(intcapacity,intconcurrency){
map=newConcurrentLinkedHashMap.Builder().weigher(Weighers.singleton())
.initialCapacity(capacity).maximumWeightedCapacity(capacity)
.concurrencyLevel(concurrency).build();
}

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

publicVget(Kkey){
Vv=map.get(key);
returnv;
}

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

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

publiclonggetCapacity(){
returnmap.capacity();
}


publicvoidupdateCapacity(intcapacity){
map.setCapacity(capacity);
}


publicintgetSize(){
returnmap.size();
}


publicvoidclear(){
map.clear();
}

publicSetgetKeySet(){
returnmap.keySet();
}
}

以上就是Java实现LRU缓存的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

Java实现LRU缓存的实例详解

热门推荐

随机推荐