HashSet<T> versus Dictionary<K, V> en ce qui concerne le temps de recherche pour trouver si un élément existe

Question

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

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

Dont .Contains retournera plus rapidement ?

Pour clarifier, j'ai besoin de 10 millions d'objets (en fait, des chaînes de caractères) dont je dois vérifier l'existence dans la structure de données. Je n'itérerai JAMAIS.

Answer 1

Test de performance HashSet vs Liste vs Dictionnaire, tiré de ici .

Ajouter 1000000 objets (sans vérifier les doublons)

Contient la vérification de la moitié des objets d'une collection de 10000

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

Answer 2

Je suppose que vous voulez dire Dictionary<TKey, TValue> dans le second cas ? HashTable est une classe non générique.

Vous devez choisir la bonne collection pour le travail en fonction de vos besoins réels. Est-ce que vous veulent pour faire correspondre chaque clé à une valeur ? Si oui, utilisez Dictionary<,> . Si vous uniquement si vous y attachez de l'importance en tant qu'ensemble, utilisez HashSet<> .

Je m'attendrais HashSet<T>.Contains y Dictionary<TKey, TValue>.ContainsKey (qui sont des opérations comparables, en supposant que vous utilisiez votre dictionnaire de manière raisonnable) pour effectuer fondamentalement la même chose - ils utilisent le même algorithme, fondamentalement. Je suppose qu'avec les entrées dans Dictionary<,> étant plus large, vous avez plus de chances de faire sauter le cache avec Dictionary<,> qu'avec HashSet<> mais j'imagine que c'est insignifiant par rapport à la difficulté de choisir le mauvais type de données, simplement en fonction de ce que vous essayez d'obtenir.

Answer 3

Extrait de la documentation MSDN sur le dictionnaire<TKey,TValue>.

"La récupération d'une valeur en utilisant sa clé est très rapide, proche de O(1) car la classe Dictionary est implémentée comme une 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/poste est ancienne - mais en cherchant une réponse à une question similaire, je suis tombée sur ceci.

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

Answer 4

La réponse acceptée à cette question ne répond PAS valablement à la question ! Elle donne la bonne réponse, mais cette réponse n'est pas démontrée par les preuves fournies.

Ce que cette réponse montre, c'est que les recherches de clés sur une Dictionary o HashSet sont beaucoup plus rapides que de chercher dans une List . Ce qui est vrai, mais n'est ni intéressant, ni surprenant, ni la preuve qu'ils ont la capacité d'agir. 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 de 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");
    }
}

Answer 5

Il s'agit de structures de données différentes. Il n'existe pas non plus de version générique de HashTable .

HashSet contient des valeurs de type T qui HashTable (ou Dictionary ) contient des paires clé-valeur. Vous devez donc choisir la collection en fonction des données que vous souhaitez stocker.