深入理解LFU缓存机制（Java语言实现LFU缓存的完整教程）

为什么选择LFU？

在某些场景下，比如热点数据长期被频繁访问，LFU能更好地保留这些高频数据，避免像LRU那样因短期未访问而被错误淘汰。因此，掌握Java缓存实现中的LFU策略，对构建高性能应用非常有价值。

LFU缓存设计思路

要高效实现LFU，我们需要解决两个关键问题：

1. 如何快速获取访问频率最低的键？
2. 如何在O(1)时间内更新某个键的访问频率？

解决方案是使用以下数据结构组合：

• HashMap<Integer, Node>：存储键到缓存节点的映射
• HashMap<Integer, DoublyLinkedList>：按频率分组，每个频率对应一个双向链表
• 维护一个minFreq变量，记录当前最小频率

Java实现LFU缓存

下面是一个完整的、支持get和put操作的LFU缓存实现：

import java.util.*;// 缓存节点类class Node {    int key;    int value;    int freq;        public Node(int key, int value) {        this.key = key;        this.value = value;        this.freq = 1;    }}// 双向链表类（用于同一频率下的节点管理）class DoublyLinkedList {    private Node head;    private Node tail;    private int size;        public DoublyLinkedList() {        head = new Node(-1, -1);        tail = new Node(-1, -1);        head.next = tail;        tail.prev = head;        size = 0;    }        public void addFirst(Node node) {        node.next = head.next;        node.prev = head;        head.next.prev = node;        head.next = node;        size++;    }        public void remove(Node node) {        node.prev.next = node.next;        node.next.prev = node.prev;        size--;    }        public Node removeLast() {        if (size == 0) return null;        Node last = tail.prev;        remove(last);        return last;    }        public boolean isEmpty() {        return size == 0;    }}// LFU缓存主类public class LFUCache {    private Map<Integer, Node> cache;    private Map<Integer, DoublyLinkedList> freqMap;    private int capacity;    private int minFreq;        public LFUCache(int capacity) {        this.capacity = capacity;        this.cache = new HashMap<>();        this.freqMap = new HashMap<>();        this.minFreq = 0;    }        public int get(int key) {        if (!cache.containsKey(key)) {            return -1;        }        Node node = cache.get(key);        updateNode(node);        return node.value;    }        public void put(int key, int value) {        if (capacity == 0) return;                if (cache.containsKey(key)) {            Node node = cache.get(key);            node.value = value;            updateNode(node);        } else {            if (cache.size() == capacity) {                // 淘汰频率最低且最久未使用的节点                DoublyLinkedList minList = freqMap.get(minFreq);                Node removed = minList.removeLast();                cache.remove(removed.key);                if (minList.isEmpty()) {                    freqMap.remove(minFreq);                }            }            Node newNode = new Node(key, value);            cache.put(key, newNode);            freqMap.computeIfAbsent(1, k -> new DoublyLinkedList()).addFirst(newNode);            minFreq = 1;        }    }        private void updateNode(Node node) {        // 从旧频率列表中移除        DoublyLinkedList oldList = freqMap.get(node.freq);        oldList.remove(node);        if (oldList.isEmpty()) {            freqMap.remove(node.freq);            if (node.freq == minFreq) {                minFreq++;            }        }                // 增加频率并加入新列表        node.freq++;        freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList()).addFirst(node);    }}

代码解析

上述代码实现了标准的LFU缓存，关键点如下：

• Node类：封装了键、值和访问频率。
• DoublyLinkedList类：用于管理同一频率下的所有节点，支持O(1)插入和删除。
• updateNode方法：当节点被访问时，将其从当前频率链表移除，并加入更高频率的链表。
• minFreq变量：始终指向当前最小非空频率，确保淘汰操作高效。

使用示例

public class Main {    public static void main(String[] args) {        LFUCache cache = new LFUCache(2);        cache.put(1, 1);        cache.put(2, 2);        System.out.println(cache.get(1)); // 输出: 1        cache.put(3, 3); // 淘汰键2（频率为1，而键1频率为2）        System.out.println(cache.get(2)); // 输出: -1（不存在）        System.out.println(cache.get(3)); // 输出: 3    }}

总结

通过本教程，你已经掌握了LFU缓存的基本原理和Java语言下的高效实现方式。这种Least Frequently Used算法在处理具有明显访问热度差异的数据时表现优异。希望这篇Java LFU教程能帮助你在实际项目中灵活运用缓存技术，提升系统性能！

提示：在实际生产环境中，可考虑使用Guava Cache等成熟库，但理解底层原理对面试和系统设计至关重要。