我需要简单的缓存结构（在python中，但这并不重要），有一些特定的要求：
- 多达数百万个小对象（平均 100 字节）
- 速度是关键（放和得到），我预计操作时间约为几微秒
- 只有一个线程访问它 - 所以它可以全部在内存中（不需要持久性）
- 密钥是 MD5 哈希（如果重要的话）
- 缓存有一个过期时间，全局 - 每个密钥都应在过期时间后从缓存中删除，从第一次放置的时间开始计算
现在，重点是如何实现过期 - 因为其他一切都可以使用简单的字典来完成。最简单的解决方案 - 定期迭代所有数据并删除过期的密钥 - 可能会将整个缓存锁定太久。可以通过在每个清理过程中迭代部分数据来改进它 - 但仍然需要一些时间（或者清理速度不够快）。此外，逐个删除密钥看起来像是浪费 CPU - 因为它们可以批量删除（不必在过期后立即删除 - 我们可以提供一些额外的 RAM 来将过期密钥保留更长的时间）。
在检索过程中检查密钥是不够的（尽管应该这样做，以免返回过期的密钥） - 因为许多密钥永远无法检索，然后它们将永远保留（或太久）。
这个问题的大多数答案都建议使用 memcached，但我认为这会浪费 CPU，特别是当我保留可以通过引用放入字典的对象时，但使用 memcached 它们必须（反）序列化。
我有一些想法如何实现这一点：将数据拆分为时间片，实际上有几个字典 - 例如，如果过期时间为 60 秒，那么我们（最多）有 4 个字典，每 20 秒我们添加新一个 - 放置新键，并删除第 4 个 - 我们将在 60 秒前添加键。这使得清理速度非常快，但代价是检索时间，您需要在 4 个字典中查找而不是一个（RAM 使用率增加了 33%）。
所以最后的问题是：有没有更好的解决方案？或者也许我错了，提到的一些解决方案（一个接一个地删除密钥）会更好更快？我不想重新发明轮子，但在网上找不到任何好的解决方案。
只有实验才能告诉你哪个更好。
这是另一个需要考虑的简单想法：按到达顺序链接链列表中的所有键。每次检索键时，请从列表的开头循环访问，并从列表和字典中删除所有过期的项目。
哈希表的一种实现是为每个哈希值存储（键，值）的列表。您可以将其扩展到存储每个哈希值的列表（键、插入时间、值）。在获取和设置中，您可以在扫描感兴趣的密钥时丢弃过期的项目。
是的，它可能会在哈希表中保留过期项目任意长的时间，但平均只有 O（N） 个项目，其中 N 是哈希表的大小。
此方法的优点是没有进行并发清理，并且开销或多或少是恒定的。
如果你关心速度，你必须用C而不是Python编写代码。
使用定时服务（在 Python 中调度？）在 N 秒后触发事件。对于每个密钥，都会安排一个计时器事件（它们非常轻量级）并让它删除密钥。
Java对应的是：http://docs.oracle.com/javase/7/docs/api/java/util/Timer.html