How the Dictionary is internally maintained ?

Question

When i say

Dictionary<int,string>

is it equivalent to two different arrays such as:

int[] keys =new int[] { 1, 2, 3 };
string[] values=new string[]{"val1","val2","val3"};

Answer 1

No, it's a Hash Table. Well it's not exactly a hash table, but it's really closely related.

http://en.wikipedia.org/wiki/Hash_table.

http://www.kirupa.com/net/dictionary_hashtable.htm

Answer 2

It's all clearly written on MSDN:

The Dictionary(Of TKey, TValue) generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary(Of TKey, TValue) class is implemented as a hash table.

Answer 3

That's not too far off. Looking at the source code in Reflector, it seems three internal collections are used:

private Entry<TKey, TValue>[] entries;
private KeyCollection<TKey, TValue> keys;
private ValueCollection<TKey, TValue> values;

Note that there is also a int[] buckets variable to keep track of the buckets required in the case of hash-code collisions.

These variables' purposes should all be fairly self-explanatory. This is not particularly surprising, anyway, since the Dictionary class is known and documented to provide (ideally, with one item per bucket) O(1) lookup time.

Answer 4

It is hashtable. For each key Dictionary calculates its hash code, and uses this as a pointer to place where value should reside. If there are two keys matching the same hash code, such situation is called collision and internally for this special case Dictionary uses binary tree.

Algorithmic complexity of Dictionary(hashtable) is O(1) and in worst case O(log(N)) (worst case means we deal only with collisions), where N is a number of elements in Dictionary.

Answer 5

As Noldorin (+1 :) ) mentioned, you can use the Reflector from Red-Gate (Plugins) to have a look at the internals of the Freamwork (which is quiet handy).

Bobby