基于Kotlin实现的LFU缓存代码求专业点评与优化建议

我是一名学生，最近在研究经典的LFU（Least Frequently Used，最少使用）缓存问题，觉得网上的算法实现很难复刻，于是从零开始用Kotlin写了一个可正常运行的LFU缓存版本。希望有经验的开发者能帮忙点评这个实现和标准方案的差距，并给出优化建议。

实现代码 #

class LFUCache(private val capacity: Int) {
    private val cache = mutableMapOf<Int, Pair<Int, Int>>() // key to (value, frequency)
    private val frequencyMap = mutableMapOf<Int, MutableSet<Int>>() // frequency to keys
    private var minFrequency = 1

    fun get(key: Int): Int {
        val (value, freq) = cache[key] ?: return -1
        // Update frequency
        frequencyMap[freq]?.remove(key)
        if (frequencyMap[freq].isNullOrEmpty()) {
            frequencyMap.remove(freq)
            if (minFrequency == freq) {
                minFrequency++
            }
        }
        val newFreq = freq + 1
        cache[key] = value to newFreq
        frequencyMap.computeIfAbsent(newFreq) { mutableSetOf() }.add(key)
        return value
    }

    fun put(key: Int, value: Int) {
        if (capacity == 0) return
        if (cache.containsKey(key)) {
            // Update existing key's value and frequency
            cache[key] = value to cache[key]!!.second
            get(key) // Reuse get logic to update frequency
            return
        }
        // Evict if capacity reached
        if (cache.size >= capacity) {
            val keyToEvict = frequencyMap[minFrequency]?.first() ?: return
            frequencyMap[minFrequency]?.remove(keyToEvict)
            if (frequencyMap[minFrequency].isNullOrEmpty()) {
                frequencyMap.remove(minFrequency)
            }
            cache.remove(keyToEvict)
        }
        // Add new key
        cache[key] = value to 1
        frequencyMap.computeIfAbsent(1) { mutableSetOf() }.add(key)
        minFrequency = 1
    }
}

核心疑问 #

• 该实现和标准LFU缓存方案的主要差距在哪里？
• 从性能优化、代码结构、边界场景处理等角度，有哪些具体的改进建议？

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