Leistung von HashSet vs. Liste

Question

Es ist klar, dass eine Suchleistung des generischen HashSet<T> Klasse höher ist als die der generischen List<T> Klasse. Vergleichen Sie einfach den hashbasierten Schlüssel mit dem linearen Ansatz in der List<T> Klasse.

Die Berechnung eines Hash-Schlüssels kann jedoch selbst einige CPU-Zyklen in Anspruch nehmen, so dass die lineare Suche bei einer geringen Anzahl von Elementen eine echte Alternative zur HashSet<T> .

Meine Frage: Wo liegt der Break-even?

Zur Vereinfachung des Szenarios (und um fair zu sein) nehmen wir an, dass die List<T> Klasse verwendet das Element Equals() Methode, um einen Artikel zu identifizieren.

Answer 1

Sie können ein HybridDictionary verwenden, das automatisch die Sollbruchstelle erkennt und Null-Werte akzeptiert, so dass es im Wesentlichen dasselbe ist wie ein HashSet.

Answer 2

Die Antwort lautet wie immer: " Es kommt darauf an ". Ich nehme an, von den Tags Sie sprechen über C #.

Am besten ist es, wenn Sie feststellen

1. Eine Reihe von Daten
2. Anforderungen an die Verwendung

und schreiben Sie einige Testfälle.

Es hängt auch davon ab, wie Sie die Liste sortieren (wenn sie überhaupt sortiert ist), welche Art von Vergleichen durchgeführt werden müssen, wie lange der Vorgang "Vergleichen" für das jeweilige Objekt in der Liste dauert, oder sogar davon, wie Sie die Sammlung verwenden wollen.

Im Allgemeinen hängt die Wahl nicht so sehr von der Größe der Daten ab, mit denen Sie arbeiten, sondern eher davon, wie Sie auf sie zugreifen wollen. Haben Sie jedes Datenelement mit einer bestimmten Zeichenkette oder anderen Daten verknüpft? Eine Hash-basierte Sammlung wäre wahrscheinlich das Beste. Ist die Reihenfolge der Daten, die Sie speichern, wichtig, oder müssen Sie auf alle Daten gleichzeitig zugreifen? Dann ist eine reguläre Liste vielleicht besser geeignet.

Zusätzlich:

Natürlich gehen meine obigen Ausführungen davon aus, dass "Leistung" Datenzugriff bedeutet. Noch etwas anderes ist zu bedenken: Wonach suchen Sie, wenn Sie "Leistung" sagen? Geht es um die Leistung bei der Suche nach einzelnen Werten? Geht es um die Verwaltung großer (10000, 100000 oder mehr) Wertesätze? Ist es die Leistung beim Füllen der Datenstruktur mit Daten? Das Entfernen von Daten? Zugriff auf einzelne Datenbits? Das Ersetzen von Werten? Iteration über die Werte? Speicherverbrauch? Geschwindigkeit beim Kopieren von Daten? Wenn Sie beispielsweise über einen String-Wert auf Daten zugreifen, Ihre Hauptanforderung an die Leistung aber eine minimale Speichernutzung ist, könnten Sie mit widersprüchlichen Designfragen konfrontiert sein.

Answer 3

Das kommt darauf an. Wenn die genaue Antwort wirklich wichtig ist, sollten Sie ein Profil erstellen und es herausfinden. Wenn Sie sicher sind, dass Sie nie mehr als eine bestimmte Anzahl von Elementen in der Menge haben werden, wählen Sie eine Liste. Wenn die Anzahl nicht begrenzt ist, verwenden Sie ein HashSet.

Answer 4

Das hängt davon ab, was man hasht. Wenn es sich bei den Schlüsseln um ganze Zahlen handelt, benötigen Sie wahrscheinlich nicht sehr viele Elemente, bevor das HashSet schneller ist. Wenn Sie es auf eine Zeichenfolge Schlüssel sind dann wird es langsamer sein, und hängt von der Eingabe Zeichenfolge.

Sie können doch sicher ganz einfach einen Benchmark erstellen?

Answer 5

Ein Faktor, den Sie nicht berücksichtigen, ist die Robustheit der Funktion GetHashcode(). Mit einer perfekten Hash-Funktion wird das HashSet eindeutig eine bessere Suchleistung haben. Aber wie die Hash-Funktion abnimmt, so wird die HashSet-Suchzeit.