LFU缓存机制

题目描述
LFU（Least Frequently Used）缓存机制是一种基于访问频率的缓存淘汰策略。当缓存容量达到上限时，LFU会淘汰访问频率最低的数据项；如果存在多个访问频率相同的数据项，则淘汰其中最久未被访问的数据项。本题要求设计并实现一个LFU缓存类，支持在O(1)时间复杂度内执行get(key)和put(key, value)操作。

核心概念解析

1. 访问频率（Freq）：每个键被访问（get或put）的次数
2. 容量限制（Capacity）：缓存最多能存储的键值对数量
3. 淘汰策略：当缓存满时，淘汰频率最低且访问时间最久的键

解题思路分析
要实现O(1)时间复杂度的操作，需要精心设计数据结构：

• 使用HashMap存储键值对（keyToValue）
• 使用HashMap存储键的访问频率（keyToFreq）
• 使用嵌套HashMap存储频率对应的键集合（freqToKeys），其中内层使用LinkedHashSet维护相同频率键的插入顺序

数据结构设计

class LFUCache {
    private int capacity;
    private int minFreq; // 当前最小频率
    private Map<Integer, Integer> keyToVal; // 键到值的映射
    private Map<Integer, Integer> keyToFreq; // 键到频率的映射
    private Map<Integer, LinkedHashSet<Integer>> freqToKeys; // 频率到键集合的映射
}

具体实现步骤

1. 初始化方法

public LFUCache(int capacity) {
    this.capacity = capacity;
    this.minFreq = 0;
    keyToVal = new HashMap<>();
    keyToFreq = new HashMap<>();
    freqToKeys = new HashMap<>();
}

2. get操作实现
当查询键key时：

• 如果key不存在，返回-1
• 如果key存在：
  a. 增加key的访问频率
  b. 调整频率映射关系
  c. 返回对应的值

public int get(int key) {
    if (!keyToVal.containsKey(key)) {
        return -1;
    }
    increaseFreq(key); // 增加访问频率
    return keyToVal.get(key);
}

3. put操作实现
当插入键值对时：

• 如果key已存在：更新值，并增加访问频率
• 如果key不存在：
  a. 如果缓存已满，先淘汰最小频率的键
  b. 插入新键值对，设置频率为1
  c. 更新minFreq为1（新插入的键频率最低）

public void put(int key, int value) {
    if (capacity == 0) return;
    
    if (keyToVal.containsKey(key)) {
        keyToVal.put(key, value);
        increaseFreq(key);
        return;
    }
    
    if (keyToVal.size() >= capacity) {
        removeMinFreqKey(); // 淘汰最小频率键
    }
    
    keyToVal.put(key, value);
    keyToFreq.put(key, 1);
    freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
    freqToKeys.get(1).add(key);
    minFreq = 1; // 新插入的键频率为1，肯定是最小频率
}

4. 增加频率的辅助方法

private void increaseFreq(int key) {
    int freq = keyToFreq.get(key);
    // 更新频率映射
    keyToFreq.put(key, freq + 1);
    
    // 从原频率集合中移除
    freqToKeys.get(freq).remove(key);
    // 如果原频率集合为空，清理并检查是否需要更新minFreq
    if (freqToKeys.get(freq).isEmpty()) {
        freqToKeys.remove(freq);
        if (freq == minFreq) {
            minFreq++;
        }
    }
    
    // 添加到新频率集合
    freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
    freqToKeys.get(freq + 1).add(key);
}

5. 淘汰最小频率键的辅助方法

private void removeMinFreqKey() {
    LinkedHashSet<Integer> keyList = freqToKeys.get(minFreq);
    int deletedKey = keyList.iterator().next(); // 获取最早插入的键
    
    // 从各个映射中移除
    keyList.remove(deletedKey);
    if (keyList.isEmpty()) {
        freqToKeys.remove(minFreq);
        // 注意：这里不需要更新minFreq，因为后面会插入新键
    }
    
    keyToVal.remove(deletedKey);
    keyToFreq.remove(deletedKey);
}

时间复杂度分析

• get操作：O(1) - 只有HashMap的查询和更新操作
• put操作：O(1) - 只有HashMap的插入、删除和更新操作
• 所有操作都达到了题目要求的O(1)时间复杂度

实际应用场景
LFU缓存常用于：

1. 数据库查询缓存
2. 网页缓存（CDN）
3. 操作系统页面置换
4. 热点数据缓存系统

总结
LFU缓存的设计关键在于维护频率到键集合的映射，并使用LinkedHashSet来维护相同频率键的插入顺序。通过三个HashMap的协同工作，实现了O(1)时间复杂度的get和put操作。这种设计思路体现了数据结构组合使用的威力，是面试中考察系统设计能力的经典题目。