LruCache

保存对有限数量值的强引证的缓存。 每次拜访一个值时，它都会移动到行列的头部。 当一个值被添加到一个完整的缓存中时，该行列末尾的值将被逐出并且可能有资格进行废物收回。

Least Recently Used , 最近最少运用，是一种常用的算法。

LRUCache 是具有必定数量约束的数据结构，该数据结构选用 LRU 算法，保护必定数量的缓存数据。假如数据结构现已达到了最大数量约束时，有新的数据刺进，则就需求依据 LRU 算法，删去最久未运用的数据。

依据它的功用描述，对数据结构的挑选就有了偏向性：

• 界说中提到了行列，完成行列的两种底层数据结构是链表和数组。
• 依据每次删去最终一个元素的特性，能够优先考虑链表结构。
• 假如集合中已存在要添加的元素，优先将其移动到队头，优先考虑链表结构，由于数组的移动开支更大。
• 每次添加新元素都要查询一遍集合中是否存在该元素，链表结构比较数组的查询时刻复杂度更高，所以优先考虑数组和用来辅助查询时刻复杂度低的 Map 。

综合前两点考虑，LinkedList 合作 HashMap 是一个不错的挑选，前者不但能够是链表结构、还完成了 Deque ，也能够视为行列、栈结构， 后者供给了更低时刻复杂度的检索。

而在 JDK 中，供给了 LinkedHashMap 用来完成 LRU 缓存的功用。

LinkedHashMap

LinkedHashMap 承继自 HashMap ，并完成了 Map 接口。结构办法包含了一个 accessOrder 参数，该参数会将元素按照拜访次序进行排序，非常合适构建 LRUCache 。

LinkedHashMap 与 HashMap 不同之处在于保护了一个**双向链表，该列表串联起了一切元素。**这个链表界说了迭代次序，通常是键刺进映射的次序（刺进次序）。

请注意，假如将键从头刺进到 Map 中，则刺进次序不会受到影响。 （假如在调用 m.containsKey(k) 时调用 m.put(k, v) 将在调用之前立即回来 true，则将键 k 从头刺进到映射 m 中。）

内部的双向链表结构：

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;
    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

每次拜访元素后，假如启用拜访排序(accessOrder = true)，会更新链表中的元素次序：

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

中心的排序逻辑在 afterNodeAccess 办法中，将最新拜访的元素移动到了链表尾部：

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 双向链表尾部节点 last
    if (accessOrder && (last = tail) != e) {
        // 拜访的节点标记为 p ，p 的前后节点保存到 b 、a 中
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 拜访节点的后续节点设置为 null ，由于是最终一个节点，所以后续节点为 null
        p.after = null; 
        // 处理删去 e 节点的逻辑
        if (b == null)
             // p 的前面不存在节点，头节点设置为 a 
            head = a;
        else 
            // p 的前面存在节点，将 p 的后续节点设置为 p 前一个节点的下一个节点  b -> p -> a 更新为 b -> a （删去 p）
            b.after = a;
        if (a != null)
            // p 存在后续节点 a , 将 a 的 before 指针更新为 b
            a.before = b;
        else
            // p 不存在后续节点 a , last 指针更新为 b
            last = b;
        // 处理尾部节点的逻辑
        if (last == null)
            // last 指针为空，更新头节点
            head = p;
        else {
            // last 指针不为空，更新链表次序为 last 
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

所以这是一种非常合适 LRUCache 的数据结构，Android 中的 LRUCache 类便是经过 LinkedHashMap 来完成的。

public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;
		//...
}

Android 的 LruCache 源码剖析

LruCache 是 Android SDK 中供给一个类，来自于 android.util 。

LruCache 中有两个中心办法，get 和 put ，再加上容量改变处理办法，构成了完善的 LRU 机制。它的内部的数据结构是 LinkedHashMap ，经过属性操控容量：

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;
      	// 启用了 拜访排序 accessOrder = true
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 
    }
		//...
}

resize

当从头设置 LruCache 的容量时，能够经过 resize 分发从头设置容量：

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

在这个办法中，经过 map.eldest() 获取到了存活最久的元素，它的完成是：

		// in LinkedHashMap
		public Map.Entry<K, V> eldest() {
        return head;
    }

最终的 entryRemoved 办法的作用是，经过调用 remove 移除或经过调用 put 替换时，将一个值被移除以腾出空间，将调用此办法。 默许完成什么也不做。

get

get 办法依据 key 检索 LinkedHashMap 中是否存在对应的元素，或许是否能够依据 create 办法创立元素。假如存在或可依据 create 办法创立，则将这个元素移动到行列头部，否则回来 null。

    public final V get(K key) {
      	// key 空查看
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V mapValue;
        synchronized (this) {
            mapValue = map.get(key); // 从 map 中读取元素
            if (mapValue != null) { // 缓存中存在元素，直接回来
                hitCount++; 
                return mapValue; 
            }
            missCount++; 
        }
				// 缓存中不存在对应 key 的元素，创立一个新元素
        V createdValue = create(key); 
        if (createdValue == null) { // 未缓存且无法创立，回来 null
            return null;
        }
				// 创立成功，存入到 map ，假如 key 已存在对应值，优先更新为之前的值
        synchronized (this) {
            createCount++;	
            mapValue = map.put(key, createdValue); // 存入新的元素，并获取前一个 key 对应的值 mapValue。
            if (mapValue != null) {
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue); // 新元素导致当时容量 + 1
            }
        }
        if (mapValue != null) { // key 对应的元素已存在
          	// 当一个值被逐出以腾出空间、经过调用 remove 移除或经过调用 put 替换时，将调用此办法。 默许完成什么也不做。
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue; 
        } else { // key 对应的元素不存在
            trimToSize(maxSize); // 扩容
            return createdValue; //回来最新刺进的元素
        }
    }

这儿的 create 办法默许回来 null , 供子类完成:

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

最终的 entryRemoved 办法的作用是，经过调用 remove 移除或经过调用 put 替换时，将一个值被移除以腾出空间，将调用此办法。 默许完成什么也不做。

protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

办法中的两个参数的含义：

• evicted – 假如条目被删去以腾出空间，则为 true，假如删去是由 put 或 remove 引起的，则为 false。
• newValue – 键的新值（假如存在）。 假如非 null，则此移除是由 put 或 get 引起的。 否则，它是由驱赶或移除引起的。

get 办法中经过操作 LinkedHashMap ，调用 LinkedHashMap 的 get 和 put 办法，会在 LinkedHashMap 内部完成排序逻辑。

put

LRUCache 的 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); // 当时容量 + 1
            previous = map.put(key, value); // 取出从前的值
            if (previous != null) {
                size -= safeSizeOf(key, previous); // map 中已存在 key 的情况下，确保 size 不变
            }
        }
				// 从前存在元素，履行元素移除后的自界说操作
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
				// 容量处理
        trimToSize(maxSize);
        return previous;
    }

这儿也有一个问题，假如 map 中已存在 key ，仅是更新数据，这儿没有涉及到排序的问题。

为什么这么说呢？是由于 LinkedHashMap 并没有界说 put 办法，需求查看 HashMap 中的 put 办法：

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

HashMap 中的 put 办法中真正逻辑是 putVal 办法，在 putVal 办法中调用了拜访元素后的处理办法 afterNodeAccess 办法，而这个办法的

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
            // ...
						if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); // 【*】
                return oldValue;
            }
            // ...
		}

afterNodeAccess 办法在 HashMap 中是空完成，经过补白能够理解，这些办法专门为 LinkedHashMap 预留的：

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

而 afterNodeAccess 在 LinkedHashMap 中的完成，和 LinkedHashMap 的 get 办法中调用的排序办法是同一个。所以 put 办法也会对元素进行排序。

remove

与 put 办法相同，remove 办法也是来自于父类 HashMap：

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

removeNode 中进行移除操作，并调用了 afterNodeRemoval 办法：

    final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
          	// ...
            if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node); // 【*】
                return node;
            }
        }
        return null;
    }

afterNodeRemoval 办法的完成在 LinkedHashMap 中，操作双向链表删去当时元素：

    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

容量核算

在运用 LruCache 类时，能够自行界说最大缓存容量，并自行核算目标的缓存。例如，初始化一个最大容量为 4M ，用来保存 Bitmap 的 LruCache ：

int cacheSize = 4 * 1024 * 1024; // 4MiB   
LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {       
  	protected int sizeOf(String key, Bitmap value) {           
      	return value.getByteCount();       
    }   
}

最大容量为 cacheSize ，关于每一个新目标，经过 sizeOf 办法来核算这个目标的巨细。

总结

• android.util.LruCache 类是 Android SDK 中的一个 LRU 缓存完成，它的内部数据结构选用的是 LinkedHashMap 。
• LinkedHashMap 完成了 HashMap ，并且保护了一个双端链表来处理元素的排序。
• LinkedHashMap 经过结构办法中的参数 accessOrder = true ，来启用拜访次序记录逻辑。
• 中心的排序逻辑在 afterNodeAccess 办法中，当超过容量约束时，会删去链表中 head 节点。每次拜访数据，会将节点移动到队尾。
• 能够创立android.util.LruCache 时，经过 cacheSize 参数合作重写 sizeOf 办法完成自界说容量核算逻辑的 LruCache 。

常见算法题

最终再来聊一下字节面试频率比较高的一道算法题，完成一个 LruCache ，经过上面的了解咱们也知道最优解便是经过一个 哈希表 + 一个 双向链表 来完成。

class LruCache(private val capacity: Int) {
    data class DLinkedNode(
        var key: Int? = null,
        var value: Int? = null,
        var prev: DLinkedNode? = null,
        var next: DLinkedNode? = null
    )
    private val cache = HashMap<Int, DLinkedNode>()
    private var size = 0
    private var head = DLinkedNode()
    private var tail = DLinkedNode()
    fun get(key: Int): Int {
        val node = cache[key] ?: return -1
        // 假如 key 存在，先经过哈希表定位，再移到头部
        moveToHead(node)
        return node.value ?: -1
    }
    fun put(key: Int, value: Int) {
        val node = cache[key]
        if (node == null) {
            // 假如 key 不存在，创立一个新的节点
            val newNode = DLinkedNode(key, value)
            // 添加进哈希表
            cache[key] = newNode
            // 添加至双向链表的头部
            addToHead(newNode)
            ++size;
            if (size > capacity) {
                // 假如超出容量，删去双向链表的尾部节点
                val tail = removeTail()
                // 删去哈希表中对应的项
                cache.remove(tail?.key)
                --size;
            }
        }
        else {
            // 假如 key 存在，先经过哈希表定位，再修正 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }
    private fun addToHead(node: DLinkedNode?) {
        node?.prev = head
        node?.next = head.next
        head.next?.prev = node
        head.next = node
    }
    private fun removeNode(node: DLinkedNode?) {
        node?.prev?.next = node?.next
        node?.next?.prev = node?.prev
    }
    private fun moveToHead(node: DLinkedNode?) {
        removeNode(node)
        addToHead(node)
    }
    private fun removeTail(): DLinkedNode? {
        val res = tail.prev 
        removeNode(res)
        return res
    }
}

时刻复杂度：关于 put 和 get 都是 O(1) 。

空间复杂度：O(capacity)，由于哈希表和双向链表最多存储 capacity + 1 个元素。

另一种使用 LinkedHashMap 的解法就比较简单了：

class LruCacheByLinkedHashMap(val capacity: Int): LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
    override fun get(key: Int): Int {
        return getOrDefault(key, -1)
    }
    override fun put(key: Int, value: Int): Int? {
        return super.put(key, value)
    }
    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
        return size > capacity
    }
}

只需求承继 LinkedHashMap ，并设置好初始容量、启用拜访次序排序，然后完成 removeEldestEntry ，这个办法在 put 调用时，会查看删去最老的元素，回来值为判别条件的成果。