Why does iterating a Dictionary's values return in the same order as insertion, when it should be be indeterministic?

Question

As we all know, Dictionary in C# theoretically does not preserve the order of the inserted elements.

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey,TValue> structure representing a value and its key. The order in which the items are returned is undefined.

Source

However, when I insert random keys into the dictionary and read them back in a foreach loop, they always come back in the insertion order.

Random rand = new Random();
var map = new Dictionary<int, int>();
for (int i = 0; i < 10; ++i)
{
    var key = rand.Next(1000000000);
    var value = 0;

    Console.WriteLine($"Key: {key}");

    if (map.ContainsKey(key))
        continue;

    map.Add(key,value);
}

Console.WriteLine("Reading Back..");
foreach (var pair in map)
{
    Console.WriteLine($"Key: {pair.Key}");
}

The output from this code is like this:

Key: 593548784  
Key: 765023454  
Key: 1460074  
Key: 913286745  
Key: 804757753  
Key: 281489700  
Key: 395818098  
Key: 227086287  
Key: 323530161  
Key: 629618868

Reading Back..

Key: 593548784  
Key: 765023454  
Key: 1460074  
Key: 913286745  
Key: 804757753  
Key: 281489700  
Key: 395818098  
Key: 227086287  
Key: 323530161  
Key: 629618868

I'm surprised because I thought when elements are inserted to dictionary, hash key is determined by taking mod N of the key field, which would mean the order would be lost (unless N is extremely large).

Does anyone know why the behavior is like this?

Answer 1

The fact that the Dictionary doesn't support sorting doesn't mean that you will get your data in a random order every time you read it. You'll usually iterate through it in the same order as it was inserted into, but it's not guaranteed:

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair structure representing a value and its key. The order in which the items are returned is undefined.

The original order will probably be lost when you start removing, inserting and adding additional entries. You can find more details in answers of this question.

Here is sample code where items are removed

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace SO59038883
{
    internal class Program
    {
        static void Main()
        {
            // keep track of the key that have been inserted
            // so we can remove a random
            var trackedKeys = new List<int>();

            var rand = new Random();
            var map = new Dictionary<int, int>();
            for (var i = 0; i < 20; i++)
            {
                var key = rand.Next(1000000000);
                trackedKeys.Add(key);
                Console.WriteLine($"Key: {key}");

                if (map.ContainsKey(key))
                    continue;

                map.Add(key, i);

                // Let's remove three random keys
                // at set interval
                if (i == 5 || i == 10 || i == 15)
                {
                    // get a random key from our tracked key list
                    var index = rand.Next(trackedKeys.Count);
                    var keyToRemove = trackedKeys[index];
                    map.Remove(keyToRemove);
                }
            }

            Console.WriteLine("Reading Back..");
            foreach (var pair in map)
            {
                Console.WriteLine($"Key: {pair.Key} - Value: {pair.Value}");
            }

            if (Debugger.IsAttached)
            {
                Console.WriteLine("Press any key to continue...");
                Console.ReadKey();
            }
        }
    }
}

Answer 2

The way Dictionary is implemented doesn't store items directly into a hash table, but instead uses a hash table of integers which is then used to identify items within a growing array. If nothing is ever removed from a Dictionary, this array will contain items in the order that they were added; such behavior has been consistent from the beginnings of .NET. If items are removed, the order in which future items get placed in the array may be much less predictable, and I would not particularly expect it to be consistent among all .NET versions.