Quand je dis
int[] keys =new int[] { 1, 2, 3 };
string[] values=new string[]{"val1","val2","val3"};
4 Réponses :
Non, c'est une table de hachage. Eh bien, ce n'est pas exactement une table de hachage, mais c'est vraiment étroitement lié.
Il est tout clairement écrit sur MSDN : < / p>
Le dictionnaire (de Thkey, Tvalue) Generic Class fournit un mappage d'un ensemble de clés à un ensemble de valeurs. Chaque ajout au dictionnaire consiste en une valeur et de sa clé associée. Récupération d'une valeur en utilisant sa clé est très rapide, près de O (1), car le dictionnaire (de Thkey, Tvalue) est mis en œuvre comme une table de hachage.
C'est tout vrai bien sûr, mais ne répond pas à la question. Bien sûr, en réalité, peu importe la mise en œuvre interne, mais plutôt sur la Comp. complexité.
Ce n'est pas trop loin. En regardant le code source dans le réflecteur, il semble que trois collections internes sont utilisées:
private Entry<TKey, TValue>[] entries; private KeyCollection<TKey, TValue> keys; private ValueCollection<TKey, TValue> values;
C'est hashtable. Pour chaque dictionnaire clé calcule son code de hachage et l'utilise comme un pointeur sur lequel la valeur devrait résider. S'il y a deux touches correspondant au même code de hachage, cette situation est appelée collision et en interne pour ce dictionnaire de cas spécial utilise un arbre binaire.
Complexité algorithmique du dictionnaire (hashtable) est O (1) et dans le pire des cas O (log (n)) (le pire des cas signifie que nous ne traitons que des collisions), où n est un certain nombre d'éléments dans le dictionnaire.