带过期时间LRU的js实现

[rudyxu1102]

原理

使用双向链表和哈希表

代码实现

// 链表节点
class Node {
    constructor (key = null, value = null) {
        this.key = key
        this.saveTime = Date.now()
        this.value = value
        this.pre = null
        this.next = null
    }
}

// 双向链表
class List {
    constructor () {
        this.dummyHead = new Node()
        this.dummyTail = new Node
        this.dummyHead.next = this.dummyTail
        this.dummyTail.pre = this.dummyHead
        this.length = 0
    }

    pop () {
        if (!this.length) return
        let node = this.dummyTail.pre
        node.pre.next = this.dummyTail
        this.dummyTail.pre = node.pre
        this.length--
        return node
    }

    unshiftNode (node) {
        let head = this.dummyHead.next
        node.next = head
        head.pre = node
        this.dummyHead.next = node
        node.pre = this.dummyHead
        this.length++
    }

    removeNode (node) {
        node.pre.next = node.next
        node.next.pre = node.pre
        this.length--
    }

    moveToHead (node) {
        this.removeNode(node)
        this.unshiftNode(node)
    }
}

// LRU缓存
class LRU {
    constructor (size, expire = 1000) {
        this.size = size
        this.expire = expire
        this.map = new Map()
        this.list = new List()
    }

    put (key, value) {
        if (this.map.has(key)) {
            let node = this.map.get(key)
            node.value = value
            this.list.moveToHead(node)
        } else {
            let node = new Node(key, value)
            this.map.set(key, node)
            this.list.unshiftNode(node)
            if (this.list.length > this.size) {
                let node = this.list.pop()
                this.map.delete(node.key)
            }
        }
    }

    get (key) {
        let node = this.map.get(key)
        if (!node) {
            return -1
        }
        if (Date.now() - node.saveTime <= this.expire) {
            this.list.moveToHead(node)
            return node.value
        } else {
            this.list.removeNode(node)
            this.map.delete(key)
            return -1
        }
    }
}

// 测试
let lru = new LRU(2) 
lru.put(1, 1)
lru.put(2, 2)
lru.put(3, 3)
let item = lru.get(1)
console.log(item) // -1

let ele = lru.get(3)
console.log(ele) // 3
setTimeout(() => {
    console.log(lru.get(3)) // -1
}, 2000)

参考

• node-lru-cache
• node-expiring-lru-cache
• yallist