原理

LFU Cache 是Least Frequently Used Cache的缩写，记录缓存对象使用次数，当缓存满了之后，删除最少使用的缓存。

缓存容量为k,随着每次读取，使用次数都在变化，可以看成是从无尽序列中维护一个前K大的序列，当缓存满了之后，删除最小的元素。可以使用小顶堆来实现，Java中有对应的实现类PriorityQueue。

首先实现一个缓存条目类，记录缓存的key，value，以及使用次数。

public class CacheEntry<K, V> implements Comparable<CacheEntry<K, V>> {
    private final K key;
    private V value;
    private int frequency;

    public CacheEntry(K key, V value) {
        this.key = key;
        this.value = value;
        this.frequency = 1;
    }

    @Override
    public int compareTo(CacheEntry<K, V> other) {
        int freqComparison = Integer.compare(frequency, other.frequency);
        return freqComparison != 0 ? freqComparison : key.hashCode() - other.key.hashCode();
    }
}

ConcurrentHashMap + PriorityQueue + 读写锁 实现

import java.util.*;
import java.util.concurrent.locks.*;

class LFUCache<K, V> {
    private final int capacity;
    private final Map<K, CacheEntry<K, V>> cache;
    private final PriorityQueue<CacheEntry<K, V>> frequencyQueue;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new ConcurrentHashMap<>();
        this.frequencyQueue = new PriorityQueue<>();
    }

    public V get(K key) {
        readLock.lock();
        try {   
            CacheEntry<K, V> entry = cache.get(key);
            if (entry != null) {
                writeLock.lock();
                try {
                    updateFrequency(entry); // 更新使用频次
                } finally {
                    writeLock.unlock();
                }
                
                return entry.value;
            }
            return null;
        } finally {
            readLock.unlock();
        }
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            CacheEntry<K, V> entry = cache.get(key);
            if (entry == null) {
                evictIfNeeded(); // 如果超过容量限制，则淘汰最低频次的条目
                entry = new CacheEntry<>(key, value);
                cache.put(key, entry);
                frequencyQueue.add(entry);
            } else {
                entry.value = value;
                updateFrequency(entry); // 更新使用频次
            }
        } finally {
            writeLock.unlock();
        }
    }

    private void updateFrequency(CacheEntry<K, V> entry) {
        frequencyQueue.remove(entry);
        entry.frequency++;
        frequencyQueue.add(entry);
    }

    private void evictIfNeeded() {
        if (cache.size() >= capacity) {
            CacheEntry<K, V> leastFrequentEntry = frequencyQueue.poll();
            if (leastFrequentEntry != null) {
                cache.remove(leastFrequentEntry.key);
            }
        }
    }

}