Undocumented feature of Dictionary?

Question

Dictionary<string, int> testdic = new Dictionary<string, int>();
testdic.Add("cat", 1);
testdic.Add("dog", 2);
testdic.Add("rat", 3);
testdic.Remove("cat");
testdic.Add("bob", 4);

Fill the dictionary and then remove the first element. Then add a new element. Bob then appears at position 1 instead of at the end, therefore it seems to remember removed entries and re-uses that memory space?

Is this documented anywhere because I can't see it on MSDN and has caused me a day of grief because I assumed it would just keep adding to the end.

Answer 1

It's not documented because it's just an implementation detail.

The implementation could change at any time. (And unless you've closely examined the source code then you can't even be sure that your assumptions about the current implementation are accurate.)

The Dictionary<K,V> type does not guarantee to store its elements in any particular order, and you shouldn't rely on any undocumented behaviour that you happen to observe. A dictionary is a map from keys to values, not an ordered list.

From the MSDN documentation:

For purposes of enumeration ... [t]he order in which the items are returned is undefined.

Answer 2

A dictionary is not sorted, so you should never assume anything about the order of the elements.

The implementation is likely to attempt to be the most efficient. This might mean that the current implementation, exhibits the behaviour you are seeing. But it is not documented to do so, so you should not rely on it.