Was ist schneller, um ein Element in einer Hashtabelle oder in einer sortierten Liste zu finden?

Question

Was ist schneller, um ein Element in einer Hashtabelle oder in einer sortierten Liste zu finden?

Answer 1

Die Komplexität von Algorithmen ist gut zu wissen, und Hash-Tabellen sind dafür bekannt, dass sie O(1) während ein sortierter Vektor (in Ihrem Fall ist es wohl besser, ein sortiertes Array als eine Liste zu verwenden) Folgendes bietet O(log n) Zugriffszeit.

Sie sollten jedoch wissen, dass die Komplexitätsnotation die Zugriffszeit für N bis ins Unendliche angibt. Das bedeutet, dass Sie, wenn Sie wissen, dass Ihre Daten wird weiter wachsen Die Komplexitätsnotation gibt Ihnen einen Hinweis auf den zu wählenden Algorithmus.

Wenn Sie wissen, dass Ihre Daten eine eher geringe Länge haben werden, z.B. weil Sie nur wenige Einträge in Ihrem Array/ihrer Tabelle haben, müssen Sie mit Ihrer Uhr gehen und messen. Machen Sie also einen Test.

Zum Beispiel in einem anderen Problem: Sortieren eines Arrays. 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) .

Entsprechend den anderen Antworten und abhängig von Ihrem Objekt müssen Sie versuchen, die beste Hash-Funktion für Ihre Hashtable-Instanz zu finden. Andernfalls kann dies zu einer dramatisch schlechten Leistung bei der Suche in Ihrer Hashtabelle führen (wie in der Antwort von Hank Gay dargelegt).

Edit: Schauen Sie sich diesen Artikel an, um zu verstehen die Bedeutung der Big-O-Notation .

Answer 2

Unter der Annahme, dass Sie mit "sortierter Liste" eine "zufällig zugängliche, sortierte Sammlung" meinen. Eine Liste hat die Eigenschaft, dass man sie nur Element für Element durchlaufen kann, was zu einer O(N)-Komplexität führt.

Der schnellste Weg, ein Element in einer sortierten indizierbaren Sammlung zu finden, ist die N-äre Suche, O(logN), während eine Hashtabelle ohne Kollisionen eine Suchkomplexität von O(1) hat.

Answer 3

Es sei denn, der Hashing-Algorithmus ist extrem langsam (und/oder schlecht) ist, wird die Hashtabelle schneller sein.

UPDATE: Wie in Kommentaren angemerkt wurde, kann die Leistung auch durch zu viele Kollisionen beeinträchtigt werden, und zwar nicht, weil Ihr Hash-Algorithmus schlecht ist, sondern weil die Hashtabelle einfach nicht groß genug ist. Die meisten Bibliotheksimplementierungen (zumindest in Hochsprachen) lassen die Hashtable im Hintergrund automatisch wachsen - was die Leistung beim Einfügen, das das Wachstum auslöst, langsamer als erwartet macht -, aber wenn Sie Ihre eigene implementieren, sollten Sie das auf jeden Fall in Betracht ziehen.

Answer 4

Le site get Operation in einer SortedList es O(log n) während die gleiche Operation bei einer HashTable O(1) . Also, normalerweise die HashTable wäre viel schneller. Aber das hängt von einer Reihe von Faktoren ab:

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

Answer 5

Das hängt ganz davon ab, wie viele Daten Sie gespeichert haben.

Unter der Voraussetzung, dass Sie genügend Speicher zur Verfügung haben (die Hash-Tabelle ist also groß genug), findet die Hash-Tabelle die Zieldaten in einer bestimmten Zeit, aber die Notwendigkeit, den Hash zu berechnen, führt zu einem (ebenfalls festen) Overhead.

Beim Durchsuchen einer sortierten Liste entfällt dieser Hashing-Overhead, aber die Zeit, die für das Auffinden der Zieldaten benötigt wird, steigt mit dem Anwachsen der Liste.

Daher ist eine sortierte Liste im Allgemeinen schneller für kleine Datensätze. (Bei extrem kleinen Datensätzen, die häufig geändert und/oder selten durchsucht werden, ist eine un sortierte Liste kann sogar noch schneller sein, da sie den Overhead der Sortierung vermeidet). Mit zunehmender Größe des Datensatzes überwiegt der Anstieg der Suchzeit für die Liste den festen Overhead des Hash-Verfahrens, und die Hash-Tabelle wird schneller.

Wo dieser Haltepunkt liegt, hängt von der jeweiligen Implementierung der Hashtabelle und der sortierten Listensuche ab. Führen Sie Tests und Leistungsvergleiche mit einer Reihe von Datensätzen typischer Größe durch, um zu sehen, was in Ihrem speziellen Fall besser funktioniert. (Oder, wenn der Code bereits "schnell genug" läuft, lassen Sie es bleiben. Verwenden Sie einfach das, womit Sie besser zurechtkommen, und machen Sie sich keine Gedanken über die Optimierung von etwas, das nicht optimiert werden muss).