¿Por qué no se ordena un Diccionario?

Bueno, por un lado, no está claro si espera que esto sea orden de inserción o orden clave . Por ejemplo, ¿cuál esperaría que fuera el resultado si escribiera:

var test = new Dictionary<int, string>();
test.Add(3, "three");
test.Add(2, "two");
test.Add(1, "one");
test.Add(0, "zero");

Console.WriteLine(test.ElementAt(0).Value);

¿Esperarías "tres" o "cero"?

Da la casualidad de que pienso la implementación actual conserva el orden de inserción siempre que nunca elimine nada, pero no debe confiar en esto . Es un detalle de implementación y eso podría cambiar en el futuro.

Las eliminaciones también afectan esto. Por ejemplo, ¿cuál esperaría que fuera el resultado de este programa?

using System;
using System.Collections.Generic;

class Test
{ 
    static void Main() 
    {
        var test = new Dictionary<int, string>();
        test.Add(3, "three");
        test.Add(2, "two");
        test.Add(1, "one");
        test.Add(0, "zero");

        test.Remove(2);
        test.Add(5, "five");

        foreach (var pair in test)
        {
            Console.WriteLine(pair.Key);
        }
    }     
}

En realidad, es (en mi caja) 3, 5, 1, 0. La nueva entrada para 5 ha usado la entrada vacante usada anteriormente por 2. Sin embargo, eso tampoco se garantizará.

Rehacer (cuando el almacenamiento subyacente del diccionario necesita expandirse) podría afectar las cosas... todo tipo de cosas lo hacen.

Simplemente no lo trate como una colección ordenada. No está diseñado para eso. Incluso si funciona ahora, estás confiando en un comportamiento no documentado que va en contra del propósito de la clase.

Un Dictionary<TKey, TValue> representa una tabla hash y en una tabla hash no hay noción de orden.

La documentación lo explica bastante bien:

Aquí hay muchas buenas ideas, pero dispersas, por lo que intentaré crear una respuesta que lo exponga mejor, aunque el problema ya se haya resuelto.

Primero, un diccionario no tiene un orden garantizado, por lo que lo usa solo para buscar rápidamente una clave y encontrar un valor correspondiente, o enumera todos los pares clave-valor sin importar cuál es el orden.

Si desea un orden, use un OrderedDictionary, pero la desventaja es que la búsqueda es más lenta, por lo que si no necesita un orden, no lo solicite.

Los diccionarios (y HashMap en Java) usan hashing. Eso es O (1) tiempo independientemente del tamaño de su tabla. Los diccionarios ordenados suelen utilizar algún tipo de árbol equilibrado que es O(log2(n)), por lo que, a medida que crecen los datos, el acceso se vuelve más lento. Para comparar, para 1 millón de elementos, eso es del orden de 2 ^ 20, por lo que tendría que hacer del orden de 20 búsquedas para un árbol, pero 1 para un mapa hash. Eso es MUCHO más rápido.

Hashing es determinista. El no determinismo significa que cuando haces hash (5) la primera vez y hash (5) la próxima vez, obtienes un lugar diferente. Eso sería completamente inútil.

Lo que la gente quería decir es que si agrega cosas a un diccionario, el orden es complicado y está sujeto a cambios cada vez que agrega (o potencialmente elimina) un elemento. Por ejemplo, imagine que la tabla hash tiene 500k elementos y usted tiene 400k valores. Cuando agrega uno más, alcanza el umbral crítico porque necesita aproximadamente un 20% de espacio vacío para ser eficiente, por lo que asigna una tabla más grande (digamos, 1 millón de entradas) y vuelve a codificar todos los valores. Ahora todos están en lugares diferentes a los que estaban antes.

Si construye el mismo Diccionario dos veces (lea mi declaración cuidadosamente, EL MISMO), obtendrá el mismo orden. Pero como bien dice Jon, no cuentes con ello. Demasiadas cosas pueden hacer que no sea lo mismo, incluso el tamaño inicialmente asignado.

Esto trae a colación un punto excelente. Es muy, muy costoso tener que cambiar el tamaño de un hashmap. Eso significa que debe asignar una tabla más grande y volver a insertar cada par clave-valor. Por lo tanto, vale la pena asignar 10 veces la memoria que necesita en lugar de tener que hacer un solo crecimiento. Conozca el tamaño de su mapa hash y asigne previamente lo suficiente si es posible, es una gran ganancia de rendimiento. Y si tiene una mala implementación que no cambia de tamaño, puede ser un desastre si elige un tamaño demasiado pequeño.

Ahora, lo que Jon discutió conmigo en mi comentario en su respuesta fue que si agrega objetos a un Diccionario en dos ejecuciones diferentes, obtendrá dos órdenes diferentes. Cierto, pero eso no es culpa del diccionario.

Cuando dices:

new Foo();

está creando un nuevo objeto en una nueva ubicación en la memoria.

Si usa el valor Foo como clave en un diccionario, sin otra información, lo único que pueden hacer es usar la dirección del objeto como clave.

Eso significa que

var f1 = new Foo(1);
var f2 = new Foo(1);

f1 y f2 no ​​son el mismo objeto, incluso si tienen los mismos valores.

Entonces, si los pusiera en diccionarios:

var test = new Dictionary<Foo, string>();
test.Add(f1, "zero");

no esperes que sea lo mismo que:

var test = new Dictionary<Foo, string>();
test.Add(f2, "zero");

incluso si f1 y f2 tienen los mismos valores. Eso no tiene nada que ver con el comportamiento determinista del Diccionario.

Hashing es un tema increíble en informática, mi favorito para enseñar en estructuras de datos.

Eche un vistazo a Cormen y Leiserson para obtener un libro de alto nivel sobre árboles rojos y negros frente a hashing. Este tipo llamado Bob tiene un gran sitio sobre hashing y hashes óptimos:http://burtleburtle.net/bob