Big O von Hash Table vs. binärer Suchbaum

Question

Welche länger dauern würde?

alle Elemente in einem binären Suchbaum in sortierter Reihenfolge oder drucken Sie alle Elemente gespeichert in einer Hash-Tabelle in sortierter Reihenfolge gespeichert drucken.

Es würde länger dauern, die Elemente einer Hash-Tabelle aus in sortierter Reihenfolge zu drucken, weil eine Hash-Tabelle wird nie richtig sortiert? und ein BST ist?

Answer 1

Sie sind richtig. Hashtables werden von einiger Hash-Funktion, nicht durch ihre natürliche Sortierreihenfolge sortiert, so würden Sie alle Einträge O (N) und sie O (NlogN) sortieren extrahieren müssen, während Sie einen binären Suchbaum in natürlicher Reihenfolge in O überqueren können ( N).

Beachten Sie jedoch, dass in Java, zum Beispiel gibt es ein LinkedHashSet und LinkedHashMap, die Ihnen einige der Vorteile von Hash gibt aber die in der Reihenfolge durchlaufen werden kann es wurde hinzugefügt, so dass Sie es sortieren konnten und in der Lage sein zu durchqueren es, dass Reihenfolge sortiert sowie Elemente von Hash zu extrahieren.

Answer 2

Richtig, eine Hash-Tabelle ist nicht „sortiert“ in der Art und Weise Sie wollen wahrscheinlich. Elemente in Hash-Tabellen sind nicht ganz vollständig sortieren, in der Regel, obwohl die Anordnung oft in der Nachbarschaft einer Art Art ist. Aber sie werden nach der Hash-Funktion angeordnet ist, die in der Regel nach ähnlichen Phrasen wild unterscheiden. Es ist nicht eine Art von jeder Metrik ein Mensch benutzen würde.

Wenn die Hauptsache Sie mit Ihrer Sammlung tun, ist es in sortierter Reihenfolge drucken, sind Sie am besten ab, irgendeine Art von BST verwenden.

Answer 3

Ein binärer Suchbaum wird in einer Art und Weise gespeichert, wenn Sie einen Tiefen ersten Traversal tun, werden Sie die Elemente in sortierter Reihenfolge finden (vorausgesetzt, Sie haben eine konsistente Vergleichsfunktion). The Big O einfach Elemente bereits im Baum Rückkehr wäre, die Big O den Baum zu durchqueren.

Sie sind richtig über Hash-Tabellen, sie sind nicht sortiert. In der Tat, um alles in einer einfachen Hash-Tabelle aufgelistet werden, müssen Sie jeden Eimer überprüfen, um zu sehen, was da drin ist, ziehen Sie es heraus, dann sortieren, was man bekommt. Viel Arbeit aus, dass eine sortierte Liste zu erhalten.

Answer 4

Richtig, Druck sortierten Daten in einer Hash-Tabelle gespeichert wären langsamer, da eine Hash-Tabelle Daten nicht sortiert ist. Es gibt Ihnen nur einen schnellen Weg, um ein bestimmtes Element zu finden. In „ Big O Notation “ es wird gesagt, dass das Element in konstanter Zeit gefunden werden kann, das heißt O (1) Zeit.

Auf der anderen Seite, können Sie ein Element in einem binären Suchbaum in „logarithmischer Zeit“ (O (log n)) finden, da die Daten bereits für Sie sortiert wurde.

Wenn Sie also Ziel ist es, eine sortierte Liste zu drucken, sind Sie viel besser dran, um die Daten in einer sortierten Reihenfolge gespeichert (d ein binärer Baum).

Genießen,

Robert C. Cartaino

Answer 5

Das bringt ein paar interessante Fragen auf. Ist ein Suchbaum noch schneller unter Berücksichtigung der folgenden?

1. Die Einbeziehung der Rüstzeit sowohl für die Hash-Tabelle und der BST?
2. Wenn der Hash-Algorithmus eine sortierte Liste von Wörtern erzeugt. Technisch gesehen, könnte man einen Hash-Tabelle erstellen, die einen Algorithmus verwendet, der Fall ist. In diesem Fall wird das die Geschwindigkeit des BST vs der Hash-Tabelle würde bis auf die Höhe der Zeit kommen, die Hash-Tabelle in der sortierten Reihenfolge zu füllen dauert.

Answer 6

Überprüfen Sie auch ähnliche Überlegungen überspringen Liste vs. Binary Tree: überspringen Liste vs. Binary Tree