A C# Dictionary is a data structure that holds a pair values instead of a single value. It is useful across a variety of sophisticated algorithms.

A C# Dictionary structure is useful because values are stored in pairs, a key component and a value component. Keys are used to access values, thus keys have to be unique, while values do not need to be.

The Dictionary data structure is a very general concept in programming. The data structure can be implemented in a several ways, each of which has its advantages and disadvantages.

There are two things to consider, the speed of inserting elements into a dictionary and the speed of searching elements. (Other operations such as remove are similar in speed to either insert or search.)

First consider insert speed. One thing the dictionary can do is to sort elements as they get inserted. This would be a relatively slow process. Second option is to enter elements in random (or apparently random) order, which would be very fast. The third option is to keep elements in the order in which they were inserted. Intuitively it’ll be faster than inserting items in order but slower than inserting them randomly.

Second consider search speed. If elements are in the order they were inserted, search time will be medium speed so to speak (O(n log n)). If elements are in sorted order, then searching can be done with binary search, which is a lot faster (O(log n)). Finally if elements were in random order, we can look for an element in the same “random” way, making search speed the fastest (O(1)).

Bringing us to three dictionary implementation in C#.

Dictionary – This class preserves the order in which items were inserted (“medium” insert speed) and thus searches with medium speed O(n log n).

SortedDictionary – This class sorts items are they are inserted (slow insert speed), but searches faster (with O(log n) speed).

Hashtable – This class inserts items “randomly” (based on hash value of element) leading to fastest insert times and fastest searching times (O(1)). Note that this class sounds too good to be true because it is. Performance speeds are only that good if the hash values of elements minimize collision (read more on hash tables). Minimizing collisions usually requires some knowledge of the types of objects being stored beforehand.