我有必要做一个基于时间的词典哈希表的大小，它不是无限增长。

I have a need to make a time-based dictionary hashtable that doesn't grow infinitely in size.

通过基于时间，我特别的意思是，如果我要添加一个词典在时间X，我想的项目不是在X + Y的时间存在。 Y是超时时间。

By "time-based", I specifically mean that if I were to add a dictionary at time X, I would like the item to not exist at X+Y time. Y being the timeout period.

我愿意保存时间在词典或作为键或值的结构。

I'm willing to store the time in the dictionary or as a structure in the key or value.

背景：

我得到的回调调用，我们使用的是这给了我4条信息（时间，键，值，operationType）。

I get "callbacks" called by a library that we're using which gives me 4 pieces of information (time, key, value, operationType).

operationType可以是开始或结束（有其它的，但它并不重要）。

operationType can be start or end (there are others, but it doesn't matter).

所以，如果我得到十大之后在Y时间内结束了，我很高兴利用这个有用的信息。否则，我可以放弃它。

So if I get an end within the Y time period after X, I'm happy to use this useful information. Otherwise I can discard it.

问：

这基本上是一个计时器线程清理字典每Ÿ区间，而主线程不断从回调中添加的东西到这个字典吗？

Is this basically a Timer-thread that cleans up the dictionary every Y intervals, and the main thread keeps adding stuff into this dictionary from the callback?

我用字典来做到这一点，没有一个计时器，它似乎无限增长，即使我删除，我能以加盟的元素。

I used Dictionary to do this, without a timer and it seemed to grow infinitely even though I removed the elements that I was able to "join".

此外，有没有某种形式的.NET库，做这样的事？

Also, is there some sort of .NET library that does something like this?

推荐答案

您可以消除不必使用优先级队列（或只是一个最小堆）和相关的字典定期扫描整个集合。不幸的是，在.NET Framework不包括一个优先队列集合，但也有一些可用的。我发表了简单的二进制堆而回。

You can eliminate having to scan the entire collection periodically by using a priority queue (or just a min heap) and an associated dictionary. Unfortunately, the .NET Framework doesn't include a priority queue collection, but there are some available. I published a simple binary heap a while back.

这里的想法是，当你加入一个项目，你将它添加到字典和堆。如果你想查找某个项目由它的键，你看它在字典中。如果你想从堆中取出的第一个项目，你从堆中得到它，并使用密钥（也就是数据的一部分），从字典中删除。

The idea here is that when you add an item, you add it to the dictionary and to the heap. If you want to look up an item by its key, you look it up in the dictionary. If you want to remove the first item from the heap, you get it from the heap and, using the key (which is part of the data), remove it from the dictionary.

的好处在于，而不是扫描整个字典，以确定需要那些被删除，你可以偷看堆的顶部：

The beauty is that, rather than having to scan the entire dictionary to determine which ones need to be removed, you can peek at the top of the heap:

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

的主要缺点这种方法是，它需要更多的内存，因为你有字典项的开销。

The primary drawback to this approach is that it takes a bit more memory because you have the overhead of the dictionary entries.