Android中LRUCache实现的分析

发表于 |
字数统计: 1,048 | 阅读时长 ≈ 5

什么是LRU：

Least Recently Used(最近最少使用)，其思想如名称，定义一个固定size的缓存池，如果缓存内容没有超过缓存池，则所有的数据都是可以直接放入到池中的，但是如果需要缓存的对象，已经超过了缓存池的限制，则LRU会将最近最少被使用到的缓存池中的对象，驱逐出池，用于腾出空位置将新对象放入其中。

什么是LinkedHashMap：

内部基于双向链表，实现了Map接口的数据结构，在使用LinkedHashMap时，可以定义内部元素存储顺序，默认是按照insert的顺序，但是也可以按照访问顺序，LRUCache的实现，就是使用了LinkedHashMap的按照访问顺序特点。—
存储顺序按照插入顺序保存，最近读取的数据放在队列的尾部，最早读取的数据放在了队列的头部，如果当前存储的数据大小已经超过定义的最大值，则新数据插入，会将队头部的数据清除。

Android实现的版本，是采用delegation的方式，如果使用inherition的方式，可以在外部直接使用Collections.sychorinzed(Map)的方式很方便的实现线程安全属性。而使用delegation的方式，则需要自己实现线程同步的问题(Android的版本是线程安全的)。

关于一个缓存工具的使用，其中必然最重要的就是get和put(add)方法的使用了，那么接下来就来分析一下其实现：

  1. LRUCache.get(K key)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
    * 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.
    */
   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++;
       }
       /**
       在缓存未命中的情况下，可能需要create一个value值，因为此方法不是线程安全的，所以在将其插入到map中，产生冲突时，保留插入之前的值，放弃create产生的值。由此可知，在继承LRUCache的子类中，可以在缓存不命中的情况下，通过create方法，产生需要的value，而不需要put显式的插入value。
       **/
       V createdValue = create(key);//create未实现的空方法。
       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;
       }
   }

  1. LRUCache.put(K key, V value):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    /**
      * Caches {@code value} for {@code key}. The value is moved to the head of
      * the queue.
      *
      * @return the previous value mapped by {@code key}.
      */
     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;
     }

  2. LRUCache.remove(K key):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    /**
        * Removes the entry for {@code key} if it exists.
        *
        * @return the previous value mapped by {@code key}.
        */
       public final V remove(K key) {
           if (key == null) {
               throw new NullPointerException("key == null");
           }
           V previous;
           synchronized (this) {
               previous = map.remove(key);
               if (previous != null) {
                   size -= safeSizeOf(key, previous);
               }
           }
           if (previous != null) {
               entryRemoved(false, key, previous, null);
           }
           return previous;
       }

  3. LRUCache.trimToSize:
    在1，2，3方法中，都涉及到了此方法，此方法是控制缓存的关键。在初始化定义LinkedHashMap的时候，指定了maxSize，该值可以指代缓存对象的多少，也可以指代缓存对象总体占用内存的多少。而在超出maxSize的时候，就需要trimToSize方法去清理 – 最近最少使用 –的对象。

    /**
  * Remove the eldest entries until the total of remaining entries is at or
  * below the requested size.
  *
  * @param maxSize the maximum size of the cache before returning. May be -1
  *            to evict even 0-sized elements.
  */
 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 || map.isEmpty()) {
                 break;
             }

             Map.Entry<K, V> toEvict = map.entrySet().iterator().next();//因为每次get都会将对象放置队尾，所以迭代器开始遍历的队首就是使用最少，最优先被evict的元素。
             key = toEvict.getKey();
             value = toEvict.getValue();
             map.remove(key);
             size -= safeSizeOf(key, value);
             evictionCount++;
         }

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