简介

我们在做图片三级缓存时，内存缓存为了防止内存溢出，导致APP崩溃，使用LruCache<K, V>来管理内存数据，内部由最近最少使用算法实现，将内存控制在一定的大小内，超出最大值时会自动回收。

原理

初始化时指定最大内存大小，google原生OS的默认值是16M，但是各个厂家的OS会对这个值进行修改，有的128 有的256等等。可使用val maxMemory = Runtime.getRuntime().maxMemory()来动态获取手机的内存大小，一般控制在总内存的1/8。

初始化

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

new LruCache<String,Bitmap>((int) maxMemory/8)

添加数据

当有新数据添加时，往LinkedHashMap里面添加数据存储到链表尾端，如果之前存在则移除之前的数据，添加完成之后计算是否超过最大内存。

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

判断内存集合是否超过最大限制；如果超过，将链表头部的对象也就是近期最少用到的数据移除，直到内存大小满足最大初始值。

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

获取数据

获取数据时，有数据时，直接返回数据，没有数据就调用create返回自定义的或者null

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

    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }
    synchronized (this) {
        createCount++;
        mapValue = map.put(key, createdValue);
        if (mapValue != null) {
            map.put(key, mapValue);
        } else {
            size += safeSizeOf(key, createdValue);
        }
    }
    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        trimToSize(maxSize);
        return createdValue;
    }
}

初始化LinkedHashMap accessOrder传值为true，调用afterNodeAccess；

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

当accessOrder的值为true，且e不是尾节点，将e移到链表的尾端；

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<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 局部同步锁
在 get, put, trimToSize, remove 四个方法里的 entryRemoved 方法都不在同步块里，因为 entryRemoved 回调的参数都属于方法域参数，不会线程不安全。

总结

通过以上源码的分析，可以知道新增数据和获取缓存时，数据都会移动到链表尾端，而当前内存大于设置最大内存的大小时，会移除链表头端的数据，与hitCount++的数量毫无关系。

面试题：最近最少使用算法是使用次数多的还是最近的数据先被移除？