Hash-Tabelle: Warum ist das löschen schwierig in offenen Adressierungsschema

Ich versuche zu verstehen, die offene Adressierung-Methode. Ich beziehe mich auf T. H. Cormen Buch zu diesem Thema, die besagt, dass der Löschvorgang schwierig ist, in offener Adressierung. Ich bin völlig stecken in diesem Absatz:

Löschen aus einem öffnen-Adresse, hash-Tabelle ist schwierig. Wenn wir löschen einen Schlüssel aus Schlitz i wir können nicht einfach daneben, dass der slot als leer durch die Speicherung NIL in es. Dies könnte es unmöglich machen, abrufen einer beliebigen Taste k während deren Einschaltung wir hatten sondiert slot i und fanden es besetzt.

Ich verstehe das nicht. Bitte erklären mit einigen Beispielen.

InformationsquelleAutor Nishant Kumar | 2012-02-03

44

Übernehmen hash(x) = hash(y) = hash(z) = i. Und übernehmen x wurde zuerst eingefügt, dann y und dann z.

In offener Adressierung: table[i] = x, table[i+1] = y, table[i+2] = z.

Nun davon aus, das Sie löschen möchten x, und legen Sie es zurück zu NULL.

Wenn später Sie die Suche für z werden Sie feststellen, dass hash(z) = i und table[i] = NULL, und Sie gibt eine falsche Antwort: z ist nicht in der Tabelle.

Um dies zu überwinden, müssen Sie table[i] mit einer speziellen Markierung, die angibt, um die Suche-Funktion zu halten suchen auf der index i+1, denn es könnte sein element gibt es mit dem hash-Wert ist auch i.
- Amit: vielen Dank für deine schöne Erklärung
- Sie sind herzlich willkommen. froh, dass es dir geholfen.
- Amit: Können Sie bitte erklären Sie dies: Drei Techniken werden Häufig verwendet, um zu berechnen, probe-Sequenzen erforderlich für offene Adressierung: lineares Sondieren, quadratisches Sondieren und doppeltes hashing. Diese Techniken garantieren Ihnen, dass h(k, 1), h(k, 2), ., h(k, m) ist eine permutation von 0, 1, . . . , m - 1 für alle Schlüssel k. Keine dieser Techniken erfüllt die Annahme von uniform hashing, da jedoch keiner von Ihnen ist fähig mehr als m2 verschiedene probe-Sequenzen (anstatt der m! das uniform-hashing erfordert).
- wenn Sie unter der Annahme, dass hash(x) = hash(y) = hash(z) = i , dann wie kann es dargestellt werden durch offene Adressierung . In diesem Fall benötigen Sie zur Aufrechterhaltung einer verknüpften Liste(oder eine andere Art der Verkettung) der Sätze richtig ?
- Auch ich habe einen Verwandte Frage hier . können Sie versuchen, Sie zu beantworten ?
- In "offene Adressierung", wenn hash(x) = hash(y) = i, und angenommen x wurde erstmals eingesetzt, um den index ich. Dann, wenn Sie ein insert-y - einfügen an eine andere vorspeise. Die einfachste (Wenngleich nicht beste) Weg, es zu tun ist: insert(y,position)=if (position is occupied) insert(y,position+1); else table[position]=y
- es ist nicht so schwierig, Koaleszenz-hashing, können Sie den Wert auf null, aber halten Sie die next Zeiger auf den nächsten index, in Koaleszenz Ansatz wie seine offene Adressierung Ansatz, aber es ist next Eigenschaft, die zeigt nächste position in der Tabelle.
InformationsquelleAutor amit
11

In einem offenen Adressierungsschema, lookups rufen Sie eine Reihe von Sonden, bis der Schlüssel gefunden wird oder ein leerer slot gefunden wird.

Wenn ein Schlüssel beinhaltet eine Kette von mehreren Sonden, es wird verloren gehen (nicht auffindbar), wenn irgendwo in der Kette eine der anderen Tasten entfernt, so dass ein leeren slot, wo ein Sprungbrett gebraucht wurde.

Die übliche Lösung ist, einen Schlüssel zu löschen durch markieren seinen Platz als available-for-resuse-aber-nicht-wirklich leer ist. In anderen Worten, ein Ersatz-Trittbrett wird Hinzugefügt, so dass die Sonde Ketten auf andere Tasten sind nicht kurz geschnitten.

Hoffe, das hilft deinem Verständnis.
- Bonus-Punkte für die Erwähnung, dass die gelöschten slot ist noch für die Wiederverwendung verfügbar.
InformationsquelleAutor Raymond Hettinger
7

Löschung aus einer linear abgetasteten offen angesprochen hash-Tabelle ist einfach. Es war pseudo-code, für die es auf der Wikipedia-Hash-Tabelle-Seite für Jahre. Ich weiß nicht, warum gibt es nicht mehr, aber hier ist ein permalink zurück zu, als es war: Alte Wikipedia-Hash-Tabelle-Seite und hier für Ihre Bequemlichkeit ist der pseudocode:
```
function remove(key)
 i := find_slot(key)
 if slot[i] is unoccupied
     return   //key is not in the table
 j := i
 loop
     j := (j+1) modulo num_slots
     if slot[j] is unoccupied
         exit loop
     k := hash(slot[j].key) modulo num_slots
     if (j > i and (k <= i or k > j)) or
        (j < i and (k <= i and k > j)) (note 2)
         slot[i] := slot[j]
         i := j
 mark slot[i] as unoccupied
```
Gibt es auch ein ref auf dieser Seite einige real-code. Ich glaube, das hat genau die gleiche performance-Charakteristik wie das einfügen.

Diese Methode der Löschung ist besser als der viel gebrauchte "Marke gelöscht, und gelegentlich rehash alles", denn die oben genannte Methode ist konstanter Zeit eher als amortisiert konstanter Zeit. Wenn Sie eine hash-Tabelle von einer million Artikel, die Sie hinzufügen und löschen aus, in der "Marke gelöscht" - Methode, gelegentlich hinzuzufügen, zu löschen oder ist eine million mal mehr als die vor und nach dem es - und das ist keine gute performance.
- Korrigieren Sie mich, wenn ich falsch Liege, aber wäre es nicht einfacher, einfach einen hash aus key und dann vergleichen, ob hashes der Schlüssel und slot[j] gleich sind? Was ich tun würde, ist das finden gerade die letzten besetzten slot (ab j = i + 1) mit dem gleichen hash als Schlüssel und bewegen Sie ihn dann in der i-TEN slot. Sie haben einen einzigen move-operation und berechnen einer hash für num_collisions Zeiten - Komplexität, dass ist das gleiche wie für contains(key) und einfügen(Schlüssel -) Operationen.
- Wenn alle Steckplätze sind entweder verwendet oder markiert, auf der Suche nach einem unexisting element wird letzten für immer, oder zumindest zu Fuss durch die ganze Tabelle, bevor Sie schließlich die Feststellung, dass es nicht existiert. Dies muss geschehen, wenn das Programm ausgeführt wird, für eine Zeit lang genug.
- Ich verstehe nicht, warum es für immer andauern würde. Sie finden Sie zuerst den nächsten leeren Platz und von dort aus rückwärts suchen Sie einen Eintrag, der vielleicht hash auf ich. Wenn gefunden (Steckplatz j), dass man in der I-TEN slot. Anschließend wiederholen Sie dieses Verfahren für slot-j, bis Sie kaum eine übereinstimmung finden. Sicher, schlimmsten Fall Sie Scannen alles, aber angenommen, die Auslastung ist niedrig genug, dies sollte durchgeführt werden in O(1) Zeit.
InformationsquelleAutor hoopsnake

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.