Lrucache源码解析

简介

• LruCache是一个范型类，内部使用了一个LinkedHashMap来储存传入的对象。主要提供put和get方法来添加和获取。当添加元素后缓存移出后时，LruCache会移出较早使用的缓存对象。
• 另外LruCache是一个线程安全的类，内部使用了比较多的锁来维护元素的安全访问。
• 与HashMap有区别的是，key与value都不支持为null。

主要构成

public class LruCache<K, V> {
    // 真正储存元素的地方
    private final LinkedHashMap<K, V> map;

    // 当前的大小以及最大支持的大小
    private int size;
    private int maxSize;

    // 一些添加命中等的计数
    private int putCount;
    private int createCount;
    private int evictionCount;
    private int hitCount;
    private int missCount;

    // 设置缓存容量
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        // map使用最近访问模式
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

    // 容量变更
    public void resize(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }

        synchronized (this) {
            this.maxSize = maxSize;
        }
        trimToSize(maxSize);
    }

    public void trimToSize(int maxSize) {
        // 依次移除元素，直到当前size不超过容量大小
        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);
        }
    }

}

构造方法可以设置可以储存的容量，容量也支持后期的变更。

get

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

protected V create(K key) {
    return null;
}

get方法首先会去调用map的get方法，如果没找到支持重载create方法来创建新的对象。

put

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

put方法也是默认使用map的put方法，然后根据是否命中同一个元素来得到此次put操作对当前size的影响。最后再使用trimToSize来确保不超出容量限制。

remove

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

这里较put会少一些，只有元素的移除后缩减空间的操作。

预留方法

// 计算元素所占空间的方法
private int safeSizeOf(K key, V value) {
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}

// 默认都为1，可以重载根据具体大小来实现。例如bitmap
protected int sizeOf(K key, V value) {
    return 1;
}

// 元素移除时的回调，可以重载来缓存到别处
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

总结

• LruCache内部使用LinkedHashMap来达到维护缓存的元素，此类key与value皆不可以为null，并且是线程安全的类。
• 可以重载sizeof方法来给不同元素设置不同大小。
• put操作后若超出了容量上限。则会依次移除map中最早使用过的对象，保证缓存的不溢出。
• 可以重载entryRemoved方法获取元素移除时的回调。

leetcode题目

146. LRU 缓存