Java实现LRU缓存_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > Java实现LRU缓存

Java实现LRU缓存

 2015/1/15 21:19:23  quentinXXZ  程序员俱乐部  我要评论(0)
  • 摘要:原文链接:http://quentinXXZ.iteye.com/blog/21763451、CacheCache对于代码系统的加速与优化具有极大的作用,对于码农来说是一个很熟悉的概念。可以说,你在内存中new了一个一段空间(比方说数组,list)存放一些冗余的结果数据,并利用这些数据完成了以空间换时间的优化目的,你就已经使用了cache。有服务级的缓存框架,如memcache,redis等。其实,很多时候,我们在自己同一个服务内,或者单个进程内也需要缓存,例如,lucene就对搜索做了缓存
  • 标签:实现 Java 缓存

原文链接:http://quentinXXZ.iteye.com/blog/2176345

class="MsoNormal">1、Cache

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

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

?

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

?

2、LinkedHashMap分析

很多没有去细究过其内部实现的人,只是将其当作一个普通的hashMap来对待。LinkedHashMap是一个双向链表,加上hashTable的实现。表现出来与普通HashMap的一个区别就是LinkedHashMap会记录存入其中的数据的顺序,并能按顺取出。

为了实现,一个hash表,自然应该先申请在一片连续的内存空间上。当需要存入数据的时候,根据相应的hash值存入。而LinkedHashMap在这个基础上,为每个entry设置了beforeafter属性,形了一个双向链表,记录了他们put进入的前后顺序。

?

不仅如此,当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同步处理。这时候,你再找,可以看到javaConcurrentHashMap的实现,但并不存在ConcurrentLinkedHashMap这样的类。

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

?

目前,我们所用的处理,是直接采和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();
    }
}

?

?

原文链接:http://quentinXXZ.iteye.com/blog/2176345

?

?

?

发表评论
用户名: 匿名