讲真,网上有很多讲关于这个的文章。我这篇只是梳理下,巩固下自己的知识。以前学习图片缓存框架的时候,接触过Lru,只知道这是一个帮助减少内存开销的方法。每次他确实是缓存的一种策略。在古老的手机只有512m的年代,手机内存是需要很节省点的(不像现在动辄就是6gb内存),虽说我看到这个策略出现的时间Android 3.1的年代,但是其中的原理是万变不离其宗的。

对了,本文基于老的LruCache研究的。新版的linkedHashMap方法有些不存在了,比如LinkedHashMap的eldest()方法。

LruCache需要分开理解。L-least r-recently u-used。结合起来就是 最近最少使用的缓存(算法)。
里面的原理主要就是靠一个linkedHashMap去维持一个栈。而这个栈不像Activity那种栈,先进后出这种。而是根据使用的情况和谁先进栈的情况综合考虑。文字描述可能有点头疼,一图流表示如下。
请输入图片描述

linkedHashMap是HashMap的子类,是一种双向链表,其构造方法的第二个参数是扩容用的(0.75标识当前容量快到0.75)第三个参数决定了是否是Lru顺序还是插入顺序。
这段不理解不要紧。你指看到创建linkedHashMap的时候,第三个参数是基于访问顺序,如果是true,就是Lru,false是不按照此顺序。

    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }


     public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

但是使用LinkedHashMap的时候,使用方法是跟hashMap是没啥区别的。只是他内部方法,帮你完成了他的特定的顺序结构罢了。

  1. get方法:
    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V mapValue;
        synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }
        
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);
            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }
        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }

hitCount代表命中次数 missCount代表丢失次数。
可以看到get()方法是有synchronized 锁住的,所以Lru是线程安全的,然后先从linkedHashMap中通过key去获取value,如果存在,命中次数+1;反之,丢失次数+1。并且create()一个新的null返回回去。

  1. put方法:
    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }
        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        trimToSize(maxSize);
        return previous;
    }

这段代码意思是,如果不为null,put数加1,缓存空间数量+加上插入的缓存空间,并尝试往linkedHashMap插入数据,如果返回value不为null,则表示链表里面存在当前的key、value,缓存空间还原回未加之前。如果自己实现了entryRemoved方法,则会处理一遍。全部完成后,会去重新trimToSize()调整缓存大小。

有些人看源码会看到,哎哎哎,这个sizeOf返回的是1。怎么回事缓存空间大小呢?
因为safeSizeOf(key,value)-----> sizeOf(key,value),而sizeOf 是我们使用的时候会去重写的方法,所以会正确的返回value的大小。
  1. trimToSize方法:
    public void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }
                if (size <= maxSize) {
                    break;
                }
                //Map.Entry<K, V> toEvict = map.eldest();高版本找不到了,替换为下面的。
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                if (toEvict == null) {
                    break;
                }
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            entryRemoved(true, key, value, null);
        }
    }

这段表明trimTosize方法是个死循环,只有两个条件可以跳出。要么当前size比最大的缓存还大,要么就是链表的map已经没有存在任何键值对了。否则,就会去找链表中的最老的那条键值对,删除它,并且减去相应的空间缓存大小。
接着循环,看是否满足跳出的条件,直到满足条件。


其实关键的一点是,LinkedHashMap的方法去实现的,很多时候,需要去深入挖掘下,本文其实挺水的。因为LinkedHashMap他具体实现我并没有去深入研究(有点看不懂--!)。等我技术好点,再回头看看吧。或者给上大牛的分析文章。

参考文章:
LruCache 源码解析
彻底解析Android缓存机制——LruCache

标签: none

添加新评论