Structures de données .Net : ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary -- Vitesse, mémoire, et quand utiliser chacune d'elles ?

Question

.NET comporte beaucoup de structures de données complexes. Malheureusement, certaines d'entre elles sont assez similaires et je ne sais pas toujours quand utiliser l'une ou l'autre. La plupart de mes livres sur le C# et le VB 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 ?

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

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

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

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

Answer 1

En haut de ma tête :

• Array * - représente un tableau de mémoire de la vieille école - un peu comme un alias pour un tableau normal. type[] réseau. Peut être énuméré. Ne peut pas croître automatiquement. Je suppose que la vitesse d'insertion et de récupération est très rapide.

• ArrayList - tableau à croissance automatique. Cela ajoute plus de frais généraux. Peut être énuméré, probablement plus lent qu'un tableau normal mais toujours assez rapide. Ces tableaux sont très utilisés dans .NET

• List - un de mes préférés - peut être utilisé avec des génériques, de sorte que vous pouvez avoir un tableau fortement typé, par ex. List<string> . A part ça, il se comporte très bien comme ArrayList

• Hashtable - un bon vieux tableau de hachage. O(1) à O(n) dans le pire des cas. Peut énumérer les propriétés value et keys, et faire des paires key/val.

• Dictionary - comme ci-dessus, mais avec un typage fort via des génériques, tels que Dictionary<string, string>

• SortedList - une liste générique triée. Ralentie à l'insertion puisqu'elle doit trouver où mettre les choses. Peut être énuméré, probablement la même chose sur la récupération puisqu'il n'a pas à recourir, mais la suppression sera plus lente qu'une vieille liste ordinaire.

J'ai tendance à utiliser List et Dictionary tout 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. KeyValuePair que vous pouvez utiliser pour faire des choses intéressantes, il y a une SortedDictionary qui peut également être utile.

Answer 2

Dans la mesure du possible, utilisez des génériques. Cela comprend :

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

Answer 3

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

Deuxièmement, un grand nombre de collections sont des doublons, car les 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 de ArrayList.
• Dictionary est une implémentation générique de Hashtable.

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

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

Ainsi, les implémentations d'IDictionary (celles qui supportent les KeyValuePairs) sont : * Hashtable * Dictionnaire * 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.

De plus, la LinkedList est une implémentation standard de liste chaînée (la List est une liste de tableaux pour une récupération plus rapide).

Answer 4

Une bonne antisèche http://bigocheatsheet.com/#data-structures en mentionnant les complexités des structures de données, des algorithmes, etc.

Answer 5

Voici quelques conseils généraux pour vous :

• Vous pouvez utiliser foreach sur les types qui implémentent IEnumerable . IList est essentiellement un IEnumberable avec Count et Item (accès aux éléments en utilisant un index basé sur zéro). IDictionary d'autre part, cela signifie que vous pouvez accéder à des éléments par n'importe quel indice hachable.

• Array , ArrayList et List tous les outils IList . Dictionary , SortedDictionary et Hashtable mettre en œuvre IDictionary .

• Si vous utilisez .NET 2.0 ou plus, il est recommandé d'utiliser les contreparties génériques des types mentionnés.

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

• Les structures de données .NET sont en System.Collections espace de 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 .