Hash-Funktion
In diesem Abschnitt besprechen wir die Hash-Funktion, die dabei hilft, den Hash-Code des zugehörigen Schlüssels des Datenelements in der Datenstruktur auszuführen, wie im Folgenden erwähnt:
Int hashItem ( int Schlüssel ){
zurückkehren Schlüssel % Tischgröße ;
}
Der Vorgang des Ausführens des Index eines Arrays wird als Hashing bezeichnet. Manchmal wird derselbe Codetyp ausgeführt, um denselben Index mit denselben Schlüsseln, sogenannten Kollisionen, zu generieren, was durch unterschiedliche Verkettung (Erstellung verknüpfter Listen) und die Implementierung offener Adressierungsstrategien gehandhabt wird.
Funktionsweise der Hash-Tabelle in C++
Die Zeiger auf die realen Werte werden in der Hash-Tabelle gespeichert. Es verwendet einen Schlüssel, um den Index eines Arrays zu ermitteln, an dem die Werte für die Schlüssel an der gewünschten Stelle in einem Array gespeichert werden müssen. Wir haben die Hash-Tabelle mit der Größe 10 genommen, wie im Folgenden erwähnt:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Nehmen wir zufällig beliebige Daten zu verschiedenen Schlüsseln und speichern Sie diese Schlüssel in einer Hash-Tabelle, indem wir einfach den Index berechnen. Daher werden die Daten mithilfe einer Hash-Funktion für die Schlüssel im berechneten Index gespeichert. Angenommen, wir nehmen Daten = {14,25,42,55,63,84} und Schlüssel =[ 15,9,5,25,66,75 ].
Berechnen Sie den Index dieser Daten mithilfe der Hash-Funktion. Der Indexwert wird im Folgenden erwähnt:
| Schlüssel | fünfzehn | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Index berechnen | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Daten | 14 | 25 | 42 | 55 | 63 | 84 |
Nachdem Sie den Index eines Arrays erstellt haben, platzieren Sie die Daten wie zuvor beschrieben anhand des Schlüssels auf dem genauen Index eines bestimmten Arrays.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Danach können wir sehen, dass es zu einer Kollision kommt, wenn zwei oder mehr Schlüssel denselben Hash-Code haben, was zu demselben Index der Elemente im Array führt. Wir haben eine Lösung, um das Risiko einer Kollision zu vermeiden: die Auswahl einer guten Hash-Methode und die Implementierung der richtigen Strategien.
Lassen Sie uns nun die verschiedenen Implementierungstechniken anhand geeigneter Beispiele diskutieren.
Beispiel: Hinzufügen von Daten zu einer Hash-Tabelle mithilfe einer offenen Hashing-Technik
In diesem Beispiel verwenden wir eine Implementierungstechnik wie Open Hashing, um Kollisionen in der Hash-Tabelle zu vermeiden. Beim offenen Hashing oder Chaining erstellen wir eine verknüpfte Liste, um die Werte der Hash-Tabelle zu verketten. Der Codeausschnitt dieses Beispiels ist im Folgenden beigefügt und beschreibt die offene Hashing-Technik:
#include#include
Klasse Hash-tabelle {
Privat :
statisch const int Tischgröße = 10 ;
std :: Liste < int > tableHas [ Tischgröße ] ;
int hashFunc ( int Schlüssel ) {
zurückkehren Schlüssel % Tischgröße ;
}
öffentlich :
Leere einfügen ( int Schlüssel ) {
int Index = hashFunc ( Schlüssel ) ;
tableHas [ Index ] . push_back ( Schlüssel ) ;
}
Leere viewTable ( ) {
für ( int ich = 0 ; ich < Tischgröße ; ++ ich ) {
std :: cout << „[“ << ich << „]“ ;
für ( Auto Es = tableHas [ ich ] . beginnen ( ) ; Es ! = tableHas [ ich ] . Ende ( ) ; ++ Es ) {
std :: cout << ' -> ' << * Es ;
}
std :: cout << std :: endl ;
}
}
} ;
int hauptsächlich ( ) {
HashTable hasTable ;
hasTable. einfügen ( fünfzehn ) ;
hasTable. einfügen ( 33 ) ;
hasTable. einfügen ( 23 ) ;
hasTable. einfügen ( 65 ) ;
hasTable. einfügen ( 3 ) ;
hasTable. viewTable ( ) ;
zurückkehren 0 ;
}
Dies ist ein sehr interessantes Beispiel: Wir erstellen eine verknüpfte Liste und fügen die Daten in die Hash-Tabelle ein. Zunächst definieren wir die Bibliotheken beim Start des Programms. Der < Liste > Die Bibliothek wird für die Implementierung verknüpfter Listen verwendet. Danach erstellen wir eine Klasse mit dem Namen „HashTable“ und erstellen die privaten Attribute der Klasse wie Tabellengröße und Tabellenarray mit dem Schlüsselwort „private:“. Denken Sie daran, dass die privaten Attribute nicht außerhalb der Klasse verwendet werden können. Hier nehmen wir die Größe der Tabelle mit „10“ an. Damit initialisieren wir die Hash-Methode und berechnen den Index der Hash-Tabelle. In der Hash-Funktion übergeben wir den Schlüssel und die Größe der Hash-Tabelle.
Wir erstellen einige erforderliche Funktionen und machen diese Funktionen in der Klasse öffentlich. Denken Sie daran, dass öffentliche Funktionen überall außerhalb der Klasse verwendet werden können. Wir verwenden das Schlüsselwort „public:“, um den öffentlichen Teil der Klasse zu starten . Da wir der Hash-Tabelle neue Elemente hinzufügen möchten, erstellen wir eine Funktion namens „InsertHash“ mit einem Schlüssel als Argument der Funktion. In der Funktion „Einfügen“ initialisieren wir die Indexvariable. Wir übergeben die Hash-Funktion an die Indexvariable. Anschließend übergeben Sie die Indexvariable an die verknüpfte Liste tableHas[], indem Sie die „Push“-Methode verwenden, um ein Element in die Tabelle einzufügen.
Danach erstellen wir eine „viewHashTab“-Funktion, um die Hash-Tabelle anzuzeigen und die neu eingefügten Daten anzuzeigen. In dieser Funktion verwenden wir eine „for“-Schleife, die die Werte bis zum Ende der Hash-Tabelle durchsucht. Stellen Sie sicher, dass die Werte im selben Index gespeichert sind, die mithilfe einer Hash-Funktion entwickelt wurden. In der Schleife übergeben wir die Werte an ihrem jeweiligen Index und beenden die Klasse hier. In der Funktion „main“ nehmen wir das Objekt einer Klasse namens „hasTable“. Mit Hilfe dieses Klassenobjekts können wir auf die Einfügemethode zugreifen, indem wir den Schlüssel in der Methode übergeben. Der Schlüssel, den wir in der Funktion „main“ übergeben haben, wird in der Funktion „insert“ berechnet, die die Indexposition in der Hash-Tabelle zurückgibt. Wir haben die Hash-Tabelle angezeigt, indem wir die Funktion „view“ mit Hilfe eines „Class“-Objekts aufgerufen haben.
Die Ausgabe dieses Codes ist im Folgenden beigefügt:
Wie wir sehen können, wurde die Hash-Tabelle mithilfe der verknüpften Liste in C++ erfolgreich erstellt. Um die Kollision desselben Index zu vermeiden, wird eine offene Verkettung verwendet.
Abschluss
Letztendlich kamen wir zu dem Schluss, dass eine Hash-Tabelle die am weitesten entwickelte Technik zum Speichern und Abrufen der Schlüssel mit Wertepaaren ist, um große Datenmengen effizient verarbeiten zu können. In der Hash-Tabelle ist die Wahrscheinlichkeit einer Kollision sehr hoch, wodurch die Daten und ihr Speicher zerstört werden. Wir können diese Kollision mithilfe verschiedener Techniken der Hash-Tabellenverwaltung überwinden. Durch die Entwicklung der Hash-Tabelle in C++ können die Entwickler die Leistung steigern, indem sie die am besten geeignete Technik zum Speichern der Daten in der Hash-Tabelle verwenden. Wir hoffen, dass dieser Artikel für Ihr Verständnis der Hash-Tabelle hilfreich ist.