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

data = new Map() data.set(key,{   value:'',//存放的具体数据   timestamp:0,//时间戳，判断是否过期用   count:0//数据被读取的次数 }) 

• 資深大佬 : 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

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

• 主 資深大佬 : 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  显示 Gist 代码 

• 資深大佬 : 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 看了，基本都差不多~~