[数据结构算法求助] 如何实现这样一个数据容器，缓存 key-value 数据？(javascript)
rikka · 2020-07-11 15:32:23 +08:00 · 2750 次点击这是一个创建于 1581 天前的主题，其中的信息可能已经有所发展或是发生改变。
背景需求是，需要一个简单的数据容器对一堆 key-value 进行缓存（什么 redis,memcache 通通都不要，我就想简单的在内存存点数据而已）
容器有两个要求
1.固定容量，满了之后插入新数据就要删除旧数据，删除算法的指导思想是，删除那些越旧读取次数越少的数据
2.数据有效时间，比如设置 10 分钟，10 分钟后读取里面某条数据就应该删掉这条数据并返回 undefined
感觉很简单啊，我用个 Map 来实现就可以了
data = new Map()
data.set(key,{
value:'',//存放的具体数据
timestamp:0,//时间戳，判断是否过期用
count:0//数据被读取的次数
})
但是问题来了，要插入新数据容器已经满了，怎么删除？
我不得根据 timestamp 和 count 这 2 个字段对全部数据进行排序？
排序就得遍历啊，极端情况要是 10 万条数据，每次删除都得遍历一下，这哪受得了
卡在这了，Map 似乎不行？应该选择什么样数据结构和算法来实现这个容器最合适？
第 1 条附言 · 2020-07-12 15:22:35 +08:00
大家都提到了 LRU，我就学习研究一番，感觉很精妙啊，目前我用 LRU 实现出来了
然后发现 LRU 实现出来有点问题，我的要求之一是数据有个有效期，而 LRU 只会删除队列最后一个
这样存在一种情况，队列最后一个数据没过期，但是倒数第二个是过期了，LRU 会把最后这个没过期的删掉了，但是实际上倒数第二个更加应该被删除才对
然后发现 LRU 实现出来有点问题，我的要求之一是数据有个有效期，而 LRU 只会删除队列最后一个
这样存在一种情况，队列最后一个数据没过期，但是倒数第二个是过期了，LRU 会把最后这个没过期的删掉了，但是实际上倒数第二个更加应该被删除才对
第 2 条附言 · 2020-07-12 16:03:36 +08:00
补充下删除算法要求，数据过期是最优先应该被删除的，然后数据的新旧程度和读取次数这 2 个权重，我感觉哪个优先都行
第 3 条附言 · 2020-07-13 17:22:17 +08:00
记录下
LRU 已经学习理解得很 OK 代码也写出来了，然后继续学习 LFU，这个就有点复杂了
看了这篇文章 https://leetcode-cn.com/problems/lfu-cache/solution/chao-xiang-xi-tu-jie-dong-tu-yan-shi-460-lfuhuan-c/
基本上弄懂了
总结下：
LRU 是根据数据的读取时间这一个维度来排列数据，关键点就是数据一旦被读取就会把数据调到队头去，它的实现是需要一个哈希表+一个双向链表
LFU 是根据数据的读取时间和访问频率两个维度来排列数据，LFU 实际上是包含了 LRU 的思想在里面，实现是需要两个哈希表+N 个双向链表，代码复杂点，空间复杂度也会高点
LFU 感觉更加科学合理一点，更加符合我的要求
LRU 已经学习理解得很 OK 代码也写出来了，然后继续学习 LFU，这个就有点复杂了
看了这篇文章 https://leetcode-cn.com/problems/lfu-cache/solution/chao-xiang-xi-tu-jie-dong-tu-yan-shi-460-lfuhuan-c/
基本上弄懂了
总结下：
LRU 是根据数据的读取时间这一个维度来排列数据，关键点就是数据一旦被读取就会把数据调到队头去，它的实现是需要一个哈希表+一个双向链表
LFU 是根据数据的读取时间和访问频率两个维度来排列数据，LFU 实际上是包含了 LRU 的思想在里面，实现是需要两个哈希表+N 个双向链表，代码复杂点，空间复杂度也会高点
LFU 感觉更加科学合理一点，更加符合我的要求
第 4 条附言 · 2020-07-14 18:37:32 +08:00
最终，在 LRU 的基础上，增加一个双向链表按时间顺序记录时间戳，以实现“不定时不遍历”，去最优先删除过期数据的目标~~任务圆满完成~~
代码以更新
感谢参与讨论的各位
代码以更新
感谢参与讨论的各位
 |
1
aijam 2020-07-11 15:37:18 +08:00
|
 |
2
luckyrayyy 2020-07-11 15:39:01 +08:00
第一个要求不就是 lfu 么，然后用懒删除策略，每次操作的时候判断创建的时间戳是不是超过了十分钟，超过的话就删除并且返回 undefined 。
|
 |
3
DonaldY 2020-07-11 15:41:27 +08:00
LRU 。
删除的话： 1. 定时遍历删除 2. 获取数据时，判断时间是否过期，过期则删除。 唉，这个我之前写过。 |
 |
4
nightwitch 2020-07-11 15:41:29 +08:00
维护一个堆结构，保持大致有序就可以了
|
 |
5
rikka OP @luckyrayyy #2
@DonaldY #3 过期这个都比较好处理 极端情况 10 万条，都没过期，现在要插入新的，怎么删，不得遍历 定时删除暂不考虑，这不还得额外弄个线程干这事，增加复杂度，你要是做 redis,memcache 这样的东西，定时就很合理很必要 |
 |
6
rabbbit 2020-07-11 15:56:54 +08:00
必须用 map 吗, key 的类型没有限制?
|
 |
8
kamal 2020-07-11 16:04:27 +08:00  1
如果时间和读取次数没有冲突的话，把条件改成时间久的删除，正常的读取变成删除+插入。
|
 |
9
chihiro2014 2020-07-11 16:11:37 +08:00
@rikka 不得遍历，hash 直接 O(1)查找然后删除不行么？
|
|
10
rabbbit 2020-07-11 16:16:06 +08:00
js 是单线程的, 大量数据定时遍历不就卡死了吗?
还是建议访问的时候再删. class Cache { time = {}; data = {}; constructor(cleanInterval = 1000 * 60 * 10) { this.cleanInterval = cleanInterval; } get(key) { if (this.data[key]) { if (Date.now() - this.time[key] < this.cleanInterval) { return this.data[key]; } else { delete this.data[key]; delete this.time[key]; } } } set(key, value) { this.data[key] = value; this.time[key] = Date.now(); } } const c = new Cache(100); c.set('a', 1); setTimeout(() => { console.log(c.get('a')); }, 1000); |
 |
13
ipwx 2020-07-11 16:17:18 +08:00
顺便常见的 LRU 实现方案是一个哈希表 + 一个链表。细节自己去搜索。
|
|
14
ipwx 2020-07-11 16:17:57 +08:00
emmm 可能是一个哈希表 + 两个链表…… 这不是重点，反正是有方案的
|
|
15
rikka OP @chihiro2014 #9 O(1)前提是你得知道 key 啊，问题是删除的时候根本不知道 key 是什么，得遍历根据条件去找符合要求的 key 然后删除啊
|
 |
17
noe132 2020-07-11 16:20:40 +08:00
|
 |
18
leapV3 2020-07-11 16:24:27 +08:00
LRU
hashmap |
|
19
kamal 2020-07-11 16:29:35 +08:00
|
|
20
rabbbit 2020-07-11 16:34:08 +08:00
抱歉,我看错帖子要求了.我上面那个回复真是错到离谱了.
|
|
21
rikka OP @kamal #19 这思路感觉有点行啊，这么搞，如果一个数据（没过期）频繁被读取就会一直保持在队列前面，需要删除的时候就不容易被删，那些没怎么被读取的就会随着队列调整落在队尾，随时准备被删除~~
|
 |
22
renmu123 2020-07-11 17:08:34 +08:00 via Android
你看一下 Redis 的实现就可以了
|
 |
23
di94sh 2020-07-11 20:31:22 +08:00 via iPhone
找个 cachetools 之类的库呗
|
 |
24
xiaoming1992 2020-07-12 05:01:04 +08:00 via Android
删除算法的指导思想是，删除那些越旧读取次数越少的数据
权重怎么样呢？一个 1s 前读取 1 次的数据、和一个 2s 前读取 2 次的数据，应该删除哪个呢？ |
 |
25
zifangsky 2020-07-12 13:27:05 +08:00
“删除那些越旧读取次数越少的数据”？到底是删除最旧的数据（ LRU ）还是删除访问次数最少的数据（ LFU ）？
|
|
26
rikka OP @xiaoming1992 #24
@zifangsky #25 其实都可以，目前我用 LRU 实现出来了 https://gist.github.com/mkanako/e8a279aa2ffd946bf7b3fd9c26479ef7 然后发现 LRU 实现出来有点问题，我的要求之一是数据有个有效期，而 LRU 只会删除队列最后一个 这样存在一种情况，队列最后一个数据没过期，但是倒数第二个是过期了，LRU 把最后这个没过期的删掉了，但是实际上倒数第二个更加应该被删除才对 |
 |
27
stardust21 2020-07-12 15:32:22 +08:00
@rikka 如果没满不删除也没影响，满了就先遍历删除过期的，再走 LRU 的逻辑
|
|
28
rikka OP @stardust21 #27 删除肯定是满了才进行删除的，遍历也不太行，极端情况存了 10 万个数据，准备删除，难道先遍历看看谁过期了在删除？好吧，那万一要是全都没过期，那就很尴尬白忙活，只能乖乖按照 LRU 删最后一个
|
 |
29
saberlong 2020-07-12 18:33:11 +08:00 via Android
LRU 变种啊，你是需要按时间删除和按最少访问删除。那么用 2 个链表。定时对超时部分删除。每次满的时候针对最少访问删除。
|
 |
30
shellus 2020-07-12 21:54:45 +08:00
0:在写入 key 的时候，将其索引写到要删除的按 10 分钟一个的数组里面，例如 15 分钟过期，就 deleteArr[20].push(key)
1:在第 20 分钟删除这些 keys，就不用遍历了 2:读取 key 的时候，检查 key 的过期时间，过期就返回 null （这时候真实删除 key 也可以，因为读取到 null 一般紧跟着缓存更新） 2:如果在定时删除前，有新的 key 要使用同样的 name，就真实删除这个 key，也不用遍历 |
|
31
rikka OP |
|
32
saberlong 2020-07-12 23:54:58 +08:00 via Android
@rikka 定时只是清理策略实现方式上的选择，不影响核心数据结构。只是将超时的判定和超过内存阀值这两个条件分开写，各管各的，实现起来更清晰，并且及时清理超时而已。合并起来也可以做清理策略。比如在触发清理时，先清理超时的，然后判定是否清理得足够多，不够再清理最少访问的就行了。然后需要在查询的地方补上超时判定。本质还是 LRU，只是根据需要做简单修改而已。我觉得你自己思考就明白了
|
 |
33
wangritian 2020-07-13 10:29:16 +08:00
LRU 的基础上，增加一块环形内存，记录时间戳和缓存 key 或地址，从左向右是时间递增的，指针 P 记录当前环形起点。当缓存队列已满需要 set 时，优先读取 P 指向的时间戳，如果没过期，执行 LRU 算法；如果过期，则替换 P 指向的 key 、value 、时间戳，然后 P 右移一位，不执行 LRU 。不知道这个方案有没有问题。
|
|
35
rikka OP @wangritian #33 我也差不多想到这了，感觉很行啊
需要增加一个双向链表，按时间顺序放入数据 当需要删除的时候，首先到这个链表取第一个数据，看看有没有过期，过期就删这个数据，没有就继续走 LRU 的逻辑 等我抽空来实现~~ |
|
36
zifangsky 2020-07-13 17:38:28 +08:00
你可以再参考下我实现的 LRU 算法，自我感觉还是比较完善的，不过我是用的 Java 实现： https://gitee.com/zifangsky/DataStructure/tree/master/src/main/java/cn/zifangsky/hashtable/lru
|
|
37
zifangsky 2020-07-13 17:40:14 +08:00
当然，LFU 算法我也实现了，你看上一层目录就可以看到。
|
 |
39
xieranmaya 2020-07-15 16:55:56 +08:00
LRU+定时器
这做个面试题是真不错 |
Select Language