前言

說到Glide就有點(diǎn)尷尬渴析，我本來想出一篇《手撕Glide》，但是很遺憾吮龄，源碼實(shí)在太多了俭茧。寫著寫著就3000多字了，甚至還沒寫完漓帚，實(shí)在不合適母债，因?yàn)槲覍懳牡脑瓌t是短小精悍，所以就暫時(shí)不出這篇文章了尝抖，這次就先講講Glide都在用的LruCache有什么神奇之處场斑。而且我抖音的面試在即，也不知道自己水平到了沒有牵署，現(xiàn)在出一篇算一篇先。

思維導(dǎo)圖

使用方法及結(jié)果

在項(xiàng)目中直接導(dǎo)入Glide的庫喧半，調(diào)用內(nèi)部的LruCache來看看效果奴迅。

LruCache lruCache = new LruCache<String, Integer>(2);
lruCache.put("1", 1);
lruCache.put("2", 2);
lruCache.put("1", 1);
lruCache.put("3", 3);
System.out.println(lruCache.get("1"));
System.out.println(lruCache.get("2"));
System.out.println(lruCache.get("3"));

簡要說明代碼內(nèi)容，創(chuàng)建一個(gè)空間為2的存儲(chǔ)空間（這里先不透漏內(nèi)部結(jié)構(gòu)）挺据，用put()方法對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)取具，再通過get()對(duì)每個(gè)數(shù)據(jù)進(jìn)行一次獲取操作，然后我們?cè)賮砜纯唇Y(jié)果扁耐。

我的天Ｏ炯臁！2沒了婉称？ 這是怎么一回事块仆？？為了知道答案王暗，那我們只好進(jìn)入Glide的庫中看看原因了悔据。

LruCache源碼導(dǎo)讀

先看看LruCache的變量家庭里有哪些小家伙把。

public class LruCache<T, Y> {
  // 容量為100的雙向鏈表
  private final Map<T, Y> cache = new LinkedHashMap<>(100, 0.75f, true); 
  private final long initialMaxSize; // 初始化最大容量
  private long maxSize; // 最大容量
  private long currentSize; // 已存在容量
}

同樣對(duì)于LruCache來說不也和HashMap一樣只有三步驟要走嘛俗壹，那我就從這三個(gè)步驟入手探索一下LruCache好了科汗，但是我們要帶上一個(gè)問題出發(fā)，initialMaxSize的作用是什么绷雏？

new LruCache<T, Y>(size)

  public LruCache(long size) {
    this.initialMaxSize = size;
    this.maxSize = size;
  }

到這里想來讀者都已經(jīng)知道套路了头滔，也就初始化了初始化最大容量和最大容量怖亭，那就直接下一步。

put(key, value)

public synchronized Y put(@NonNull T key, @Nullable Y item) {
    // 返回值就是一個(gè)1
    final int itemSize = getSize(item);
    // 如果1大于等于最大值就無操作
    // 也就說明整個(gè)初始化的時(shí)候并不能將size設(shè)置成1
    if (itemSize >= maxSize) {
      //用于重寫的保留方法
      onItemEvicted(key, item);
      return null;
    }
    // 對(duì)當(dāng)前存在數(shù)據(jù)容量加一
    if (item != null) {
      currentSize += itemSize;
    }
    @Nullable final Y old = cache.put(key, item);
    if (old != null) {
      currentSize -= getSize(old);
    
      if (!old.equals(item)) {
        onItemEvicted(key, old);
      }
    }
    evict(); // 1 -->

    return old;
  }
// 由注釋1直接調(diào)用的方法
private void evict() {
    trimToSize(maxSize); // 2 -->
  }
// 由注釋2直接調(diào)用的方法 
protected synchronized void trimToSize(long size) {
    Map.Entry<T, Y> last;
    Iterator<Map.Entry<T, Y>> cacheIterator;
    // 說明當(dāng)前的容量大于了最大容量
    // 需要對(duì)最后的數(shù)據(jù)進(jìn)行一個(gè)清理
    while (currentSize > size) {
      cacheIterator = cache.entrySet().iterator();
      last = cacheIterator.next();
      final Y toRemove = last.getValue();
      currentSize -= getSize(toRemove);
      final T key = last.getKey();
      cacheIterator.remove();
      onItemEvicted(key, toRemove);
    }
  }

這是一個(gè)帶鎖機(jī)制的方法坤检，通過對(duì)當(dāng)前容量和最大容量的判斷兴猩，來抉擇是否需要把我們的數(shù)據(jù)進(jìn)行一個(gè)刪除。但是問題依舊存在缀蹄，initialMaxSize的作用是什么峭跳？，我們能夠知道的是maxSize是一個(gè)用于控制容量大小的值缺前。

get()

 public synchronized Y get(@NonNull T key) {
    return cache.get(key);
  }

那這就是調(diào)用了LinkedHashMap中的數(shù)據(jù)蛀醉，但是終究還是沒有說出initialMaxSize的作用。

關(guān)于initialMaxSize

這里就不買關(guān)子了衅码，因?yàn)槠鋵?shí)就我的視角來看這個(gè)initialMaxSize確實(shí)是沒啥用處的拯刁。哈哈哈哈哈！Ｊ哦巍垛玻！但是，又一個(gè)地方用到了它奶躯。

public synchronized void setSizeMultiplier(float multiplier) {
    if (multiplier < 0) {
      throw new IllegalArgumentException("Multiplier must be >= 0");
    }
    maxSize = Math.round(initialMaxSize * multiplier);
    evict();
  }

也就是用于調(diào)控我們的最大容量大小帚桩，但是我覺得還是沒啥用，可是是我太菜了吧嘹黔，這個(gè)方法沒有其他調(diào)用它的方法账嚎，是一個(gè)我們直接在使用過程中使用的，可能和數(shù)據(jù)多次使用的一個(gè)保存之類的問題相關(guān)聯(lián)把儡蔓，場(chǎng)景的話也就類似Glide的圖片緩存加載把郭蕉。也希望知道的讀者能給我一個(gè)解答。

LinkedHashMap

因?yàn)椴僮鞣绞胶?code>HashMap一致就不再復(fù)述喂江，就看看他的節(jié)點(diǎn)長相召锈。

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        // 存在前后節(jié)點(diǎn)，也就是我們所說的雙向鏈表
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }

但是到這里获询，我又出現(xiàn)了一個(gè)問題涨岁，為什么我沒有看到整個(gè)數(shù)據(jù)的移動(dòng)？也就是最近使用的數(shù)據(jù)應(yīng)該調(diào)換到最后開始的位置吉嚣，他到底實(shí)在哪里進(jìn)行處理的呢卵惦？做一個(gè)猜想好了，既然是使用了put()才會(huì)造成雙向鏈表中數(shù)據(jù)的變換瓦戚，那我們就應(yīng)該是需要進(jìn)入對(duì)LinkedHashMap.put()方法中進(jìn)行查詢沮尿。

當(dāng)然有興趣探索的讀者們，我需要提一個(gè)醒，就是這次的調(diào)用不可以直接進(jìn)行對(duì)put()進(jìn)行查詢畜疾，那樣只會(huì)調(diào)用到一個(gè)接口函數(shù)赴邻，或者是抽象類函數(shù)，最適合的方法還是使用我們的斷點(diǎn)來進(jìn)行探索查詢啡捶。

但是經(jīng)過一段努力后姥敛，不斷深度調(diào)用探索發(fā)現(xiàn)這樣的問題，他最后會(huì)調(diào)用到這樣的問題瞎暑。

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { } // 把數(shù)據(jù)移動(dòng)到最后一位
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

這是之前我們?cè)诹私?code>HashMap是并沒有發(fā)現(xiàn)幾個(gè)方法彤敛，上面也明確寫著為LinkedHashMap保留。哇哦Ａ硕摹墨榄！那我們的操作肯定實(shí)在這些里面了。

// --> HashMap源碼第656行附近調(diào)用到下方方法
// 在putVal()方法內(nèi)部存在這個(gè)出現(xiàn)
afterNodeAccess(e);
// --> LinkedHashMap對(duì)其具體實(shí)現(xiàn)
// 就是將當(dāng)前數(shù)據(jù)直接推到最后一個(gè)位置
// 也就是成為了最近剛使用過的數(shù)據(jù)
void afterNodeAccess(Node<K,V> e) { // move node to last
        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;
        }
    }

好了勿她，自此我們也就清楚了整個(gè)鏈表的變換過程了害捕。

實(shí)戰(zhàn)：手?jǐn)]LruCache

這是一個(gè)非常緊張刺激的環(huán)節(jié)了蝠引，擼代碼前双絮，我們來找找思路好了跺嗽。

（1）存儲(chǔ)容器用什么？ 因?yàn)?code>LinkedHashMap的思路太過冗長砍聊，我們用數(shù)組來重新完成整個(gè)代碼的構(gòu)建

（2）關(guān)鍵調(diào)用方法put()背稼、get()以及put()涉及的已存在變量移位。

哇哦玻蝌！看來要做的事情也并沒有這么多,那我們就先來看看第一次構(gòu)造出來的框架好了雇庙。

public class LruCache {

    private Object objects[];
    private int maxSize;
    private int currentSize;

    public LruCache(int size){
        objects = new Object[size];
        maxSize = size;
    }

    /**
     * 插入item
     * @param item
     */
    public void put(Object item){
        
    }

    /**
     * 獲取item
     * @param item
     */
    public Object get(Object item){
        return null;
    }

    /**
     * 根據(jù)下標(biāo)對(duì)應(yīng)，將后續(xù)數(shù)組移位
     * @param index
     */
    public void move(int index){
        
    }
}

因?yàn)橹灰菙?shù)組變換就存在移位灶伊，所以移位操作是必不可少的。那我們現(xiàn)在的工作也就是把數(shù)據(jù)填好了寒跳，對(duì)應(yīng)的移位是怎么樣的操作的思路了聘萨。

public class LruCache {

    public Object objects[];
    private int maxSize;
    public int currentSize;

    public LruCache(int size) {
        objects = new Object[size];
        maxSize = size;
    }

    /**
     * 插入item
     *
     * @param item
     */
    public void put(Object item) {
        // 容量未滿時(shí)分成兩種情況
        // 1。 容器內(nèi)存在
        // 2童太。 容器內(nèi)不存在
        int index = search(item);
        if (index == -1) {
            if (currentSize < maxSize) { //容器未滿米辐，直接插入
                objects[currentSize] = item;
                currentSize++;
            } else { // 容器已滿，刪去頭部插入
                move(0);
                objects[currentSize - 1] = item;
            }
        }else {
            move(index);
        }
    }

    /**
     * 獲取item
     *
     * @param item
     */
    public Object get(Object item) {
        int index = search(item);
        return index == -1 ? null : objects[index];
    }

    /**
     * 根據(jù)下標(biāo)對(duì)應(yīng)书释，將后續(xù)數(shù)組移位
     *
     * @param index
     */
    public void move(int index) {
        Object temp = objects[index];
        // 將后續(xù)數(shù)組移位
        for (int i = index; i < currentSize - 1; i++) {
            objects[i] = objects[i + 1];
        }
        objects[currentSize - 1] = temp;
    }

    /**
     * 搜尋數(shù)組中的數(shù)組
     * 存在則返回下標(biāo)
     * 不存在則返回 -1
     * @param item
     * @return
     */
    private int search(Object item) {
        for (int i = 0; i < currentSize; i++) {
            if (item.equals(objects[i])) return I;
        }
        return -1;
    }

因?yàn)橐呀?jīng)真的寫的比較詳細(xì)了翘贮，也沒什么難度的擼了我的20分鐘，希望讀者們能夠快入入門爆惧，下面給出我的一份測(cè)試樣例狸页，結(jié)束這個(gè)話題。

總結(jié)

想來我們都知道在操作系統(tǒng)中有這樣的問題需要思考，具體題型的話就是缺頁中斷芍耘。
用一個(gè)例題來徹底了解LruCache的算法址遇。

例： 存入內(nèi)存的數(shù)據(jù)序列為：（1，2斋竞，1倔约，3，2）坝初，內(nèi)存容量為2浸剩。

LruCache 主要用于緩存的處理,這里的緩存主要指的是內(nèi)存緩存和磁盤緩存袖扛。

以上就是我的學(xué)習(xí)成果，如果有什么我沒有思考到的地方或是文章內(nèi)存在錯(cuò)誤十籍，歡迎與我分享蛆封。

相關(guān)文章推薦：

面試中的HashMap、ConcurrentHashMap和Hashtable勾栗，你知道多少惨篱？

還不會(huì)七大排序，是準(zhǔn)備家里蹲嗎ＮХ砸讳？

手撕ButterKnife