what - search in dictionary c#

¿Por qué un diccionario "no está ordenado"?

Question

He leído esto en respuesta a muchas preguntas aquí. ¿Pero qué significa exactamente?

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

El código anterior parece funcionar como se esperaba. Entonces, ¿de qué manera se considera un diccionario desordenado? ¿En qué circunstancias podría fallar el código anterior?

Answer 1

Aquí hay muchas buenas ideas, pero dispersas, así que voy a tratar de crear una respuesta que lo describa mejor, aunque el problema haya sido respondido.

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 puede enumerar a través de todos los pares clave-valor sin importar el orden.

Si desea un pedido, utiliza un OrderedDictionary pero la compensación es que la búsqueda es más lenta, por lo que si no necesita un pedido, no lo solicite.

Los diccionarios (y HashMap en Java) usan hash. Eso es O (1) vez, independientemente del tamaño de su mesa. Los diccionarios ordenados generalmente usan algún tipo de árbol balanceado que es O (log2 (n)) de modo que a medida que crecen sus 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. No determinismo significa cuando hash (5) la primera vez, y hash (5) la próxima vez, obtienes un lugar diferente. Eso sería completamente inútil.

Lo que las personas querían decir es que si agrega cosas a un diccionario, el orden es complicado y está sujeto a cambios cada vez que agregue (o elimine) un elemento. Por ejemplo, imagina que la tabla hash tiene 500k elementos y tienes 400k valores. Cuando agrega uno más, alcanza el umbral crítico porque necesita alrededor del 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 calcular todos los valores. Ahora están todos en lugares diferentes de lo que eran antes.

Si construyes el mismo diccionario dos veces (lee mi declaración cuidadosamente, EL MISMO), obtendrás el mismo orden. Pero como Jon dice correctamente, no cuentes con eso. Demasiadas cosas pueden hacer que no sea lo mismo, incluso el tamaño inicialmente asignado.

Esto trae a colación un excelente punto. Es realmente, muy caro 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. Así que vale la pena asignar 10 veces la memoria que necesita en lugar de tener que crecer. Conozca su tamaño de hashmap, y preasigne lo suficiente si es posible, es una gran ganancia de rendimiento. Y si tiene una implementación incorrecta que no cambia de tamaño, puede ser un desastre si elige un tamaño demasiado pequeño.

Ahora bien, 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 ordenamientos diferentes. Es cierto, pero eso no es culpa del diccionario.

Cuando tu dices:

new Foo();

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

Si usa el valor Foo como la clave en un diccionario, sin otra información, lo único que pueden hacer es usar la dirección del objeto como la 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 ambos f1 y f2 tienen los mismos valores. Eso no tiene nada que ver con el comportamiento determinista del Diccionario.

Hashing es un tema impresionante en ciencias de la computación, 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 rojo-negro vs. hash. Este tipo llamado Bob tiene un gran sitio sobre hash y hashes óptimos: http://burtleburtle.net/bob

Answer 2

Bueno, para empezar, no está claro si espera que esto sea de orden de inserción o de orden de 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, creo que la implementación actual conserva el orden de inserción siempre y cuando nunca elimines nada, pero no debes 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 casilla) 3, 5, 1, 0. La nueva entrada para 5 ha utilizado la entrada vacante previamente utilizada por 2. Sin embargo, eso no va a estar garantizado.

El reajuste (cuando el almacenamiento subyacente del diccionario debe expandirse) podría afectar las cosas ... todo tipo de cosas.

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

Answer 3

El diccionario <string, Obj>, no SortedDictionary <string, Obj>, se secuencia por orden de inserción. Por extraño que sea, debes declarar específicamente que SortedDictionary tiene un diccionario ordenado por orden de cadena clave:

public SortedDictionary<string, Row> forecastMTX = new SortedDictionary<string, Row>();

Answer 4

El orden no es determinista.

De documentation

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

Tal vez para sus necesidades OrderedDictionary es el requerido.

Answer 5

La clase Dictionary<TKey,TValue> se implementa utilizando una lista indexada respaldada por matriz. Si no se eliminan elementos, la tienda de respaldo mantendrá los elementos en orden. Sin embargo, cuando se elimina un elemento, el espacio se marcará para su reutilización antes de que se amplíe la matriz. Como consecuencia, si, por ejemplo, se agregan diez elementos a un nuevo diccionario, se elimina el cuarto elemento, se agrega un nuevo elemento y se enumera el diccionario, el nuevo elemento probablemente aparecerá en cuarto lugar en lugar de décimo, pero no hay garantía de que las diferentes versiones de Dictionary manejarán las cosas de la misma manera.

En mi humilde opinión, habría sido útil para Microsoft documentar que un diccionario del que no se eliminen nunca elementos enumerará los artículos en el orden original, pero que una vez que se eliminan los elementos, cualquier cambio futuro en el diccionario puede permutar los elementos arbitrarios. Mantener esa garantía siempre que no se eliminen elementos sería relativamente barato para la mayoría de las implementaciones razonables del diccionario; continuar manteniendo la garantía después de eliminar los artículos sería mucho más costoso.

Alternativamente, podría haber sido útil tener un AddOnlyDictionary que sea seguro para la secuencia de un único escritor simultáneo con cualquier número de lectores, y garantizar la retención de los elementos en secuencia (tenga en cuenta que si los elementos solo se agregan, nunca se eliminan o se modifican) --uno puede tomar una "instantánea" simplemente al notar cuántos elementos contiene actualmente). Hacer un diccionario de propósito general seguro para subprocesos es costoso, pero agregar el nivel anterior de seguridad de subprocesos sería barato. Tenga en cuenta que el uso eficaz de varios escritores de múltiples escritores no requeriría el uso de un bloqueo de lector-escritor, sino que podría manejarse simplemente bloqueando los escritores y haciendo que los lectores no se molesten en hacerlo.

Microsoft no implementó un AddOnlyDictionary como se describió anteriormente, por supuesto, pero es interesante observar que el ConditionalWeakTable seguro para subprocesos tiene semántica de solo agregado, probablemente porque, como se señaló, es mucho más fácil agregar simultaneidad a las colecciones de solo agregado. que a las colecciones que permiten la eliminación.

Answer 6

No sé C # ni ninguno de .NET, pero el concepto general de un diccionario es que se trata de una colección de pares clave-valor.
No accede secuencialmente a un diccionario como lo haría cuando, por ejemplo, itera una lista o matriz.
Usted accede al tener una clave, y luego encuentra si hay un valor para esa tecla en el diccionario y de qué se trata.
En su ejemplo, publicó un diccionario con teclas numéricas que son secuenciales, sin espacios y en orden ascendente de inserción.
Pero no importa en qué orden inserte un valor para la clave ''2'', siempre obtendrá el mismo valor cuando consulte la clave ''2''.
No sé si C # lo permite, supongo que sí, para tener tipos de teclas que no sean números, pero en ese caso, es lo mismo, no hay un orden explícito en las teclas.
La analogía con un diccionario de la vida real podría ser confusa, ya que las teclas que son las palabras están ordenadas alfabéticamente para que podamos encontrarlas más rápido, pero si no lo fueran, el diccionario funcionaría de todos modos, porque la definición de la palabra "Aardvark" "tendría el mismo significado, incluso si vino después de" Zebra ". Piense en una novela, por otro lado, cambiar el orden de las páginas no tendría ningún sentido, ya que son una colección ordenada en esencia.

Answer 7

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

La documentation explica bastante bien:

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