2

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

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.

CONTEXT:

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

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

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.

QUESTION:

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".

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

svick
  • 236,525
  • 50
  • 385
  • 514
halivingston
  • 3,727
  • 4
  • 29
  • 42
  • Also, Given that I can allocate as much space as I want (once), i.e. an array. And my key is 128-bit, is there a way to generate a hashtable over an array such that keys never collide? Does anyone have pointers for such a hashing function? – halivingston Jan 23 '13 at 00:00
  • 3
    Have you looked at the .NET Cache classes? http://msdn.microsoft.com/en-us/library/dd997357.aspx – Ian Mercer Jan 23 '13 at 00:03
  • I'd take a look at the ASP.NET Cache as a starting point. I know you are doing this in a class library, but looking at how someone else did this might giev you ideas. – Sam Axe Jan 23 '13 at 00:04
  • Ah, ok. Let me add the time is specified by the callback, and is not physical time per se. That is the callback could be called 10 minutes after the interval. So I need the time field to be read by the dictionary. – halivingston Jan 23 '13 at 00:35
  • More info about the key. Are they sequential? Why 128 bit? – paparazzo Jan 23 '13 at 04:17

1 Answers1

1

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.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • “priority queue (or just a min heap)” That doesn't make much sense, min heap is one possible implementation of priority queue. – svick Jan 23 '13 at 03:48
  • @svick: That's one way to look at it. I tend to think of a heap as a more general data structure. – Jim Mischel Jan 23 '13 at 14:02