Java实现LFU缓存案例

本文目录导读：

1. LFU缓存实现
2. 使用示例
3. 实现要点

我来提供一个完整的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");
        }
    }
}

实现要点

1. 时间复杂度：get和put操作均为O(1)
2. 数据结构：
   • HashMap存储键值对
   • HashMap+LinkedHashSet维护频率到节点的映射
3. 淘汰策略：当缓存满时，淘汰频率最低且最久未使用的元素
4. 频率更新：每次访问（get/put）都会增加元素的访问频率
5. 线程安全：如果需要线程安全，可以在方法上添加synchronized或使用ConcurrentHashMap

这个实现可以处理各种复杂场景,是生产级别的LFU缓存实现。