十一、LruCache原理

LrcCache是Android3.1所提供的一個(gè)緩存類。LruCache類是泛型類朴摊,主要算法原理是把最近使用的對(duì)象強(qiáng)引用(即我們平常使用的對(duì)象引用方式)存儲(chǔ)在LinkedHashMap中。當(dāng)緩存滿時(shí)此虑,把最近最少使用的對(duì)象從內(nèi)存中移除甚纲,并提供了get和put方法來(lái)完成緩存的獲取和添加操作。

1朦前、LruCache的使用

lruCache的使用非常簡(jiǎn)單介杆,以圖片緩存為例

    private LruCache mMemoryCache = null;
    private void lrcCaheceInit() {
        int maxMemory = (int) (Runtime.getRuntime().totalMemory() / 1024);
        int cacheSize = maxMemory / 8;
        mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap value) {
                return value.getRowBytes() * value.getHeight() / 1024;
            }
        };
    }
  1. 設(shè)置LruCache緩存的大小鹃操,一般為當(dāng)前進(jìn)程可用容量的1/8.
  2. 重寫(xiě)sizeOf方法,計(jì)算出要緩存的每張圖片的大小春哨。
    注意:緩存的總量和每個(gè)緩存對(duì)象的大小所用單位要一致荆隘。

2、LruCache實(shí)現(xiàn)的原理

維護(hù)一個(gè)緩存對(duì)象的列表赴背,其中對(duì)象列表的排序方式是按照訪問(wèn)的順序?qū)崿F(xiàn)的椰拒,即一直沒(méi)有訪問(wèn)的對(duì)象,就放在隊(duì)尾凰荚,即將被淘汰燃观。而最近訪問(wèn)的對(duì)象放在隊(duì)頭,最后被淘汰便瑟。淘汰過(guò)程圖:

淘汰過(guò)程圖

該隊(duì)列便是由linkedHashMap來(lái)維護(hù)缆毁。而LinkedHashMap則是由數(shù)組+雙向鏈表的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。其中雙向鏈表的結(jié)構(gòu)可以實(shí)現(xiàn)訪問(wèn)順序和插入順序胳徽,使得LinkedHashMap中的鍵值對(duì)积锅,按照一定的順序排列起來(lái)。
通過(guò)下面構(gòu)造函數(shù)來(lái)指定LinkedHashMap中的結(jié)構(gòu)是訪問(wèn)順序還是插入順序养盗。

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

其中accessOrder設(shè)置為true則為訪問(wèn)順序,false則為插入順序适篙。

具體例子解釋往核,當(dāng)設(shè)置為true時(shí):

        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 
                0.75f, true);
        map.put(0, 0);
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        map.put(4, 4);
        map.put(5, 5);
        map.put(6, 6);
        map.get(1);
        map.get(2);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }

輸出結(jié)果:

0:0
3:3
4:4
5:5
6:6
1:1
2:2

即最近訪問(wèn)的的最后輸出,那么這就正好滿足LRU緩存算法的思想嚷节。

在LruCache源碼中聂儒,怎么應(yīng)用LinkedHashMap來(lái)實(shí)現(xiàn)緩存的添加,獲得和刪除的硫痰。

   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);
    }

從LruCache的構(gòu)造函數(shù)中可以看到是用了LinkedHashMap的訪問(wèn)順序衩婚。
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) {
        //插入的緩存對(duì)象加1
            putCount++;
    //增加已有的緩存大小
            size += safeSizeOf(key, value);
    //在map中加入緩存對(duì)象
            previous = map.put(key, value);
    //如果已有緩存對(duì)象,則緩存大小回復(fù)之前的大小
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }
    //空方法效斑,自行實(shí)現(xiàn)
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
    //調(diào)整緩存大小的關(guān)鍵方法
        trimToSize(maxSize);
        return previous;
    }

put方法中非春,主要的就是添加緩存對(duì)象后,調(diào)用trimSize()方法缓屠,來(lái)判斷是否緩存已滿奇昙,如果滿了就要?jiǎng)h除近期最少使用的算法。

  private void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
    //如果map為空并且緩存size不等于0或者緩存size小于0敌完,則拋出異常
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }
      //如果緩存大小小于最大緩存储耐,跳出緩存
                if (size <= maxSize) {
                    break;
                }
    //遍歷map集合,取隊(duì)尾的元素滨溉,近期訪問(wèn)最少的元素
                Map.Entry<K, V> toEvict = null;
                for (Map.Entry<K, V> entry : map.entrySet()) {
                    toEvict = entry;
                }
              
                if (toEvict == null) {
                    break;
                }
                key = toEvict.getKey();
                value = toEvict.getValue();
    //刪除該對(duì)象什湘,并更新緩存大小
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            entryRemoved(true, key, value, null);
        }
    }

trimToSize()方法不停地刪除LinkedHashMap中隊(duì)尾的元素长赞,即近期最少訪問(wèn)的,知道緩存大小小于最大值闽撤。
當(dāng)調(diào)用LruCache的get()方法獲取緩存中的對(duì)象時(shí)涧卵,就代表了一次該元素,將會(huì)更新隊(duì)列腹尖,保持整個(gè)隊(duì)列是按照訪問(wèn)順序排序柳恐。這個(gè)更新過(guò)程就是在LinkedHashMap中的get()方法中完成的。
get()方法:

    public final V get(K key) {
    //key為空拋出異常
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V mapValue;
        synchronized (this) {
    //獲取對(duì)應(yīng)的緩存對(duì)象
    //get()方法會(huì)實(shí)現(xiàn)將訪問(wèn)的元素更新到隊(duì)列頭部的功能热幔。
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

其中LinkedHashMap的get()方法如下:

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
          //實(shí)現(xiàn)排序的方法
            afterNodeAccess(e);
        return e.value;
    }

afterNodeAccess()方法

    void afterNodeAccess(Node<K,V> e) { // 將節(jié)點(diǎn)挪到隊(duì)尾
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<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;
        }
    }

由此乐设,LruCache中維護(hù)了一個(gè)集合LinkedHashMap,該LinkedHashMap是以順序排序的绎巨。當(dāng)調(diào)用put()方法時(shí)近尚,就會(huì)在集合中添加元素,并調(diào)用trimToSize()判斷緩存是否已滿场勤。如果滿了就刪除最后的元素戈锻。當(dāng)調(diào)用get()方法訪問(wèn)緩存的對(duì)象時(shí),就調(diào)用LinkedHashMap的get()方法獲得對(duì)應(yīng)集合元素和媳。同時(shí)更新該元素到隊(duì)頭格遭。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市留瞳,隨后出現(xiàn)的幾起案子拒迅,更是在濱河造成了極大的恐慌,老刑警劉巖她倘,帶你破解...
    沈念sama閱讀 216,470評(píng)論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件璧微,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡硬梁,警方通過(guò)查閱死者的電腦和手機(jī)前硫,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,393評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)荧止,“玉大人屹电,你說(shuō)我怎么就攤上這事≌窒ⅲ” “怎么了嗤详?”我有些...
    開(kāi)封第一講書(shū)人閱讀 162,577評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)瓷炮。 經(jīng)常有香客問(wèn)我葱色,道長(zhǎng),這世上最難降的妖魔是什么娘香? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,176評(píng)論 1 292
  • 正文 為了忘掉前任苍狰,我火速辦了婚禮办龄,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘淋昭。我一直安慰自己俐填,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,189評(píng)論 6 388
  • 文/花漫 我一把揭開(kāi)白布翔忽。 她就那樣靜靜地躺著英融,像睡著了一般。 火紅的嫁衣襯著肌膚如雪歇式。 梳的紋絲不亂的頭發(fā)上驶悟,一...
    開(kāi)封第一講書(shū)人閱讀 51,155評(píng)論 1 299
  • 那天,我揣著相機(jī)與錄音材失,去河邊找鬼痕鳍。 笑死,一個(gè)胖子當(dāng)著我的面吹牛龙巨,可吹牛的內(nèi)容都是我干的笼呆。 我是一名探鬼主播,決...
    沈念sama閱讀 40,041評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼旨别,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼诗赌!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起昼榛,我...
    開(kāi)封第一講書(shū)人閱讀 38,903評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤境肾,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后胆屿,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,319評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡偶宫,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,539評(píng)論 2 332
  • 正文 我和宋清朗相戀三年非迹,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片纯趋。...
    茶點(diǎn)故事閱讀 39,703評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡憎兽,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出吵冒,到底是詐尸還是另有隱情纯命,我是刑警寧澤,帶...
    沈念sama閱讀 35,417評(píng)論 5 343
  • 正文 年R本政府宣布痹栖,位于F島的核電站亿汞,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏揪阿。R本人自食惡果不足惜疗我,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,013評(píng)論 3 325
  • 文/蒙蒙 一咆畏、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧吴裤,春花似錦旧找、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,664評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至剖膳,卻和暖如春魏颓,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背潮秘。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,818評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工琼开, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人枕荞。 一個(gè)月前我還...
    沈念sama閱讀 47,711評(píng)論 2 368
  • 正文 我出身青樓柜候,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親躏精。 傳聞我的和親對(duì)象是個(gè)殘疾皇子渣刷,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,601評(píng)論 2 353