arithmetic

LruCache (Lru 算法)

Posted by Jfson on 2017-12-22

LRUCache

  • 1.Android 的缓存中不管是内存缓存和磁盘缓存都用到了LruCache，LruCache的核心思想就是LRU(Least Recently Used)算法

LRU 算法

  • LRU(Least Recently Used)直面翻译过来：最近最少使用，就是淘汰旧数据的策略，保留最近访问过的数据。如果需要加载新数据但空间不足的情况下，会按照最近访问时间排序，将最老的数据淘汰掉。

辅助知识

  • LinkedHashMap

    • HashMap我们很熟悉了，LinkedHashMap 是HashMap的子类，可以理解为是：HashMap+LinkedList，一个有序的HashMap。
    • 通过维护所有item的双向链表，保证了元素的顺序。该迭代顺序可以是插入顺序或者是访问顺序。迭代顺序在构造时可以指定。

  • LinkedHashMap 排序模式

1
2
3
4
5
6
7
8
9
10
11
/**
  * initialCapacity 初始容量
  * loadFactor 达到该百分比就扩容Map
  * 排序模式：true为访问顺序  false为插入顺序
  */
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
}
  • 访问顺序，当插入10个数据后(0,1,2,3,4,5,6,7,8,9),这时候如果对第3个数据进行访问/操作，该数据会被排在队列尾部（0,1,3,4,5,6,7,8,9,2）
  • 插入顺序，当插入10个数据后(0,1,2,3,4,5,6,7,8,9),这时候如果对第3个数据进行访问/操作，该数据位置不会产生变动（0,1,2,3,4,5,6,7,8,9）

LRUCache源码

  • 1、 从构造看起，构造并没有多余的东西，初始化了一个LinkedHashMap，和 maxSize。这里我们看到LinkedHashMap中传的第三个参数为true,那么其排序模式为访问模式。
1
2
3
4
5
6
7
8
9
10
11
12
13
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 Map.Entry<K, V> eldest() {
    Entry<K, V> eldest = header.after;
    return eldest != header ? eldest : null;
}
  • 2、put() 增
    • a.有则覆盖，无则put进map
    • b.size 计数
    • c.trimToSize() 刷新数据，移除超过maxSize数据
      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
      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 ++ 增大缓存大小
                  size += safeSizeOf(key, value);
                  previous = map.put(key, value);
                  if (previous != null) {
                      // size-- 如果已有了，恢复增加的
                      size -= safeSizeOf(key, previous);
                  }
              }
              if (previous != null) {
                  // 无逻辑，自行实现
                  entryRemoved(false, key, previous, value);
              }
              // LRU 核心方法
              trimToSize(maxSize);
              return previous;
          }
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
//移除超过maxSize数据
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) {
                    // while 结束
                    break;
                }
                //获取最旧的数据
                Map.Entry<K, V> toEvict = map.eldest();
                if (toEvict == null) {
                    // while 结束
                    break;
                }
                key = toEvict.getKey();
                value = toEvict.getValue();
                // 移除该最旧的数据
                map.remove(key);
                // size--  更新size
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            entryRemoved(true, key, value, null);
        }
    }
  • 3、get() 获取
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
public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V mapValue;
        synchronized (this) {
            // 查找，并根据访问排序的规则，该key的数据将被放置到map队列末尾
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }
        // 尝试新建一个（不明觉厉）
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
        synchronized (this) {
            createCount++;
            // 并加到map中
            mapValue = map.put(key, createdValue);
            
            if (mapValue != null) {
                //如果冲突了，把映射的mapValue，put进去
                map.put(key, mapValue);
            } else {
                // size++ 
                size += safeSizeOf(key, createdValue);
            }
        }
        if (mapValue != null) {
            // 又释放掉了
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            // 刷新map,移除超size的数据
            trimToSize(maxSize);
            return createdValue;
        }
    }
  • 3、remove 移除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 --
                size -= safeSizeOf(key, previous);
            }
        }
        if (previous != null) {
            entryRemoved(false, key, previous, null);
        }
        return previous;
    }

总结

  • 1.LRUCache 利用LinkedHashMap对数据进行访问排序
  • 2.对size进行计数，在trimToSize()中从队列首部依次删除超过size的数据
  • 3.获取数据时，将该数据置于队列末尾并返回。
FEATURED TAGS
arithmetic
pv UV: