146. LRU缓存机制

关于 LRU 缓存(优先淘汰最长时间未被使用的元素)，在面试中应该是老生常谈了，但有意思的是，一般人还是用不到。

在看题解的时候发现了这个骚操作：

class LRUCache(private val capacity: Int) : LinkedHashMap<Int?, Int?>(capacity, 0.75f, true) {
    operator fun get(key: Int): Int {
        return super.getOrDefault(key, -1)?:-1
    }

    fun put(key: Int, value: Int) {
        super.put(key, value)
    }

    override fun removeEldestEntry(eldest: Map.Entry<Int?, Int?>): Boolean {
        return size > capacity
    }
}

0.75的负载因子是默认的，只是为了调用三参构造函数中的第三个排序参数，才需要手动填，removeEldestEntry是为了实现超出大小就抛弃掉。

但肯定这样肯定不合适，需要去把 linkedlist 抄一抄，哈哈，开玩笑。我觉得官方题解的那份就挺不错，能写出来，说明理解链表，同时利用了 MAP，拥有最快 O(1)的时间复杂度，面试时能写出来也很不错了。

class LRUCache(var capacity: Int) {

    class LinkedNode(val key: Int = -1, var value: Int = -1) {
        var prev: LinkedNode? = null
        var next: LinkedNode? = null
    }

    val cache = HashMap<Int, LinkedNode>()
    var size = 0

    var head: LinkedNode = LinkedNode()
    var tail: LinkedNode = LinkedNode()

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = cache[key] ?: return -1
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        val node = cache[key]
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            val newNode = LinkedNode(key, value)
            // 添加进哈希表
            cache[key] = newNode
            // 添加至双向链表的头部
            addToHead(newNode)
            ++size
            if (size>capacity){
                // 如果超出容量，删除双向链表的尾部节点
                val lastNode = removeTail()
                // 删除哈希表中对应的项
                cache.remove(lastNode.key)
                --size
            }
        }else{
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value=value
            moveToHead(node)
        }

    }


    private fun moveToHead(node: LinkedNode) {
        removeNode(node)
        addToHead(node)
    }

    private fun addToHead(node: LinkedNode) {
        node.prev = head
        node.next = head.next
        head.next?.prev = node
        head.next = node
    }

    private fun removeNode(node: LinkedNode) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    private fun removeTail(): LinkedNode {
        val res = tail.prev!!
        removeNode(res)
        return res
    }

}

手抄了一遍，注释按官方的给复制过来了，逻辑简单，但细节还是得注意注意。