LRU Cache — 什么是LRU缓存、淘汰算法及其工作原理

什么是LRU Cache？

LRU Cache（Least Recently Used Cache）——一种固定大小的数据结构，存储有限数量的元素，并自动删除那些最不常访问的元素。当应用程序请求一个元素时，它会被移动到缓存的「新鲜」部分，而长时间未使用的元素会向后移动，达到限制时被删除。

「Least Recently Used」这个名称描述了淘汰策略：在所有存储的元素中，删除最长时间未使用的元素。这基于引用局部性（locality of reference）的假设——最近请求的数据很可能会再次需要。因此，LRU被认为是大多数应用程序最高效的缓存策略之一。

经典的LRU Cache实现需要两种数据结构：哈希表用于通过键以O(1)访问任意元素，双向链表用于跟踪使用顺序。哈希表存储指向链表节点的引用，链表则维护从最新元素（头部）到最旧元素（尾部）的顺序。

LRU Cache的基本操作

get(key)操作检查哈希表中是否存在键。如果找到元素，它将被移动到链表头部（成为最新元素）并返回其值。如果未找到——返回null或抛出异常。put(key, value)操作插入新元素：如果键已存在——更新值并将元素移动到头部。如果缓存已满，在插入前会删除链表的尾部元素。所有操作在常数时间O(1)内完成。

LRU Cache如何工作

LRU Cache算法基于两个原则：按时间顺序的访问计数器和溢出时的淘汰机制。每个元素存储在双向链表的节点中，指向这些节点的指针位于哈希表中。每次访问元素时，它会从当前位置断开并插入到链表头部。

当缓存大小达到最大值（maxSize）并且收到插入新元素的请求时，算法会删除双向链表的尾部元素——这是最长时间未使用的元素。删除后为新元素腾出空间，该元素被插入到链表头部。哈希表同时更新：旧键被删除，新键被添加。

LRU的一个特点是对循环重复的访问模式不敏感。如果应用程序定期访问比缓存大小更大的数据集，LRU可能会遭受thrashing——频繁的元素替换，每个新请求淘汰前一个。在这种情况下，LFU（Least Frequently Used）或自适应算法可能更有效。

缓存大小和指标

LRU Cache大小的选择是内存消耗与命中率（hit-ratio，成功访问的百分比）之间的权衡。移动应用的典型值：图片缓存占可用内存的10–20%，网络响应缓存占50–200条记录。命中率80–95%被认为是一个良好指标，此时缓存的内存成本是合理的。监控使用hitCount和missCount计数器，这些在Android的LruCache实现中可用。

LRU Cache的实现：HashMap + Doubly Linked List

标准的LRU Cache实现使用哈希表和双向链表的组合。哈希表提供通过键以O(1)访问任意节点的能力，双向链表则提供以O(1)将节点移动到头部和从尾部删除的能力。链表必须是双向的：这允许从链表中间断开节点而无需遍历所有元素。

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

在实现中，每个节点（Node）存储值和指向前后节点的引用。哨兵节点head和tail简化了边界情况——插入和删除时不需要检查null。get方法将找到的节点移动到头部，put在溢出时删除尾部元素。单独的removeKeyByValue方法通过节点引用在哈希表中找到键并删除它。

Android中内置的LruCache实现

Android SDK在android.util包中提供了现成的LruCache类，它使用LinkedHashMap以access-order模式实现LRU算法。该类是线程安全的，支持hit/miss计数，并提供entryRemoved回调以在元素被淘汰时释放资源。缓存大小以任意单位（字节、元素数量）设置——只需重写sizeOf方法即可。

LRU Cache vs FIFO和LIFO

所有三种算法——LRU、FIFO和LIFO——解决同一个问题：通过溢出时淘汰元素来限制内存消耗。然而，它们使用根本不同的标准来选择淘汰对象，这决定了它们在不同场景下的效率。

FIFO根据添加时间淘汰最旧的元素，无论其访问频率如何。如果旧元素仍然相关，这可能会低效。LRU通过考虑访问模式避免了这一缺点。LIFO淘汰最新添加的元素——对撤销场景有用，但不适合缓存，因为新数据往往比旧数据更需要。LRU被认为是大多数应用中实现复杂度和命中率之间的最佳平衡。

LRU Cache代码示例

让我们看看如何使用Android SDK中的内置LruCache类来缓存加载的图片。示例展示了在应用程序可用内存的1/8处初始化缓存，这是Google对图片缓存的标准建议。

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

sizeOf方法以与cacheSize相同的单位返回元素的大小。这里使用Bitmap的大小（以千字节为单位，rowBytes × height / 1024）。当所有元素的sizeOf总和超过cacheSize时，LruCache自动淘汰最近最少使用的Bitmap。entryRemoved回调可用于调用bitmap.recycle()——在淘汰前释放内存。

Swift中的LRU Cache实现

iOS没有内置的LRU Cache类，但可以通过NSCache（使用类似但未记录的淘汰策略）或基于Dictionary + Doubly Linked List的自定义实现轻松实现，如下所示。

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

在此Swift实现中，Node是一个内部类，包含value、next和prev字段。moveToHead方法将节点从当前位置断开并插入到链表头部。溢出时，tail——最长时间未使用的元素——被删除。对于生产版本，建议通过NSLock或DispatchQueue队列添加线程安全。