HashSet<T> versus Dictionary<K, V> w.r.t searching time to find if an item exists
HashSet vs List vs Dictionary performance test, taken from here.
Add 1000000 objects (without checking duplicates)
Contains check for half the objects of a collection of 10000
Remove half the objects of a collection of 10000
I assume you mean Dictionary<TKey, TValue>
in the second case? HashTable
is a non-generic class.
You should choose the right collection for the job based on your actual requirements. Do you actually want to map each key to a value? If so, use Dictionary<,>
. If you only care about it as a set, use HashSet<>
.
I would expect HashSet<T>.Contains
and Dictionary<TKey, TValue>.ContainsKey
(which are the comparable operations, assuming you're using your dictionary sensibly) to basically perform the same - they're using the same algorithm, fundamentally. I guess with the entries in Dictionary<,>
being larger you end up with a greater likelihood of blowing the cache with Dictionary<,>
than with HashSet<>
, but I'd expect that to be insignificant compared with the pain of choosing the wrong data type simply in terms of what you're trying to achieve.
From MSDN documentation for Dictionary<TKey,TValue>
"Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table."
With a note:
"The speed of retrieval depends on the quality of the hashing algorithm of the type specified for TKey"
I know your question/post is old - but while looking for an answer to a similar question I stumbled across this.
Hope this helps. Scroll down to the Remarks section for more details. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx