题解 | 设计LFU缓存结构

1、解题思路

为了实现LFU（Least Frequently Used）缓存，我们维护了两个主要的数据结构：

1. freq_mp：一个哈希表，映射频率到双向链表，链表中的每个节点包含频率、键和值。
2. mp：另一个哈希表，直接映射键到双向链表中的节点迭代器。

此外，我们还需要跟踪当前的最小频率（min_freq）和缓存的剩余容量（size）。

• set(key, value)：如果键存在，更新其值和频率；如果不存在且缓存未满，直接插入；如果缓存已满，移除使用频率最低且最早访问的键，然后插入新键。
• get(key)：如果键存在，返回其值并更新使用频率；否则返回-1。

2、代码实现

C++

#include <ios>
#include <unordered_map>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        size = k;
        for (const auto& op : operators) {
            if (op[0] == 1) {
                set(op[1], op[2]);
            } else {
                res.push_back(get(op[1]));
            }
        }
        return res;
    }

  private:
    // 频率到双向链表的映射, 每个链表节点存储 [频率, 键, 值]
    unordered_map<int, list<vector<int>>> freq_mp;
    // 键到链表节点的迭代器的映射
    unordered_map<int, list<vector<int>>::iterator> mp;
    // 当前最小使用频率
    int min_freq = 0;
    // 缓存剩余容量
    int size = 0;

    // 更新节点, 更新频率或值
    void update(list<vector<int>>::iterator iter, int key, int value) {
        int freq = (*iter)[0];
        // 从原频率链表中移除该节点
        freq_mp[freq].erase(iter);
        // 如果原链表为空, 删除该频率条目
        if (freq_mp[freq].empty()) {
            freq_mp.erase(freq);
            // 更新最小频率
            if (min_freq == freq) {
                min_freq++;
            }
        }
        // 将节点插入到频率 +1 的链表头部
        freq_mp[freq + 1].push_front({freq + 1, key, value});
        mp[key] = freq_mp[freq + 1].begin();
    }

    // 设置键值对
    void set(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            // 键存在, 更新其值和频率
            update(it->second, key, value);
        } else {
            // 键不存在
            if (size == 0) {
                // 缓存已满, 移除最少使用的键
                int old_key = freq_mp[min_freq].back()[1];
                freq_mp[min_freq].pop_back();
                if (freq_mp[min_freq].empty()) {
                    freq_mp.erase(min_freq);
                }
                mp.erase(old_key);
            } else {
                size--;
            }
            // 插入新建
            min_freq = 1;
            freq_mp[1].push_front({1, key, value});
            mp[key] = freq_mp[1].begin();
        }
    }

    // 获取键的值
    int get(int key) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            auto iter = it->second;
            int value = (*iter)[2];
            update(iter, key, value);
            return value;
        }
        return -1;
    }
};

Java

import java.util.*;


public class Solution {
    // 频率到双向链表的映射，每个节点包含[频率, 键, 值]
    private Map<Integer, LinkedList<int[]>> freqMap;
    // 键到链表节点的映射
    private Map<Integer, int[]> keyMap;
    // 当前最小频率
    private int minFreq;
    // 缓存容量
    private int capacity;

    public Solution() {
        freqMap = new HashMap<>();
        keyMap = new HashMap<>();
        minFreq = 0;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        capacity = k;
        List<Integer> res = new ArrayList<>();
        for (int[] op : operators) {
            if (op[0] == 1) {
                set(op[1], op[2]);
            } else {
                res.add(get(op[1]));
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    // 更新节点：更新频率或值
    private void update(int key, int value) {
        int[] node = keyMap.get(key);
        int freq = node[0];
        // 从原频率链表中移除该节点
        freqMap.get(freq).remove(node);
        if (freqMap.get(freq).isEmpty()) {
            freqMap.remove(freq);
            if (minFreq == freq) {
                minFreq++;
            }
        }
        // 将节点插入到频率+1的链表头部
        node = new int[] {freq + 1, key, value};
        freqMap.computeIfAbsent(freq + 1, k1 -> new LinkedList<>()).addFirst(node);
        keyMap.put(key, node);
    }

    // 设置键值对
    private void set(int key, int value) {
        if (keyMap.containsKey(key)) {
            update(key, value);
        } else {
            if (keyMap.size() >= capacity) {
                // 缓存已满，移除最少使用的键
                int[] oldNode = freqMap.get(minFreq).removeLast();
                keyMap.remove(oldNode[1]);
                if (freqMap.get(minFreq).isEmpty()) {
                    freqMap.remove(minFreq);
                }
            }
            // 插入新键
            minFreq = 1;
            int[] newNode = new int[] {1, key, value};
            freqMap.computeIfAbsent(1, k -> new LinkedList<>()).addFirst(newNode);
            keyMap.put(key, newNode);
        }
    }

    // 获取键的值
    private int get(int key) {
        if (keyMap.containsKey(key)) {
            int[] node = keyMap.get(key);
            update(key, node[2]);
            return node[2];
        }
        return -1;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
from collections import defaultdict, OrderedDict


class Solution:
    def __init__(self):
        self.freq_map = defaultdict(OrderedDict)
        self.key_map = {}
        self.min_freq = 0
        self.capacity = 0

    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        self.capacity = k
        res = []
        for op in operators:
            if op[0] == 1:
                self.set(op[1], op[2])
            else:
                res.append(self.get(op[1]))
        return res

    def update(self, key, value):
        freq, val = self.key_map[key]
        # 从原频率链表中移除该节点
        del self.freq_map[freq][key]
        if not self.freq_map[freq]:
            del self.freq_map[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        # 将节点插入到频率+1的链表头部
        new_freq = freq + 1
        self.freq_map[new_freq][key] = (new_freq, value)
        self.key_map[key] = (new_freq, value)

    def set(self, key, value):
        if key in self.key_map:
            self.update(key, value)
        else:
            if len(self.key_map) >= self.capacity:
                # 缓存已满，移除最少使用的键
                old_key, _ = self.freq_map[self.min_freq].popitem(last=False)
                del self.key_map[old_key]
                if not self.freq_map[self.min_freq]:
                    del self.freq_map[self.min_freq]
            # 插入新键
            self.min_freq = 1
            self.freq_map[1][key] = (1, value)
            self.key_map[key] = (1, value)

    def get(self, key):
        if key in self.key_map:
            freq, value = self.key_map[key]
            self.update(key, value)
            return value
        return -1

3、复杂度分析

1. 数据结构： freq_mp/freqMap/freq_map：频率到双向链表的映射，每个链表的节点包含频率、键和值。mp/keyMap/key_map：键到链表节点的映射，用于快速查找键对应的节点。min_freq/minFreq：当前最小使用频率。size/capacity：缓存容量。
2. 主要方法： update：更新节点的频率或值，并将其移动到更高频率的链表头部。set：插入或更新键值对，处理缓存满的情况。get：查找键的值，并更新其使用频率。
3. 操作流程： set：键存在则更新频率和值；不存在则插入新键，缓存满时移除最少使用的键。get：键存在则返回值并更新频率；不存在则返回-1。

这种方法确保了get和set操作的时间复杂度均为O(1)，满足了题目要求。