Wie wähle ich zwischen einer Hash-Tabelle und einem Trie (Präfix-Baum)?

StackOverflow https://stackoverflow.com/questions/245878

Frage

Also, wenn ich zwischen einer Hash-Tabelle oder einem Präfix-Baum zu wählen, was die Unterscheidungsfaktoren sind, die mich führen würde einen über den anderen zu wählen. Aus meiner eigenen naiven Sicht scheint es, als ob mit einem Trie einige zusätzliche Overhead hat, da es nicht als Array gespeichert wird, sondern dass in Bezug auf der Laufzeit (vorausgesetzt, der längste Schlüssel das längste Wort Englisch ist) kann es im Wesentlichen seines O (1) (in Bezug auf die obere Grenze). Vielleicht ist das längste Wort Englisch ist 50 Zeichen?

Hash-Tabellen sind sofort nachschlagen , wenn Sie den Index erhalten . den Schlüssel Hashing der Index jedoch zu bekommen scheint, wie es leicht in der Nähe von 50 Schritte unternehmen könnte.

Kann jemand geben Sie mir einen erfahreneren Perspektive auf das? Dank!

War es hilfreich?

Lösung

Vorteile der Versuche:

Die Grundlagen:

  • Vorhersehbare O (k) Lookup Zeit, in der k die Größe der Taste
    • ist
  • Lookup kann weniger als k Zeit in Anspruch nehmen, wenn er nicht da ist
  • Unterstützung bestellt Traversal
  • Keine Notwendigkeit für eine Hash-Funktion
  • Löschen ist einfach

Neue Operationen:

  • Sie können schnell Präfixe des Schlüssels nachschlagen, aufzuzählen alle Einträge mit einem bestimmten Präfix, etc.

Vorteile der verlinkten Struktur:

  • Wenn es viele gemeinsame Präfixe sind, der Raum, den sie benötigen geteilt wird.
  • Immutable versucht können Struktur teilen. Statt einen Trie anstelle aktualisieren, können Sie einen neuen bauen, die nur entlang einer Niederlassung anders, an anderer Stelle in die alte trie zeigt. Dies kann für die Parallelität, mehrere gleichzeitige Versionen einer Tabelle, usw. nützlich sein.
  • Ein unveränderlicher trie ist komprimierbar. Das heißt, es teilt Struktur auf dem Suffixe als auch durch Hash-consing.

Vorteile von Hash-Tabellen:

  • Jeder weiß, Hash-Tabellen, nicht wahr? Ihr System wird bereits eine schöne gut optimierte Implementierung schneller als Versuche für die meisten Zwecke.
  • Ihr Schlüssel haben braucht keine spezielle Struktur.
  • Platz sparender als die offensichtliche verknüpft Trie-Struktur ( siehe Kommentare unten )

Andere Tipps

Es hängt alles davon ab, welches Problem Sie zu lösen versuchen. Wenn alles, was Sie tun müssen, um Einfügungen und Lookups ist, geht mit einer Hash-Tabelle. Wenn Sie komplexere Probleme wie Präfix bezogene Abfragen lösen müssen, dann ein Trie vielleicht die bessere Lösung sein.

Jeder weiß, Hash-Tabelle und ihre Anwendungen, aber es ist nicht genau das konstante Zeit nachzuschlagen, es hängt davon ab, wie groß die Hash-Tabelle ist, die Rechenkomplexität der Hash-Funktion.

Erstellen von großen Hash-Tabellen für eine effiziente Lookup ist keine elegante Lösung in den meisten Industrie Szenarien, in denen auch kleine Latenz / Skalierbarkeit Angelegenheiten (z .: Hochfrequenzhandel). Sie haben über die Datenstrukturen pflegen Raum optimiert werden, um es zu im Speicher in Anspruch nimmt Cache-Miss zu reduzieren.

Ein sehr gutes Beispiel, wo Trie passt besser zu den Anforderungen Middleware-Messaging. Sie haben eine Million Abonnenten und Verlegern von Nachrichten an verschiedene Kategorien (in JMS Begriffe - Themen oder Austausch), in solchen Fällen, wenn Sie Nachrichten herauszufiltern, auf Themen basieren soll (die eigentlich Strings sind), können Sie definitiv nicht wollen, Hash-Tabelle erstellen für die Millionen Abonnements mit Mio. Themen. Ein besserer Ansatz ist es, die Themen in Trie speichern, so dass, wenn Filterung basierend auf Thema Spiel gemacht wird, seine Komplexität ist unabhängig von der Anzahl der Themen / Zeichnungen / Herausgebers (hängt nur von der Länge der Saite). Ich mag es, weil Sie mit dieser Datenstruktur kreativ sein können, um den Platzbedarf zu optimieren und damit niedrigere Cache-Miss haben.

Verwenden Sie einen Baum:

  1. Wenn Sie Auto-Vervollständigen-Funktion
  2. Alle Wörter beginnend mit 'a' oder 'ax' so weiter.
  3. Ein Suffix-Baum ist eine besondere Form eines Baumes. Suffix Bäume haben eine ganze Liste von Vorteilen, die Hash nicht abdecken kann.

HashTable Implementierung ist der Raum effizient im Vergleich zu Grunde Trie Umsetzung. Aber mit Streichern, Bestellung ist notwendig, in den meisten praktischen Anwendungen. Aber HashTable stört total die lexographical Ordnung. Nun, wenn Sie Ihre Anwendung Operationen tut basierend auf lexographical Ordnung (wie Teil-Suche, alle Saiten mit gegebenem Präfix, alle Worte in sortierter Reihenfolge), sollten Sie Tries verwenden. Für nur Nachschlag sollte HashTable verwendet werden (wie wohl es Mindest Lookup Zeit gibt).

P. S:. Anders als diese, Ternary Suchbäume (TSTs) wäre eine ausgezeichnete Wahl. Seine Lookup-Zeit ist mehr als HashTable, ist aber zeiteffizient in allen anderen Operationen. Auch sein mehr Platz effizienter als versucht.

Es gibt etwas, das ich jemand ausdrücklich nicht gesehen erwähnen, dass ich denke, wichtig ist, im Auge zu behalten. Beide Hash-Tabellen und Versuche verschiedener Art werden in der Regel O(k) Operationen aufweisen, wobei k die Länge der Zeichenfolge in Bits ist (oder äquivalent in Zeichen).

Dies wird vorausgesetzt, Sie eine gute Hash-Funktion haben. Wenn Sie nicht „Farm“ wollen und „Nutztiere“ auf den gleichen Wert auf Hash, dann wird die Hash-Funktion müssen alle Bits des Schlüssels verwenden und so Hashing „Nutztieren“ sollte etwa doppelt so lange dauern, wie „Farm“ (es sei denn, Sie in irgendeiner Art sind Hash-Szenario von rollen, aber es gibt etwas ähnliche Operation Sparszenarien versucht auch). Und mit einem Vanille versuchen, es ist klar, warum „Nutztieren“ Einfügen dauert etwa doppelt so lang wie nur „Farm“. Auf lange Sicht ist es mit Druck versucht auch wahr.

Einfügen und Lookup auf einem Trie ist linear mit dem lengh der Eingabezeichenfolge O (n).

Ein Hash gibt Ihnen einen O (1) für die Suche an Insertion, aber zuerst müssen Sie die Hash-Berechnung basierend auf der Eingabezeichenfolge, die wiederum ist O (n).

conclussion, die asymptotische Zeitkomplexität ist in beiden Fällen linear.

Die Trie hat etwas mehr Aufwand aus Daten Perspektive, aber Sie können eine komprimierte Trie wählen, die Sie wieder gestellt werden, mehr oder weniger auf einer Bindung mit der Hash-Tabelle.

Um brechen die Krawatte Sie sich diese Frage stellen: Muss ich nur für ganze Wörter nachzuschlagen? Oder brauche ich alle Wörter zurückkehren ein Präfix passend? (Wie bei einem prädiktiven Texteingabesystem). Für den ersten Fall, gehen Sie für einen Hash. Es ist einfacher und sauberer Code. Einfacher zu testen und zu warten. Für einen ellaborated Verwendung Fall, in dem Präfix oder sufixes Angelegenheit, für eine Trie.

Und wenn Sie es nur zum Spaß, ein Trie-Implementierung würde einen Sonntagnachmittag zu einem guten Zweck.

Einige (in der Regel eingebettet in Echtzeit) Anwendungen erfordern, dass die Bearbeitungszeit der Daten unabhängig sein. In diesem Fall kann eine Hash-Tabelle eine bekannte Ausführungszeit garantieren, während ein Trie basierend auf den Daten variiert.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top