tags:

views:

385

answers:

2

The description of System.Collection.Specialized.HybridDictionary is this:

Implements IDictionary by using a System.Collections.Specialized.ListDictionary while the collection is small, and then switching to a System.Collections.Hashtable when the collection gets large.

Is there an equivalent Generic implementation?

+3  A: 

Not that I know of. However, is there a proven need? Hash tables don't have a large overhead, even for very small N it should be faster just to use the normal hash table than to search linearly.

EDIT I don't have a benchmark to prove it but just by comparing the algorithms I conclude that hash tables should be faster than linear search as soon as N > 6 on average (for string keys or similar nontrivial hashes) so there is really no reason for a hybrid implementation.

The argument is as follows. In linear search, on average half the elements have to be compared to your input, i.e. N / 2. In a hash table, it is known that the expected number of comparisons is 2, regardless of input size (for very small hash tables with a load factor of less than 0.1 this is actually approaching 1). Additionally, the hash has to be calculated. This results in 3 operations on your input, plus a very small overhead that can be neglected. Thus, we search for which N it is true that 3 > N / 2, which is trivially N > 6.

Note that the above calculation is actually wrong because for this small number of elements, the load factor of .NET's Dictionary will be much less than 0.1. The tipping point is therefore actually even lower.

Konrad Rudolph
+1  A: 

You can use Sorted Dictionary

MSDN:

The SortedDictionary<(Of <(TKey, TValue>)>) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<(Of <(TKey, TValue>)>) generic class. The two classes have similar object models, and both have O(log n) retrieval.

You can also search in PowerCollections. Maby you will find something that will satisfy you.

Jarek
`SortedDictionary` is another type altogether, with much worse runtime behaviour in cases where you'd normally use hash tables. As the name indicates, `SortedDictionary`s are useful (only) if you additionally need your data sorted.
Konrad Rudolph