Structures de données .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Vitesse, mémoire et quand les utiliser?

.NET possède de nombreuses structures de données complexes. Malheureusement, certains d'entre eux sont assez similaires, et je ne sais pas toujours quand en utiliser un et quand en utiliser un autre. La plupart de mes livres C # et Visual Basic en parlent dans une certaine mesure, mais ils n'entrent jamais vraiment dans les détails.

Quelle est la différence entre Array, ArrayList, List, Hashtable, Dictionary, SortedList et SortedDictionary?

Lesquelles sont énumérables (IList - peut faire des boucles 'foreach')? Lesquelles utilisent des paires clé / valeur (IDict)?

Qu'en est-il de l'empreinte mémoire? Vitesse d'insertion? Vitesse de récupération?

Y a-t-il d'autres structures de données qui méritent d'être mentionnées?

Je cherche toujours plus de détails sur l'utilisation et la vitesse de la mémoire (notation Big-O).

Du haut de ma tête:

• Array* - représente un tableau de mémoire old-school - un peu comme un alias pour un type[]tableau normal . Peut énumérer. Ne peut pas grandir automatiquement. Je suppose que la vitesse d'insertion et de retour est très rapide.

• ArrayList- matrice en croissance automatique. Ajoute plus de frais généraux. Peut énumérer., Probablement plus lent qu'un tableau normal mais toujours assez rapide. Ceux-ci sont beaucoup utilisés dans .NET

• List- un de mes favoris - peut être utilisé avec des génériques, vous pouvez donc avoir un tableau fortement typé, par exemple List<string>. A part ça, ça ressemble beaucoup àArrayList

• Hashtable- vieille table de hachage simple. O (1) à O (n) pire cas. Peut énumérer les propriétés de valeur et de clés et faire des paires clé / val

• Dictionary - comme ci-dessus uniquement fortement typé via des génériques, tels que Dictionary<string, string>

• SortedList- une liste générique triée. Ralenti lors de l'insertion car il doit trouver où mettre les choses. Peut énumérer, probablement la même chose lors de la récupération car il n'a pas à recourir, mais la suppression sera plus lente qu'une ancienne liste.

J'ai tendance à utiliser Listet Dictionarytout le temps - une fois que vous commencez à les utiliser fortement typés avec des génériques, il est vraiment difficile de revenir aux standards non génériques.

Il y a aussi beaucoup d'autres structures de données - il y en a KeyValuePairque vous pouvez utiliser pour faire des choses intéressantes, il y en a SortedDictionaryqui peuvent aussi être utiles.

Si possible, utilisez des génériques. Ceci comprend:

• Liste au lieu de ArrayList
• Dictionnaire au lieu de HashTable

Tout d'abord, toutes les collections de .NET implémentent IEnumerable.

Deuxièmement, de nombreuses collections sont des doublons car des génériques ont été ajoutés dans la version 2.0 du framework.

Ainsi, bien que les collections génériques ajoutent probablement des fonctionnalités, pour la plupart:

• List est une implémentation générique d'ArrayList.
• Le dictionnaire est une implémentation générique de Hashtable

Les tableaux sont une collection de taille fixe que vous pouvez modifier la valeur stockée à un index donné.

SortedDictionary est un IDictionary trié en fonction des clés. SortedList est un IDictionary trié en fonction d'un IComparer requis.

Ainsi, les implémentations IDictionary (celles qui prennent en charge KeyValuePairs) sont: * Hashtable * Dictionary * SortedList * SortedDictionary

Une autre collection qui a été ajoutée dans .NET 3.5 est le Hashset. Il s'agit d'une collection qui prend en charge les opérations d'ensemble.

En outre, LinkedList est une implémentation standard de liste liée (la liste est une liste de tableaux pour une récupération plus rapide).

Voici quelques conseils généraux pour vous:

• Vous pouvez utiliser foreachsur les types qui implémentent IEnumerable. IListest essentiellement une propriété IEnumberablewith Countet Item(accès aux éléments à l'aide d'un index de base zéro). IDictionaryd'autre part, vous pouvez accéder aux éléments par n'importe quel index hachable.

• Array, ArrayListEt Listtout mettre en œuvre IList. Dictionary, SortedDictionaryet Hashtablemettre en œuvre IDictionary.

• Si vous utilisez .NET 2.0 ou supérieur, il est recommandé d'utiliser des équivalents génériques des types mentionnés.

• Pour la complexité temporelle et spatiale de diverses opérations sur ces types, vous devriez consulter leur documentation.

• Les structures de données .NET sont System.Collections espace noms. Il existe des bibliothèques de types telles que PowerCollections qui offrent des structures de données supplémentaires.

• Pour obtenir une compréhension approfondie des structures de données, consultez des ressources telles que CLRS .

Structures de données .NET:

En savoir plus sur les raisons pour lesquelles ArrayList et List sont réellement différents

Tableaux

Comme le dit un utilisateur, les tableaux sont la collection «old school» (oui, les tableaux sont considérés comme une collection bien qu'ils ne fassent pas partie de System.Collections ). Mais, qu'est-ce que la «vieille école» sur les tableaux par rapport à d'autres collections, c'est-à-dire celles que vous avez répertoriées dans votre titre (ici, ArrayList et List (Of T))? Commençons par les bases en examinant les tableaux.

Pour commencer, les tableaux dans Microsoft .NET sont des «mécanismes qui vous permettent de traiter plusieurs éléments [liés logiquement] comme une seule collection» (voir l'article lié). Qu'est-ce que ça veut dire? Les tableaux stockent les membres individuels (éléments) séquentiellement, l'un après l'autre en mémoire avec une adresse de départ. En utilisant le tableau, nous pouvons facilement accéder aux éléments stockés séquentiellement en commençant à cette adresse.

Au-delà de cela et contrairement à la programmation de 101 conceptions courantes, les tableaux peuvent vraiment être assez complexes:

Les tableaux peuvent être monodimensionnels, multidimensionnels ou jaddés (les tableaux dentelés valent la peine d'être lus). Les tableaux eux-mêmes ne sont pas dynamiques: une fois initialisé, un tableau de taille n réserve suffisamment d'espace pour contenir n nombre d'objets. Le nombre d'éléments dans le tableau ne peut pas augmenter ou diminuer. Dim _array As Int32() = New Int32(100)réserve suffisamment d'espace sur le bloc de mémoire pour que le tableau contienne 100 objets de type primitif Int32 (dans ce cas, le tableau est initialisé pour contenir 0). L'adresse de ce bloc est retournée à _array.

Selon l'article, Common Language Specification (CLS) requiert que tous les tableaux soient basés sur zéro. Les tableaux en .NET prennent en charge les tableaux non basés sur zéro; cependant, c'est moins courant. En raison de la «banalité» des baies à base zéro, Microsoft a passé beaucoup de temps à optimiser leurs performances ; par conséquent, les tableaux à base zéro (SZ) à une dimension sont "spéciaux" - et vraiment la meilleure implémentation d'un tableau (par opposition à multidimensionnel, etc.) - parce que les SZ ont des instructions de langage intermédiaire spécifiques pour les manipuler.

Les tableaux sont toujours transmis par référence (en tant qu'adresse mémoire) - une pièce importante du puzzle de tableau à savoir. Bien qu'ils vérifient les limites (génèrent une erreur), la vérification des limites peut également être désactivée sur les tableaux.

Encore une fois, le plus grand obstacle aux tableaux est qu'ils ne sont pas redimensionnables. Ils ont une capacité "fixe". Présentation de ArrayList et List (Of T) à notre histoire:

ArrayList - liste non générique

L' ArrayList (ainsi que List(Of T)- bien qu'il existe quelques différences critiques, ici, expliquées plus loin) - est peut-être mieux considéré comme le prochain ajout aux collections (au sens large). ArrayList hérite de l' interface IList (un descendant de 'ICollection'). Les listes de tableaux elles-mêmes sont plus volumineuses - nécessitant plus de frais généraux - que les listes.

IListpermet à l'implémentation de traiter les listes de tableaux comme des listes de taille fixe (comme les tableaux); cependant, au-delà de la fonctionnalité supplémentaire ajoutée par ArrayLists, il n'y a aucun avantage réel à utiliser des ArrayLists dont la taille est fixe car les ArrayLists (sur les tableaux) dans ce cas sont nettement plus lents.

D'après ma lecture, ArrayLists ne peut pas être irrégulier: "L'utilisation de tableaux multidimensionnels comme éléments ... n'est pas prise en charge". Encore une fois, un autre clou dans le cercueil d'ArrayLists. ArrayLists sont pas non plus « typés » - ce qui signifie que, tout en dessous, un ArrayList est tout simplement un tableau de dynamique d'objets: Object[]. Cela nécessite beaucoup de boxe (implicite) et unboxing (explicite) lors de l'implémentation d'ArrayLists, ajoutant encore à leur surcharge.

Pensée sans fondement: je pense que je me souviens avoir lu ou entendu l'un de mes professeurs dire que les tableaux de tableaux sont en quelque sorte l'enfant conceptuel bâtard de la tentative de passer des tableaux aux collections de type liste, c'est-à-dire tout en ayant une fois été une grande amélioration des tableaux, ils ne sont plus la meilleure option car un développement plus poussé a été fait en ce qui concerne les collections

List (Of T): Ce qu'ArrayList est devenu (et espérait être)

La différence d'utilisation de la mémoire est suffisamment importante pour indiquer qu'une liste (Of Int32) a consommé 56% de mémoire en moins qu'une ArrayList contenant le même type primitif (8 Mo contre 19 Mo dans la démonstration liée de gentleman ci-dessus: encore une fois, liée ici ) - bien que c'est un résultat aggravé par la machine 64 bits. Cette différence montre vraiment deux choses: premièrement (1), un "objet" de type Int32 encadré (ArrayList) est beaucoup plus grand qu'un pur type primitif Int32 (List); deuxième (2), la différence est exponentielle en raison du fonctionnement interne d'une machine 64 bits.

Alors, quelle est la différence et qu'est-ce qu'une liste (de T) ? MSDN définit un List(Of T)as, "... une liste fortement typée d'objets accessibles par index." L'importance ici est le bit "fortement typé": un List (Of T) 'reconnaît' les types et stocke les objets comme leur type. Ainsi, un Int32est stocké comme un Int32et non comme un Objecttype. Cela élimine les problèmes causés par la boxe et le déballage.

MSDN spécifie que cette différence entre en jeu uniquement lors du stockage de types primitifs et non de types de référence. Trop, la différence se produit vraiment à grande échelle: plus de 500 éléments. Ce qui est plus intéressant, c'est que la documentation MSDN indique: "Il est avantageux d'utiliser l'implémentation spécifique au type de la classe List (Of T) au lieu d'utiliser la classe ArrayList ...."

Essentiellement, List (Of T) est ArrayList, mais en mieux. C'est "l'équivalent générique" d'ArrayList. Comme ArrayList, il n'est pas garanti d'être trié jusqu'à ce qu'il soit trié (allez comprendre). List (Of T) a également des fonctionnalités supplémentaires.

Je sympathise avec la question - j'ai aussi trouvé (trouver?) Le choix déconcertant, alors je me suis fixé scientifiquement pour voir quelle structure de données est la plus rapide (j'ai fait le test en utilisant VB, mais j'imagine que C # serait le même, car les deux langues faire la même chose au niveau CLR). Vous pouvez voir ici certains résultats d'analyse comparative (il y a aussi une discussion sur le type de données qu'il est préférable d'utiliser dans quelles circonstances).

Ils sont assez bien définis dans l'intellisense. Tapez simplement System.Collections. ou System.Collections.Generics (préféré) et vous obtiendrez une liste et une brève description de ce qui est disponible.

Les tables de hachage / dictionnaires sont des performances O (1), ce qui signifie que les performances ne sont pas fonction de la taille. C'est important à savoir.

EDIT: En pratique, la complexité de temps moyenne pour les recherches Hashtable / Dictionary <> est O (1).

Les collections génériques fonctionneront mieux que leurs homologues non génériques, en particulier lors de l'itération à travers de nombreux éléments. En effet, la boxe et le déballage ne se produisent plus.

Une note importante sur Hashtable vs Dictionary pour l'ingénierie de trading systématique à haute fréquence: Thread Safety Issue

Hashtable est sans fil pour une utilisation par plusieurs threads. Les membres statiques publics du dictionnaire sont thread-safe, mais aucun membre d'instance n'est garanti.

Hashtable reste donc le choix «standard» à cet égard.

Il existe des différences subtiles et pas si subtiles entre les collections génériques et non génériques. Ils utilisent simplement différentes structures de données sous-jacentes. Par exemple, Hashtable garantit un seul auteur-plusieurs-lecteurs sans synchronisation. Le dictionnaire ne fonctionne pas.

Structures et collections de données C # les plus populaires

• Array
• Liste des tableaux
• liste
• LinkedList
• dictionnaire
• HashSet
• Empiler
• Queue
• SortedList

C # .NET possède de nombreuses structures de données différentes, par exemple, l'une des plus courantes est un tableau. Cependant, C # est livré avec de nombreuses structures de données plus basiques. Choisir la bonne structure de données à utiliser fait partie de l'écriture d'un programme bien structuré et efficace.

Dans cet article, je vais passer en revue les structures de données C # intégrées, y compris les nouvelles introduites dans C # .NET 3.5. Notez que beaucoup de ces structures de données s'appliquent à d'autres langages de programmation.

Array

La structure de données peut-être la plus simple et la plus courante est le tableau. Le tableau AC # est essentiellement une liste d'objets. Ses traits distinctifs sont que tous les objets sont du même type (dans la plupart des cas) et il y en a un nombre spécifique. La nature d'un tableau permet un accès très rapide aux éléments en fonction de leur position dans la liste (autrement connu comme l'index). Le tableau AC # est défini comme ceci:

[object type][] myArray = new [object type][number of elements]

Quelques exemples:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Comme vous pouvez le voir dans l'exemple ci-dessus, un tableau peut être initialisé sans éléments ou à partir d'un ensemble de valeurs existantes. L'insertion de valeurs dans un tableau est simple tant qu'elles conviennent. L'opération devient coûteuse lorsqu'il y a plus d'éléments que la taille du tableau, point auquel le tableau doit être étendu. Cela prend plus de temps car tous les éléments existants doivent être copiés dans le nouveau tableau plus grand.

Liste des tableaux

La structure de données C #, ArrayList, est un tableau dynamique. Cela signifie qu'une ArrayList peut avoir n'importe quelle quantité d'objets et de n'importe quel type. Cette structure de données a été conçue pour simplifier les processus d'ajout de nouveaux éléments dans un tableau. Sous le capot, un ArrayList est un tableau dont la taille est doublée à chaque fois qu'il manque d'espace. Le doublement de la taille du tableau interne est une stratégie très efficace qui réduit la quantité de copie d'éléments à long terme. Nous n'entrerons pas dans la preuve de cela ici. La structure des données est très simple à utiliser:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

L'inconvénient de la structure de données ArrayList est qu'il faut reconstituer les valeurs récupérées dans leur type d'origine:

int arrayListValue = (int)myArrayList[0]

Sources et plus d'informations que vous pouvez trouver ici :

• Structures de données C #
• Collections et structures de données
• List vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• Espace de noms System.Collections.Generic
• Espace de noms System.Collections

J'ai trouvé la section "Choisir une collection" de Microsoft Docs sur la page Collection et structure de données très utile

Collections C # et structures de données: choisissez une collection

Et aussi la matrice suivante pour comparer d'autres fonctionnalités