HashSet <T> versus Dictionary <K, V> pendant la recherche pour trouver si un élément existe

103
HashSet<T> t = new HashSet<T>();
// add 10 million items


Dictionary<K, V> t = new Dictionary<K, V>();
// add 10 million items.

Quelle .Containsméthode reviendra le plus rapidement?

Juste pour clarifier, mon exigence est que j'ai 10 millions d'objets (enfin, des chaînes vraiment) dont j'ai besoin pour vérifier s'ils existent dans la structure de données. Je ne réitérerai JAMAIS.

Halivingston
la source
1
Étape 1: voir si les deux font la même chose (dans ce cas, les deux collections sont à des fins différentes) Étape 2: reportez - vous à la documentation et voyez si vous vous sentez bien dans leur complexité asymptotique. Étape 3: Si vous sentez que vous devez vous inquiéter davantage, mesurez-vous, puis posez la question en affichant le repère avec lui. Dans votre cas, la question devient inutile dans un premier temps.
nawfal

Réponses:

153

Test de performance HashSet vs List vs Dictionary, tiré d' ici .

Ajouter 1000000 objets (sans vérifier les doublons)

Contient le chèque pour la moitié des objets d'une collection de 10000

Retirez la moitié des objets d'une collection de 10000

eu
la source
9
Excellente analyse! Il semble que le .Contains for Dictionary soit si rapide qu'il n'y a aucun avantage à utiliser HashSet, dans le cas de l'OP.
EtherDragon
2
ouais, j'avais la même question que l'OP. J'ai déjà un dictionnaire que j'utilise pour d'autres raisons et je voulais savoir si je tirais avantage du passage à un Hashset au lieu d'utiliser ContainsKey. On dirait que la réponse est non puisque les deux sont si rapides.
FistOfFury
4
Contrairement à ce que les commentaires précédents semblent impliquer, oui, vous devriez passer à HashSet car il vous donne ce que vous voulez: stocker un ensemble de valeurs (par opposition à maintenir une sorte de mappage). Cette réponse indique qu'il n'y aura aucun impact négatif sur les performances par rapport à Dictionary.
Francois Beaussier
Cette réponse ne vous dit PAS comment les performances de HashSet et Dictionary se comparent ... tout ce qu'elle vous dit, c'est qu'ils sont tous les deux plus rapides qu'une liste ... eh bien ... ouais! Évidemment! HashSet pourrait être 3 fois plus rapide et vous ne le sauriez pas car le test pertinent s'est réduit à la fois à "ils sont instantanés ... par rapport à une liste ".
Brondahl le
71

Je suppose que vous voulez dire Dictionary<TKey, TValue>dans le deuxième cas? HashTableest une classe non générique.

Vous devez choisir la bonne collection pour le travail en fonction de vos besoins réels. Avez - vous réellement souhaitez mapper chaque touche à une valeur? Si tel est le cas, utilisez Dictionary<,>. Si vous ne vous en souciez que comme un ensemble, utilisez HashSet<>.

Je m'attendrais à ce que HashSet<T>.Containset Dictionary<TKey, TValue>.ContainsKey(qui sont les opérations comparables, en supposant que vous utilisez votre dictionnaire raisonnablement) pour effectuer fondamentalement la même chose - ils utilisent le même algorithme, fondamentalement. Je suppose que les entrées Dictionary<,>étant plus vous vous retrouvez avec une plus grande probabilité de faire sauter le cache avec Dictionary<,>qu'avec HashSet<>, mais je pense que d'être insignifiant par rapport à la douleur de choisir le mauvais type de données simplement en termes de ce que vous êtes essayer de réaliser.

Jon Skeet
la source
Oui, je voulais dire Dictionary <TKey, TValue>. Je suis uniquement préoccupé par la recherche de l'existence d'un élément dans une structure de données, c'est tout .
halivingston
3
@halivingston Dans ce cas, utilisez HashSet. Il est évident que c'est tout ce que vous avez besoin.
Jon Skeet
2
OK merci. J'ai en fait un HashSet <TKey> en ce moment, et une copie en double de Dictionary <Tkey, TValue> également en mémoire. Je commence par .Contains sur le HashSet, puis récupère la valeur dans Dictionary <TKey, TValue>. J'ai une mémoire infinie en ce moment, mais je crains bientôt que ma mémoire ne soit limitée et notre équipe me demandera de supprimer ce truc en double dans la mémoire, à quel point je serai obligé d'utiliser Dictionary <TKey, TValue>.
halivingston
4
Vous savez que le dictionnaire a aussi une fonction ContainsKey? Pourquoi dupliquez-vous des données?
Blindy
8
Si vous avez déjà les données dans le dictionnaire, votre premier commentaire est clairement incorrect - vous devez également associer des clés à des valeurs. Peut-être pas pour ce morceau de code particulier, mais ce n'est pas pertinent. Si vous en avez déjà un Dictionarypour d'autres raisons, vous devriez l'utiliser.
Jon Skeet
7

À partir de la documentation MSDN pour Dictionary <TKey, TValue>

"Récupérer une valeur à l'aide de sa clé est très rapide, proche de O (1) , car la classe Dictionary est implémentée sous forme de table de hachage. "

Avec une note:

"La vitesse de récupération dépend de la qualité de l'algorithme de hachage du type spécifié pour TKey"

Je sais que votre question / message est ancien - mais en cherchant une réponse à une question similaire, je suis tombé dessus.

J'espère que cela t'aides. Faites défiler jusqu'à la section Remarques pour plus de détails. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

ripvlan
la source
4

Ce sont des structures de données différentes. Il n'existe pas non plus de version générique de HashTable.

HashSetcontient des valeurs de type T qui HashTable(ou Dictionary) contiennent des paires clé-valeur. Vous devez donc choisir la collecte sur les données dont vous avez besoin pour stocker.

Andrew Bezzub
la source
0

La réponse acceptée à cette question ne répond PAS valablement à la question! Il se trouve que cela donne la bonne réponse, mais cette réponse n'est pas montrée par les preuves qu'ils ont fournies.

Ce que cette réponse montre, c'est que les recherches clés sur un Dictionaryou HashSetsont beaucoup plus rapides que la recherche dans un fichier List. Ce qui est vrai, mais pas intéressant, ni surprenant, ni preuve qu'ils ont le même vitesse.

J'ai exécuté le code ci-dessous pour comparer les temps de recherche, et ma conclusion est qu'ils SONT en fait la même vitesse. (Ou du moins, s'il y a une différence, alors la différence est bien dans l'écart type de cette vitesse)

Plus précisément, 100 000 000 de recherches prenaient entre 10 et 11,5 secondes pour les deux, pour moi, dans ce test.

Code de test:

private const int TestReps = 100_000_000;
[Test]
public void CompareHashSetContainsVersusDictionaryContainsKey()
{
    for (int j = 0; j < 10; j++)
    {
        var rand = new Random();
        var dict = new Dictionary<int, int>();
        var hash = new HashSet<int>();

        for (int i = 0; i < TestReps; i++)
        {
            var key = rand.Next();
            var value = rand.Next();
            hash.Add(key);
            dict.TryAdd(key, value);
        }

        var testPoints = Enumerable.Repeat(1, TestReps).Select(_ => rand.Next()).ToArray();
        var timer = new Stopwatch();
        var total = 0;
        
        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (hash.Contains(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);
        
        var target = total;
        Assert.That(total == target);
        

        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (dict.ContainsKey(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);

        Assert.That(total == target * 2);
        Console.WriteLine("Set");
    }
}
Brondahl
la source