cuando digo¿Cómo se mantiene internamente el diccionario?
Dictionary<int,string>
es lo equivalente a dos matrices diferentes, tales como:
int[] keys =new int[] { 1, 2, 3 };
string[] values=new string[]{"val1","val2","val3"};
No está muy lejos. Mirando el código fuente en el reflector, al parecer se utilizan tres colecciones internas:
private Entry<TKey, TValue>[] entries;
private KeyCollection<TKey, TValue> keys;
private ValueCollection<TKey, TValue> values;
Tenga en cuenta que también hay una variable int[] buckets para realizar un seguimiento de la buckets requerido en el caso de colisiones de hash de código.
El propósito de estas variables debería ser bastante claro. Esto no es particularmente sorprendente, ya que la clase Dictionary es conocida y documentada para proporcionar (idealmente, con un artículo por segmento) O(1) tiempo de búsqueda.
No, es una tabla hash. Bueno, no es exactamente una tabla hash, pero está muy relacionada.
Es todo claramente escrito en MSDN:
El Diccionario (De TKey, TValue) clase genérica proporciona una correspondencia entre un conjunto de llaves de un conjunto de valores. Cada adición al diccionario consiste en un valor y su clave asociada. Recuperar un valor usando su clave es muy rápido, cerca de O (1), porque la clase Diccionario (de TKey, TValue) se implementa como una tabla hash.
Es hashtable. Para cada clave, Dictionary calcula su código hash y lo utiliza como un puntero para colocar donde debe residir el valor. Si hay dos claves que coinciden con el mismo código hash, dicha situación se llama colisión e internamente para este caso especial Diccionario utiliza árbol binario.
La complejidad algorítmica del Diccionario (hashtable) es O (1) y en el peor de los casos O (log (N)) (el peor caso significa que solo tratamos con colisiones), donde N es un número de elementos en Dictionary.
Eso es todo cierto, por supuesto, pero no acaba de responder a la pregunta. Por supuesto, en realidad, importa poco sobre la implementación interna, sino sobre el borrador. complejidad. – Noldorin