算法练习: 设计题

[ShannonChenCHN]

LeetCode 设计类型的题库：https://leetcode-cn.com/tag/design/

题目列表

• 146. LRU 缓存机制⭐️
• 分别用数组和链表实现一个队列
• 实现一个循环队列
• 460. LFU 缓存

总结

• 重点掌握 LRU 缓存设计

[ShannonChenCHN]

146. LRU 缓存机制

2021.05.07 09:15 pm ~ 11: 15 pm

参考题解：

• https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
• https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
• raywenderlich/swift-algorithm-club/LRU Cache

期望效果：

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1);   // 缓存更新成 {1: 1}
lRUCache.put(2, 2);  // 缓存更新成 {2: 2, 1: 1}
lRUCache.get(1);       // 返回 1，缓存更新成 {1: 1, 2: 2}
lRUCache.put(3, 3);  // 超出限制，关键字 2 作废，缓存更新成 {3: 3, 1: 1}
lRUCache.get(2);      // 返回 -1 (未找到)
lRUCache.put(4, 4); // 超出限制，关键字 1 作废，缓存更新成 {4: 4, 3: 3}
lRUCache.get(1);      // 返回 -1 (未找到)
lRUCache.get(3);     // 返回 3
lRUCache.get(4);     // 返回 4

题目最重要的两点要求：

• put 和 get 方法的时间复杂度为 O(1)
• 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间

综上，我们可以总结出 cache 用到的数据结构需要满足的条件：增删改查快，有顺存储。

（1）什么数据结构同时符合上述条件呢？
哈希表查找快，但是数据存储是无序的；链表是有序的，而且插入删除快，但是查找慢。所以我们可以将两者结合起来：哈希表+链表。

（2）为什么要是双向链表，单链表行不行？
删除节点时需要获取到前一个节点，而题目要求删除的时间复杂度是 O(1)，所以必须是双向链表。

（3）哈希表和双向链表中需要存储的内容是什么？
哈希表中存储的 value 应该是双向链表的节点，而不是外面输入的 value，因为我们需要在读取哈希表中的缓存的同时，还要能够快速访问链表中对应的节点。

双向链表中需要存储的内容有以下四个：

• key：用于关联哈希表中的数据
• value：用于保存输入的数值
• dummyHead：头结点的哨兵
• dummyTail：尾结点的哨兵，用来保证 removeLast() 的时间复杂度为 O(1)

伪代码：

class LRUCache {
    
    init(_ capacity: Int) {

    }

    /// 时间复杂度：O(1)
    func get(_ key: Int) -> Int {
        从 Hash Map 中读取缓存
        if 缓存不存在 {
            return -1
        }

        将 Linked List 中的节点前置到 head

        将缓存结果返回
    }
    
    /// 时间复杂度：O(1)
    func put(_ key: Int, _ value: Int) {
        创建新的链表节点

        if Hash Map 中已经存在该缓存 {
            更新 Hash Map 中的缓存
            删除 Linked List 中的旧缓存
            在 Linked List 中插入新的缓存
        } else {
            if 超出容量 {
                删除 Linked List 中的尾端的缓存
                删除 Hash Map 中对应的缓存
            }

            在 Hash Map 中添加新缓存
            在 Linked List 中插入新的缓存
        }
    }
}

代码实现：

class LRUCache {
    var capacity: Int
    var hashMap: [Int: ListNode] = [:]
    var list: LinkedList = LinkedList()

    init(_ capacity: Int) {
        self.capacity = capacity
    }
    
    /// 时间复杂度：O(1)
    func get(_ key: Int) -> Int {
        if let node = hashMap[key] {
            list.moveToHead(node)
            return node.value
        }
        return -1
    }
    
    /// 时间复杂度：O(1)
    func put(_ key: Int, _ value: Int) {
        if let node = hashMap[key] {
            node.value = value
            list.moveToHead(node)
        } else {
            if list.count == capacity {
                if let tail = list.removeLast() {
                    hashMap[tail.key] = nil
                }
            }
            let node = ListNode(key, value)
            hashMap[key] = node
            list.insert(node)
        }
    }


}

class LinkedList {
    var count: Int = 0
    var dummyHead: ListNode = ListNode(0, 0)
    var dummyTail: ListNode = ListNode(0, 0) // 为了保证 removeLast 的时间复杂度为 O(1)

    init() {
        dummyHead.next = dummyTail
        dummyTail.prev = dummyHead
    }

    /// 时间复杂度: O(1)
    func insert(_ node: ListNode) {
        let prev = dummyHead
        let next = dummyHead.next!
        prev.next = node
        node.prev = prev
        node.next = next
        next.prev = node

        count += 1
    }

    /// 时间复杂度: O(1)
    func remove(_ node: ListNode) {
        let prev = node.prev!
        let next = node.next!
        prev.next = node.next
        next.prev = prev

        count -= 1
    }

    /// 时间复杂度: O(1)
    func moveToHead(_ node: ListNode) {
        remove(node)
        insert(node)
    }

    /// 时间复杂度: O(1)
    func removeLast() -> ListNode? {
        let tail = dummyTail.prev!
        if tail === dummyHead { // 没有节点了
            return nil
        }
        remove(tail)
        return tail
    }
}

class ListNode {
    var key: Int
    var value: Int
    var next: ListNode?
    var prev: ListNode?

    init(_ key: Int, _ value: Int) {
        self.key = key
        self.value = value
        self.next = nil
        self.prev = nil
    }
}

进阶：如果考虑到线程安全问题，该怎么设计呢？

延伸阅读

• YYCache 设计思路| Garan no dou - ibireme
• YYCache 源码解析
• 深入理解 YYCache
• YYCache 设计分析
• 源码浅析-iOS缓存NSCache
• apple/swift-corelibs-foundation 开源代码中的 NSCache.swift
• GNUStep 开源代码中的 NSCache.m
• GNUStep 开源代码中的 NSCache.h