'Dictionary Types' In .Net

Question

I've used generic dictionaries in C# a fair bit. Things like:

var example = new Dictionary<int, string> { 
                                        { 0, "Test0" }, 
                                        { 1, "Test1" } };

I vaguely remember being told that, before generics came along, you could use a Hashtable(). Basically the same thing, but without a specific type (so value types are going to be boxed, I think).

var example2 = new Hashtable {
                          {0, "Test0"},
                          {1, "Test1"} };

And there are questions like this one discussing why we prefer Dictionary over Hashtables (Why is Dictionary preferred over hashtable?).

But what about all the other 'dictionary' types?

• SortedDictionary<K,V> - Seems to work like Dictionary but it's .Keys collection is sorted. I'm not sure why you'd care though.
• OrderedDictionary is non-generic like a Hashtable, but I can't wrap my head around what's different than a Hashtable. http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx mentions that it's keys are not sorted like a SortedDictionary, so I just plain don't see why or when to use this.
• ListDictionary - Smaller/Faster than Hashtable (but is it faster than a generic Dictionary?) when the number of elements is less than 10. Again, I'm at a loss for when you'd use this.

I'm also confused about SortedList<K,V>. When I hear List I don't think key/value pairs (maybe I should?). It implements IDictionary<TKey,TValue>. From this question, I can see that it differs from SortedDictionary in it's performance characteristics (What's the difference between SortedList and SortedDictionary?)

Can Someone Briefly Explain When To Use Which Dictionary Type?

For the sake of simplicity, assume I have access to .Net 4.5 or higher...so maybe there is no situation where Hashtable is useful any more?

Answer 1

Use Dictionary<TKey,TValue>. There's no reason to use the older non-generic hash table.

---

Ordered Dictionary

If the insertion order of the items in the dictionary matter, then use the OrderedDictionary.

Say I have a mapping of children to their favorite ice cream.

OrderedDictioanry childToIcecream = new OrderedDictionary();
childToIcecream["Jake"] = "Vanilla";
childToIcecream["Kevin"] = "Chocolate";
childToIcecream["Megan"] = "Strawberry";

Each day one child gets an extra scoop in rotation. We could take the day number (Sunday = 0, Monday = 1..) mod it by the number of children, and pull their index from the dictionary to select whose lucky day it is. This of course only works if the dictionary maintains the order. Otherwise I would need a separate List<string> just for maintaining the order. You get key/value pairs and order in one container.

It's unfortunate there's no generic ordered dictionary, but someone posted an implementation here,

---

Sorted Dictionary

Same for sorted dictionary. If you had a requirement that the key/value pairs needed to be sorted this would save you time to keep it always sorted rather than have to do an expensive sort operating when you needed it to be.

SortedDictionary<char, string> letterToWord = new SortedDictionary<char, string>();
letterToWord['b'] = "bat";    
letterToWord['c'] = "cat";    
letterToWord['a'] = "apple";

Say you have a dictionary like the above, except the user can build the letter associations at runtime. You always want to display it in alphabetical order, so it makes sense to always keep it sorted as each new item is added.

---

TLDR; Always use Dictionary<TKey, TValue> unless you have a circumstance that requires it to be ordered or sorted.

Answer 2

Both Dictionary and Hashtable indicate the use of some kind of indexing of the data. Consulting the index takes some time, making it slower at small numbers of elements.

A List does not use an index, and items are typically added at the end. When inserting items, the other items "physically" move to create room for the new element, and when removing items, the other items move to close the gap.

A Dictionary typically does not preserve order, and may contain gaps in memory. When adding items, these gaps may be filled by the new item. Iterating over the Dictionary would then return the items in a different order.

Sorting is a different kind of ordering - it does not preserve the order in which items were added, but follows rules to determine the place of added items.

It's funny that ArrayList became List<T> when the genericalisation happened, and Hashtable became Dictionary<T, U> - both removing the technical aspect from the name, leaving only the name of the abstraction.