第150题 用JS实现一个LRU缓存

• 什么是LRU缓存
  • LRU（Least Recently Used） 最近最少使用
  • 假如我们有一块内存，专门用来缓存我们最近发访问的网页，访问一个新网页，我们就会往内存中添加一个网页地址，随着网页的不断增加，内存存满了，这个时候我们就需要考虑删除一些网页了。这个时候我们找到内存中最早访问的那个网页地址，然后把它删掉。这一整个过程就可以称之为 LRU 算法
  • 核心两个API，get和set
• 分析
  • 用哈希表存储数据，这样get set才够快，时间复杂度O(1)
  • 必须是有序的，常用数据放在前面，沉水数据放在后面
  • 哈希表 + 有序，就是Map

    class LRUCache {
        constructor(length) {
            if (length < 1) throw new Error('invalid length')
            this.length = length
        }
    
        set(key, value) {
            const data = this.data
    
            if (data.has(key)) {
                data.delete(key)
            }
            data.set(key, value)
    
            if (data.size > this.length) {
                // 如果超出了容量，则删除 Map 最老的元素
                const delKey = data.keys().next().value
                data.delete(delKey)
            }
        }
    
        get(key) {
            const data = this.data
    
            if (!data.has(key)) return null
    
            const value = data.get(key)
    
            // 先删除，再添加，就是最新的了
            data.delete(key)
            data.set(key, value)
    
            return value
        }
    }

    // 测试
    
    const lruCache = new LRUCache(2)
    lruCache.set(1, 1) // {1=1}
    lruCache.set(2, 2) // {1=1, 2=2}
    console.info(lruCache.get(1)) // 1 {2=2, 1=1}
    lruCache.set(3, 3) // {1=1, 3=3}
    console.info(lruCache.get(2)) // null
    lruCache.set(4, 4) // {3=3, 4=4}
    console.info(lruCache.get(1)) // null
    console.info(lruCache.get(3)) // 3 {4=4, 3=3}
    console.info(lruCache.get(4)) // 4 {3=3, 4=4}