BlogAbout
Published on

LRU

Authors

基础

LRU（Least recently used，最近最少使用）。

我个人感觉这个命名少了个动词，让人理解起来怪怪的，缓存淘汰算法嘛，淘汰最近最少使用。

它的核心时：如果数据最近被访问过，那么将来被访问的几率也更高。

简单实现

LRU 一般使用双向链表+哈希表实现，在 JavaScript 中我使用 Map 数据结构来实现缓存，因为 Map 可以保证加入缓存的先后顺序，

不同的是，这里是把 Map cache 的尾当头，头当尾。

class LRU {
    constructor(size) {
        this.cache = new Map()
        this.size = size
    }
    // 新增时，先检测是否已经存在
    put(key, value) {
        if (this.cache.has(key)) this.cache.delete(key)
        this.cache.set(key, value)
        // 检查是否超出容量
        if (this.cache.size > this.size) {
            this.cache.delete(this.cache.keys().next().value) // 删除Map cache 的第一个数据
        }
    }
    // 访问时，附件重新进入缓存池的动作
    get(key) {
        if (!this.cache.has(key)) return -1
        const temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    }
}

分析：

  1. cache 中的元素必须有时序, 便于后面删除需要淘汰的那个
  2. 在 cache 中快速找到某个 key,判断是否存在并且得到对应的 val O(1)
  3. 访问到的 key 需要被提到前面, 也就是说得能实现快速插入和删除 O(1)

lc.146 LRU 缓存

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.cache = new Map()
    this.capacity = capacity
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (!this.cache.has(key)) return -1
    const val = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, val)
    return val
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.cache.has(key)) this.cache.delete(key)
    this.cache.set(key, value)
    if (this.cache.size > this.capacity) {
        this.cache.delete(this.cache.keys().next().value)
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

双向链表版本

class ListNode {
    constructor(key = 0, value = 0) {
        this.key = key
        this.value = value
        this.prev = null
        this.next = null
    }
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity
    this.cache = new Map()
    this.head = new ListNode()
    this.tail = new ListNode()
    this.head.next = this.tail
    this.tail.prev = this.head
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    const node = this.cache.get(key)

    if (node) {
        node.prev.next = node.next
        node.next.prev = node.prev

        node.next = this.head.next
        node.prev = this.head.next.prev
        this.head.next.prev = node
        this.head.next = node
    }

    return node ? node.value : -1
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    let node = null
    if (this.cache.has(key)) {
        node = this.cache.get(key)
        node.value = value
        node.prev.next = node.next
        node.next.prev = node.prev
    } else {
        node = new ListNode(key, value)
    }

    node.next = this.head.next
    node.prev = this.head.next.prev
    this.head.next.prev = node
    this.head.next = node

    if (!this.cache.has(key) && this.cache.size === this.capacity) {
        // remove
        this.cache.delete(this.tail.prev.key)
        this.tail.prev = this.tail.prev.prev
        this.tail.prev.next = this.tail
    }

    this.cache.set(key, node)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

小心指针的变换就好了。

View on GitHub