HashSet <T> versus Dictionary <K, V> für die Suchzeit, um festzustellen, ob ein Element vorhanden ist

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


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

Wessen .ContainsMethode wird schneller zurückkehren?

Zur Verdeutlichung ist meine Anforderung, dass ich 10 Millionen Objekte (also wirklich Zeichenfolgen) habe, die ich überprüfen muss, ob sie in der Datenstruktur vorhanden sind. Ich werde nie wiederholen.

halivingston
quelle
1
Schritt 1: Überprüfen Sie, ob beide dasselbe tun (in diesem Fall dienen die beiden Sammlungen unterschiedlichen Zwecken). Schritt 2: Lesen Sie in der Dokumentation nach, ob Sie sich hinsichtlich ihrer asymptotischen Komplexität wohl fühlen. Schritt 3: Wenn Sie das Gefühl haben, dass Sie sich mehr Sorgen machen müssen, messen Sie sich selbst und stellen Sie dann die Frage, die den Benchmark zusammen mit dem Benchmark veröffentlicht. In Ihrem Fall wird die Frage im ersten Schritt sinnlos.
Nawfal

Antworten:

153

HashSet vs List vs Dictionary Leistungstest, von hier genommen .

1000000 Objekte hinzufügen (ohne Duplikate zu überprüfen)

Enthält die Prüfung für die Hälfte der Objekte einer Sammlung von 10000

Entfernen Sie die Hälfte der Objekte einer Sammlung von 10000

hätten
quelle
9
Tolle Analyse! Es sieht so aus, als ob .Contains for Dictionary so schnell ist, dass die Verwendung von HashSet im Fall des OP überhaupt keinen Nutzen bringt.
EtherDragon
2
Ja, ich hatte die gleiche Frage wie das OP. Ich habe bereits ein Wörterbuch, das ich aus anderen Gründen verwende, und wollte wissen, ob ich von einem Wechsel zu einem Hashset anstelle von ContainsKey profitiere. Sieht so aus, als wäre die Antwort nein, da beide so schnell sind.
FistOfFury
4
Im Gegensatz zu den vorherigen Kommentaren sollten Sie zu HashSet wechseln, da es Ihnen das bietet, was Sie möchten: Speichern einer Reihe von Werten (im Gegensatz zum Beibehalten einer Art Zuordnung). Diese Antwort zeigt an, dass die Leistung im Vergleich zu Dictionary nicht negativ beeinflusst wird.
Francois Beaussier
Diese Antwort sagt Ihnen NICHT, wie die Leistung von HashSet und Dictionary verglichen wird ... alles, was sie Ihnen sagt, ist, dass beide schneller als eine Liste sind ... na ja! Offensichtlich! HashSet könnte dreimal schneller sein und Sie würden es nicht wissen, da der relevante Test beide auf "Sie sind augenblicklich ... im Vergleich zu einer Liste " zusammengebrochen ist.
Brondahl
71

Ich nehme an, Sie meinen Dictionary<TKey, TValue>im zweiten Fall? HashTableist eine nicht generische Klasse.

Sie sollten die richtige Sammlung für den Job basierend auf Ihren tatsächlichen Anforderungen auswählen. Haben Sie eigentlich wollen jede Taste auf einen Wert zuzuordnen? Wenn ja, verwenden Sie Dictionary<,>. Wenn Sie sich nur als Set dafür interessieren, verwenden Sie HashSet<>.

Ich würde erwarten, dass ( HashSet<T>.Containsund Dictionary<TKey, TValue>.ContainsKeydas sind die vergleichbaren Operationen, vorausgesetzt, Sie verwenden Ihr Wörterbuch sinnvoll) im Grunde das Gleiche tun - sie verwenden im Grunde den gleichen Algorithmus. Ich denke Dictionary<,>, wenn die Einträge größer sind, ist die Wahrscheinlichkeit, dass Sie den Cache aufblasen, größer Dictionary<,>als bei HashSet<>, aber ich würde erwarten, dass dies unbedeutend ist, verglichen mit dem Schmerz, den falschen Datentyp einfach in Bezug auf das zu wählen, was Sie sind versuchen zu erreichen.

Jon Skeet
quelle
Ja, ich meinte Dictionary <TKey, TValue>. Ich mache mir nur Sorgen um die Suche nach der Existenz eines Elements in einer Datenstruktur, das ist alles .
Halivingston
3
@halivingston In diesem Fall verwenden Sie HashSet. Es macht deutlich, dass das alles ist, was Sie brauchen.
Jon Skeet
2
OK danke. Ich habe gerade ein HashSet <TKey> und eine Kopie von Dictionary <Tkey, TValue> ebenfalls im Speicher. Ich enthalte zuerst das HashSet und rufe dann den Wert im Wörterbuch <TKey, TValue> ab. Ich habe momentan unendlich viel Speicher, aber bald befürchte ich, dass mein Speicher eingeschränkt wird, und unser Team wird mich bitten, dieses doppelte Material im Speicher zu entfernen. Ab diesem Zeitpunkt werde ich gezwungen sein, Dictionary <TKey, TValue> zu verwenden.
Halivingston
4
Sie wissen, dass Dictionary auch eine ContainsKey-Funktion hat, oder? Warum duplizieren Sie Daten?
Blindy
8
Wenn Sie die Daten bereits im Wörterbuch haben, ist Ihr erster Kommentar eindeutig falsch - Sie müssen Schlüssel auch Werten zuordnen. Vielleicht nicht für diesen bestimmten Code, aber das ist irrelevant. Wenn Sie Dictionaryaus anderen Gründen bereits eine haben, sollten Sie diese verwenden.
Jon Skeet
7

Aus der MSDN-Dokumentation für Dictionary <TKey, TValue>

"Das Abrufen eines Werts mithilfe seines Schlüssels ist sehr schnell und liegt nahe bei O (1) , da die Dictionary-Klasse als Hash-Tabelle implementiert ist . "

Mit einem Hinweis:

"Die Geschwindigkeit des Abrufs hängt von der Qualität des Hashing-Algorithmus des für TKey angegebenen Typs ab."

Ich weiß, dass Ihre Frage / Ihr Beitrag alt ist - aber als ich nach einer Antwort auf eine ähnliche Frage suchte, bin ich darauf gestoßen.

Hoffe das hilft. Scrollen Sie zum Abschnitt " Bemerkungen ", um weitere Informationen zu erhalten. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

ripvlan
quelle
4

Dies sind unterschiedliche Datenstrukturen. Auch gibt es keine generische Version von HashTable.

HashSetenthält Werte vom Typ T, die HashTable(oder Dictionary) Schlüssel-Wert-Paare enthalten. Sie sollten also die Erfassung der Daten auswählen, die gespeichert werden sollen.

Andrew Bezzub
quelle
0

Die akzeptierte Antwort auf diese Frage beantwortet die Frage NICHT gültig! Es gibt zwar die richtige Antwort, aber diese Antwort wird durch die von ihnen vorgelegten Beweise nicht angezeigt.

Was diese Antwort zeigt, ist, dass Schlüsselsuchen auf einem Dictionaryoder HashSetviel schneller sind als auf einem List. Das ist wahr, aber nicht interessant, weder überraschend noch ein Beweis dafür, dass sie die gleiche Geschwindigkeit haben.

Ich habe den folgenden Code ausgeführt, um die Suchzeiten zu vergleichen, und meine Schlussfolgerung ist, dass sie tatsächlich die gleiche Geschwindigkeit haben. (Oder zumindest, wenn es einen Unterschied gibt, liegt der Unterschied innerhalb der Standardabweichung dieser Geschwindigkeit.)

Insbesondere 100.000.000 Suchvorgänge dauerten in diesem Test für mich zwischen 10 und 11,5 Sekunden.

Testcode:

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
quelle