Was ist die Datenstruktur einer Hash-Tabelle (Hash-Tabelle)? Was sind die spezifischen Operationen?

1. Was ist eine Hash-Tabelle?

Wenn Sie wissen möchten, was eine Hash-Tabelle ist, müssen Sie zunächst die Hash-Funktion verstehen

Hash Funktion:

Verglichen mit dem im vorherigen Blog diskutierten binären Sortierbaum, dem binären ausgeglichenen Baum, dem Rot-Schwarz-Baum B und dem B+-Baum beginnt ihre Suche am Wurzelknoten und dann Entnimmt die Daten oder den Index und sucht den Wert aus dem Knoten. Führen Sie einen Vergleich durch. Gibt es also eine Funktion H? Basierend auf dieser Funktion und dem Suchschlüsselwort kann die Position des Suchwerts direkt bestimmt werden, ohne einen nach dem anderen zu vergleichen. Auf diese Weise können Sie den Standort des Schlüssels im Voraus „kennen“, die Daten direkt finden und die Effizienz verbessern.

Das heißt, Adressindex = H (Schlüssel)

Um es ganz klar auszudrücken: Die Hash-Funktion berechnet den Ort, an dem die Adresse basierend auf dem Schlüssel gespeichert werden soll, und die Hash-Tabelle ist a Suche basierend auf der Hash-Funktion. Tabelle

II, Aufbaumethode der Hash-Funktion

Nach bisherigen Erfahrungen sind die folgenden Konstruktionsmethoden häufig verwendeter Hash-Funktionen:

Direkte Anpassungsmethode

Die Hash-Funktion ist eine lineare Funktion des Schlüsselworts wie z als H (Schlüssel) = a* Schlüssel+b

Diese Konstruktionsmethode ist relativ einfach und einheitlich, weist jedoch große Einschränkungen auf und ist auf den Fall beschränkt, dass die Adressgröße = Schlüsselwortsatz

ist Anwendungsbeispiel:

Annahme Es ist notwendig, die Altersverteilung der chinesischen Bevölkerung zu berechnen, wobei 10 die Mindesteinheit ist. Dieses Jahr ist 2018, daher werden die unter 10-Jährigen im Zeitraum 2008–2018 verteilt, und die unter 20-Jährigen im Zeitraum 1998–2008. Unter der Annahme, dass 2018 direkte Daten aus den Jahren 2018–2008 darstellt, sollten die Schlüsselwörter 2018 lauten , 2008, 1998...

Dann kann die Hash-Funktion H(key)=(2018-key)/10=201-key/10 konstruiert werden

Dann wird die Hash-Tabelle erstellt wie folgt

Indexschlüssel Alter Anzahl der Personen (Angenommene Daten)

0 2018 0-10 200W

1 2008 10-20 250W

2 1998 20-30 253W

3 1988 30- 40 300W

……

Zahlenanalysemethode
Gehen Sie davon aus, dass jedes Schlüsselwort das Schlüsselwort eingibt Der Satz besteht aus s Ziffern (k1, k2,...,knk1,k2,...,kn), analysiert alle Daten im Schlüssel und extrahiert eine Anzahl gleichmäßig verteilter Bits oder deren Kombination, um das Ganze

Anwendungsbeispiel

Da wir wissen, dass ID-Nummern regulär sind, möchten wir nun die ID-Nummern der Schüler einer Klasse speichern. Gehen wir davon aus, dass die Schüler dieser Klasse alle in derselben Gegend geboren wurden Im selben Jahr sind die ersten Ziffern ihrer Ausweise gleich. Dann können wir die folgenden unterschiedlichen Bits abfangen und speichern. Angenommen, es gibt 5 verschiedene Bits, und dann verwenden wir diese fünf Bits, um die Adresse darzustellen.

H(key)=key%100000

Diese Methode wird normalerweise verwendet, wenn die Anzahl der Ziffern lang ist. Es müssen bestimmte Regeln für die Zahlen gelten und die Verteilung der Zahlen muss erfolgen bekannt, wie zum Beispiel oben. Wir wissen im Voraus, dass die Schüler dieser Klasse im selben Jahr und in der gleichen Gegend geboren wurden.

Quadriermethode

Wenn in jeder Ziffer des Schlüsselworts bestimmte Zahlen häufig vorkommen, können Sie zunächst den Quadratwert des Schlüsselworts ermitteln und die Differenz um erweitern quadrieren und dann die mittlere Ziffer als endgültige Speicheradresse verwenden.

Verwendungsbeispiel

Zum Beispiel key=1234 1234^2=1522756, nehmen Sie 227 als Hash-Adresse

Zum Beispiel key=4321 4321^2=18671041, Nehmen Sie 671 als Hash-Adresse

Diese Methode eignet sich für Situationen, in denen die Daten nicht im Voraus bekannt sind und die Datenlänge gering ist

Faltmethode Wenn Die Zahl hat viele Ziffern, die Zahl kann in mehrere Teile geteilt werden, ihre Überlagerungssumme wird als Hash-Adresse verwendet
Verwendungsbeispiel
Beispiel: Schlüssel=123 456 789
Wir können es in 61524 speichern die letzten drei Ziffern, und es gibt eine Position von 524
Diese Methode eignet sich für Zahlen, wenn es viele Ziffern gibt und die Datenverteilung nicht im Voraus bekannt ist

Die Divisions- und Restmethode wird häufig verwendet

H (Schlüssel) = Schlüssel MOD p (p Offensichtlich ist die Wahl von p eine Schlüsselfrage.

Verwendungsbeispiel

Wenn wir beispielsweise 3 6 9 speichern, dann kann p nicht 3 sein

Weil 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p sollte eine Primzahl sein, die nicht größer als m ist, oder eine zusammengesetzte Zahl ohne Primfaktoren unter 20, was Adressduplizierungen (Konflikte) reduzieren kann

Zum Beispiel: Schlüssel = 7, 39, 18, 24, 33. Wenn 21, nehmen Sie die Tabellenlänge m als 9 und p als 7 und speichern Sie sie dann wie folgt:

Zufallszahlenmethode H (Schlüssel) =Random (Schlüssel)
Nimm den Zufallsfunktionswert des Schlüsselworts als Hash-Adresse

Überlegungen zum Design der Hash-Funktion

1 Die zum Berechnen der Hash-Adresse erforderliche Zeit (d. h. die Hash-Funktion selbst sollte nicht zu kompliziert sein)
2 Länge des Schlüsselworts
3. Ist die Verteilung der Schlüsselwörter gleichmäßig und regelmäßig?
5
3. Hash-Konflikt

Das heißt, unterschiedliche Schlüsselwerte erzeugen dieselbe Adresse, H (Schlüssel1) = H (Schlüssel2) Zum Beispiel, wenn wir 3 6 9 speichern Oben nimmt p 3 als

3 MOD 3 == 6 MOD 3 == 9 MOD 3

Zu diesem Zeitpunkt traten Hash-Konflikte in 3 6 9 auf


Die Lösung für den Hash Konflikt

Egal wie clever die Hash-Funktion gestaltet ist, es wird immer spezielle Schlüssel geben, die Hash-Konflikte verursachen, insbesondere bei dynamischen Nachschlagetabellen.

Die Hash-Funktion verfügt über die folgenden gängigen Methoden zum Lösen von Konflikten

1. Offene Anpassungsmethode

2 >

3. Methode des öffentlichen Überlaufbereichs

Erstellen Sie einen speziellen Speicherplatz zum Speichern widersprüchlicher Daten. Diese Methode eignet sich für Situationen, in denen weniger Daten und Konflikte vorliegen.

4. Rehash-Methode

Wenn ein Konflikt mit der ersten Hash-Funktion auftritt, verwenden Sie die zweite Hash-Funktion Dritte... Konzentrieren Sie sich auf die offene Anpassungsmethode und die Kettenadressmethode

Die offene Anpassungsmethode

Zuerst gibt es eine H-(Tasten-)Hash-Funktion

Wenn H(key1)=H(keyi)

Dann ist keyi Speicherort Hi=(H(key)+di)MODmHi=(H(key)+di)MODmm die Tabellenlänge

Beachten Sie, dass

Inkrement di die folgenden Eigenschaften haben sollte (Vollständigkeit): Die generierten Hi (Adressen) sind nicht gleich und die generierten s (m -1) Hi kann alle Adressen in der Hash-Tabelle abdecken

* Während der Quadraterkennung muss die Tabellenlänge m eine Primzahl von 4j+3 sein (die Länge der Quadraterkennungstabelle ist begrenzt)

* Es gibt keinen gemeinsamen Faktor zwischen m und di während der Zufallserkennung (die Zufallserkennung di ist begrenzt)

Beispiele für Konfliktlösungslösungen für drei offene Adressierungsmethoden

Den gibt es Ein Datensatz 19 01 23 14 55 68 11 86 37 soll in einem Array mit der Tabellenlänge 11 gespeichert werden, wobei H (Schlüssel) = Schlüssel MOD 11

Folgen Sie dann den oben genannten Anweisungen Drei Konfliktlösungsmethoden zum Speichern Der Prozess ist wie folgt:

(Tabellenerläuterung: Daten von vorne nach hinten einfügen. Wenn die Einfügeposition bereits belegt ist und ein Konflikt auftritt, beginnen Sie eine neue Zeile für den Konflikt und berechnen Sie die Adresse, bis die Adresse verfügbar ist. Das Endergebnis sind die obersten Daten (da es sich um die am meisten „belegenden“ Daten handelt)

Lineare Erkennung dann Hashing

Wir nehmen di=1, d. h. Nach dem Konflikt wird es an der Position nach dem Konflikt gespeichert. Wenn immer noch ein Konflikt besteht, fahren Sie rückwärts fort

Quadraterkennung und dann Hashing

Zufällige Erkennung nach Hashing (doppelte Erkennung und dann Hashing)

Nach der Kollision

H(key)'=(H(key) +di)MOD m In diesem Beispiel
H(key)=key MOD 11 Wenn wir di=key MOD 10 +1
nehmen, dann haben wir folgende Ergebnisse:

Kettenadressmethode

Nachdem ein Hash-Konflikt auftritt, fügen Sie nach den gespeicherten Daten einen Zeiger hinzu, um auf die widersprüchlichen Daten zu verweisen
Im obigen Beispiel ist die Kettenadressmethode wie folgt:

4. Durchsuchen der Hash-Tabelle

Der Suchvorgang ist derselbe wie der Tabellenerstellungsprozess Die offene Adressierungsmethode wird verwendet, um Konflikte zu behandeln. Der Suchvorgang ist dann:

Berechnen Sie für einen bestimmten Schlüssel den Hash-Adressindex = H (Schlüssel)

Wenn der Wert des Arrays arr [index] ist leer, die Suche ist nicht erfolgreich

Wenn das Array arr[index] == ist, ist die Suche erfolgreich

Andernfalls verwenden Sie die Konfliktlösungsmethode, um die nächste Adresse zu finden, bis arr[index] == key oder arr[index] == null

Es ist ersichtlich, dass unabhängig von der Funktion der Durchschnitt umso größer ist, je größer der Ladefaktor ist Suchlänge: Je kleiner der Ladefaktor α, desto besser? Nein, genau wie eine Tabellenlänge von 100 nur ein Datenelement speichert, ist α klein, aber die Raumnutzung ist nicht hoch. Dies ist ein Kompromiss zwischen Zeit und Raum. Unter normalen Umständen gilt α = 0,75 als die Situation mit der höchsten Gesamtnutzungseffizienz von Zeit und Raum.

Die obige Tabelle ist besonders nützlich. Angenommen, ich habe jetzt 10 Daten, möchte die Kettenadressmethode zum Lösen von Konflikten verwenden und benötige eine durchschnittliche Suchlänge

, dann gibt es 1+α/2

α

Das heißt, n/m

m>10/2

m>5 Das heißt, unter Verwendung der Kettenadresse Methode, die durchschnittliche Suchlänge beträgt Es handelt sich um eine Funktion, die auf dem Ladefaktor basiert, das heißt, wenn die Daten n zunehmen, kann ich die Tabellenlänge m erhöhen, um den Ladefaktor unverändert zu lassen und sicherzustellen, dass ASL unverändert bleibt.

Dann sollte die Struktur der Hash-Tabelle so aussehen:

5. Löschen der Hash-Tabelle

Zuerst kann die Kettenadressierungsmethode Elemente direkt löschen, die offene Adressierungsmethode jedoch nicht. Wenn wir Element 1 löschen und seine Position leer lassen, wird 23 nie gefunden. Der richtige Ansatz sollte darin bestehen, nicht vorhandene Daten einzufügen, bevor sie gelöscht werden, z. B. -1.

Weitere verwandte Fragen finden Sie auf der chinesischen PHP-Website:

Praktisches PHP-Video-Tutorial

Das obige ist der detaillierte Inhalt vonWas ist die Datenstruktur einer Hash-Tabelle (Hash-Tabelle)? Was sind die spezifischen Operationen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!