支持存活时间的HashMap
设计一个HashMap，需要完成
我能想出来O(N)的方法和O(logN)的方法，但是我觉得都不是面试官想要的。求教能不能有O(1)的方法。
https://www.1point3acres.com/bbs ... read&tid=459371
https://www.1point3acres.com/bbs ... read&tid=203157
https://www.1point3acres.com/bbs/thread-230236-1-1.html
这个put和get O（1）都好办。
不知道这个size()是不是一定要指还活着的keys。如果是，那么这个size（）比较难想。如果不用多线程的话，任何时间别人叫size（）都能正确回答，我能想到的也就只有 O（Log N）而且这样也会导致put变成 O（Log N）了。
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已经过期，就继续做这个操作，使他们过期。
设计一个HashMap，需要完成
- put(key, value, ttl)
- get(key)
- size()
我能想出来O(N)的方法和O(logN)的方法，但是我觉得都不是面试官想要的。求教能不能有O(1)的方法。
https://www.1point3acres.com/bbs ... read&tid=459371
https://www.1point3acres.com/bbs ... read&tid=203157
https://www.1point3acres.com/bbs/thread-230236-1-1.html
这个put和get O（1）都好办。
不知道这个size()是不是一定要指还活着的keys。如果是，那么这个size（）比较难想。如果不用多线程的话，任何时间别人叫size（）都能正确回答，我能想到的也就只有 O（Log N）而且这样也会导致put变成 O（Log N）了。
| 这个问题我之前在一个回帖里稍微写过一点，复制过来.. 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 |
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已经过期，就继续做这个操作，使他们过期。
