Die Verwirrung hier ist auf die Notation in CLRS zurückzuführen. Um mit der wahren Frage übereinzustimmen, verwende ich die CLRS-Notation in dieser Antwort.

Wir verwenden die Hash-Tabelle, um Schlüssel-Wert-Paare zu speichern. Der Wertteil wird im CLRS-Pseudocode nicht erwähnt, während der Schlüsselteil als k definiert ist.

In meiner Kopie von CLR (ich arbeite hier von der ersten Ausgabe ab) sind die Routinen, die für Hashes mit Verkettung aufgelistet sind, Einfügen, Suchen und Löschen (mit ausführlicheren Namen im Buch). Die Einfüge- und Löschroutinen nehmen das Argument x , , das ist das verknüpfte Listenelement, das dem Schlüssel key[x] zugeordnet ist. Die Suchroutine verwendet das Argument k , das den Schlüsselabschnitt eines Schlüssel / Wert-Paares darstellt. Ich glaube, die Verwirrung besteht darin, dass Sie die Löschroutine so interpretiert haben, als würden Sie einen Schlüssel anstelle eines verknüpften Listenelements verwenden.

Da x ein verkettetes Listenelement ist, ist es ausreichend, eine O (1) -Deletion von der verknüpften Liste im h(key[x]) -Slot der Hash-Tabelle zu machen, wenn es doppelt ist. verknüpfte Liste Wenn es sich jedoch um eine einfach verknüpfte Liste handelt, ist x nicht ausreichend. In diesem Fall müssen Sie am Anfang der verknüpften Liste im Slot h(key[x]) der Tabelle beginnen und die Liste durchlaufen, bis Sie schließlich x erreichen, um den Vorgänger zu erhalten. Nur wenn Sie den Vorgänger von x haben, kann der Löschvorgang durchgeführt werden, weshalb das Buch besagt, dass der einfach verknüpfte Fall zu denselben Laufzeiten für Suchen und Löschen führt.

Zusätzliche Diskussion

Obwohl CLRS angibt, dass Sie die Löschung in O (1) -Zeit durchführen können, müssen Sie bei einer doppelt verknüpften Liste auch x beim Aufrufen von delete angeben. Der Punkt ist folgender: Sie definierten die Suchroutine, um ein Element x zurückzugeben. Diese Suche ist keine konstante Zeit für einen beliebigen Schlüssel k . Sobald Sie x von der Suchroutine erhalten haben, vermeiden Sie die Kosten einer weiteren Suche im Aufruf zum Löschen, wenn Sie doppelt verknüpfte Listen verwenden.

Die Pseudocode-Routinen sind niedriger als bei Verwendung einer Hashtabellenschnittstelle für einen Benutzer. Zum Beispiel fehlt eine Löschroutine, die den Schlüssel k als Argument akzeptiert. Wenn dieses Löschen dem Benutzer zugänglich gemacht wird, würden Sie wahrscheinlich einfach auf einfach verknüpften Listen bleiben und eine spezielle Version der Suche haben, um das mit x verbundene k und sein Vorgängerelement gleichzeitig zu finden.

Ich kann mir einen Grund vorstellen, aber das ist nicht sehr gut. Angenommen, wir haben eine Hash-Tabelle der Größe 100. Nun nehmen wir an, dass die Werte A und G der Tabelle hinzugefügt werden. Vielleicht hackt A zu Slot 75. Nun nehme man an, dass G auch auf 75 hashed, und unsere Kollisions-Auflösungsstrategie ist, um eine konstante Schrittgröße von 80 vorwärts zu springen. Also versuchen wir zu (75 + 80)% 100 = 55 zu springen. Anstatt an der Vorderseite der Liste zu beginnen und vorwärts 85 zu fahren, könnten wir am aktuellen Knoten beginnen und rückwärts 20 zurückgehen, was schneller ist. Wenn wir zu dem Knoten kommen, bei dem G ist, können wir ihn als Grabstein markieren, um ihn zu löschen.

Dennoch empfehle ich die Verwendung von Arrays bei der Implementierung von Hash-Tabellen.

Hashtable wird oft als Vektor von Listen implementiert. Wo Index in Vektor ist der Schlüssel (Hash).
Wenn Sie nicht mehr als einen Wert pro Schlüssel haben und keine Logik in Bezug auf diese Werte interessiert, reicht eine einzelne verknüpfte Liste. Ein komplexeres / spezifischeres Design beim Auswählen eines der Werte erfordert möglicherweise eine doppelt verkettete Liste.

Lassen Sie uns die Datenstrukturen für einen Caching-Proxy entwerfen. Wir brauchen eine Karte von URLs zu Inhalt; Lassen Sie uns eine Hash-Tabelle verwenden. Wir brauchen auch einen Weg, um Seiten zu finden, die wir vertreiben können; Verwenden wir eine FIFO-Warteschlange, um die Reihenfolge zu verfolgen, in der zuletzt auf URLs zugegriffen wurde, sodass wir die LRU-Räumung implementieren können. In C könnte die Datenstruktur ungefähr wie

Eine Feinheit: Um einen Sonderfall zu vermeiden und Speicherplatz in den Hash-Buckets zu verschwenden, zeigt x->hashbucketprev auf den Zeiger, der auf x zeigt. Wenn x zuerst im Bucket ist, zeigt es in hashbucket ; Ansonsten zeigt es auf einen anderen Knoten. Wir können x aus seinem Bucket mit

Bei der Entfernung durchlaufen wir die Knoten, auf die zuletzt zugegriffen wurde, über den Zeiger queuehead . Ohne hashbucketprev müssten wir jeden Knoten hashen und seinen Vorgänger mit einer linearen Suche finden, da wir ihn nicht über hashbucketnext erreicht haben. (Ob das wirklich schlimm ist, ist fraglich, da der Hashwert billig sein sollte und die Kette kurz sein sollte. Ich vermute, dass der Kommentar, nach dem Sie fragen, im Grunde ein Wegwerfartikel war.)

Wenn die Elemente in Ihrer Hashtabelle in "aufdringlichen" Listen gespeichert sind, können sie sich der verknüpften Liste bewusst sein, der sie angehören. Wenn die Intrusivliste also doppelt verknüpft ist, können Elemente schnell aus der Tabelle entfernt werden.

(Beachten Sie jedoch, dass die "Aufdringlichkeit" als Verletzung der Abstraktionsprinzipien angesehen werden kann ...)

Ein Beispiel: In einem objektorientierten Kontext kann eine aufdringliche Liste erfordern, dass alle Elemente von einer Basisklasse abgeleitet werden.

Der Leistungsvorteil besteht darin, dass jedes Element schnell aus seiner doppelt verknüpften Liste entfernt werden kann, ohne den Rest der Liste zu lokalisieren oder zu durchlaufen.

Leider ist meine Kopie von CLRS gerade in einem anderen Land, daher kann ich sie nicht als Referenz verwenden. Aber hier ist, was ich denke, es sagt:

Grundsätzlich unterstützt eine doppelt verknüpfte Liste O (1) Löschungen, denn wenn Sie die Adresse des Elements kennen, können Sie einfach Folgendes tun:

um das Objekt aus der verknüpften Liste zu löschen, während Sie in einer verknüpften Liste, selbst wenn Sie die Adresse haben, die verknüpfte Liste durchsuchen müssen, um den Vorgänger zu finden:

Wenn Sie also ein Element aus der Hash-Tabelle löschen, suchen Sie es nach, was aufgrund der Eigenschaften von Hash-Tabellen O (1) ist, und löschen Sie es dann in O (1), da Sie jetzt die Adresse haben.

Wenn dies eine einfach verknüpfte Liste wäre, müssten Sie den Vorgänger des Objekts finden, das Sie löschen möchten, was O (n) erfordern würde.

Allerdings:

Ich bin auch etwas verwirrt über diese Behauptung im Fall von verketteten Hash-Tabellen, weil Lookup funktioniert. Wenn es in einer verketteten Hashtabelle zu einer Kollision kommt, müssen Sie bereits die verknüpfte Werteliste durchlaufen, um das gewünschte Element zu finden, und müssen daher auch den Vorgänger finden.

Aber die Art und Weise, wie die Aussage formuliert wird, gibt eine Klarstellung: "Wenn die Hash-Tabelle das Löschen unterstützt, sollten ihre verknüpften Listen doppelt verknüpft sein, damit wir einen Artikel schnell löschen können. Wenn die Listen nur einzeln verknüpft waren, dann löschen Element x, wir müssten zuerst x in der Liste T [h (x.key)] finden, damit wir das nächste Attribut des Vorgängers von x aktualisieren könnten. "

Dies bedeutet, dass Sie bereits das Element x haben, was bedeutet, dass Sie es auf die obige Weise löschen können. Wenn Sie eine einfach verknüpfte Liste verwenden würden, selbst wenn Sie bereits das Element x hätten, müssten Sie immer noch den Vorgänger finden, um ihn zu löschen.