简单实现LRU缓存

发表于 | 分类于 | 阅读次数:
字数统计: 582 | 阅读时长 ≈ 2

avatar

什么是LRU

LRU 缓存淘汰算法是一种常用缓存策略, LRU 全称是 Least Recently Used, 用于管理缓存中的数据。

工作原理：

  • 【初始化】: 初始化一定 “容量” 的 [缓存管道], 当缓存溢出需要将最底部的数据移除
  • 【访问数据】: 每次访问 (读或写) 缓存中的数据时, 将数据移到数据最顶部 (起始位) 或更新数据位置
  • 【移除老旧数据】: 当缓存达到容量上限时, 需要移除最久并未访问过的数据, 即尾部数据
1
2
3
4
5
6
7
const cache = new LRUcache(3)
cache.put(1, 1) // 返回 null 此时为[1]
cache.put(2, 2) // 返回 null 此时为[2, 1]
cache.put(3, 3) // 返回 null 此时为[3, 3]
cache.get(1) // 返回 [1] 此时为[1, 3, 2]
cache.put(4, 4) // 返回null 此时超出容量移除最久未访问的数据, 即 [4, 1, 3]
cache.get(4) // 返回-1 此时为[4, 1, 3]不存在索引4的数据

javascript中的Map

Map是一种数据结构, Map的键可以是任意类型的数据, 而我们可以借助 Map.prototype.keys 实现.
先看 Map.keys 能拿到什么
map

这时可以拿到 Map迭代器 , 我们知道迭代器 iterator 有 next 方法, 每次调用都会返回一个包含 value, done 的对象
map

这时我们可以利用Map自身api及iterator.next返回的键值对实现LRU

LRU
直接看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class LRUCache {
    constructor(max) {
        this.max = max
        this.cache = new Map()
    }

    get(key) {
        // 场景一 cache不存在key则返回-1
        if(!this.cache.has(key)) return -1
        // 场景二 cache中已存在key对应的value,则把该值变成'新鲜'
        this.makeFresh(key)
        return this.cache.get(key)
    }

    set(key, val) {
        // 场景一 cache中已存在key,则把key对应的value赋最新值且变'新鲜'
        if(this.cache.has(key)) {
            this.cache.set(key, val)
            this.makeFresh(key)
            return
        }
        // 场景二 cache中不存在key
        // 缓存区未满, 则直接设置键值对
        if(this.cache.size >= this.max) {
            const oldKey = this.cache.keys().next().value
            this.cache.delete(oldKey)
        }
        this.cache.set(key, val)
        // 缓存区已满, 把尾部数据移除再设置新的键值对
    }

    makeFresh(key) {
        const val = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, val)
    }
}