LFU缓存实现出现随机不一致结果的问题求助

你的LFU缓存出现随机结果，核心原因都是违反了TreeMap的设计约束，即使在单线程环境下也会导致逻辑混乱：

1. 可变的TreeMap Key破坏内部结构
   你定义的CacheKey是可变类（counter、timestamp、value均可修改），但TreeMap依赖key的不可变性来维护有序性和查找正确性。当你修改CacheKey的属性后，它在TreeMap中的排序位置已经失效，且调用timeKeeper.remove(searchKey)时，由于searchKey状态已变，无法匹配TreeMap中存储的原始key，导致移除失败——旧条目仍留在TreeMap中，新条目又被添加，最终TreeMap堆积了同一个缓存key的多个无效条目，后续pollFirstEntry拿到的元素完全随机。

2. Key唯一性无法保证
   你用counter+timestamp作为TreeMap的排序规则，但如果两个不同缓存key在同一毫秒内被创建/更新，它们的counter和timestamp会完全相同，此时TreeMap会认为这两个key相等，导致后添加的条目覆盖前者，直接丢失数据。此外，CacheKey的equals和hashCode包含value字段，与Comparator逻辑不一致，进一步加剧了TreeMap的行为异常。

另外，put方法中存在冗余操作：pollFirstEntry()已经移除了TreeMap的第一个元素，后续再调用timeKeeper.remove(lfuKey)不仅多余，还可能因key状态变化引发额外错误。

针对上述问题，我们需要从TreeMap的使用约束和LFU核心逻辑入手重构代码：

1. 让缓存条目不可变 #

将CacheKey改为不可变类（所有字段用final修饰），每次更新访问次数或时间戳时，创建新条目而非修改原有对象，保证TreeMap中的key状态始终稳定。

2. 保证条目的唯一性 #

添加全局递增的序列号，作为Comparator的最后比较项，避免因counter和timestamp相同导致的条目覆盖问题（比System.nanoTime()更可靠）。

3. 修正TreeMap逻辑错误 #

移除put中冗余的remove操作，确保每次更新缓存时先彻底移除旧条目，再添加新条目。

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class LFUCache {
    // 不可变缓存条目类
    private static class CacheEntry {
        private final int counter;
        private final long timestamp;
        private final int value;
        private final int sequence; // 全局唯一序列号，保证条目唯一性

        public CacheEntry(int counter, long timestamp, int value, int sequence) {
            this.counter = counter;
            this.timestamp = timestamp;
            this.value = value;
            this.sequence = sequence;
        }

        // 创建新条目：递增访问次数，更新时间戳和序列号
        public CacheEntry withIncrementedAccess(long newTimestamp, int newSequence) {
            return new CacheEntry(this.counter + 1, newTimestamp, this.value, newSequence);
        }

        // 创建新条目：更新value，递增访问次数，更新时间戳和序列号
        public CacheEntry withNewValue(int newValue, long newTimestamp, int newSequence) {
            return new CacheEntry(this.counter + 1, newTimestamp, newValue, newSequence);
        }

        // getter方法
        public int getCounter() { return counter; }
        public long getTimestamp() { return timestamp; }
        public int getValue() { return value; }
        public int getSequence() { return sequence; }

        // equals和hashCode与Comparator逻辑一致
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CacheEntry that = (CacheEntry) o;
            return counter == that.counter && timestamp == that.timestamp && sequence == that.sequence;
        }

        @Override
        public int hashCode() {
            return Objects.hash(counter, timestamp, sequence);
        }
    }

    private final TreeMap<CacheEntry, Integer> timeKeeper;
    private final Map<Integer, CacheEntry> cache;
    private final int capacity;
    private final AtomicInteger sequenceGenerator; // 全局递增序列号生成器

    public LFUCache(int capacity) {
        this.capacity = capacity;
        // Comparator优先级：访问次数最少 → 时间最早 → 序列号最小
        this.timeKeeper = new TreeMap<>(Comparator.comparingInt(CacheEntry::getCounter)
                .thenComparingLong(CacheEntry::getTimestamp)
                .thenComparingInt(CacheEntry::getSequence));
        this.cache = new HashMap<>();
        this.sequenceGenerator = new AtomicInteger(0);
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }

        // 移除旧条目，创建并添加新条目
        CacheEntry oldEntry = cache.get(key);
        timeKeeper.remove(oldEntry);

        long now = System.currentTimeMillis();
        int newSeq = sequenceGenerator.getAndIncrement();
        CacheEntry newEntry = oldEntry.withIncrementedAccess(now, newSeq);

        cache.put(key, newEntry);
        timeKeeper.put(newEntry, key);

        return newEntry.getValue();
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        if (cache.containsKey(key)) {
            // 更新已有条目：移除旧的，添加新的
            CacheEntry oldEntry = cache.get(key);
            timeKeeper.remove(oldEntry);

            long now = System.currentTimeMillis();
            int newSeq = sequenceGenerator.getAndIncrement();
            CacheEntry newEntry = oldEntry.withNewValue(value, now, newSeq);

            cache.put(key, newEntry);
            timeKeeper.put(newEntry, key);
            return;
        }

        // 缓存已满，淘汰LFU/LRU条目
        if (cache.size() >= capacity) {
            Map.Entry<CacheEntry, Integer> lfuEntry = timeKeeper.pollFirstEntry();
            if (lfuEntry != null) {
                cache.remove(lfuEntry.getValue());
            }
        }

        // 添加新条目
        long now = System.currentTimeMillis();
        int newSeq = sequenceGenerator.getAndIncrement();
        CacheEntry newEntry = new CacheEntry(1, now, value, newSeq);
        cache.put(key, newEntry);
        timeKeeper.put(newEntry, key);
    }

    // 测试用例
    public static void main(String[] args) {
        LFUCache lfuCache = new LFUCache(2);
        lfuCache.put(1, 1);
        lfuCache.put(2, 2);
        System.out.println(lfuCache.get(1)); // 1
        lfuCache.put(3, 3); // 淘汰2
        System.out.println(lfuCache.get(2)); // -1
        System.out.println(lfuCache.get(3)); //3
        lfuCache.put(4,4); // 淘汰1（访问次数1，3的访问次数2）
        System.out.println(lfuCache.get(1)); //-1
        System.out.println(lfuCache.get(3)); //3
        System.out.println(lfuCache.get(4)); //4
        // 预期输出：1 -1 3 -1 3 4
    }
}

• 不可变条目：每次更新都创建新的CacheEntry，TreeMap中的key状态永远稳定，remove和put操作能精准定位，不会出现无效条目堆积。
• 全局序列号：即使两个条目的counter和timestamp完全相同，序列号也能保证它们在TreeMap中唯一，不会出现覆盖问题。
• 修正冗余操作：移除了put中多余的remove调用，避免了不必要的错误。

现在运行测试用例，每次都会得到预期输出，不会再出现随机结果。

内容的提问来源于stack exchange，提问作者Niko