Welche ist schneller ein Element in einer Hash-Tabelle oder in einer sortierten Liste zu finden?

https://stackoverflow.com/questions/876923

22-08-2019
|

Frage

Lösung

Algorithmus Komplexität ist eine gute Sache, zu wissen, und Hash-Tabellen sind dafür bekannt, O (1) , während ein sortierten Vektor (in Ihrem Fall, dass ich denke, es ist besser, ein sortiertes Array als eine Liste zu verwenden, ) liefert O (log n) Zugriffszeit.

Aber Sie sollten wissen, dass die Komplexität Notation gibt Ihnen die Zugriffszeit für N ins Unendliche gehen. Das bedeutet, dass, wenn Sie wissen, dass Ihre Daten wird weiter wachsen , Komplexität Notation gibt Ihnen einen Hinweis auf den Algorithmus zu wählen.

Wenn Sie wissen, dass Ihre Daten eine eher geringe Länge halten: zum Beispiel nur ein paar Einträge in Ihrem Array / Hash-Tabelle hat, Sie mit Ihrer Uhr und messen gehen müssen. So einen Test haben.

Zum Beispiel in einem anderen Problem: Sortierung ein Array. Für ein paar Einträge Blasensortierung während O (N ^ 2) kann schneller sein als .. die schnelle Art, während es O (n log n) .

Auch entsprechend zu anderen Antworten, und je nach Artikel, müssen Sie versuchen, die beste Hash-Funktion für Ihre hashtable Instanz zu finden. Sonst kann es zu dramatischer schlechter Leistung für die Suche in Ihrem hashtable führt (wie in Hank Homosexuell Antwort darauf hingewiesen).

Edit: Werfen Sie einen Blick auf diesen Artikel zu verstehen Sinne von Big O-Notation .

Andere Tipps

Unter der Annahme, dass die von ‚sortierte Liste‘ du meinst ‚Zufall zugänglich, sortierte Sammlung‘. Eine Liste hat die Eigenschaft, dass Sie nur das Element für Element durchqueren können, die in einem O (N) Komplexität führen.

Der schnellste Weg, um ein Element in einer sortierten Wende Sammlung von N-ary Suche, O (log N) zu finden, während eine Hash-Tabelle ohne collissions hat einen finden Komplexität von O (1).

Wenn der Hash-Algorithmus ist extrem langsam (und / oder schlecht), wird die Hash-Tabelle schneller sein.

UPDATE: Wie commen hat darauf hingewiesen, könnten Sie auch verminderte Leistung von zu vielen Kollisionen immer nicht, weil Ihr Hash-Algorithmus ist schlecht, sondern einfach, weil die Hash-Tabelle ist nicht groß genug. Die meisten Bibliothek Implementierungen (zumindest in Hochsprachen) wird automatisch Ihre Hash-Tabelle hinter den Kulissen-die wachsen langsamer als erwartet verursacht Leistung auf dem Einsatz, der das löst wachstums aber wenn Sie Ihre eigenen sind rollen, dann ist es auf jeden Fall etwas zu berücksichtigen.

Der get Betrieb in einem SortedList wird O(log n) während der gleiche Vorgang e eine HashTable O(1) ist. Also, normal , würde die HashTable viel schneller sein. Aber das hängt von einer Reihe von Faktoren ab:

Die Größe der Liste
Performance des Hashing-Algorithmus
Die Anzahl der Kollisionen / Qualität des Hashing-Algorithmus

Es hängt ganz von der Menge der Daten, die Sie gespeichert haben.

Wenn Sie genügend Speicher, um es zu werfen (so die Hash-Tabelle ist groß genug), die Hash-Tabelle wird die Zieldaten in einer festgelegten Menge von Zeit zu finden, aber die Notwendigkeit, den Hash berechnen wird einige (auch feste hinzufügen ) Overhead.

eine sortierte Liste Suche wird nicht Overhead-Hashing, aber die Zeit benötigt, um die Arbeit der tatsächlich Lokalisierung der Zieldaten zu tun wächst wie die Liste erhöhen.

Also, in der Regel eine sortierte Liste wird in der Regel für kleine Datensätze schneller sein. (Für extrem kleine Datensätze, die häufig geändert und / oder nur selten gesucht, ein un sortierte Liste kann noch schneller, da sie den Aufwand zu tun, die Art vermeidet.) Da die Datenmenge groß wird, das Wachstum der Suchzeit Liste überschattet die fix Gemeinkosten von Hashing und die Hash-Tabelle wird schneller.

Dabei gilt, dass Haltepunkt auf Ihre speziellen Hash-Tabelle und geordnet-list-Suche Implementierungen variieren je nach Bestimmungsort ist. Führen Sie Tests und Benchmark-Performance auf einer Reihe von typischerweise großen Datensätze zu sehen, welche tatsächlich eine bessere Leistung in Ihrem speziellen Fall. (Oder, wenn der Code bereits läuft „schnell genug“, nicht. Verwenden Sie einfach je nachdem, was Sie sind bequemer mit und mach dir keine Sorgen über etwas zu optimieren, das muss nicht optimiert werden.)

In einigen Fällen kommt es auf die Größe der Sammlung (und in geringerem Maße, Implementierungsdetails). Wenn Ihre Liste ist sehr klein, 10.05 Artikel vielleicht, würde ich die Liste erraten schneller wäre. xtofl es sonst hat Recht.

HashTable wäre effizienter für die Liste mehr als 10 Stück enthalten. Wenn die Liste weniger als 10 Stück hat, wird der Aufwand aufgrund Hashing algo mehr sein.

Wenn Sie brauchen einen schnellen Wörterbuch, sondern auch die Elemente in einer geordneten Art und Weise die OrderedDictionary verwenden halten müssen. (.NET 2.0 an)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow