如何在 Java 中利用数组实现简单的 LRU 缓存置换策略中的访问频率计数器

在讨论缓存实现时，一个常见的概念混淆点在于LRU和LFU的区别。简单来说，LRU（最近最少使用）策略的核心是访问时间顺序，而LFU（最不经常使用）策略才真正关心访问频次。因此，如果你想在Ja va中用数组结构实现一个“访问频率计数器”，并将其用于淘汰决策，那么你实际上是在构建一个简化版的LFU缓存，而非标准的LRU。

当然，用数组来实现这个逻辑，虽然性能上不适用于生产环境，但对于理解核心概念或进行教学演示，却是一个非常直观的切入点。

明确目标：用数组模拟 LFU 计数器（更贴合需求）

假设我们有一个固定容量为 N 的缓存。最直接的模拟方式，就是使用三个平行的数组：

• keys[]：用来存储缓存项的键。
• values[]：用来存储缓存项对应的值。
• counts[]：这个数组是关键，它在相同下标的位置，记录对应键被访问的次数，也就是我们所说的“频率计数器”。

整个缓存的工作流程就清晰了：每次查询（get）一个存在的键，除了返回值，还要把对应的计数器加一。每次插入（put）时，如果键已存在，就更新值和计数器；如果缓存已满且键不存在，那就需要启动淘汰机制——找出 counts[] 中计数值最小的那个项，把它替换掉。

关键操作：查找、更新与淘汰

由于底层是数组，缺乏哈希表的快速定位能力，所以所有操作都不可避免地需要遍历，时间复杂度为 O(N)。这决定了它只适合小规模场景，但其逻辑一目了然：

• 查找键：遍历 keys[]，使用 equals 方法进行比对，找到则返回下标。
• 更新计数：一旦找到目标下标，对 counts[i] 执行加一操作即可。
• 淘汰策略（LFU）：当需要淘汰时，遍历 counts[] 寻找最小值。如果遇到多个项拥有相同的最小计数值，一个常见的处理原则是淘汰其中最早插入的（即下标最小的），这样可以保证淘汰行为是确定的，而非随机的。

代码片段示意（无泛型简化版）

为了更清晰地展示上述逻辑，下面是一个极度简化的核心代码示例，它省略了泛型等细节，专注于算法骨架：

class SimpleLFUCache {
    private final int capacity;
    private final String[] keys;
    private final String[] values;
    private final int[] counts;
    private int size;

    public SimpleLFUCache(int capacity) {
        this.capacity = capacity;
        this.keys = new String[capacity];
        this.values = new String[capacity];
        this.counts = new int[capacity];
        this.size = 0;
    }

    public String get(String key) {
        for (int i = 0; i < size; i++) {
            if (keys[i] != null && keys[i].equals(key)) {
                counts[i]++;
                return values[i];
            }
        }
        return null;
    }

    public void put(String key, String value) {
        // 先尝试更新已存在项
        for (int i = 0; i < size; i++) {
            if (keys[i] != null && keys[i].equals(key)) {
                values[i] = value;
                counts[i]++;
                return;
            }
        }
        // 新增：缓存未满，直接插入末尾
        if (size < capacity) {
            keys[size] = key;
            values[size] = value;
            counts[size] = 1;
            size++;
            return;
        }
        // 缓存已满：找 counts 最小且下标最小的位置替换
        int minIdx = 0;
        for (int i = 1; i < capacity; i++) {
            if (counts[i] < counts[minIdx]) {
                minIdx = i;
            }
        }
        keys[minIdx] = key;
        values[minIdx] = value;
        counts[minIdx] = 1;
    }
}

注意事项与局限

在理解这个示例的同时，有几点关键的局限性必须指出：

• 概念澄清：这实现的是LFU，而非LRU。真正的LRU需要维护一个精确的访问时间顺序链表，通常结合哈希表来实现，以达到O(1)的访问和更新效率。
• 性能瓶颈：数组的线性查找（O(N)）是主要性能瓶颈。在高并发或数据量大的生产环境中，应优先考虑 LinkedHashMap（其构造器支持按访问顺序排序）或手动组合 ConcurrentHashMap 与双向链表。
• 混合策略的误区：如果你确实需要在LRU缓存中“统计”频率，可以额外维护一个 Map 来计数。但请注意，这个频率数据通常与LRU的淘汰逻辑（基于时间）是解耦的，不参与核心的淘汰决策。
• 工程细节：示例代码为了简洁，省略了很多工程实践必需的考虑，例如对null键值的妥善处理、线程安全的保证（上述代码非线程安全），以及当键为自定义对象时正确重写 equals 和 hashCode 方法的重要性。

总而言之，用数组实现缓存频率计数器是一个很好的学习工具，它能帮你厘清LFU的核心思想。但在实际项目中，选择合适的现成数据结构或成熟库，往往是更可靠、更高效的做法。