HashSet préserve-t-il l'ordre d'insertion?

Question

Est-ce que le HashSet collection introduite dans .NET 3.5 conserve l’ordre d’insertion lorsqu’elle est itérée avec foreach?

La documentation indique que la collection n'est pas triée, mais cela ne dit rien sur l'ordre d'insertion. Une pré-version de la BCL entrée de blog indique qu'il n'est pas ordonné, mais cet article indique qu'il est conçu pour préserver l'insertion. ordre. Mes tests limités suggèrent que cet ordre est préservé, mais que cela pourrait être une coïncidence.

Answer 1

Cette page MSDN de HashSet indique spécifiquement:

  

Un ensemble est une collection qui ne contient aucun élément en double et dont les éléments ne sont dans aucun ordre particulier.

Answer 2

Je pense que l'article affirmant qu'il préserve les commandes est tout simplement faux. Pour des tests simples, l'ordre d'insertion peut très bien être conservé en raison de la structure interne, mais il n'est pas garanti et ne fonctionnera pas toujours de cette façon. Je vais essayer de trouver un contre-exemple.

EDIT: Voici le contre-exemple:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        var set = new HashSet<int>();

        set.Add(1);
        set.Add(2);
        set.Add(3);
        set.Remove(2);
        set.Add(4);


        foreach (int x in set)
        {
            Console.WriteLine(x);
        }
    }
}

Ceci imprime 1, 4, 3 bien que 3 ait été inséré avant 4.

Il est possible que, si vous ne supprimez jamais d’éléments, l’ordre d’insertion soit préservé. Je ne suis pas sûr, mais je ne serais pas entièrement surpris. Cependant, je pense que ce serait une très mauvaise idée de compter sur cela:

• Cela n'a pas été documenté, et la documentation indique explicitement que ce n'est pas trié.
• Je n'ai pas examiné les structures internes ni le code source (ce que je n'ai pas, bien sûr). Il faudrait que je les étudie attentivement avant de faire une telle affirmation de manière ferme.
• La mise en œuvre pourrait très facilement changer entre les versions du framework. S'en remettre à cela équivaudrait à compter sur le fait que l'implémentation string.GetHashCode ne change pas - ce que certaines personnes ont fait dans les jours .NET 1.1, puis elles ont été brûlées lorsque la mise en œuvre a changé dans .NET 2.0. ..

Answer 3

La documentation indique:

  

Une collection HashSet < (Of < (T >) >)) n'est pas triée et ne peut pas contenir d'éléments en double. Si la duplication de l'ordre ou des éléments est plus importante que les performances de votre application, envisagez d'utiliser la classe List & Lt; (Of & Lt; (T & Gt;) & Gt;) avec la méthode Sort. .

Par conséquent, peu importe si elle préserve réellement l’ordre des éléments dans la mise en œuvre actuelle, car cela n’est pas documenté de la sorte, et même si cela semble maintenant, cela peut changer à tout moment dans le futur (même dans les versions précédentes). un correctif au framework).

Vous devriez programmer des contrats documentés et non pas des détails de mise en œuvre .

Answer 4

Il existe spécifiquement une SortedSet<T> collection dans .NET4 .

Cela vous donnerait le tri, mais il est peu probable qu'il s'agisse d'un tri par ordre d'insertion. Puisque vous pouvez utiliser une coutume IComparer, vous pouvez théoriquement faire n'importe quoi.

Answer 5

Non, un ensemble de hachages ne conservera pas l'ordre d'insertion, du moins de manière prévisible. Vous pouvez utiliser un LinkedHashSet (Java) ou un équivalent. Un LinkedHashSet préservera l'ordre.

Si vous voulez de l'ordre, vous ne devriez même pas utiliser un ensemble en premier lieu ... ce n'est pas fait pour les éléments commandés, sauf dans des cas exceptionnels.

EDIT: on dirait que je suis en train de prêcher: - / Désolé.

Answer 6

Lecture du code source pour HashSet.AddIfNotPresent vous pouvez voir que l'ordre d'insertion est conservé en supposant qu'il n'y ait eu aucune suppression .

Ainsi, new HashSet<string> { "Tom", "Dick", "Harry" } conserve l'ordre, mais si vous supprimez Dick et ajoutez Rick, l'ordre sera [& "Tom &"; & "Rick &"; < !> "Harry &";].