狗狗新鲜电面

jiaguofang 发表于 2017-2-22 16:09
我的意思是：
假如你用min heap，越早expire的存在顶端。某次set之后，某个key的expiration time变短， ...

我想楼主的意思应该是set的时候重新插入一个值到heap里
当从heap里出来的时候从新检查一下expire time是否和map里的一样 不一样说明是旧的值

帮楼主解释下, 因为一般priority_queue (pq) 无法update, 所以不管set的key是否存在, 都纪录到pq里.
那同个key被set很多次的话, 在pq里面会有多个entry.
所以clean()在pop pq和删old key的时候, 要check map里的expiration time, 如果map里面是相同的expiration time才能delete;
否则代表pq的纪录是旧的, key有被udpate过,不能删key.

感谢分享！哈哈

DWill008 发表于 2017-2-23 04:35
对3个操作time complexity有要求吗？都需要O(1) 吗？O(logn)可以吗？

我觉得可以这样，如果logn允许的话 ...

看了一下大家的回复，总结一下第二种思路：如果同一个key没有多个Value的话，可以考虑用Map加priorityqueue, 根据expire time从小到大排序，建议把expire time转换成具体时间点。get时直接检查是否小时当前时间，如果小于，返回null。set时同时更新Map和priorityqueue。更新priorityqueue时，直接加入新的Node，原来的先不做处理。cleanup的时候，检查从pq poll出来的node的expire time和map里是否一样，如果不同或者map里不存在这个node，只删除pq里的node，否则同时删除两边的。

猫小白 发表于 2018-9-29 11:24
看了一下大家的回复，总结一下第二种思路：如果同一个key没有多个Value的话，可以考虑用Map加priorityque ...

这样的话每一步都是O（1）的对吧？

emilyw 发表于 2018-10-15 13:32
这样的话每一步都是O（1）的对吧？

对pq操作的时候是log n

猫小白 发表于 2018-10-15 21:43
对pq操作的时候是log n

万一pq里的全expire了，那clean不就是nlogn了吗？是不是还不如O(n)解法的一个个比较啊？