本文目录导读：
我来提供一个完整的LFU（Least Frequently Used）缓存实现案例：
LFU缓存实现
import java.util.*;
/**
* LFU (Least Frequently Used) 缓存实现
* 支持get和put操作，时间复杂度O(1)
*/
public class LFUCache<K, V> {
// 缓存容量
private final int capacity;
// 存储key对应的节点
private Map<K, Node<K, V>> cache;
// 存储频率对应的双向链表
private Map<Integer, LinkedHashSet<Node<K, V>>> frequencyMap;
// 当前最小频率
private int minFrequency;
// 当前缓存大小
private int size;
/**
* 节点类
*/
private static class Node<K, V> {
K key;
V value;
int frequency = 1;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
/**
* 构造函数
*/
public LFUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.frequencyMap = new HashMap<>();
this.minFrequency = 0;
this.size = 0;
}
/**
* 获取缓存值
*/
public V get(K key) {
if (!cache.containsKey(key)) {
return null;
}
Node<K, V> node = cache.get(key);
// 更新频率
updateFrequency(node);
return node.value;
}
/**
* 放入缓存
*/
public void put(K key, V value) {
if (capacity <= 0) {
return;
}
// 如果key已存在，更新值并增加频率
if (cache.containsKey(key)) {
Node<K, V> node = cache.get(key);
node.value = value;
updateFrequency(node);
return;
}
// 如果缓存已满，需要淘汰
if (size >= capacity) {
evict();
}
// 创建新节点
Node<K, V> newNode = new Node<>(key, value);
cache.put(key, newNode);
addToFrequencyMap(newNode);
minFrequency = 1;
size++;
}
/**
* 更新节点频率
*/
private void updateFrequency(Node<K, V> node) {
// 从当前频率的链表中移除节点
LinkedHashSet<Node<K, V>> currentSet = frequencyMap.get(node.frequency);
currentSet.remove(node);
// 如果当前频率的链表为空，且是最小频率，更新最小频率
if (currentSet.isEmpty()) {
frequencyMap.remove(node.frequency);
if (minFrequency == node.frequency) {
minFrequency++;
}
}
// 增加频率并添加到新的频率链表
node.frequency++;
addToFrequencyMap(node);
}
/**
* 添加到频率映射
*/
private void addToFrequencyMap(Node<K, V> node) {
frequencyMap.computeIfAbsent(node.frequency,
k -> new LinkedHashSet<>()).add(node);
}
/**
* 淘汰最不经常使用的节点
*/
private void evict() {
// 获取最小频率的链表
LinkedHashSet<Node<K, V>> set = frequencyMap.get(minFrequency);
if (set != null && !set.isEmpty()) {
// 移除链表中的第一个元素（最久未使用）
Node<K, V> evictNode = set.iterator().next();
set.remove(evictNode);
// 从缓存中移除
cache.remove(evictNode.key);
size--;
// 如果链表为空，移除该频率的映射
if (set.isEmpty()) {
frequencyMap.remove(minFrequency);
}
}
}
/**
* 获取缓存大小
*/
public int size() {
return size;
}
/**
* 清空缓存
*/
public void clear() {
cache.clear();
frequencyMap.clear();
size = 0;
minFrequency = 0;
}
/**
* 是否包含key
*/
public boolean containsKey(K key) {
return cache.containsKey(key);
}
/**
* 获取所有键
*/
public Set<K> keySet() {
return cache.keySet();
}
/**
* 打印缓存内容
*/
public void printCache() {
System.out.println("========= LFU Cache =========");
for (Map.Entry<Integer, LinkedHashSet<Node<K, V>>> entry :
frequencyMap.entrySet()) {
System.out.print("频率 " + entry.getKey() + ": ");
for (Node<K, V> node : entry.getValue()) {
System.out.print("[" + node.key + "=" + node.value + "] ");
}
System.out.println();
}
System.out.println("============================");
}
// 测试代码
public static void main(String[] args) {
// 创建容量为3的LFU缓存
LFUCache<String, Integer> cache = new LFUCache<>(3);
System.out.println("=== 测试基本操作 ===");
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
cache.printCache();
// 访问A两次，增加A的频率
cache.get("A");
cache.get("A");
System.out.println("\n访问A两次后:");
cache.printCache();
// 访问B一次
cache.get("B");
System.out.println("\n访问B一次后:");
cache.printCache();
// 添加新元素D，应该淘汰频率最低的C
cache.put("D", 4);
System.out.println("\n添加D后(淘汰C):");
cache.printCache();
System.out.println("\n=== 测试键值更新 ===");
cache.put("A", 10);
System.out.println("更新A的值后:");
cache.printCache();
// 测试缓存淘汰策略
System.out.println("\n=== 测试复杂淘汰策略 ===");
LFUCache<Integer, String> testCache = new LFUCache<>(2);
testCache.put(1, "one");
testCache.put(2, "two");
System.out.println("初始状态:");
testCache.printCache();
// 访问1两次，增加1的频率
testCache.get(1);
testCache.get(1);
// 添加3，应该淘汰2（频率最低）
testCache.put(3, "three");
System.out.println("\n添加3后(应该淘汰2):");
testCache.printCache();
// 验证缓存内容
System.out.println("\n=== 验证结果 ===");
System.out.println("是否包含1: " + testCache.containsKey(1));
System.out.println("是否包含2: " + testCache.containsKey(2));
System.out.println("是否包含3: " + testCache.containsKey(3));
System.out.println("缓存大小: " + testCache.size());
// 测试清空操作
System.out.println("\n=== 测试清空操作 ===");
testCache.clear();
System.out.println("清空后大小: " + testCache.size());
System.out.println("是否包含1: " + testCache.containsKey(1));
}
}
使用示例
// 更实际的使用示例
public class LFUCacheExample {
public static void main(String[] args) {
// 创建一个缓存最近访问数据的LFU
LFUCache<String, String> userSessionCache =
new LFUCache<>(100); // 最多缓存100个用户会话
// 模拟用户访问
String userId = "user123";
String sessionData = "session_data_for_user";
// 存储用户会话
userSessionCache.put(userId, sessionData);
// 获取用户会话
String data = userSessionCache.get(userId);
if (data != null) {
System.out.println("Session found: " + data);
} else {
System.out.println("Session expired or not found");
}
}
}
实现要点
- 时间复杂度：get和put操作均为O(1)
- 数据结构：
HashMap存储键值对HashMap+LinkedHashSet维护频率到节点的映射
- 淘汰策略：当缓存满时，淘汰频率最低且最久未使用的元素
- 频率更新：每次访问（get/put）都会增加元素的访问频率
- 线程安全：如果需要线程安全，可以在方法上添加
synchronized或使用ConcurrentHashMap
这个实现可以处理各种复杂场景,是生产级别的LFU缓存实现。
