LRU的实现是否有问题？

[Moyulingjiu]

详见于文件：https://github.com/project-mirai/mirai-api-http/blob/master/mirai-api-http/src/main/kotlin/net/mamoe/mirai/api/http/context/cache/MessageSourceCache.kt

该文件中定义了一个LRU的缓存。但实际确为FIFO的实现。

测试代码如下：

import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.ConcurrentLinkedQueue

fun main(args: Array<String>) {
    val map = LRUCache<String, Int>(3)
    map.put("a", 1)
    println("插入a: 1")
    map.show()

    map.put("b", 2)
    println("插入b: 2")
    map.show()

    map.put("c", 3)
    println("插入c: 3")
    map.show()

    println("获取a: ${map.get("a")}")
    map.show()

    map.put("d", 4)
    println("插入d: 4")
    map.show()

    println("获取a: ${map.get("a")}")
    map.show()
}

open class LRUCache<K: Any, V: Any>(private val cacheSize: Int) {
    private val lruQueen = ConcurrentLinkedQueue<K>()
    private val cacheData = ConcurrentHashMap<K, V>()

    open fun show() {
        println("Cache size: $cacheSize")
        println("Cache data: $cacheData")
        println("Cache queue: $lruQueen")
        println()
    }

    open fun get(key: K): V? {
        return cacheData[key]
    }

    fun put(key: K, value: V) {
        val old = cacheData.put(key, value)
        if (old == null) {
            lruQueen.offer(key)
            lru()
        }
    }

    private fun lru() {
        while (lruQueen.size > cacheSize) {
            val poll = lruQueen.poll()
            cacheData.remove(poll)
        }
    }

    fun size() = cacheData.size
}

输出如下：

插入a: 1
Cache size: 3
Cache data: {a=1}
Cache queue: [a]

插入b: 2
Cache size: 3
Cache data: {a=1, b=2}
Cache queue: [a, b]

插入c: 3
Cache size: 3
Cache data: {a=1, b=2, c=3}
Cache queue: [a, b, c]

获取a: 1
Cache size: 3
Cache data: {a=1, b=2, c=3}
Cache queue: [a, b, c]

插入d: 4
Cache size: 3
Cache data: {b=2, c=3, d=4}
Cache queue: [b, c, d]

获取a: null
Cache size: 3
Cache data: {b=2, c=3, d=4}
Cache queue: [b, c, d]

进程已结束，退出代码为 0

可以很明显发现，在插入三个数据后获取了a但是队列的顺序并没有改变，随后插入元素d，a就被抛弃了。但是其刚刚被使用。

考虑如下修改LRU（不是什么太大的问题就懒得提PR了）：

  open fun get(key: K): V? {
      if (cacheData.containsKey(key)) {
          lruQueen.remove(key)
          lruQueen.add(key)
          return cacheData[key]
      }
      return null
  }

更改后输出如下：

插入a: 1
Cache size: 3
Cache data: {a=1}
Cache queue: [a]

插入b: 2
Cache size: 3
Cache data: {a=1, b=2}
Cache queue: [a, b]

插入c: 3
Cache size: 3
Cache data: {a=1, b=2, c=3}
Cache queue: [a, b, c]

获取a: 1
Cache size: 3
Cache data: {a=1, b=2, c=3}
Cache queue: [b, c, a]

插入d: 4
Cache size: 3
Cache data: {a=1, c=3, d=4}
Cache queue: [c, a, d]

获取a: 1
Cache size: 3
Cache data: {a=1, c=3, d=4}
Cache queue: [c, d, a]

可见扔掉的为b而非刚刚使用的a。

对于是否要从FIFO改为LRU持保留意见，但是方法命名存在误导性，这并不是LRU算法。建议考虑更改代码或者更改命名。LRU维护队列毕竟是O(n)算法，FIFO的O(1)不见得无法满足需求。

[ryoii]

原本是考虑实现LRU的，但是考虑到这样做的意义不大，仅提供一个能提供固定大小的消息缓存就足够了，慢慢地就退化下来了

[Moyulingjiu]

原本是考虑实现LRU的，但是考虑到这样做的意义不大，仅提供一个能提供固定大小的消息缓存就足够了，慢慢地就退化下来了

我也感觉LRU意义不大，所以感觉更改一下命名就行了，避免误导一些刚开始阅读代码的新人。