欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现LRU缓存的实例详解

程序员文章站 2024-03-31 10:40:04
java实现lru缓存的实例详解 1.cache cache对于代码系统的加速与优化具有极大的作用,对于码农来说是一个很熟悉的概念。可以说,你在内存中new 了一个一段...

java实现lru缓存的实例详解

1.cache

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

有服务级的缓存框架,如memcache,redis等。其实,很多时候,我们在自己同一个服务内,或者单个进程内也需要缓存,例如,lucene就对搜索做了缓存,而无须依赖外界。那么,我们如何实现我们自己的缓存?还要带自动失效的,最好还是lru(least recently used)。

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

2.linkedhashmap分析

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

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

void afternodeaccess(node<k,v> e) { // move node to last
  linkedhashmap.entry<k,v> last;
  if (accessorder && (last = tail) != e) {
    linkedhashmap.entry<k,v> p =
      (linkedhashmap.entry<k,v>)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;
  }
}

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

void afternodeinsertion(boolean evict) { // possibly remove eldest
  linkedhashmap.entry<k,v> first;
  if (evict && (first = head) != null && removeeldestentry(first)) {
    k key = first.key;
    removenode(hash(key), key, null, false, true);
  }
} 

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

@override
public boolean removeeldestentry(map.entry<k, v> eldest){   
  return size()>capacity;    
}

3.线程安全的lru cache

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

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

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

import java.util.set;

 import com.googlecode.concurrentlinkedhashmap.weighers;
 import com.googlecode.concurrentlinkedhashmap.concurrentlinkedhashmap;
 public class concurrentlrucache<k, v> {
   public static final int           default_concurency_level = 32;

 private final concurrentlinkedhashmap<k, v> map;


 public concurrentlrucache(int capacity) {
   this(capacity, default_concurency_level);
 }

 public concurrentlrucache(int capacity, int concurrency) {
   map = new concurrentlinkedhashmap.builder<k, v>().weigher(weighers.<v> singleton())
    .initialcapacity(capacity).maximumweightedcapacity(capacity)
    .concurrencylevel(concurrency).build();
 }

 public void put(k key, v value) {
   map.put(key, value);
 }

 public v get(k key) {
   v v = map.get(key);
   return v;
 }

 public v getinternal(k key) {
   return map.get(key);
 }

 public void remove(k key) {
   map.remove(key);
 }

 public long getcapacity() {
   return map.capacity();
 }


 public void updatecapacity(int capacity) {
   map.setcapacity(capacity);
 }


 public int getsize() {
   return map.size();
 }


 public void clear() {
   map.clear();
 }

 public set<k> getkeyset() {
   return map.keyset();
 }
}

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