Was ist der Unterschied zwischen Verkettung und Sondierung in Hashtabellen?

Question

Wie funktionieren sie? Was sind ihre Hauptunterschiede? Was sind ihre jeweiligen Kompromisse? Was sind ihre Typen (falls vorhanden)? Wann wird man einem anderen vorgezogen (wenn überhaupt)?

PS: Ich habe bereits Anagrams - Hashing with chaining and probing in C und Why do we use linear probing in Hash tables when there is separate chaining linked with lists? durchlaufen, aber keiner scheint einen Kontrast zwischen den beiden Methoden zu ziehen.

Answer 1

Verkettung und offene Adressierung (eine einfache Implementierung, die auf Linear-Sondieren basiert) werden in Hashtables verwendet, um Kollisionen zu lösen. Eine Kollision tritt immer dann auf, wenn die Hash-Funktion für zwei verschiedene Schlüssel auf dieselbe Position zeigt, um den Wert zu speichern.

Um beide Werte mit unterschiedlichen Schlüsseln zu speichern, die am gleichen Ort gespeichert worden wären, haben Verkettung und offene Adressierung unterschiedliche Ansätze: Während der Verkettung wird der Konflikt gelöst, indem eine verknüpfte Liste von Werten mit demselben Hash erstellt wird; open-addressing versucht, einen anderen Speicherort zu finden, um die Werte mit demselben Hash zu speichern.

Eine interessante Alternative zum linearen Antasten für die Konfliktlösung bei offener Adressierung ist das sogenannte Double-Hashing.

Der Hauptunterschied besteht in der Geschwindigkeit des Abrufens des Werts, der unter verschiedenen Bedingungen gehashed wird.

Beginnen wir mit chaining als Kollisionsauflösung. Beachten Sie, dass Sie nach dem Berechnen der Hash-Funktion für Lisa das erste Element aus der Liste abrufen müssen, um den erforderlichen Wert zu erhalten. Daher greifen Sie auf den Zeiger auf den Kopf der Liste und dann auf den Wert: 2 Operationen.

Auf der anderen Seite erhalten Sie bei offener Adressierung, wie linear-probing, wenn keine Kollision vorliegt, sofort den Wert, den Sie suchen. Das heißt, Sie benötigen nur 1 Operation, die schneller ist.

Wenn Ihre HashTable jedoch beginnt, voll zu werden, und Sie eine hohe load factor haben, aufgrund der häufiger auftretenden Kollisionen, müssen Sie beim Prüfen mehr Hashtable-Positionen überprüfen, bevor Sie den gewünschten tatsächlichen Wert finden. Bei einem Ladefaktor von 0.8 beginnt die Verkettung aufgrund mehrerer Kollisionen effizienter zu werden: Sie müssten viele leere Zellen untersuchen, um den tatsächlichen Wert zu finden, den Sie mit der Suche haben möchten, während Sie bei der Verkettung eine Liste mit Werten haben die denselben Hash-Schlüssel haben.

Dies ist nur ein kurzer Überblick, da die tatsächlichen Daten, die Verteilung der Schlüssel, die verwendete Hash-Funktion und die präzise Implementierung der Kollisionsauflösung die tatsächliche Geschwindigkeit beeinflussen.