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

Question

L' HashSet collection .NET 3.5 préserver l'ordre d'insertion lors de l'itération en utilisant foreach?

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

Answer 1

Cette page MSDN 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 la commande est tout simplement faux. Pour de simples tests de l'ordre d'insertion peuvent ainsi être conservés en raison de la structure interne, mais il n'est pas garanti et ne fonctionne 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 permet d'imprimer 1, 4, 3, malgré 3 ayant été insérée avant 4.

Il est possible que, si vous ne retirez jamais tous les éléments, il permettra de préserver l'ordre d'insertion. Je ne suis pas sûr, mais je ne serais pas totalement surpris. Cependant, je pense que ce serait une très mauvaise idée de s'appuyer sur:

• Ce n'est pas documentée à travailler de cette façon, et la documentation stipule explicitement que ce n'est pas triée.
• Je n'ai pas regardé à l'intérieur de structures ou de code source (je n'en ai pas, évidemment) - j'aurais à les étudier attentivement avant de prendre une telle demande dans une ferme.
• La mise en œuvre pourraient modifier très facilement entre les différentes versions du framework. En s'appuyant sur ce serait comme s'appuyant sur l' string.GetHashCode mise en œuvre pas de modification de certaines personnes dans les .NET 1.1 jours, et ensuite ils ont été brûlés lors de la mise en œuvre n'a changer dans .NET 2.0...

Answer 3

La documentation indique:

Un HashSet<(Of <(T>)>) de la collection n'est pas triée et ne peut pas contenir les éléments en double. Si la commande ou de l'élément de duplication est plus important que les performances de votre application, pensez à utiliser la Liste des<(Of <(T>)>) de la classe avec la méthode de Tri.

Par conséquent, il n'a pas d'importance si c'conserve l'ordre des éléments dans l'implémentation actuelle, car il n'est pas documentée de le faire, et même si elle semble maintenant, cela peut changer à tout moment dans l'avenir (même dans un correctif pour le cadre).

Vous devriez être en programmation à l'encontre de contrats documentés, pas de détails de mise en œuvre.

Answer 4

Oui, mais l'ordre d'insertion n'est pas séquentiel :) HashSet utilise en interne un tableau et décide où insérer en utilisant une fonction de hachage et modulo, comme toutes les tables de hachage. L'énumérateur HashSet examine essentiellement ce tableau où les éléments peuvent être placés à des emplacements aléatoires.

Vous ne pouvez donc pas l'utiliser avec foreach et vous attendre à revoir les éléments avec votre ordre d'insertion.

Answer 5

Non, un ensemble de hachage ne préservera 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 commander, 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 prêche: - / Désolé.