一、双哈希表

1.思路总结

定义缓存节点Node：

以双向链表的方式来记录缓存；
每个缓存节点里存放三个信息：key、val、freq(使用频率)；

定义两个哈希表：

键值哈希表keyMap：以键值key为key，以缓存节点Node为val；
频率哈希表freqMap：以频率freq为key，以双向链表(存放所有频率是freq的节点)为val；

定义最少使用频率minFreq：用于容量已满时，可以快速定位需要删除元素的双向链表，进而删除节点；

总结Get操作：

检查capacity为0时，直接返回-1；
在keyMap查找key的节点；
- 不存在：直接返回-1；
- 已存在：1.双向链表中删除节点、2.删除空链表、3.更新minFreq、4.创建新节点(频率加1)、5.重新插入两个哈希表；

总结Put操作：

检查capacity为0时，直接返回；
在keyMap查找key的节点；
- 不存在：1.判断已满，若已满先删除旧节点、2.创建新节点(频率为1)、3.插入两个哈希表、4.更新最低访问频率minFreq为1；
- 已存在：1.更新目标节点的val，然后接下来的参考Get流程；

2.复杂度分析

时间复杂度：get和put时间复杂度都是O(1)，因为都是使用哈希表来操作；

空间复杂度：O(capacity)，capacity是LFU的缓存容量；

3.代码示例

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    func LFU ( _ operators: [[Int]],  _ k: Int) -> [Int] {
        let cache = LFUCache(k) 
        var res:[Int] = []
        for op in operators {
            if op.count == 3 {
                cache.put(op[1], op[2])
            }else {
                let val = cache.get(op[1])
                res.append(val)
            }
        }
        return res        
    }
}


class LFUCache {
    var capacity: Int = 0 // 缓存容量
    var minFreq: Int = 0 // 最小使用频率
    var keyMap: [Int: Node] = [:]
    var freqMap: [Int: LinkedList] = [:]

    init(_ capacity: Int) {
        self.capacity = capacity
    }

    func get(_ key: Int) -> Int {
        guard capacity != 0 else { return -1 }
        // 缓存不存在，直接返回-1
        guard let node = keyMap[key] else { return -1 }
        // 缓存已存在，更新其访问频率
        update(key: key, node: node)
        // 返回访问到的节点值
        return node.val
    }

    func put(_ key: Int, _ value: Int) {
        guard capacity != 0 else { return }
        // 缓存已存在，更新其访问频率和val，与Get操作类似
        if let node = keyMap[key] {
            node.val = value
            update(key: key, node: node)
            return
        }
        // 缓存不存在，需要增加节点
        // 1.缓存已满时，首先通过minFreq删除最不常使用节点oldNode
        if keyMap.count == capacity {
            let oldNode = freqMap[minFreq]?.removeLast()
            keyMap.removeValue(forKey: oldNode!.key)
            if freqMap[minFreq]?.count == 0 {
                freqMap.removeValue(forKey: minFreq)
            }
        }

        // 2.创建新节点(频率加1)，并插入两个哈希表中
        let newNode = Node(key: key, val: value, freq: 1)
        let list = freqMap[1] ?? LinkedList()
        list.addFirst(newNode)
        freqMap[1] = list
        keyMap[key] = newNode

        // 3.新节点的访问频率为1，所以更新最低访问频率
        minFreq = 1
    }

    func update(key: Int, node: Node) {
        // 1. 频率哈希表->双向链表->删除节点
        let freq = node.freq
        freqMap[freq]?.remove(node)
        // 2. 删除目标节点后，双向链表若为空，则删除链表(为空无存在意义)
        if freqMap[freq]?.count == 0 {
            freqMap.removeValue(forKey: freq)
            // 目标节点是唯一元素且访问频率最小，则minFreq加1
            if minFreq == freq {
                minFreq += 1
            }
        }

        // 3.创建新节点(频率加1)
        let newNode = Node(key: key, val: node.val, freq: freq + 1)
        // 4. 重新插入两个哈希表中
        let list = freqMap[freq + 1] ?? LinkedList()
        list.addFirst(newNode)
        freqMap[freq + 1] = list
        keyMap[key] = newNode
    }
}

class Node {
    var key: Int = 0
    var val: Int = 0
    var freq: Int = 0
    var prev: Node?
    var next: Node?

    init() {}
    init(key: Int, val: Int, freq: Int) {
        self.key = key
        self.val = val
        self.freq = freq
    }
}

class LinkedList {
    var count: Int = 0
    private var head: Node?
    private var tail: Node?

    init() {
        head = Node()
        tail = Node()
        head?.next = tail
        tail?.prev = head
        count = 0
    }

    // 插入链表头部节点
    public func addFirst(_ node: Node) {
        node.prev = head
        node.next = head?.next
        head?.next?.prev = node
        head?.next = node
        count += 1
    }

    // 删除链表中的节点（node一定存在）
    public func remove(_ node: Node) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
        count -= 1
    }

    // 删除链表最后一个节点，并返回该节点
    @discardableResult
    public func removeLast() -> Node? {
        if tail?.prev === head {
            return nil
        }
        let last = tail?.prev
        remove(last!)
        return last
    }
}

题解 | #设计LFU缓存结构#

一、双哈希表

1.思路总结

2.复杂度分析

3.代码示例