基于Java 实现的LFU算法，特别适合新手，带有测试case

package com.springboot.learn.redis; import java.util.HashMap; import java.util.LinkedHashSet; import java.util.Map; public class LFUCache { private Map<Integer, Integer> keyToValue; // 存储键值对的哈希表 private Map<Integer, Integer> keyToFreq; // 存储键的访问频率的哈希表 private Map<Integer, LinkedHashSet<Integer>> freqToKeys; // 存储相同访问频率的键的集合的哈希表 private int capacity; // 缓存容量 private int minFreq; // 最小访问频率 public LFUCache(int capacity) { this.keyToValue = new HashMap<>(); this.keyToFreq = new HashMap<>(); this.freqToKeys = new HashMap<>(); this.capacity = capacity; this.minFreq = 0; } public int get(int key) { if (!keyToValue.containsKey(key)) { return -1; // 如果键不存在，则返回 -1 } int value = keyToValue.get(key); int freq = keyToFreq.get(key); updateFreq(key, freq); // 更新键的访问频率 return value; } public void put(int key, int value) { if (capacity <= 0) { return; // 如果缓存容量为 0，则直接返回 } if (keyToValue.containsKey(key)) { keyToValue.put(key, value); // 如果键已存在，则更新值 int freq = keyToFreq.get(key); updateFreq(key, freq); // 更新键的访问频率 } else { if (keyToValue.size() >= capacity) { evict(); // 如果缓存已满，则淘汰一个键 } keyToValue.put(key, value); // 添加新的键值对 keyToFreq.put(key, 1); // 设置键的初始访问频率为 1 freqToKeys.putIfAbsent(1, new LinkedHashSet<>()); // 初始化访问频率为 1 的键集合 freqToKeys.get(1).add(key); // 将键添加到访问频率为 1 的键集合中 minFreq = 1; // 更新最小访问频率为 1 } } private void updateFreq(int key, int freq) { freqToKeys.get(freq).remove(key); // 从原访问频率的键集合中移除键 if (freqToKeys.get(freq).isEmpty() && freq == minFreq) { minFreq++; // 如果原访问频率的键集合为空且等于最小访问频率，则更新最小访问频率 } freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>()); // 初始化新访问频率的键集合 freqToKeys.get(freq + 1).add(key); // 将键添加到新访问频率的键集合中 keyToFreq.put(key, freq + 1); // 更新键的访问频率 } private void evict() { LinkedHashSet<Integer> keys = freqToKeys.get(minFreq); // 获取最小访问频率的键集合 int evictKey = keys.iterator().next(); // 获取集合中的第一个键进行淘汰 keys.remove(evictKey); // 从键集合中移除被淘汰的键 keyToValue.remove(evictKey); // 从键值对哈希表中移除被淘汰的键值对 keyToFreq.remove(evictKey); // 从访问频率哈希表中移除被淘汰的键 } }