剖析LruCache

  提到Android的缓存策略任何一个Android开发人员都能随口说出LruCache,利用最新最少使用(Least Recently Used)的原则进行缓存,可LRU到底是怎么实现的呢?

LruCache简介

  LruCache是个泛型类,主要算法原理是把最近使用的对象用强引用(即我们平常使用的对象引用方式)存储在 LinkedHashMap 中。当缓存满时,把最近最少使用的对象从内存中移除,并提供了getput方法来完成缓存的获取和添加操作。

实现原理

LruCache内部维护的是一个LinkedHashMap,最近最少的算法判断逻辑都是由LinkedHashMap来实现,如果对LinkedHashMap原理不了解的童鞋,可以先了解下LinkedHashMap的原理分析这篇文章。

初始化

private final LinkedHashMap<K, V> map;

    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;    //当前cache的大小
    private int maxSize; //cache最大大小

    private int putCount;       //put的次数
    private int createCount;    //create的次数
    private int evictionCount;  //回收的次数
    private int hitCount;       //命中的次数
    private int missCount;      //未命中次数

    /**
     * @param maxSize for caches that do not override {@link #sizeOf}, this is
     *     the maximum number of entries in the cache. For all other caches,
     *     this is the maximum sum of the sizes of the entries in this cache.
     */
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        //将LinkedHashMap的accessOrder设置为true来实现LRU
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);  
    }

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);  //size加上预put对象的大小
            previous = map.put(key, value);
            if (previous != null) {
                //如果之前存在键为key的对象,则size应该减去原来对象的大小
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        //每次新加入对象都需要调用trimToSize方法看是否需要回收
        trimToSize(maxSize);
        return previous;
    }

由上面的代码可以看出来,首先把size增加,然后判断是否以前已经有元素,如果有,就更新当前的size,并且调用entryRemoved方法,entryRemoved是一个空实现,如果我们使用LruCache的时候需要掌握元素移除的信息,可以重写这个方法。最后就会调用trimToSize,来调整集合中的内容。

trimToSize 方法

/**
     * @param maxSize the maximum size of the cache before returning. May be -1
     *     to evict even 0-sized elements.
     * 此方法根据maxSize来调整内存cache的大小,如果maxSize传入-1,则清空缓存中的所有对象
     */
    private 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!");
                }
                //如果当前size小于maxSize或者map没有任何对象,则结束循环
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }
                //移除链表头部的元素,并进入下一次循环
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;  //回收次数+1
            }

            entryRemoved(true, key, value, null);
        }
    }

这个方法是一个无限循环,跳出循环的条件是,size < maxSize或者 map 为。主要的功能是判断当前容量时候已经超出最大的容量,如果超出了maxSize的话,就会循环移除map中的第一个元素,直到达到跳出循环的条件。由上面的分析知道,map中的第一个元素就是最近最少使用的那个元素。

get

/**
     * Returns the value for {@code key} if it exists in the cache or can be
     * created by {@code #create}. If a value was returned, it is moved to the
     * head of the queue. This returns null if a value is not cached and cannot
     * be created.
     * 通过key获取相应的item,或者创建返回相应的item。相应的item会移动到队列的尾部,
     * 如果item的value没有被cache或者不能被创建,则返回null。
     */
    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) {
                //mapValue不为空表示命中,hitCount+1并返回mapValue对象
                hitCount++;
                return mapValue;
            }
            missCount++;  //未命中
        }

        /*
         * Attempt to create a value. This may take a long time, and the map
         * may be different when create() returns. If a conflicting value was
         * added to the map while create() was working, we leave that value in
         * the map and release the created value.
         * 如果未命中,则试图创建一个对象,这里create方法返回null,并没有实现创建对象的方法
         * 如果需要事项创建对象的方法可以重写create方法。因为图片缓存时内存缓存没有命中会去
         * 文件缓存中去取或者从网络下载,所以并不需要创建。
         */
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
        //假如创建了新的对象,则继续往下执行
        synchronized (this) {
            createCount++;  
            //将createdValue加入到map中,并且将原来键为key的对象保存到mapValue
            mapValue = map.put(key, createdValue);   
            if (mapValue != null) {
                // There was a conflict so undo that last put
                //如果mapValue不为空,则撤销上一步的put操作。
                map.put(key, mapValue);
            } else {
                //加入新创建的对象之后需要重新计算size大小
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            //每次新加入对象都需要调用trimToSize方法看是否需要回收
            trimToSize(maxSize);
            return createdValue;
        }
    }

这个方法就先通过key来获取value,如果能获取到就就直接返回,获取不到的话,就调用create()方法创建一个,事实上,如果我们不重写这个create方法的话是return null的,所以整个流程就是获取得到就直接返回,获取不到就返回null

不要以为LruCache是多么复杂的一个算法,看过之后是不是感觉也就那么回事?-

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,284评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,115评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,614评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,671评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,699评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,562评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,309评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,223评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,668评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,859评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,981评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,705评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,310评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,904评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,023评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,146评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,933评论 2 355

推荐阅读更多精彩内容