实现线程安全的泛型LRU缓存系统

题目

实现线程安全的泛型LRU缓存系统

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

并发编程,内存管理,泛型应用,LRU算法,Swift高级特性

快速回答

实现线程安全的LRU缓存需要：

• 使用DispatchQueue屏障保证线程安全
• 双向链表实现O(1)访问和删除
• 字典存储键值映射
• 泛型支持任意键值类型
• 注意内存管理和循环引用

核心原理

LRU（Least Recently Used）缓存淘汰策略需要：

• 双向链表：维护访问顺序（头节点最新，尾节点最旧）
• 哈希表：实现O(1)时间复杂度访问
• 线程安全：使用DispatchQueue屏障确保读写安全
• 内存管理：弱引用避免循环引用，deinit清理资源

代码实现

final class LRUCache<Key: Hashable, Value> {

    private class Node {
        var key: Key?
        var value: Value?
        weak var prev: Node?
        var next: Node?

        init(key: Key? = nil, value: Value? = nil) {
            self.key = key
            self.value = value
        }
    }

    private let capacity: Int
    private var head = Node()
    private var tail = Node()
    private var cache: [Key: Node] = [:]
    private let queue: DispatchQueue

    init(capacity: Int, label: String = "com.lru.cache") {
        self.capacity = max(1, capacity)
        self.queue = DispatchQueue(label: label, attributes: .concurrent)
        head.next = tail
        tail.prev = head
    }

    func setValue(_ value: Value, forKey key: Key) {
        queue.async(flags: .barrier) { [weak self] in
            guard let self = self else { return }

            if let node = cache[key] {
                node.value = value
                moveToHead(node)
                return
            }

            let newNode = Node(key: key, value: value)
            cache[key] = newNode
            addNode(newNode)

            if cache.count > capacity, let last = popTail() {
                cache.removeValue(forKey: last.key!)
            }
        }
    }

    func getValue(forKey key: Key) -> Value? {
        queue.sync {
            guard let node = cache[key] else { return nil }
            moveToHead(node)
            return node.value
        }
    }

    private func addNode(_ node: Node) {
        node.prev = head
        node.next = head.next
        head.next?.prev = node
        head.next = node
    }

    private func removeNode(_ node: Node) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    private func moveToHead(_ node: Node) {
        removeNode(node)
        addNode(node)
    }

    private func popTail() -> Node? {
        guard let last = tail.prev, last !== head else { return nil }
        removeNode(last)
        return last
    }

    deinit {
        queue.async(flags: .barrier) {
            self.cache.removeAll()
            var current = self.head.next
            while current != nil && current !== self.tail {
                let next = current?.next
                current?.prev = nil
                current?.next = nil
                current = next
            }
            self.head.next = self.tail
            self.tail.prev = self.head
        }
    }
}

最佳实践

• 线程安全策略：使用.barrier确保写操作独占，读操作并发执行
• 内存优化：节点使用弱引用避免循环引用，deinit主动清理资源
• 性能保障：链表操作保持O(1)时间复杂度，字典保证快速查询
• 泛型设计：支持任意Hashable键类型和任意值类型

常见错误

• 线程竞争：未使用屏障导致写操作冲突
• 循环引用：节点强引用形成闭环（需使用weak）
• 边界处理：链表操作遗漏prev/next指针更新
• 容量处理：插入新节点时未检查容量导致内存溢出

扩展知识

• 淘汰策略对比：LFU（最不常用） vs FIFO（先进先出） vs MRU（最近最常用）
• 性能优化：使用os_unfair_lock替代GCD在特定场景提升性能
• 持久化扩展：结合Codable实现缓存磁盘存储
• Swift特性应用：使用@discardableResult标记非必要返回值方法