public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LRUCache(int capacity) {
        // accessOrder=true 表示按訪問順序排序
        super(capacity, 0.75f, true);
        this.maxCapacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;  // 容量超標(biāo)時移除最老元素
    }
}

LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.get(1);        // 訪問1，使其變?yōu)樽钚?
cache.put(4, "D");   // 觸發(fā)淘汰，移除最久未用的2
System.out.println(cache); // {3=C, 1=A, 4=D}

class LFUCache {
    private Map<Integer, Node> keyToNode;    // key -> 數(shù)據(jù)節(jié)點(diǎn)
    private Map<Integer, LinkedHashSet<Node>> freqToKeys; // 頻率 -> 該頻率下的key集合（用LinkedHashSet保證順序）
    private int minFreq;  // 當(dāng)前最小頻率
    private int capacity;

    class Node {
        int key, value, freq;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;  // 初始頻率為1
        }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        keyToNode = new HashMap<>();
        freqToKeys = new HashMap<>();
        minFreq = 0;
    }

    public int get(int key) {
        if (!keyToNode.containsKey(key)) return -1;
        Node node = keyToNode.get(key);
        updateFreq(node);  // 訪問后頻率+1
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (keyToNode.containsKey(key)) {
            Node node = keyToNode.get(key);
            node.value = value;
            updateFreq(node);
        } else {
            if (keyToNode.size() >= capacity) {
                // 淘汰最小頻率中最久未使用的那個
                LinkedHashSet<Node> set = freqToKeys.get(minFreq);
                Node oldest = set.iterator().next();
                set.remove(oldest);
                keyToNode.remove(oldest.key);
                if (set.isEmpty()) freqToKeys.remove(minFreq);
            }
            Node newNode = new Node(key, value);
            keyToNode.put(key, newNode);
            freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(newNode);
            minFreq = 1;  // 新插入的一定是頻率最低
        }
    }

    private void updateFreq(Node node) {
        int oldFreq = node.freq;
        // 從舊頻率集合中移除
        LinkedHashSet<Node> oldSet = freqToKeys.get(oldFreq);
        oldSet.remove(node);
        if (oldSet.isEmpty()) {
            freqToKeys.remove(oldFreq);
            if (minFreq == oldFreq) minFreq++;
        }
        // 放入新頻率集合
        node.freq++;
        freqToKeys.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(node);
    }
}

// Caffeine 同時支持 LRU 和 LFU（實(shí)際是 TinyLFU，LFU的增強(qiáng)版）
Cache<String, Object> cache = Caffeine.newBuilder()
    .maximumSize(1000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .recordStats()
    .build();