[数据结构算法求助] 如何实现这样一个数据容器，缓存 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 似乎不行？应该选择什么样数据结构和算法来实现这个容器最合适？

[rikka]

@kamal #19 这思路感觉有点行啊，这么搞，如果一个数据（没过期）频繁被读取就会一直保持在队列前面，需要删除的时候就不容易被删，那些没怎么被读取的就会随着队列调整落在队尾，随时准备被删除~~

[renmu123]

你看一下 Redis 的实现就可以了

[di94sh]

找个 cachetools 之类的库呗

[xiaoming1992]

删除算法的指导思想是，删除那些越旧读取次数越少的数据

权重怎么样呢？一个 1s 前读取 1 次的数据、和一个 2s 前读取 2 次的数据，应该删除哪个呢？

[zifangsky]

“删除那些越旧读取次数越少的数据”？到底是删除最旧的数据（ LRU ）还是删除访问次数最少的数据（ LFU ）？

[rikka]

@xiaoming1992 #24
@zifangsky #25

其实都可以，目前我用 LRU 实现出来了
https://gist.github.com/mkanako/e8a279aa2ffd946bf7b3fd9c26479ef7


然后发现 LRU 实现出来有点问题，我的要求之一是数据有个有效期，而 LRU 只会删除队列最后一个

这样存在一种情况，队列最后一个数据没过期，但是倒数第二个是过期了，LRU 把最后这个没过期的删掉了，但是实际上倒数第二个更加应该被删除才对

[stardust21]

@rikka 如果没满不删除也没影响，满了就先遍历删除过期的，再走 LRU 的逻辑

[rikka]

@stardust21 #27 删除肯定是满了才进行删除的，遍历也不太行，极端情况存了 10 万个数据，准备删除，难道先遍历看看谁过期了在删除？好吧，那万一要是全都没过期，那就很尴尬白忙活，只能乖乖按照 LRU 删最后一个

[saberlong]

LRU 变种啊，你是需要按时间删除和按最少访问删除。那么用 2 个链表。定时对超时部分删除。每次满的时候针对最少访问删除。

[shellus]

0:在写入 key 的时候，将其索引写到要删除的按 10 分钟一个的数组里面，例如 15 分钟过期，就 deleteArr[20].push(key)
1:在第 20 分钟删除这些 keys，就不用遍历了
2:读取 key 的时候，检查 key 的过期时间，过期就返回 null （这时候真实删除 key 也可以，因为读取到 null 一般紧跟着缓存更新）
2:如果在定时删除前，有新的 key 要使用同样的 name，就真实删除这个 key，也不用遍历

[rikka]

@saberlong #29
@shellus #30

你说“定时”什么的，这不就得依赖系统时钟，增加额外的线程。当然实际项目完全可以这么干，有了“定时”，事情也就变得很简单了

而我其实是希望用纯数据结构纯算法来完成这个事，给自己增加点挑战~~

[saberlong]

@rikka 定时只是清理策略实现方式上的选择，不影响核心数据结构。只是将超时的判定和超过内存阀值这两个条件分开写，各管各的，实现起来更清晰，并且及时清理超时而已。合并起来也可以做清理策略。比如在触发清理时，先清理超时的，然后判定是否清理得足够多，不够再清理最少访问的就行了。然后需要在查询的地方补上超时判定。本质还是 LRU，只是根据需要做简单修改而已。我觉得你自己思考就明白了

[wangritian]

LRU 的基础上，增加一块环形内存，记录时间戳和缓存 key 或地址，从左向右是时间递增的，指针 P 记录当前环形起点。当缓存队列已满需要 set 时，优先读取 P 指向的时间戳，如果没过期，执行 LRU 算法；如果过期，则替换 P 指向的 key 、value 、时间戳，然后 P 右移一位，不执行 LRU 。不知道这个方案有没有问题。

[rikka]

@saberlong #32 能明白，不过暂时不考虑这种方式

[rikka]

@wangritian #33 我也差不多想到这了，感觉很行啊

需要增加一个双向链表，按时间顺序放入数据
当需要删除的时候，首先到这个链表取第一个数据，看看有没有过期，过期就删这个数据，没有就继续走 LRU 的逻辑

等我抽空来实现~~

[zifangsky]

你可以再参考下我实现的 LRU 算法，自我感觉还是比较完善的，不过我是用的 Java 实现： https://gitee.com/zifangsky/DataStructure/tree/master/src/main/java/cn/zifangsky/hashtable/lru

[zifangsky]

当然，LFU 算法我也实现了，你看上一层目录就可以看到。

[rikka]

@zifangsky #37 看了，基本都差不多~~

[xieranmaya]

LRU+定时器
这做个面试题是真不错