计算机►Android

Android开源项目分析-LruCache

Index
  1. 1. 1.简介：
  2. 2. 2.源码查看：
  3. 3. 3.原理
  4. 4. 4.代码分析
  5. 5. 4.1 构造函数
  6. 6. 4.2 加入缓存对象put操作
  7. 7. 4.3 获取缓存对象get操作
  8. 8. 4.4 移除缓存对象remove操作
  9. 9. 4.5 缓存调整trimToSize
  10. 10. 5.总结
  11. 11. 6.相关文章：

摘要：本文对开源代码LruCache源码进行分析。

1.简介：

　　通过LruCache通过键值将存储数据缓存内存中，用户只需提供创建方式，无需关注释放问题，可以用来避免OOM，基于LRU算法实现。

2.源码查看：

　　http://androidxref.com/6.0.1_r10/xref/frameworks/base/core/java/android/util/LruCache.java

3.原理

　　Lru缓存实现原理是在队列中保存了一定数量的强引用对象。每当对象被访问，这个对象被移动到队列最前面。当一个对象添加到队列已满的缓存时，缓存队列中最后的对象被移除，这个对象适当的时候会被垃圾回收器回收。

4.代码分析

4.1 构造函数

1
2
3
4
5
6
7
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);
}

其中maxSize与map的定义如下：

1
2
private final LinkedHashMap<K, V> map;
private int maxSize;

maxSize有两种状态表示：
　　1、当类中的LruCache::sizeOf没被重载时，它表示队列中对象的数目；
　　2、如果LruCache::sizeof被重载了，那么它表示的是队列中所有对象的字节大小总和。

map为LinkedHashMap是一个有序的HashMap，这里将它理解为能通过键值查询的队列，它用来存储需要缓存的对象。
LinkedHashMap实现代码参见http://androidxref.com/6.0.1_r10/xref/libcore/luni/src/main/java/java/util/LinkedHashMap.java。

4.2 加入缓存对象put操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
        // 相同key，需要去除之前的size大小
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }
    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }
    trimToSize(maxSize);
    return previous;
}

1、首先进行空指针判断，如果key和value有空指针则抛出异常；
2、计算当前所有对象大小size，并同时将对象记录到map中；
3、如果具备相同key，previous将不为空，则调用entryRemoved来判断是否要显式释放内存；
4、通过trimToSize将最先插入到map的移除，保证当前map大小小于maxSize。

4.3 获取缓存对象get操作

1
2
3
4
public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

空指针判断

1
2
3
4
5
6
7
8
9
V mapValue;
synchronized (this) {
    mapValue = map.get(key);
    if (mapValue != null) {
        hitCount++;
        return mapValue;
    }
    missCount++;
}

通过map获取缓存对象，存在的话返回对象，并增加命中数hitCount，否则未命中数missCount。

1
2
3
4
V createdValue = create(key);
if (createdValue == null) {
    return null;
}

通过create函数来创建需要缓存的对象，LruCache::create返回null，所以需要子类重载来返回需要缓存的对象。

1
2
3
4
5
6
7
8
9
10
11
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);
    }
}

增加创建次数createCount，并且将创建的对象放入到map中。
如果map添加对象时返回对象，说明存在冲突（可能多线程原因在其它线程中刚好创建），那重新将之前的缓存对象保存到map中；否则重新计算缓存大小size。
这一步也保证了线程安全(thread-safe)。

1
2
3
4
5
6
7
8
    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        trimToSize(maxSize);
        return createdValue;
    }
}

如果mapValue不为空，也就说明创建时存在冲突，需要通知新创建的值createdValue需要销毁，并且返回旧的缓存对象mapValue；
否则调用trimToSize重新调整map，并且返回新的创建的缓存对象。

4.4 移除缓存对象remove操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

移除缓存只需要通过移除map中的对象，重新调整缓存大小，同时通过entryRemoved来给LruCache的子类对象来决定是否主动回收缓存对象。

4.5 缓存调整trimToSize

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
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) {
                break;
            }
            Map.Entry<K, V> toEvict = map.eldest();
            if (toEvict == null) {
                break;
            }
            key = toEvict.getKey();
            value = toEvict.getValue();
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
        }
        entryRemoved(true, key, value, null);
    }
}

缓存调整函数trimToSize为LruCache缓存策略核心实现。
当map缓存大小size大于maxSize时，使用LRU算法将最久未被使用的对象从map中移除。
LRU算法实现使用是LinkedHashMap.eldest()，这里无需考虑算法的具体实现，便可以很快的找到需要移除的对象，这也是LruCache为什么使用LinkedHashMap的原因。

5.总结

通过LruCache了解到如何对类进行线程安全处理以及LinkedHashMap使用，同时LruCache将create创建以及entryRemoved释放强引用对象操作留给子类，有点IoC的味道。

6.相关文章：

　　http://m.blog.chinaunix.net/uid-26930580-id-4138306.html
　　http://m.blog.csdn.net/article/details?id=9316683
　　http://blog.csdn.net/linghu_java/article/details/8574102