支持存活时间的HashMap

求教一道狗家的面试题。题目是：

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

这个问题我之前在一个回帖里稍微写过一点，复制过来..

Map with expiration可以参考一下比较有名的key-value cache例如Redis和Memcached的实现，其实它们就是用的lazy check TTL + daemon clean up，关于expiration方面好像没有什么更fancy的东西了。这边举一下Memcached的例子：
--
(1) Memcached的item结构中的timestamp部分：
https://github.com/memcached/mem ... er/memcached.h#L471

(2) Memcached的get操作中进行lazy expiration：
https://github.com/memcached/memcached/blob/master/items.c#L1007

(3) Memcached的daemon thread cleanup：
Daemon线程的主循环在这边：
https://github.com/memcached/memcached/blob/master/crawler.c#L365

其在主循环中遍历（Memcached中称为crawl）一定数量的item并且清理，通过加mutex锁来避免与get/set之类的操作产生race：
clean up的锁：https://github.com/memcached/memcached/blob/master/crawler.c#L398
get item的锁：https://github.com/memcached/memcached/blob/master/thread.c#L563

然后主循环第419行通过函数指针调用了crawler_expired_eval()来做具体的expire工作：
https://github.com/memcached/memcached/blob/master/crawler.c#L194
--

然后是getSize()的问题。首先面试题里提到的getSize()好像是要返回当前时间所有“真正”没有expire的元素个数 —— 但现实中什么场景下需要知道这个比较精确的净值呢？而且Redis和Memcached都不支持这一命令（它们返回的count应该都是包括已经expire但没有清除的元素的），总体上感觉getSize()只是一个只是用来面试的伪需求。

不过一定要支持的话也仍然可以用牺牲一点“实时性”的方法。

首先不妨假定expire的时间最长不能设到两天以后，那么最多就是3600 * 24 * 2 = 172800秒。现在开一个长度为172800的int型循环队列S，用数组实现（以支持对任意位置的随机访问），那么只要不到1MB的内存空间。这个队列就是记录未来每一秒内有多少个item将要expire的，每次add/update/remove item时都可以用O(1)时间维护。

同时，维护一个atomic int型的total_live_items变量，每次add/remove item时也是O(1)时间更新。最后，再用一个daemon线程，每隔一秒将total_live_item减去当前这秒对应的队列S的头部值，并将S向后滚动一秒。

这样getSize()直接返回total_live_items的值，就可以保证结果的实时性在1秒以内

当然，也可以将时间尺度分得再细一些，比如每10毫秒一个slot，那么循环队列就要扩大100倍，也就是占用200M不到的空间，也可以接受。

补充内容 (2019-3-11 13:41):
那个“(1) Memcached的item结构中的timestamp部分”的链接应该是：
https://github.com/memcached/mem ... er/memcached.h#L471

magicsets 发表于 2019-3-11 13:39
这个问题我之前在一个回帖里稍微写过一点，复制过来..

Map with expiration可以参考一下比较有名的key-v ...

Redis里的实现：

Try to expire a few timed out keys. The algorithm used is adaptive and will use few CPU cycles if there are few expiring keys, otherwise it will get more aggressive to avoid that too much memory is used by keys that can be removed from the keyspace.

#define ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP 20 /* Loopkups per loop. */


https://github.com/antirez/redis/blob/5.0/src/expire.c#L229

在key空间不是太稀疏的时候，对于带有TTL的keys，随机选取20个，如果5个（概率25%）的key已经过期，就继续做这个操作，使他们过期。

想到一个问题求指教
可能有点trivial
如果用了thread来删除
那size()就可以是constant time直接回传hashmap length了吗

假设CPU单核心, 并且一个thread只会执行0.1单位时间
用一timer预计t=10的时候唤醒并删除某个当下过期的key
是否会在t=9.95切换到main thread
于是t=9.95~10.05的时候执行main thread
导致t=10~10.05的时候执行size()而回传了错误的size?

系统是否会足够聪明知道t=10有个thread要唤醒而保留时间不执行main thread?