El orden de los elementos en el diccionario

107

Mi pregunta es sobre la enumeración de elementos del diccionario.

// Dictionary definition
private Dictionary<string, string> _Dictionary = new Dictionary<string, string>();

// add values using add

_Dictionary.Add("orange", "1");
_Dictionary.Add("apple", "4");
_Dictionary.Add("cucumber", "6");

// add values using []

_Dictionary["banana"] = 7;
_Dictionary["pineapple"] = 7;

// Now lets see how elements are returned by IEnumerator
foreach (KeyValuePair<string, string> kvp in _Dictionary)
{
  Trace.Write(String.Format("{0}={1}", kvp.Key, kvp.Value));
}

¿En qué orden se enumerarán los elementos? ¿Puedo forzar el orden alfabético?

Capitán Comic
fuente

Respuestas:

125

El orden de los elementos en un diccionario no es determinista. La noción de orden simplemente no está definida para tablas hash. Por lo tanto, no confíe en enumerar en el mismo orden en que se agregaron los elementos al diccionario. Eso no está garantizado.

Cita del doc :

Para fines de enumeración, cada elemento del diccionario se trata como una KeyValuePair<TKey, TValue>estructura que representa un valor y su clave. El orden en el que se devuelven los artículos no está definido.

Darin Dimitrov
fuente
1
Pero hay OrderedDictionary .
Peter Mortensen
28

Si desea que los elementos estén ordenados, use un OrderedDictionary . Un hastable / diccionario ordinario se ordena solo en cierto sentido del diseño de almacenamiento.

Trigo Mitch
fuente
10
OrderedDictionary es incorrecto en la mayoría de los casos. No está ordenado por clave o valor, sino por un índice interno. SortedDictionary es el que está ordenado de una manera que el usuario puede manipular (clave predeterminada)
Offler
2
La pregunta es sobre ordenar en orden alfabético (asumiendo que el interrogador está hablando de la clave). Un diccionario ordenado, si entiendo la documentación correctamente, escupirá los elementos en el orden en que están insertados, es decir, no alfabéticamente, sino usando el índice interno. Un SortedDictionary es probablemente la mejor opción para la pregunta del usuario.
Mattpm
28

Siempre puedes usar SortedDictionarypara eso. Tenga en cuenta que el diccionario está ordenado por clave, de forma predeterminada, a menos que se haya especificado un comparador.

Soy escéptico con respecto al uso de OrderedDictionarypara lo que desea, ya que la documentación dice que:

Los elementos de un OrderedDictionary no se ordenan por clave, a diferencia de los elementos de una clase SortedDictionary.

Adriano Carneiro
fuente
Es importante tener en cuenta que SortedDictionary<K,V>se implementa como un árbol de búsqueda binario, lo que le da a sus operaciones una complejidad de tiempo y espacio diferente en comparación con el basado en tablas hash Dictionary<K,V>. Si los usuarios necesitan una O(1)estructura de tabla hash de inserción / eliminación y también desean iterar sobre los elementos en el orden de las claves, entonces deberían dict.Keys.OrderBy( k => k ).Select( k => dict[k] )hacerlo (a costa de O(n)espacio y O( n log n )tiempo) para el OrderBy()(que necesitará almacenar toda la colección de claves en una lista interna). ).
Dai
12

Los elementos se devolverán en el orden en el que estén almacenados físicamente en el diccionario, lo que depende del código hash y del orden en que se agregaron. Por lo tanto, el orden parecerá aleatorio y, a medida que cambien las implementaciones, nunca debe depender de que el orden permanezca igual.

Puede ordenar los artículos al enumerarlos:

foreach (KeyValuePair<string, string> kvp in _Dictionary.OrderBy(k => k.Value)) {
  ...
}

En framework 2.0, primero tendría que poner los elementos en una lista para ordenarlos:

List<KeyValuePair<string, string>> items = new List<KeyValuePair<string, string>>(_Dictionary);
items.Sort(delegate(KeyValuePair<string, string> x, KeyValuePair<string, string> y) { return x.Value.CompareTo(y.Value); });
foreach (KeyValuePair<string,string> kvp in items) {
  ...
}
Guffa
fuente
11

Para un diccionario ordenado:

 var _OrderedDictionary = new System.Collections.Specialized.OrderedDictionary();

_OrderedDictionary.Add("testKey1", "testValue1");
_OrderedDictionary.Add("testKey2", "testValue2");
_OrderedDictionary.Add("testKey3", "testValue3");

var k = _OrderedDictionary.Keys.GetEnumerator();
var v = _OrderedDictionary.Values.GetEnumerator();

while (k.MoveNext() && v.MoveNext()) {
    var key = k.Current; var value = v.Current;
}

Los artículos se devuelven en el orden en que se agregan.

Barton
fuente
5

Las matrices asociativas (también conocidas como tablas hash) no están ordenadas, lo que significa que los elementos se pueden ordenar de cualquier forma imaginable.

SIN EMBARGO, puede buscar las claves de matriz (solo las claves), ordenarlas alfabéticamente (a través de una función de clasificación) y luego trabajar en eso.

No puedo darte una muestra de C # porque no conozco el idioma, pero esto debería ser suficiente para que lo hagas tú mismo.

Tim Čas
fuente