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

.NET a beaucoup de structures de données complexes. Malheureusement, certains d’entre eux sont assez similaires, et je ne suis pas toujours sûr de savoir 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-on 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 à mentionner?

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

Du haut de ma tête:

  • Array * – représente un tableau de mémoire à l’ancienne – un peu comme un alias pour un tableau de type[] normal. Peut énumérer Ne peut pas croître automatiquement Je suppose que la vitesse d’insertion et de retour est très rapide.

  • ArrayList – tableau en croissance automatique. Ajoute plus de frais généraux. Peut enum., 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 . A part ça, agit beaucoup comme ArrayList

  • Hashtable – plaine vieille hashtable. O (1) à O (n) pire des cas. Peut énumérer les propriétés value et keys et faire des paires clé / val

  • Dictionary – identique à ci-dessus, uniquement fortement typé via des génériques, tels que Dictionary

  • SortedList – une liste générique sortingée. Ralenti lors de l’insertion, car il faut trouver où mettre les choses. Peut-on enum., Probablement le même lors de la récupération car il ne doit pas être utilisé, mais la suppression sera plus lente que dans une liste ancienne.

J’ai tendance à utiliser List and 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 – il y a KeyValuePair que vous pouvez utiliser pour faire des choses intéressantes, il y a un SortedDictionary qui peut être utile aussi.

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 dans .NET implémentent IEnumerable.

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

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

  • 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 dans laquelle vous pouvez modifier la valeur stockée dans un index donné.

SortedDictionary est un IDictionary sortingé en fonction des clés. SortedList est un IDictionary sortingé en fonction d’un IComparer requirejs.

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

Une autre collection ajoutée dans .NET 3.5 est le Hashset. C’est une collection qui prend en charge les opérations définies.

De plus, la propriété 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 foreach sur les types qui implémentent IEnumerable . IList est essentiellement un IEnumberable avec Count et Item (access aux éléments en utilisant un index de base zéro). IDictionary , d’autre part, signifie que vous pouvez accéder aux éléments par index indexable.

  • Array , ArrayList et List all implémentent IList . Dictionary , SortedDictionary et Hashtable implémentent IDictionary .

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

  • Pour la complexité en temps et en espace des différentes opérations sur ces types, vous devriez consulter leur documentation.

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

  • Pour bien comprendre les structures de données, consultez des ressources telles que CLRS .

Un bon aide- mémoire mentionnant la complexité des structures de données, des algorithmes, etc.

Je sympathise avec la question – j’ai aussi trouvé (trouver?) Le choix déconcertant, alors je me suis lancé scientifiquement pour voir quelle structure de données est la plus rapide (j’ai fait le test avec VB, mais j’imagine que C # serait le même, faire la même chose au niveau du CLR). Vous pouvez voir ici quelques résultats d’parsing comparative (il y a aussi une discussion sur le type de données à utiliser dans quelles circonstances).

Structures de données .NET:

Plus d’informations sur la raison pour laquelle ArrayList et List sont différents

Tableaux

Comme l’indique un utilisateur, les tableaux constituent la collection «old school» (oui, les tableaux sont considérés comme une collection mais ne font pas partie de System.Collections ). Mais qu’est-ce que “old school” à propos des tableaux par rapport aux autres collections, c’est-à-dire celles que vous avez listées dans votre titre (ici, ArrayList et List (Of T))? Commençons par les bases en regardant Arrays.

Pour commencer, les tableaux dans Microsoft .NET sont des “mécanismes qui vous permettent de traiter plusieurs éléments [liés logiquement] en tant que collection unique” (voir l’article lié). Qu’est-ce que ça veut dire? Les tableaux stockent des membres individuels (éléments) de manière séquentielle, 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 à partir de cette adresse.

Au-delà de cela et contrairement à la programmation de 101 conceptions communes, les tableaux peuvent être très complexes:

Les tableaux peuvent être à une seule dimension, multidimensionnels ou jaddés (les tableaux irréguliers méritent d’être lus). Les tableaux eux-mêmes ne sont pas dynamics: une fois initialisé, un tableau de taille n réserve suffisamment d’espace pour contenir un nombre d’objects. 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 objects de type primitif Int32 (dans ce cas, le tableau est initialisé pour contenir des 0). L’adresse de ce bloc est renvoyée à _array .

Selon l’article, la spécification CLS ( Common Language Specification ) exige que tous les tableaux soient basés sur zéro. Les tableaux dans .NET prennent en charge les tableaux non basés sur zéro; Cependant, c’est moins commun. En raison de la “banalité” des baies à base zéro, Microsoft a consacré beaucoup de temps à optimiser leurs performances . par conséquent, les tableaux à dimension unique et à base zéro (SZs) sont “spéciaux” – et constituent la meilleure implémentation d’un tableau (par opposition à multidimensionnel, etc.) – car les SZ ont des instructions de langage intermédiaire spécifiques pour les manipuler.

Les tableaux sont toujours passés par référence (comme une adresse mémoire) – un élément important du puzzle Array à connaître. Pendant qu’ils effectuent la vérification des limites (jettent 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”. Introduire ArrayList et List (Of T) dans notre histoire:

ArrayList – liste non générique

L’ ArrayList (avec List(Of T) – bien qu’il y ait quelques différences critiques, ici, expliqué 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 ArrayLists, elles-mêmes, sont plus volumineuses – nécessitant plus de frais généraux – que les listes.

IList permet à l’implémentation de traiter les ArrayLists 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 pas de réel avantage à utiliser ArrayLists qui est de taille fixe car les ArrayLists (sur Arrays) dans ce cas sont nettement plus lents.

De mon sharepoint vue, ArrayLists ne peut pas être déchiqueté: “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. Les ArrayLists ne sont pas non plus “typés” – ce qui signifie que, sous tout, ArrayList est simplement un tableau dynamic d’objects: Object[] . Cela nécessite beaucoup de boxe (implicite) et unboxing (explicite) lors de l’implémentation de ArrayLists, ce qui ajoute encore à leur surcharge.

Pensée non fondée: Je pense que je me souviens avoir lu ou entendu l’un de mes professeurs que ArrayLists est en quelque sorte l’enfant conceptuel bâtard de la tentative de passer de tableaux à des collections de type liste, c’est-à-dire ils ne sont plus la meilleure option car d’autres développements ont été réalisés en ce qui concerne les collections

List (Of T): Qu’est-ce que ArrayList est devenu (et espérait être)

La différence d’utilisation de la mémoire est assez importante pour qu’une liste (Of Int32) consum 56% moins de mémoire qu’une ArrayList contenant le même type primitif (8 Mo contre 19 Mo dans la démonstration liée ci-dessus: à nouveau, liée ici ) – bien que c’est un résultat aggravé par la machine 64 bits. Cette différence démontre vraiment deux choses: d’abord (1), un “object” de type Int32 en boîte (ArrayList) est beaucoup plus gros qu’un type primitif Int32 pur (List); Deuxièmement (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 (Of T) ? MSDN définit une List(Of T) tant que “… une liste fortement typée d’objects accessibles par index”. L’importance ici est le bit “fortement typé”: une liste (Of T) “reconnaît” les types et stocke les objects en tant que type. Ainsi, un Int32 est stocké sous forme de type Int32 et non pas d’ Object . Cela élimine les problèmes causés par la boxe et le déballage.

MSDN spécifie que cette différence n’entre en jeu que lors du stockage de types primitifs et non de types de référence. La différence existe aussi à 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 à la classe de List (Of T) au lieu d’utiliser la classe ArrayList ….”

Essentiellement, List (Of T) est ArrayList, mais mieux. C’est l’équivalent générique de ArrayList. Comme ArrayList, il n’est pas garanti qu’il soit sortingé avant d’être sortingé (voir figure). List (Of T) a également des fonctionnalités supplémentaires.

Ils sont bien expliqués dans 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 de savoir.

EDIT: En pratique, la complexité temporelle moyenne des recherches Hashtable / Dictionary <> est O (1).

Les collections génériques seront plus performantes que leurs homologues non génériques, en particulier lorsqu’elles parcourent de nombreux éléments. C’est parce que la boxe et le désencapsulation ne se produisent plus.

Une note importante sur Hashtable vs Dictionary pour l’ingénierie de trading systématique à haute fréquence: Problème de sécurité des threads

Hashtable est compatible avec les threads pour une utilisation par plusieurs threads. Les membres statiques publics du dictionnaire sont sécurisés pour les threads, mais les membres de l’instance ne sont pas garantis.

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

En fait, je pense que MSDN aide à fournir de très bonnes réponses à toutes ces questions. Recherchez simplement les collections .NET.

Il existe des différences subtiles et peu 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 lecteur unique à plusieurs lecteurs sans synchronisation. Dictionnaire pas.

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

  • Tableau
  • ArrayList
  • liste
  • LinkedList
  • dictionnaire
  • HashSet
  • Emstackr
  • Queue
  • SortedList

C # .NET a beaucoup de structures de données différentes, par exemple, l’un des plus courants est un tableau. Cependant, C # est livré avec beaucoup plus de structures de données de base. 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 celles introduites dans C # .NET 3.5. Notez que plusieurs de ces structures de données s’appliquent à d’autres langages de programmation.

Tableau

La structure de données peut-être la plus simple et la plus courante est le tableau. AC # array est essentiellement une liste d’objects. Ses traits caractéristiques sont que tous les objects sont du même type (dans la plupart des cas) et qu’ils en contiennent un certain nombre. La nature d’un tableau permet un access très rapide aux éléments en fonction de leur position dans la liste (également appelée index). AC # array 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 ni à 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, à quel point le tableau doit être développé. Cela prend plus de temps car tous les éléments existants doivent être copiés sur le nouveau tableau plus grand.

ArrayList

La structure de données C #, ArrayList, est un tableau dynamic. Qu’est-ce que cela signifie, une ArrayList peut avoir n’importe quelle quantité d’objects et de tout 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, une ArrayList est un tableau dont la taille est doublée chaque fois qu’il manque d’espace. Doubler la taille de la masortingce interne est une stratégie très efficace qui réduit la quantité d’éléments à copier à long terme. Nous n’entrerons pas dans la preuve de cela ici. La structure de données est très simple à utiliser:

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

L’inconvénient de la structure de données ArrayList est que l’on doit replacer les valeurs retracées dans leur type d’origine:

 int arrayListValue = (int)myArrayList[0] 

Sources et plus d’informations, vous pouvez trouver ici :

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