¿Por qué las entradas tienen un orden adicional en un diccionario .Net?

Question

Acabo de ver este comportamiento y estoy un poco sorprendido...

Si agrego 3 o 4 elementos a un Diccionario y luego hago un "Para cada uno" para obtener todas las claves, aparecen en el mismo orden en que las agregué.

La razón por la que esto me sorprende es que se supone que un Diccionario es una HashTable internamente, por lo que esperaba que las cosas salieran en CUALQUIER orden (ordenadas por el hash de la clave, ¿verdad?)

¿Que me estoy perdiendo aqui?¿Es este un comportamiento con el que puedo contar?

EDITAR:Bien, ya pensé en muchas de las razones por las que esto podría suceder (como la lista separada de entradas, si esto es una coincidencia, etc.).Mi pregunta es, ¿alguien saber ¿Cómo funciona esto realmente?

Answer 1

Si usa .NET Reflector en las bibliotecas de clase 3.5, puede ver que la implementación de Dictionary en realidad almacena los elementos en una matriz (que se redimensiona según sea necesario), y agrega índices a esa matriz. Al obtener las claves, ignora por completo la tabla hash e itera sobre la matriz de elementos. Por este motivo, verá el comportamiento que ha descrito ya que se agregan nuevos elementos al final de la matriz. Parece que haces lo siguiente:

add 1
add 2
add 3
add 4
remove 2
add 5

obtendrá 1 5 3 4 porque reutiliza las ranuras vacías.

Es importante tener en cuenta, como lo han hecho muchos otros, no puede contar con este comportamiento en versiones futuras (o pasadas). Si desea que su diccionario se ordene, entonces hay una SortedDictionary para este propósito.

Answer 2

Un diccionario recupera elementos en orden hash. El hecho de que salieron en orden de inserción fue una coincidencia total.

La documentación de MSDN dice:

  

El orden de las claves en KeyCollection no está especificado, pero es el mismo orden que los valores asociados en ValueCollection devueltos por la propiedad Values.

Answer 3

No puede contar con este comportamiento, pero no es sorprendente.

Considere cómo implementaría la iteración clave para una tabla hash simple. Tendría que iterar sobre todos los cubos de hash, independientemente de si tenían algo o no. Obtener un pequeño conjunto de datos de una gran tabla hash podría ser ineficiente.

Por lo tanto, podría ser una buena optimización mantener una lista de claves separada y duplicada. Usando una lista de doble enlace, aún obtiene inserción / eliminación de tiempo constante. (Mantendría un puntero del cubo de tabla hash de regreso a esta lista). De esa manera, la iteración a través de la lista de teclas depende solo del número de entradas, no del número de cubos.

Answer 4

Creo que esto proviene de la antigua época de .NET 1.1, donde había dos tipos de diccionarios, "ListDictionary" y "HybridDictionary". ListaDiccionario era un diccionario implementado internamente como una lista ordenada y se recomendaba para "pequeños conjuntos de entradas".Entonces tuviste Diccionario híbrido, que inicialmente se organizó internamente como una lista, pero si crecía más allá de un umbral configurable se convertiría en una tabla hash.Esto se hizo porque históricamente los diccionarios basados ​​en hash se consideraban caros.Hoy en día eso no tiene mucho sentido, pero supongo que .NET simplemente basó su nueva clase genérica Diccionario en el antiguo HybridDictionary.

Nota:De todos modos, como ya señaló alguien más, deberías nunca contar con el orden del diccionario para cualquier cosa

Answer 5

Una cita de MSDN :

  

El orden de las teclas en el   Dictionary & Lt; (Of & Lt; (TKey,   TValue & Gt;) & Gt;). KeyCollection es   sin especificar, pero es el mismo orden   como los valores asociados en el   Dictionary & Lt; (Of & Lt; (TKey,   TValue & Gt;) & Gt;). ValueCollection   devuelto por el Diccionario < (Of < (TKey,   TValue & Gt;) & Gt;). Propiedad de valores.

Answer 6

¿Con qué claves agregó en su prueba y en qué orden?

Answer 7

Sus entradas pueden estar todas en el mismo depósito de hash en el diccionario. Cada depósito es probablemente una lista de entradas en el depósito. Esto explicaría las entradas que vuelven en orden.

Answer 8

Por lo que sé, esto no debería ser un comportamiento en el que confiar. Para verificarlo rápidamente, use los mismos elementos y cambie el orden en que los agrega al diccionario. Verá si los recupera en el orden en que se agregaron, o fue solo una coincidencia.

Answer 9

Hasta cierto tamaño de lista, es más barato verificar cada entrada en lugar de hash. Eso es probablemente lo que está sucediendo.

Agregue 100 o 1000 elementos y vea si todavía están en el mismo orden.

Answer 10

Odio este tipo de " por diseño " funcionalidades Creo que cuando le da a su clase un nombre genérico como & Quot; Dictionary & Quot ;, también debería comportarse & Quot; como generalmente se esperaba & Quot ;. Por ejemplo, std :: map siempre mantiene sus valores clave ordenados.

Editar: aparentemente la solución es usar SortedDictionary, que se comporta de manera similar a std :: map.

Answer 11

La pregunta y muchas de las respuestas parecen malinterpretar el propósito de una tabla hash o diccionario. Estas estructuras de datos no tienen comportamientos específicos con respecto a la enumeración de los valores (o de hecho las claves) de los elementos contenidos en la estructura de datos.

El propósito de un diccionario o tabla hash es poder buscar eficientemente un valor específico dada una clave conocida. La implementación interna de cualquier diccionario o tabla hash debería proporcionar esta eficiencia en las búsquedas, pero no necesita proporcionar ningún comportamiento específico con respecto a las enumeraciones o & Quot; para cada & Quot; escriba iteraciones en los valores o claves.

En resumen, la estructura de datos interna puede almacenar y enumerar estos valores de la manera que desee, incluido el orden en que se insertaron.