Ist es möglich, eine Hash-Tabelle zu beschleunigen, indem binäre Suchbäume für eine separate Verkettung verwendet werden?

Ich möchte eine Hash-Tabelle mithilfe von binären Suchbäumen implementieren, um die Suchkomplexität im Prozess der getrennten Verkettung von O (n) (mithilfe einer verknüpften Liste) auf O (Protokoll n) (mithilfe von BST) zu reduzieren. Kann das gemacht werden und wenn ja, wie? Es wäre einfacher zu verstehen, ob die Lösung Schritt für Schritt die Implementierung der Logik ist.

Ich möchte die Suchzeit in der Hashtabelle reduzieren (Build mit separater Verkettung), aber gleichzeitig möchte ich nicht, dass sich die Einfügezeit erhöht. Für mein Projekt kann ich die Hash-Funktion nicht ändern, um Kollisionen zu reduzieren. Aufgrund der Skalierbarkeit kommt es jedoch zu Kollisionen. Ich versuche, eine Lösung zu finden, damit ich im Falle einer Kollision irgendwie mit der besten Zugriffs- und Einfügezeit arbeiten kann ... dh um den aktuellen Status zu verwalten, als den gesamten Algorithmus neu zu strukturieren. Wenn es nicht klappt, muss es umstrukturiert werden. Also irgendwelche Ideen?

algorithms data-structures hashing binary-tree Aviral
quelle

Hash-Tabellen und binäre Suchbäume sind unterschiedliche Container. Sie können also nicht tun, was Sie vorschlagen (oder Sie machen einen terminologischen Fehler).

Basile Starynkevitch

Ich denke, Sie könnten ein Hash / Wert-Paar in jeden Knoten in einem Baum einfügen ... aber das wäre entweder eine schlechte Hash-Tabelle oder ein schlechter Binärbaum. Ohne eine Klarstellung darüber, warum Sie dies überhaupt tun möchten und wozu das Endergebnis fähig sein soll, bin ich mir nicht sicher, ob dies wirklich verantwortlich ist.

Ixrec

@AK_: Ja, so etwas, wie du gesagt hast. Ich möchte die Kollisionen mit binären Suchbaum behandeln. Ich habe meine Frage ein wenig korrigiert, um sie klarer zu machen.

Aviral

Beachten Sie, dass dann für jede Einfügung die Strafe von O (n log n) gilt . Wenn Sie eine Hash-Tabelle haben, die zu voll wird (und die Ketten länger sind, als Sie tolerieren können), erstellen Sie den Hash im Allgemeinen neu. Wenn Sie regelmäßig auf Ketten stoßen, die länger als 3 oder 4 sind, stimmt etwas nicht.

Es gibt eine Vielzahl von Variationen der Hash-Tabelle zur Kollisionsreduzierung, offenen Adressierung und dynamischen Größenänderung der Tabelle. Welches Ihren Anforderungen entspricht, müssen Sie prüfen. Ihr aktueller Ansatz wird unter Separate Verkettung mit anderen Strukturen behandelt

Antworten:

Was Sie verlangen, ist aufgrund Ihrer Einschränkungen möglich.

Analyse

Die Stärke einer Hash-Tabelle liegt in ihrer schnellen Suche und Einfügegeschwindigkeit. Um diese Geschwindigkeit zu erreichen, muss man jeden Anschein von Ordnung in der Tabelle aufgeben: dh alle Einträge sind durcheinander. Es ist akzeptabel, eine Liste als Tabelleneintrag zu verwenden, da die Listen, während die Durchquerung O (n) ist, dazu neigen, kurz zu sein, vorausgesetzt, die Hash-Tabelle ist ausreichend groß und die in der Tabelle gespeicherten Objekte werden unter Verwendung eines Hash-Algorithmus guter Qualität gehasht.

Ein binärer Suchbaum (BST) hat eine schnelle Einfügung und Suche bei O (log ₂ n). Außerdem werden die gespeicherten Elemente eingeschränkt: Es muss eine Möglichkeit geben, die Elemente zu ordnen. Bei zwei im Baum gespeicherten Elementen A und B muss festgestellt werden können, ob A vor B steht oder ob sie eine äquivalente Reihenfolge haben.

Eine Hash-Tabelle unterliegt keiner solchen Einschränkung: Elemente in einer Hash-Tabelle müssen zwei Eigenschaften haben. Erstens muss es eine Möglichkeit geben, festzustellen, ob sie gleichwertig sind. Zweitens muss es eine Möglichkeit geben, einen deterministischen Hash-Code zu berechnen. Bestellung ist keine Voraussetzung.

Wenn Ihre Hash-Tabellenelemente eine Reihenfolge haben, können Sie eine BST als Hash-Tabelleneintrag verwenden, um Objekte mit demselben Hash-Code (Kollisionen) zu speichern. Aufgrund einer BST mit O (log ₂ n) -Suche und Einfügung ist der schlechteste Fall für die gesamte Struktur (Hash-Tabelle plus BST) jedoch technisch besser als die Verwendung einer Liste als Tabelleneintrag. Abhängig von der BST-Implementierung wird mehr Speicher als eine Liste benötigt, aber wahrscheinlich nicht viel mehr.

Bitte beachten Sie, dass der Overhead und das Verhalten eines BST in realen Situationen normalerweise nichts als Hash-Tabellen-Buckets auf den Tisch bringen , weshalb die theoretisch schlechte Leistung einer Liste akzeptabel ist. Mit anderen Worten, die Hash-Tabelle gleicht die Schwäche der Liste aus, indem weniger Elemente in jede Liste (Bucket) eingefügt werden. Das Problem stellte jedoch ausdrücklich fest, dass die Hash-Tabelle nicht größer werden kann und Kollisionen häufiger auftreten als in einer Hash-Tabelle üblich.

Implementierung

Ich werde hier keinen Code einfügen, weil es ehrlich gesagt nicht wirklich notwendig ist und Sie sowieso keine Sprache angegeben haben.

Ich würde einfach die Standard-Hash-Tabelle, die die Standardbibliothek Ihrer Sprache enthält, in eine neue Klasse kopieren und dann den Tabellen-Bucket-Typ von einer Liste in einen Baum ändern. Abhängig von der Sprache und der Standardbibliothek kann dies sehr trivial sein.

Normalerweise würde ich das Kopieren und Einfügen einer solchen Codierung nicht befürworten. Es ist jedoch eine einfache Möglichkeit, sehr schnell eine kampferprobte Datenstruktur zu erhalten .

quelle

In asymptotischen Begriffen ändert die Verwendung eines Binärbaums für die Kollisionsbehandlung nichts an der erwarteten Leistung einer Hash-Tabelle, vorausgesetzt , die Hash-Tabelle hat bereits die üblichen Tricks ausgeführt, um eine amortisierte O (1) -Leistung zu erzielen. Wenn Sie die Größe der Hashtabelle ändern, um eine gute Leistung sicherzustellen, werden auch die erwarteten Elemente pro Bucket (die Größe der Binärbäume) voraussichtlich klein sein, sodass Sie in beiden Fällen das gleiche erwartete amortisierte O (1) erhalten. Selbst im schlimmsten Fall - ohne Angabe einer Ausgleichsbeschränkung - besteht die schlechteste Leistung eines Binärbaums darin, dass er sich ohnehin wie eine verknüpfte Liste verhält.

Steve314

@ Steve314 Denken Sie daran, dass das Problem darin besteht, dass es viele Kollisionen gibt. Er erwartet daher, dass ein Bucket mehr Elemente enthält als eine Hash-Tabelle normalerweise.

Guter Punkt - z. B. für eine Hash-Tabelle mit konstanter Größe und unbegrenzten Daten ist die asymptotische Leistung der Hash-Tabelle dieselbe wie die asymptotische Leistung der Kollisionsbehandlung - die Hash-Tabelle ändert nur die konstanten Faktoren.

Steve314

@ Steve314 richtig, im Wesentlichen, wenn die Hash-Tabelle die Anzahl der Elemente in jedem Bucket nicht effektiv begrenzen kann, verschlechtert sich die asymptotische Leistung in die Subdatenstruktur, die in jedem Bucket verwendet wird. Ich habe meiner Antwort einen Absatz hinzugefügt, um dies zu verdeutlichen.

Die Verwendung eines Binärbaums für die Kollisionsbehandlung in einer Hash-Tabelle ist nicht nur möglich, sondern wurde bereits durchgeführt.

Walter Bright ist am besten als Erfinder der Programmiersprache D bekannt , hat aber auch eine ECMAScript-Variante namens DMDScript geschrieben . In der Vergangenheit war eine Schlagzeile von DMDScript (oder möglicherweise eines Vorfahren - ich erinnere mich an den Namen DScript), dass seine Hashtabellen dazu neigten, die in vielen ähnlichen Sprachen zu übertreffen. Der Grund - Kollisionsbehandlung mit Binärbäumen.

Ich erinnere mich nicht genau, woher das kommt, aber die verwendeten Bäume waren naive Binärbäume ohne partielles Ausgleichsschema (nicht AVL, rot-schwarz oder was auch immer), was sinnvoll ist, wenn man annimmt, dass die Größe der Hashtabelle selbst geändert wird, wenn sie überfüllt wird und Sie erhalten keine absurd unwahrscheinlichen Raten von Hash-Kollisionen, die Binärbäume sollten immer klein sein. Grundsätzlich ist der schlimmste Fall immer noch derselbe wie die Verwendung einer verknüpften Liste für die Kollisionsbehandlung (außer Sie zahlen den Preis für zwei Zeiger pro Knoten anstelle von einem), aber der durchschnittliche Fall reduziert den Suchaufwand in jedem Hash-Bucket.

Steve314
quelle