Klassische Konfliktbehandlung von Hash-Tabellen (Hash-Tabellen) in Datenstrukturen

Hash besteht darin, eine bestimmte Korrespondenzbeziehung f zwischen dem Speicherort des Datensatzes und seinem Schlüsselwort herzustellen, sodass jeder Schlüsselwortschlüssel einem Speicherort f (Schlüssel) entspricht und die gegenseitige Beziehung zwischen dem Schlüsselwort und dem Speicherort herstellt. Korrespondenzbeziehung, diese Beziehung f wird als Hash-Funktion (Hash-Funktion) bezeichnet. Der Herausgeber dieses Artikels spricht hauptsächlich über das Konfliktbehandlungsproblem der Hash-Funktion.

Während des Suchvorgangs hängt die Anzahl der Schlüsselcodevergleiche von der Anzahl der Konflikte ab, desto höher ist die Suche Effizienz wird es viele Konflikte geben und die Sucheffizienz wird gering sein. Daher sind Faktoren, die die Anzahl der Konflikte beeinflussen, Faktoren, die die Sucheffizienz beeinflussen. Die folgenden drei Faktoren beeinflussen die Anzahl der Konflikte:

Ob die Hash-Funktion einheitlich ist;

3 der Hash-Tabelle.

Der Füllfaktor der Hash-Tabelle ist definiert als: α = die Anzahl der in der Tabelle gefüllten Elemente / die Länge der Hash-Tabelle

α ist ein Vorzeichenfaktor für den Füllgrad der Hash-Tabelle. Da die Tabellenlänge ein fester Wert ist, ist α proportional zur „Anzahl der in der Tabelle ausgefüllten Elemente“. Je größer α ist, desto mehr Elemente werden in die Tabelle eingefügt, und je größer die Wahrscheinlichkeit eines Konflikts, desto kleiner α: Je weniger Elemente Sie in die Tabelle eintragen, desto geringer ist die Wahrscheinlichkeit, dass es zu Konflikten kommt.

Tatsächlich ist die durchschnittliche Suchlänge einer Hash-Tabelle eine Funktion des Füllfaktors α, aber verschiedene Methoden zur Konfliktbehandlung haben unterschiedliche Funktionen.

Zu den Methoden zur Lösung von Hash-Konflikten gehören im Allgemeinen:

NR.1 Offene Adressierungsmethode

Die sogenannte offene Adressierungsmethode bedeutet, dass, sobald ein Konflikt auftritt, nach dem gesucht wird Solange die Hash-Tabelle groß genug ist, kann die leere Hash-Adresse immer gefunden und der Datensatz gespeichert werden.

Formel: f(key)=(f(key)+di)%m(di=1,2,3….m-1)

Der Schlüsselwortsatz lautet beispielsweise {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}, die Tabellenlänge beträgt 12. Hash-Funktion f(key) = key mod 12.

Bei der Berechnung der ersten fünf Zahlen {12, 67, 56, 16, 25} sind sie alle Hash-Adressen ohne Konflikt und werden bei der Berechnung von Schlüssel = 37 direkt gespeichert. Es wird festgestellt, dass f(37) = 1. Zu diesem Zeitpunkt steht es im Konflikt mit der Position 25. Wenden Sie also die obige Formel f(37) = (f(37) + 1) mod 12 =2, an. Also wird 37 am Ort mit Index 2 gespeichert. Die nächsten 22, 29, 15 und 47 haben keine Konflikte und werden normal hinterlegt. Bei 48 haben wir berechnet, dass f(48) = 0, was mit der 0-Position von 12 in Konflikt steht. Es spielt keine Rolle, wir haben f(48) = (f(48) + 1) mod 12 = 1, was jetzt in Konflikt steht mit der Position 25. Konflikt. Also f(48) = (f(48) + 2) mod 12 = 2, es gibt immer noch einen Konflikt... bis f(48) = (f(48) + 6) mod 12 = 6, gibt es freie Stellen in der Tabelle unten dargestellt.

16

Seriennummer

0

1

2

3

4

5

6

7

8

9

10

11

Schlüsselwörter

12

25

序号	0	1	2	3	4	5	6	7	8	9	10	11
关键字	12	25			16			67	56

67

56

NR.2 Re-Hashing-Methode

Für Hash-Tabellen können mehrere Hash-Funktionen im Voraus vorbereitet werden.

Formel: fi(key)=RHi(key)(i=1,2,3...,k)

Hier ist RHi eine andere Hash-Funktion, Sie können dividieren und verlassen Der Rest wird zum Falten, Quadrieren und Zentrieren verwendet. Immer wenn ein Hash-Adresskonflikt auftritt, wird eine andere Hash-Funktion zur Berechnung verwendet.

Diese Methode kann die Keyword-Aggregation verhindern, erhöht aber auch entsprechend die Berechnungszeit.

NO.3 Kettenadressmethode (Zipper-Methode)

Speichern Sie alle Datensätze, deren Schlüsselwörter Synonyme sind, in einer einfach verknüpften Liste. Diese Liste wird als Synonym-Unterliste bezeichnet Vorher werden alle Synonym-Unterlisten in der Hash-Tabelle gespeichert. Verwenden Sie für den Schlüsselwortsatz {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34} dieselbe 12 wie zuvor als Rest und führen Sie die Divisions- und Restmethode aus, um die Struktur zu erhalten unten.

NR.4 Erstellen Sie einen öffentlichen Überlaufbereich

Diese Methode besteht darin, eine neue Adresse für Sie zu finden und einen öffentlichen Überlaufbereich für alle widersprüchlichen Schlüsselwörter zu erstellen. Überlaufbereich zur Lagerung.

Was das vorherige Beispiel betrifft, gibt es drei Schlüsselwörter 37, 48 und 34, die mit den vorherigen Schlüsselwortpositionen in Konflikt stehen, also speichern Sie sie in der Überlauftabelle. Wie unten gezeigt.

Nach der Berechnung der Hash-Adresse des angegebenen Werts durch die Hash-Funktion wird dieser zunächst mit der entsprechenden Position in der Basistabelle verglichen. Wenn sie gleich sind, Suche erfolgreich; wenn nicht gleich, führen Sie eine sequentielle Suche in der Überlauftabelle durch. Wenn es im Vergleich zur Basistabelle nur sehr wenige widersprüchliche Daten gibt, ist die Struktur des gemeinsamen Überlaufbereichs für die Suchleistung immer noch sehr hoch.

[Empfohlene Kurse: C++-bezogene Kurse]

Das obige ist der detaillierte Inhalt vonKlassische Konfliktbehandlung von Hash-Tabellen (Hash-Tabellen) in Datenstrukturen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!