System.Collections.Generic.Dictionary foreach order

Question

Looking at some code that iterates through a Dictionary, and it appears that the code relies on access by ascending order of the key values, using foreach.

The MSDN documentation states that "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.".

Yet during execution the code does access each KeyValuePair in the 'correct' order.

I've updated the code to order the items explicitly, but was interested if anyone had an explanation as to why the original code behave as the author expected.

#if pl
my $hdr = '
  Test script.
  Once per session, run
    "C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\bin\vcvars32.bat"
   or equivalent.
  Run "perl FooInstallTest.cs".
';

use strict;
use Test::More tests => 2;
use sigtrap 'handler', \&cleanup, 'normal-signals';

my @reference = (qw(
));


sub main {
   my $ret;
   my $prog = "FooInstallTest.exe";

   my $cmd =
    "csc /debug " .
    "/nologo " .
    "/platform:x86 " .
    "/out:FooInstallTest.exe " .
    "/d:TRACE /d:DEBUG " .
    "/define:FooInstallTest " .
    ""
   ;

   foreach my $reference (@reference) {
      $cmd .= ('/reference:' . $reference . " ");
   }

   $cmd .=
    "FooInstallTest.cs " .
    "";

   unlink($prog);

   foreach my $reference (@reference) {
      system("xcopy /y $reference .");
   }

   1 && print("$cmd\n");
   $ret = system($cmd);
   is($ret, 0, "Compile.");

   my $run = $prog;
   1 && print("$run\n");
   $ret = system($run);
   is($ret, 0, "Run.");

   cleanup();
}

sub cleanup {
   foreach my $reference (@reference) {
      $reference =~ s/.*\\//;
      (-e $reference) && (unlink($reference));
   }
}

main();

__END__
#endif

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Data;
using System.Data.Linq;
using System.Diagnostics;
using System.Linq;

#if FooInstallTest
#endif


#if FooInstallTest
public class FooInstallTest {

   public static int Main(String[] args) {
      FooInstallTest foo_install_test = new FooInstallTest();
      return foo_install_test.main();
   }

   public int main() {
      UpdateFooDB();
      return 0;
   }

   void UpdateFooDB() {
      string serverPath = 
       @"Server=.\sqlexpress;Trusted_Connection=True;Database=foo;";

      System.Collections.Generic.Dictionary<double, string> upgrades = 
       new System.Collections.Generic.Dictionary<double, string> {
         {1.2,   "foo_1_2.sql"},
         {1.3,   "foo_1_3.sql"},
         {1.6,   "foo_1_6.sql"},
         {1.7,   "foo_1_7.sql"},
         {1.8,   "foo_1_8.sql"},
         {1.9,   "foo_1_9.sql"},
         {2.0,   "foo_2_0.sql"},
         {2.01,  "foo_2_01.sql"},
         {2.02,  "foo_2_02.sql"},
         {2.03,  "foo_2_03.sql"},
         {2.031, "foo_2_031.sql"},
         {2.032, "foo_2_032.sql"},
         {2.033, "foo_2_033.sql"},
         {2.034, "foo_2_034.sql"},
         {2.035, "foo_2_035.sql"},
         {2.036, "foo_2_036.sql"},
         {2.037, "foo_2_037.sql"},
         {2.038, "foo_2_038.sql"},
         {2.039, "foo_2_039.sql"},
         {2.040, "foo_2_040.sql"},
         {2.041, "foo_2_041.sql"},
         {2.042, "foo_2_042.sql"},
      };
      UpdateDatabase(serverPath, upgrades);
   }

   void UpdateDatabase(
    string serverPath, 
    System.Collections.Generic.Dictionary<double, string> upgrades
   ) {
      //ing (SqlConnection conn = new SqlConnection(serverPath))
      {
         //nn.Open();

         double targetVersion = upgrades.LastOrDefault().Key;
         //uble currentVersion = GetVersion(conn);
         double currentVersion = 1.0;

         string diagMessage = String.Format(
          "Installer: Update Database: current: [{0}], target: [{1}]"
          ,currentVersion.ToString()
          ,targetVersion.ToString()
         );
         Console.WriteLine(diagMessage);

         foreach (var item in upgrades) {
            if ((currentVersion < targetVersion) && (currentVersion < item.Key)) {
               diagMessage = String.Format(
                "Execute Update: current: [{0}], key: [{1}], file: [{2}]"
                ,currentVersion.ToString()
                ,item.Key.ToString()
                ,item.Value.ToString()
               );
               Console.WriteLine(diagMessage);
               //ecuteSqlFile(conn, item.Value);
               currentVersion = item.Key;
            }
         }
      }
   }
}

#endif

Answer 1

I looked at the current implementation. The dictionary uses two arrays internally: one for the entries containing the key, the value and other infos, and another (called buckets) using the hash code as index and containing the indexes of the corresponding entries within the entries array. The buckets info is indeed unsorted and unordered, but the entries array is ordered, i.e. it keeps the entries in the order they have been added to the dictionary. These entries are however not sorted, i.e. if you add the entries in an unsorted way, they will remain unsorted.

When the dictionary is enumerated the entries array is enumerated. This explains the order you have seen.

Don't rely on this behavior. It could change in future, if Microsoft changes the implementation.

Answer 2

By chance and arbitrary implementation details. It is explicitly not guaranteed and should not be relied upon. It could behave differently on different .NET frameworks and different implementations (mono, etc).