[数据结构算法求助] 如何实现这样一个数据容器，缓存 key-value 数据？(javascript)

[rikka]

背景需求是，需要一个简单的数据容器对一堆 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 似乎不行？应该选择什么样数据结构和算法来实现这个容器最合适？

[aijam]

类似： https://leetcode.com/problems/lru-cache/

[luckyrayyy]

第一个要求不就是 lfu 么，然后用懒删除策略，每次操作的时候判断创建的时间戳是不是超过了十分钟，超过的话就删除并且返回 undefined 。

[DonaldY]

LRU 。

删除的话：
1. 定时遍历删除
2. 获取数据时，判断时间是否过期，过期则删除。

唉，这个我之前写过。

[nightwitch]

维护一个堆结构，保持大致有序就可以了

[rikka]

@luckyrayyy #2
@DonaldY #3
过期这个都比较好处理
极端情况 10 万条，都没过期，现在要插入新的，怎么删，不得遍历

定时删除暂不考虑，这不还得额外弄个线程干这事，增加复杂度，你要是做 redis,memcache 这样的东西，定时就很合理很必要

[rabbbit]

必须用 map 吗, key 的类型没有限制?

[rikka]

@rabbbit #6 map 我感觉不行，key 类型不是关键啊

[kamal]

如果时间和读取次数没有冲突的话，把条件改成时间久的删除，正常的读取变成删除+插入。

[chihiro2014]

@rikka 不得遍历，hash 直接 O(1)查找然后删除不行么？

[rabbbit]

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);

[ipwx]

@rikka 就是 LRU 。你随便找个语言看看别人怎么实现 LRU cache 的就懂了。

[rikka]

@kamal #8 时间和读取次数本来就没啥冲突啊，你这意思是读取变成会更新时间？？

[ipwx]

顺便常见的 LRU 实现方案是一个哈希表 + 一个链表。细节自己去搜索。

[ipwx]

emmm 可能是一个哈希表 + 两个链表…… 这不是重点，反正是有方案的

[rikka]

@chihiro2014 #9 O(1)前提是你得知道 key 啊，问题是删除的时候根本不知道 key 是什么，得遍历根据条件去找符合要求的 key 然后删除啊

[rikka]

@ipwx #14 行吧都说是 LRU，我研究学习下。。。

[noe132]

https://www.npmjs.com/package/lru-cache

[leapV3]

LRU
hashmap

[kamal]

@rikka #12 是的，变成了按照时间排序的数组或者链表。
正常读取：读取-删除-（未过期）-插入队首-返回
超时：读取-删除-（已过期）-返回空
长度超出；读取-删除-插入队首-删除队尾-返回

[rabbbit]

抱歉,我看错帖子要求了.我上面那个回复真是错到离谱了.