Alternative to Dictionary for doing fast key lookups?

Question

I run into situations where I need to keep track if I've processed a particular value. In these cases, I use Dictionary(Of TKey, TValue) to keep track of the values that I've processed. Basically, as each value is processed, I insert the processed value into as key into the dictionary. When I want to see if I've processed that value, I use the ContainsKey method to see if the value exists in the collection.

This works well, but I do have to insert something in the value side of the key-value pair. I would just use a List(Of T) but I want the performance of the hash table lookup that Dictionary provides. Is there a data collection in .Net that is more suitable for this purpose?

Answer 1

I would suggest a HashSet<T>. You could just enter the key, if all you need to know is that the key has already been used.

It's really simple, too:

if (myHashSet.Add(key))
{
    // item wasn't in the hash set, so process it.
}

Add is like "add if not there." It returns true if the item was added. It returns false if the item was already in the collection.

Or, you can use Contains to test, and then Add to add.

Answer 2

On .NET 3.5 or later, you can use a HashSet for that purpose. The methods you need are called Add and Contains. Both operations have time complexity O(log n), as opposed to O(n) for a List.