LruCache算法原理及实现

LruCache算法原理

LRU为Least Recently Used的缩写，意思也就是近期最少使用算法。LruCache将LinkedHashMap的顺序设置为LRU顺序来实现LRU缓存，每次调用get并获取到值(也就是从内存缓存中命中)，则将该对象移到链表的尾端。调用put插入新的对象也是存储在链表尾端，这样当内存缓存达到设定的最大值时，将链表头部的对象（近期最少用到的）移除。

基于LinkedHashMap的LRUCache的实现，关键是重写LinkedHashMap的removeEldestEntry方法，在LinkedHashMap中该方法默认返回false（LRUCache本身未考虑线程安全的问题），这样此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

LruCache算法实现的思路

• 按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，LinkedHashMap提供了LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)构造函数，该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。

• LinkedHashMap提供了removeEldestEntry(Map.Entry eldest)方法。该方法在每次添加新条目时移除最旧条目，但该方法默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。因而需要重写该方法。

基于LinkedHashMap的LruCache具体实现

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> {
    private LinkedHashMap<K, V> map;//链表存储对象

    private int cacheSize;//cache大小
    private int hitCount;//命中次数
    private int missCount;//未命中次数

    public synchronized final int getCacheSize() {
        return cacheSize;
    }

    public synchronized final int getHitCount() {
        return hitCount;
    }

    public synchronized final int getMissCount() {
        return missCount;
    }

    static final int DEFAULT_CACHE_SIZE = 2;//cache默认大小

    public V put(K key, V value) {
        return map.put(key, value);
    }

    public V get(Object key) {

        if (null == key) {
            throw new NullPointerException(" key == null ");
        }

        V val = null;
        synchronized (this) {
            val = map.get(key);
            if (null != val) {
                hitCount += 1;
                return val;
            }

            missCount += 1;
        }

        return val;
    }

    public LruCache() {
        this(DEFAULT_CACHE_SIZE);
    }

    public LruCache(int cacheSize) {
        this.cacheSize = cacheSize;
        int hashTableSize = (int) (Math.ceil(cacheSize / 0.75f) + 1);

        //LruCache算法实现的关键

        //1、按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap
        //public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder); //该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。
        //2、LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
        map = new LinkedHashMap<K, V>(hashTableSize, 0.75f, true){
            private static final long serialVersionUID = 1L;

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                System.out.println(" ***** size=" + size() + " cacheSize=" + LruCache.this.cacheSize + " ****");
//                return super.removeEldestEntry(eldest);
                return size() > LruCache.this.cacheSize;
            }
        };
    }

    public static void main(String[] args) {

        LruCache<String, String> lruCache = new LruCache<String, String>(3);
        lruCache.put("1", "1");
        lruCache.put("2", "2");
        lruCache.put("3", "3");
        lruCache.put("4", "4");
        lruCache.put("5", "5");

        System.out.println("==========================================================================");
        System.out.println("hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println("==========================================================================");

        System.out.println(lruCache.get("1") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println(lruCache.get("2") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println(lruCache.get("3") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println(lruCache.get("4") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println(lruCache.get("4") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println(lruCache.get("4") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        System.out.println(lruCache.get("4") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());
        lruCache.put("6", "6");
        lruCache.put("7", "7");
        System.out.println(lruCache.get("4") + " hitCount=" + lruCache.getHitCount() + " missCount=" + lruCache.getMissCount());
        lruCache.put("8", "8");

        System.out.println(lruCache.get("5") + " hitCount=" + lruCache.getHitCount() + " missCount=" +  lruCache.getMissCount());

        System.out.println("==========================================================================");
        for(Map.Entry<String, String> entry : lruCache.map.entrySet()) {
            System.out.println(entry.getKey()+":"+entry.getValue());
        }

    }
}

执行结果

***** size=1 cacheSize=3 ****
***** size=2 cacheSize=3 ****
***** size=3 cacheSize=3 ****
***** size=4 cacheSize=3 ****
***** size=4 cacheSize=3 ****
==========================================================================
hitCount=0 missCount=0
==========================================================================
null hitCount=0 missCount=1
null hitCount=0 missCount=2
3 hitCount=1 missCount=2
4 hitCount=2 missCount=2
4 hitCount=3 missCount=2
4 hitCount=4 missCount=2
4 hitCount=5 missCount=2
***** size=4 cacheSize=3 ****
***** size=4 cacheSize=3 ****
4 hitCount=6 missCount=2
***** size=4 cacheSize=3 ****
null hitCount=6 missCount=3
==========================================================================
7:7
4:4
8:8

参考文档：

• http://blog.csdn.net/pingnanlee/article/details/40585941
• http://www.cnblogs.com/children/archive/2012/10/02/2710624.html