Diccionario vs Lista

Así que me encontré con un Dictionary<int, int>hoy en el trabajo. Esto me pareció extraño porque probablemente hubiera usado un List<int>en su lugar. ¿Hay alguna diferencia y habría un caso de uso en el que se preferiría una estructura sobre la otra?

Usaría a Dictionary<int, int>si sus índices tienen un significado especial además de la colocación posicional.

El ejemplo inmediato que viene a la mente es almacenar una columna de identificación y una columna int en una base de datos. Por ejemplo, si tiene una [person-id]columna y una [personal-pin]columna, entonces podría incluirlas en un Dictionary<int, int>. De esta manera pinDict[person-id]le da un PIN, pero el índice es significativo y no solo una posición en a List<int>.

Pero realmente, cada vez que tenga dos listas de enteros relacionadas, esta podría ser una estructura de datos apropiada.

Piense en el Listcomo una matriz y Dictionarycomo una tabla hash . Solo usaría Dictionarysi necesitara asignar (o asociar) claves significativas a valores, mientras que Listsolo asigna (o asocia) posiciones (o índices) a valores.

Por ejemplo, supongamos que desea almacenar una asociación entre la edad de una persona y su estatura. Puede usar a Dictionary<int, int>para asignar la edad de la persona (an int) a su altura (an int):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

No es un ejemplo muy útil, pero el punto es que no sería capaz de hacer esto tan elegantemente con un Listporque necesitaría almacenar estos valores posicionalmente.

Semánticamente, una Dictionary<int, T>y List<T>son muy similares, ambos son recipientes de acceso aleatorio del marco .NET. Para usar una lista como reemplazo de un diccionario, necesita un valor especial en su tipo T(like null) para representar los espacios vacíos en su lista. Si Tno es un tipo anulable como int, podría usar int?en su lugar, o si solo espera almacenar valores positivos, también podría usar un valor especial como -1 para representar ranuras vacías.

El que elija dependerá del rango de los valores clave. Si sus claves Dictionary<int, T>están dentro de un intervalo entero, sin muchos espacios entre ellas (por ejemplo, 80 valores de [0, ... 100]), entonces List<T>será más apropiado, ya que el acceso por índice es más rápido, y En este caso, hay menos sobrecarga de memoria y tiempo en comparación con un diccionario.

Si sus valores clave son 100 intvalores de un rango como [0, ..., 1000000], entonces a List<T>necesita memoria para contener 1000000 valores de T, donde su diccionario solo necesitará memoria en un orden de magnitud alrededor de 100 valores de T, 100 valores de int (más algunos gastos generales, en realidad esperan aproximadamente 2 veces la memoria para almacenar esas 100 claves y valores). Entonces, en el último caso, un diccionario será más apropiado.

¿Cómo puede alguien considerarlos equivalentes?

El diccionario es escaso y permite inserciones aleatorias, pero hace que el recorrido en orden sea un problema, la Lista no es escasa y una inserción fuera de orden es costosa, ya que proporciona un recorrido en orden inherentemente.

Habría muy pocas situaciones en las que una no fuera dramáticamente superior a la otra.

Aparte: Otros lenguajes de programación se refieren a este tipo de estructura de datos como un Mapa, en lugar de un Diccionario.

Si sus datos pueden definirse significativamente como pares clave / valor, entonces un Diccionario proporcionará un acceso mucho más rápido si necesita encontrar un valor utilizando su clave.

Por ejemplo, suponga que tiene una lista de Clientes. Cada cliente incluye detalles como un nombre y una dirección, y un número de cliente único. Supongamos que también tiene una lista de pedidos en proceso. Cada pedido contendrá detalles de lo que se está haciendo y deberá incluir el número de cliente de la persona que lo ordenó.

Cuando un pedido está listo para enviarse, debe encontrar la dirección para enviarlo. Si los clientes se almacenan como una Lista simple, entonces debe buscar en toda la lista para encontrar al cliente con el número de cliente correcto. En cambio, podría almacenar a los clientes en un Diccionario, con el número de cliente como clave. El Diccionario ahora le permitirá sacar al cliente correcto en un solo paso sin ninguna búsqueda.

El diccionario utiliza hashing para buscar los datos. Un diccionario primero calculó un valor hash para la clave y este valor hash conduce al depósito de datos objetivo. Después de eso, se debe verificar la igualdad de cada elemento en el depósito. Pero en realidad la lista será más rápida que el diccionario en la búsqueda del primer elemento porque no hay nada que buscar en el primer paso. Pero en el segundo paso, la lista tiene que mirar el primer elemento y luego el segundo elemento. Entonces, cada paso de la búsqueda lleva más y más tiempo. Cuanto más grande sea la lista, más se demora.

Más sobre .... Diccionario Vs List con ejemplo.

Si el código en cuestión está almacenando dos conjuntos de valores correlacionados, la clase Diccionario proporciona una forma indexada de buscar valores mediante una clave. Si solo hay un conjunto de valores, pero es necesario acceder a ese conjunto de forma aleatoria (quizás para verificar la existencia de una clave en un conjunto), y los valores son únicos, un HashSet podría ser la mejor clase de conjunto para usar.

Estas son excelentes respuestas que parecen cubrir las bases.

Otra consideración que ofreceré es que los diccionarios (en C #) son más complejos desde una perspectiva de codificación. Tener ambas listas y diccionarios en la misma base de código hace que su código sea más difícil de mantener, ya que ambos métodos tienen diferencias sutiles en cómo realizar operaciones básicas, como buscar y ordenar datos de objetos. Mi perspectiva es que, a menos que necesite un diccionario por alguna razón justificada, use una lista.