Bedeutung von offenem Hashing und geschlossenem Hashing

93

Offenes Hashing (separate Verkettung):

Beim offenen Hashing werden Schlüssel in verknüpften Listen gespeichert, die an Zellen einer Hash-Tabelle angehängt sind.

Geschlossenes Hashing (offene Adressierung):

Beim geschlossenen Hashing werden alle Schlüssel ohne Verwendung verknüpfter Listen in der Hash-Tabelle selbst gespeichert.

Ich kann nicht verstehen, warum sie offen, geschlossen und getrennt genannt werden. Kann es jemand erklären?

Hareendra Reddy
quelle
Eigentlich speichern wir niemals Schlüssel in Hash-Tabellen, wir nehmen ein Tupel (Schlüssel, Wert) und verwenden den Schlüssel, um zu berechnen, wo der Wert gespeichert werden soll. Also speichern wir die Werte in der Hash-Tabelle
Mr. Suryaa Jha

Antworten:

117

Die Verwendung von "geschlossen" vs. "offen" spiegelt wider, ob wir an die Verwendung einer bestimmten Position oder Datenstruktur gebunden sind oder nicht (dies ist eine äußerst vage Beschreibung, aber hoffentlich hilft der Rest).

Beispielsweise gibt das "Öffnen" in "Offene Adressierung" an, dass der Index (auch bekannt als "Adresse"), unter dem ein Objekt in der Hash-Tabelle gespeichert wird, nicht vollständig durch seinen Hash-Code bestimmt wird. Stattdessen kann der Index variieren, je nachdem, was bereits in der Hash-Tabelle enthalten ist.

Das "geschlossene" in "geschlossenes Hashing" bezieht sich auf die Tatsache, dass wir die Hash-Tabelle niemals verlassen; Jedes Objekt wird direkt an einem Index im internen Array der Hash-Tabelle gespeichert. Beachten Sie, dass dies nur mit einer offenen Adressierungsstrategie möglich ist. Dies erklärt, warum "geschlossenes Hashing" und "offene Adressierung" Synonyme sind.

Vergleichen Sie dies mit offenem Hashing. Bei dieser Strategie wird keines der Objekte tatsächlich im Array der Hash-Tabelle gespeichert. Sobald ein Objekt gehasht ist, wird es in einer Liste gespeichert, die vom internen Array der Hash-Tabelle getrennt ist. "offen" bezieht sich auf die Freiheit, die wir erhalten, wenn wir die Hash-Tabelle verlassen und eine separate Liste verwenden. "Separate Liste" gibt übrigens Hinweise darauf, warum offenes Hashing auch als "separate Verkettung" bezeichnet wird.

Kurz gesagt, "geschlossen" bezieht sich immer auf eine strenge Garantie, beispielsweise wenn wir garantieren, dass Objekte immer direkt in der Hash-Tabelle gespeichert werden (geschlossenes Hashing). Dann ist das Gegenteil von "geschlossen" "offen". Wenn Sie also keine solchen Garantien haben, wird die Strategie als "offen" betrachtet.

Ken Wayne VanderLinde
quelle
17
Wir sollten hinzufügen, dass Open Hashing (Separate Chaining) nicht auf verknüpfte Listen beschränkt ist, die nicht cachefreundlich sind und bei Kollisionsangriffen auf das O (n / 2) -Verhalten denegerieren. Sie können auch Bäume oder sortierte Arrays für die kollidierenden Eimer verwenden.
Rurban
Downvote aufgrund der widersprüchlichen Informationen: Sie sagten "offen" und "geschlossen sind Synonyme, dann am Ende:" das Gegenteil von "geschlossen" ist "offen"
Marwen Trabelsi
1
@ MarwenTrabelsi Ich habe nie gesagt, dass "geschlossen" und "offen" Synonyme sind.
Ken Wayne VanderLinde
"Dies erklärt, warum" geschlossenes Hashing "und" offene Adressierung "Synonyme sind."
Marwen Trabelsi
1
Kann jemand eine Quelle angeben, die beweist, dass dies die richtige historische Etymologie ist?
Santropedro
3

Sie haben ein Array, das die "Hash-Tabelle" ist.

Beim Open Hashing zeigt jede Zelle im Array auf eine Liste mit den Kollisionen. Das Hashing hat für alle Elemente in der verknüpften Liste den gleichen Index erstellt.

In Closed Hashing verwenden Sie nur ein Array für alles. Sie speichern die Kollisionen im selben Array. Der Trick besteht darin, auf intelligente Weise von Kollision zu Kollisionseinheit zu springen, damit Sie das finden, was Sie wollen. Und das auf reproduzierbare / deterministische Weise.

Anton Andreev
quelle
2

Der Name offene Adressierung bezieht sich auf die Tatsache, dass die Position ("Adresse") des Elements nicht durch seinen Hashwert bestimmt wird. (Diese Methode wird auch als geschlossenes Hashing bezeichnet.)

In separater Verkettung ist jeder Bucket unabhängig und verfügt über eine Art ADT (Liste, binäre Suchbäume usw.) von Einträgen mit demselben Index. In einer guten Hash-Tabelle hat jeder Bucket null oder einen Eintrag, da wir Operationen der Ordnung O (1) zum Einfügen, Suchen usw. benötigen.

Dies ist ein Beispiel für eine separate Verkettung unter Verwendung von C ++ mit einer einfachen Hash-Funktion unter Verwendung des Mod-Operators (eindeutig eine schlechte Hash-Funktion).

D. Pérez
quelle