Eficiencia de los diccionarios C #

Los diccionarios de C # son una forma sencilla de encontrar si existe algo, etc., pero tengo una pregunta sobre cómo funcionan. Digamos que en lugar de un diccionario, uso una ArrayList. En lugar de usar ContainsKey(o un método equivalente en otro idioma) recorro la ArrayList para verificar si existe algo allí (o realizar una búsqueda binaria si los datos están ordenados o algo similar). ¿Cuál es la diferencia en eficiencia? ¿El ContainsKeymétodo está utilizando una forma más eficiente en lugar de recorrer las teclas y verificar si lo que estoy buscando existe?

Si digamos que he creado una función hash específica que corresponde al tipo de datos que tengo y está específicamente diseñada para ese conjunto de datos, entonces sí, esa función hash es realmente más rápida que recorrer los datos. Pero los diccionarios son generales. El método ContainsKey no es específico de los datos que obtiene, es un método de búsqueda general.

Básicamente lo que estoy preguntando es. Los diccionarios son útiles para los programadores. Incluyen métodos que ayudan con muchas cosas y combinan cadenas con enteros (claves y valores) y muchos más. Pero con respecto a la eficiencia, ¿qué ofrecen? ¿Cuál es la diferencia en tener un dictionaryvs un ArrayListdestructs(string,int)

Tienes que cavar un poco para ver cómo se implementa el Diccionario en C # - No es tan obvio como HashMap (una tabla hash) o TreeMap (un árbol ordenado) (o ConcurrentSkipListMap - una lista de omisión ).

Si profundiza en la sección "Observaciones":

La clase genérica Diccionario proporciona una asignación de un conjunto de claves a un conjunto de valores. Cada adición al diccionario consta de un valor y su clave asociada. Recuperar un valor utilizando su clave es muy rápido, cercano a O (1), porque la clase Diccionario se implementa como una tabla hash.

Y ahí lo tenemos. Es una tabla hash . Tenga en cuenta que he vinculado el artículo de Wikipedia allí, es una lectura bastante buena. Es posible que desee leer la sección sobre resolución de colisiones. Es posible obtener un conjunto de datos patológicos donde la búsqueda se convierte en O (N) (por ejemplo, todo lo que inserte cae al mismo valor o índice de hash en la tabla de hash por alguna razón y le quedan sondeos lineales ).

Si bien el Diccionario es una solución de propósito general, no debería pasar por tipos concretos (como el Diccionario), debería pasar por las interfaces. En este caso, esa interfaz es IDictionary( docs ). Para esto, es perfectamente capaz de escribir su propia implementación de diccionario que hace las cosas de manera óptima para los datos que tiene.

En cuanto a la eficiencia de varias búsquedas / contiene?

• Recorrer una lista sin clasificar: O (N)
• Búsqueda binaria de una matriz ordenada: O (log N)
• Árbol clasificado: O (log N)
• Tabla hash: O (1)

Para la mayoría de las personas, la tabla hash es lo que quieren.

Puede encontrar que SortedDictionary es lo que desea en su lugar:

La SortedDictionary<TKey, TValue>clase genérica es un árbol de búsqueda binario con recuperación O (log n), donde n es el número de elementos en el diccionario. A este respecto, es similar a la SortedList<TKey, TValue>clase genérica. Las dos clases tienen modelos de objetos similares, y ambas tienen recuperación O (log n).

Sin embargo, una vez más, si la estructura de datos no es la que funciona idealmente con sus datos, se le proporcionan las herramientas (las interfaces) para poder escribir una que funcione mejor para sus datos.

El diccionario en sí es un tipo de datos abstracto . Me das un Diccionario y sé lo que puedo hacer con él y todas las herramientas allí para que pueda usarlo por la naturaleza de que sea un Diccionario. Si me proporcionara una ArrayList, me encontraría escribiendo mi propio código para buscar, insertar o eliminar elementos de la lista. Esto desperdicia mi tiempo y también significa que hay más probabilidades de un error al copiar el código una y otra vez de un lugar a otro.