Swift - LRU 缓存
什么是 LRU 缓存？
LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略。当缓存满了，它会优先删除最久没被访问的数据，保留最近刚用过的。
举个生活例子：你有一个只能放3本书的书架。每次读书都会把书放在最顺手的位置。当要放第4本书时，就把最角落（最久没读）的那本拿走。
核心设计：为什么用“双向链表 + 哈希表”？
- 哈希表：让你能用
key快速找到对应的数据（O(1)）。 - 双向链表：帮你记住数据的访问顺序，方便把刚访问的节点移到头部，并快速删除尾部的节点（O(1)）。
两者结合，就能做到所有操作都在常数时间内完成。
链表结构（带虚拟头尾节点）
head <-> [最近使用] <-> ... <-> [最久未使用] <-> tail
head和tail是虚拟节点，不存数据，只为了方便操作，省去判断边界。
核心操作实现（Swift 示例）
1. 节点定义
private final class LRUNode<Key: Hashable, Value> {
var key: Key?
var value: Value?
var prev: LRUNode<Key, Value>?
var next: LRUNode<Key, Value>?
init() {}
}
2. 缓存类
/// LRU（Least Recently Used）缓存
/// 当缓存容量达到上限时，淘汰最久未被使用的元素
public final class LRUCache<Key: Hashable, Value>: @unchecked Sendable {
private let capacity: Int
private var dict: [Key: LRUNode<Key, Value>] = [:]
private let head: LRUNode<Key, Value>
private let tail: LRUNode<Key, Value>
private let lock = NSLock()
/// 初始化 LRU 缓存
/// - Parameter capacity: 缓存最大容量，必须大于 0
public init(capacity: Int) {
guard capacity > 0 else {
fatalError("LRU 缓存容量必须大于 0")
}
self.capacity = capacity
self.head = LRUNode<Key, Value>()
self.tail = LRUNode<Key, Value>()
head.next = tail
tail.prev = head
}
}
3. get(key) – 获取数据
/// 获取缓存值（存在则移到链表头部，标记为最近使用）
public func get(_ key: Key) -> Value? {
lock.lock()
defer { lock.unlock() }
guard let node = dict[key] else {
return nil
}
moveNodeToHead(node)
return node.value
}
4. put(key, value) – 放入数据
/// 添加/更新缓存（满了则淘汰最久未使用的节点）
public func put(_ key: Key, value: Value) {
lock.lock()
defer { lock.unlock() }
if let existingNode = dict[key] {
existingNode.value = value
moveNodeToHead(existingNode)
} else {
let newNode = LRUNode<Key, Value>()
newNode.key = key
newNode.value = value
dict[key] = newNode
addNodeToHead(newNode)
if dict.count > capacity {
if let removedNode = removeTailNode() {
if let removedKey = removedNode.key {
dict.removeValue(forKey: removedKey)
}
}
}
}
}
5. 链表操作（核心原语）
/// 移除指定缓存
public func remove(_ key: Key) {
lock.lock()
defer { lock.unlock() }
guard let node = dict[key] else { return }
removeNode(node)
dict.removeValue(forKey: key)
}
private func addNodeToHead(_ node: LRUNode<Key, Value>) {
let temp = head.next
head.next = node
node.prev = head
node.next = temp
temp?.prev = node
}
private func removeNode(_ node: LRUNode<Key, Value>) {
let prevNode = node.prev
let nextNode = node.next
prevNode?.next = nextNode
nextNode?.prev = prevNode
}
private func moveNodeToHead(_ node: LRUNode<Key, Value>) {
removeNode(node)
addNodeToHead(node)
}
private func removeTailNode() -> LRUNode<Key, Value>? {
guard let targetNode = tail.prev, targetNode !== head else {
return nil
}
removeNode(targetNode)
return targetNode
}
实际应用小贴士
- 容量设置：根据数据量合理设置，避免内存过大。
- 可监控：添加命中率、淘汰次数等统计，便于调试。
- 与系统缓存搭配：LRU 可作为
NSCache的补充，实现更精准的淘汰策略。
总结
LRU 缓存通过哈希表 + 双向链表，实现了 O(1) 的读写和淘汰操作，是工程中最常用的缓存算法之一。理解它的原理，能让你在需要自己实现缓存时更有底气，也能更明智地选择已有的缓存方案。
