具有 128 位键的基于时间的字典/哈希表，即从字典中超时一个值

本文关键字：字典 中超 超时 一个 哈希表 于时间 时间 具有 | 更新日期: 2023-09-27 17:55:09

我需要制作一个基于时间的字典哈希表，它的大小不会无限增长。

通过"基于时间"，我的意思是，如果我要在时间 X 添加字典，我希望该项目在 X+Y 时间不存在。Y 是超时期限。

我愿意将时间存储在字典中或作为键或值中的结构。

上下文：

我

收到我们正在使用的库调用的"回调"，它给了我 4 条信息（时间、键、值、操作类型）。

操作类型可以是开始或结束（还有其他的，但没关系）。

因此，如果我在 X 之后的 Y 时间段内结束，我很乐意使用这些有用的信息。否则我可以丢弃它。

问题：

这基本上是一个计时器线程，每隔 Y 间隔清理一次字典，并且主线程不断从回调向这个字典中添加内容吗？

我

使用字典来做到这一点，没有计时器，即使我删除了我能够"加入"的元素，它似乎也会无限增长。

另外，是否有某种 .NET 库可以执行此类操作？

具有 128 位键的基于时间的字典/哈希表，即从字典中超时一个值

通过使用优先级队列（或仅最小堆）和关联的字典，可以避免定期扫描整个集合。遗憾的是，.NET Framework 不包含优先级队列集合，但有一些可用的集合。不久前我发布了一个简单的二进制堆。

这里的想法是，当您添加项目时，您将它添加到字典和堆中。如果要按键查找项目，请在字典中查找它。如果要从堆中删除第一项，可以从堆中获取它，并使用键（这是数据的一部分）将其从字典中删除。

美妙之处在于，您不必扫描整个字典来确定需要删除哪些字典，而是可以查看堆的顶部：

while (heap.Count > 0 && heap.Peek().ExpirationTime < time)
{
    var item = heap.RemoveRoot();
    dictionary.Remove(item.Key);
}

此方法的主要缺点是它需要更多的内存，因为您有字典条目的开销。

相关文章：