Structures de données .net : ArrayList, liste, HashTable, Dictionary, SortedList, SortedDictionary

.Net a beaucoup de structures de données complexes. Malheureusement, certains d'entre eux sont assez semblables et je ne suis pas toujours sûr quand à l'utilisation un et quand utiliser un autre. La plupart de mes c# et VB livres parles dans une certaine mesure, mais n'a jamais vraiment entrer dans aucun détail réel.

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

Ceux qui est énumérables (IList--peut faire la boucle « foreach ») ? Ceux qui utilise les 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 des autres structures de données mentionner ?

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

répondre #1

Du haut de ma tête :

Array-représente un tableau de mémoire old school - sorte de comme un alias pour un normal type[] tableau. Peut énumérer. Ne peut pas croître automatiquement. Je suppose retriv et à l'insertion très rapide. vitesse.

ArrayList-Tableau automatiquement croissante. Ajoute plus de frais généraux. Pouvez enum., probablement plus lent qu'un tableau normal mais encore assez rapide. Ils sont beaucoup utilisés dans .net

List-l'un de mes préférés - peut être utilisé avec les fabricants de médicaments génériques, donc vous pouvez avoir un tableau fortement typé, par exemple List<string> . Autre que celui, actes comme très ArrayList .

Hashtable-plaine hashtable vieux. O (1) au pire des cas O(n). Peut énumérer les clés et la valeur des propriétés et faire des paires clé/val.

Dictionary-même que ci-dessus, seulement fortement typé par le biais de médicaments génériques, telles queDictionary<string, string>

SortedList-une liste triée des générique. Ralenti sur insertion, car il faut savoir où mettre les choses. Pouvez enum., probablement le même sur la récupération puisqu'il n'a pas à recourir, mais suppression sera plus lente qu'une simple liste vieux.

J'ai tendance à utiliser List et Dictionary tout le temps - une fois que vous commencer à utiliser leur fortement typée avec génériques, ses vraiment dur de revenir à la norme celles non générique.

Il y a beaucoup d'autres structures de données trop - il y a KeyValuePair qui vous permet de faire des choses intéressantes, il y a un SortedDictionary qui peut être utile aussi bien.

répondre #2

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

  • La liste au lieu de ArrayList
  • Dictionnaire au lieu de table de hachage
répondre #3

Voici quelques conseils pour vous :

  • Vous pouvez utiliser foreach sur les types de cette mise en oeuvre IEnumerable . IList est essentiellement un IEnumberable avec Count et Item (accès aux éléments à l'aide d'un index de base zéro) propriétés. IDictionary signifie en revanche vous pouvez accéder aux articles par index tout-hashables.

  • Array, ArrayList , List et SortedList tout mettre en oeuvre IList . Dictionary , SortedDictionary , et Hashtable mettre en œuvre des IDictionary .

  • Si vous utilisez .net 2.0 ou supérieur, il est recommandé que vous utilisez équivalent générique des types mentionnés.

  • Pour la complexité spatiale et temporelle des diverses opérations sur ces types, vous devriez consulter leurs documents.

  • Structures de données .net sont en System.Collections espace de noms. Il existe des bibliothèques de types tels que PowerCollections , qui offrent des structures de données supplémentaires.

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

répondre #4

Tout d'abord, toutes les collections dans la mise en œuvre de .net IEnumerable.

Deuxièmement, beaucoup de collections sont des doublons parce que les fabricants de médicaments génériques ont été ajoutées dans la version 2.0 du framework.

Ainsi, tandis que les collections génériques probables ajouter des fonctionnalités, la plupart du temps :

  • La liste est une implémentation générique de ArrayList.
  • 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 qui est triée basé sur les clés. SortedList est un IDictionary qui est basé sur un IComparer requis.

Ainsi, les implémentations de IDictionary (ceux qui soutiennent KeyValuePairs) sont: * Hashtable * dictionnaire * SortedList * SortedDictionary

Une autre collection qui a été ajoutée en .net 3.5 est la Hashset. C'est une collection que prend en charge les opérations ensemblistes.

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

répondre #5

Je compatis avec la question - j'ai trouvé trop (trouver?) choix ahurissant, donc je reproduis scientifiquement pour voir la structure de données est le plus rapide (j'ai fait le test à l'aide de VB, mais j'imagine que C# serait le même, puisque les deux langues font la même chose au niveau CLR). Vous pouvez voir l' analyse comparative des résultats ici (il y a aussi quelques discussions de données type est préférable d'utiliser dans quelles circonstances).

répondre #6

En fait, je pense que l'aide msdn fournit assez de bonnes réponses à toutes ces questions. Il suffit de considérer des collections de .net.

répondre #7

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

répondre #8

Les collections génériques interprétera mieux que leurs homologues non générique, surtout lors d'une itération à travers de nombreux articles. C'est parce que les conversions boxing et unboxing ne se produit.

répondre #9

Il y a des différences subtiles et pas subtiles entre les collections génériques et non génériques. Ils utilisent simplement les différentes structures de données sous-jacentes. Par exemple, Hashtable garantit un-écrivain-plusieurs-lecteurs sans synchronisation. Dictionnaire ne le fait pas.

répondre #10

Tables de hachage et les dictionnaires sont o (1) performance, ce qui signifie que le rendement n'est pas fonction de la taille. C'est important de savoir.

EDIT : Dans la pratique, la complexité moyenne de temps pour les recherches de Hashtable/Dictionnaire <> est o (1).

répondre #11

Une remarque importante au sujet de Hashtable vs dictionnaire pour haute fréquence commercial ingénierie systématique : problème de sécurité des threads

Hashtable est thread-safe pour une utilisation par plusieurs threads. Les membres statiques publics de dictionnaire sont thread-safe, mais les membres d'instance ne sont pas garantis en ce sens.

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


Tags lesen

  
 
logo_banner