Einführung in die Hashing-Funktion in C
Dieser Artikel enthält einen kurzen Hinweis zum Hashing (Hash-Tabelle und Hash-Funktion). Das wichtigste Konzept ist die Suche, die die zeitliche Komplexität bestimmt. Um die Zeitkomplexität zu reduzieren, wird ein Hashing-Konzept eingeführt, das im Durchschnitt O (1) -Zeit hat und im schlimmsten Fall O (n) -Zeit benötigt.
Hashing ist eine Technik mit schnellerem Zugriff auf Elemente, die die angegebenen Daten mit einem geringeren Schlüssel für Vergleiche abbildet. Im Allgemeinen werden bei dieser Technik die Schlüssel unter Verwendung der Hash-Funktion in einer als Hash-Tabelle bekannten Tabelle verfolgt.
Was ist die Hash-Funktion?
Die Hash-Funktion ist eine Funktion, die die Konstantzeitoperation zum Speichern und Abrufen des Werts aus der Hash-Tabelle verwendet, der auf die Schlüssel als Ganzzahlen angewendet wird und der als Adresse für Werte in der Hash-Tabelle verwendet wird.
Arten einer Hash-Funktion
Die Arten von Hash-Funktionen werden nachfolgend erläutert:
1. Teilungsmethode
Bei dieser Methode ist die Hash-Funktion vom Rest einer Division abhängig.
Beispiel: Elemente, die in einer Hash-Tabelle platziert werden sollen, sind 42, 78, 89, 64. Nehmen wir die Tabellengröße 10.
Hash (Schlüssel) = Elements% table size;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Die Tabellendarstellung ist wie folgt zu sehen:
2. Mid Square-Methode
Bei dieser Methode wird der mittlere Teil des quadratischen Elements als Index verwendet.
Elemente, die in die Hash-Tabelle eingefügt werden sollen, sind 210, 350, 99, 890 und die Größe der Tabelle beträgt 100.
210 * 210 = 44100, Index = 1 als Mittelteil des Ergebnisses (44100) ist 1.
350 * 350 = 122500, Index = 25 als Mittelteil des Ergebnisses (122500) ist 25.
99 * 99 = 9801, Index = 80 als Mittelteil des Ergebnisses (9801) ist 80.
890 * 890 = 792100, Index = 21 als Mittelteil des Ergebnisses (792100) ist 21.
3. Digit Folding-Methode
Bei dieser Methode ist das Element, das in die Tabelle uh eingefügt werden soll, ein Sing-Hash-Schlüssel, der durch Teilen der Elemente in verschiedene Teile und anschließendes Kombinieren der Teile durch Ausführen einiger einfacher mathematischer Operationen erhalten wird.
Das zu platzierende Element ist 23576623, 34687734.
- Hash (Schlüssel) = 235 + 766 + 23 = 1024
- Hash-Schlüssel) = 34 + 68 + 77 + 34 = 213
Bei diesen Arten von Hashing wird angenommen, dass wir Zahlen von 1 bis 100 und die Größe der Hash-Tabelle = 10 haben. Elemente = 23, 12, 32
Hash (Schlüssel) = 23% 10 = 3;
Hash (Schlüssel) = 12% 10 = 2;
Hash (Schlüssel) = 32% 10 = 2;
Aus dem obigen Beispiel geht hervor, dass beide Elemente 12 und 32 auf den 2. Platz in der Tabelle zeigen, wo es nicht möglich ist, beide an derselben Stelle zu schreiben. Dieses Problem wird als Kollision bezeichnet. Um diese Art von Problemen zu vermeiden, gibt es einige Techniken von Hash-Funktionen, die verwendet werden können.
Arten von Kollisionsauflösungstechniken
Lassen Sie uns die Arten von Kollisionsauflösungstechniken diskutieren:
1. Verketten
Bei dieser Methode wird, wie der Name schon sagt, eine Kette von Feldern für den Datensatz in der Tabelle mit zwei Elementeinträgen bereitgestellt. Wenn solche Kollisionen auftreten, werden die Kästchen als verknüpfte Liste gebildet.
Beispiel: 23, 12, 32 mit Tischgröße 10.
Hash (Schlüssel) = 23% 10 = 3;
Hash (Schlüssel) = 12% 10 = 2;
Hash (Schlüssel) = 32% 10 = 2;
2. Öffnen Sie Adressierung
- Lineare Abtastung
Dies ist eine weitere Methode zur Lösung von Kollisionsproblemen. Wie der Name schon sagt, sollten bei jeder Kollision zwei Elemente auf den gleichen Eintrag in der Tabelle gesetzt werden. Mit dieser Methode können wir jedoch nach dem nächsten leeren Platz oder Eintrag in der Tabelle suchen und das zweite Element platzieren. Dies kann wiederum zu einem anderen Problem führen. Wenn wir keinen leeren Eintrag in der Tabelle finden, führt dies zu Clustering. Daher ist dies als Clustering-Problem bekannt, das durch das folgende Verfahren gelöst werden kann.
Beispiel: 23, 12, 32 mit Tischgröße 10
Hash (Schlüssel) = 23% 10 = 3;
Hash (Schlüssel) = 12% 10 = 2;
Hash (Schlüssel) = 32% 10 = 2;
In diesem Diagramm können 12 und 32 im selben Eintrag mit Index 2 platziert werden, aber nach dieser Methode werden sie linear platziert.
- Quadratische Abtastung
Diese Methode ist eine Lösung für das Clustering-Problem beim linearen Abtasten. Bei dieser Methode wird die Hash-Funktion mit dem Hash-Schlüssel berechnet als Hash (Schlüssel) = (Hash (Schlüssel) + x * x)% Größe der Tabelle (wobei x = 0, 1, 2…).
Beispiel: 23, 12, 32 mit Tischgröße 10
Hash (Schlüssel) = 23% 10 = 3;
Hash (Schlüssel) = 12% 10 = 2;
Hash (Schlüssel) = 32% 10 = 2;
Darin können wir sehen, dass 23 und 12 leicht platziert werden können, 32 jedoch nicht, da 12 und 32 denselben Eintrag mit demselben Index in der Tabelle teilen, wie gemäß dieser Methode hash (key) = (32 + 1 * 1). % 10 = 3. In diesem Fall wird der Tabelleneintrag mit Index 3 mit 23 versehen, sodass wir den x-Wert um 1 erhöhen müssen. Hash (Schlüssel) = (32 + 2 * 2)% 10 = 6. Jetzt können wir platzieren 32 im Eintrag mit Index 6 in der Tabelle.
- Double Hashing
Mit dieser Methode müssen wir 2 Hash-Funktionen berechnen, um das Kollisionsproblem zu lösen. Die erste wird mit einer einfachen Teilungsmethode berechnet. Der zweite muss zwei Regeln erfüllen; es darf nicht gleich 0 sein und Einträge müssen geprüft werden.
- 1 (Schlüssel) = Schlüssel% Größe der Tabelle.
- 2 (key) = p - (key mod p), wobei p Primzahlen <Größe der Tabelle ist.
Beispiel: 23, 12, 32 mit Tischgröße 10
Hash (Schlüssel) = 23% 10 = 3;
Hash (Schlüssel) = 12% 10 = 2;
Hash (Schlüssel) = 32% 10 = 2;
Auch hier kann das Element 32 mit hash2 (key) = 5 - (32% 5) = 3 platziert werden. So kann 32 an index 5 in der Tabelle platziert werden, die leer ist, da wir 3 Einträge springen müssen, um sie zu platzieren.
Fazit-Hashing-Funktion in C
Hashing ist eine der wichtigsten Techniken für die Suche nach Daten, die mit sehr effizienten und schnellen Methoden unter Verwendung von Hash-Funktionen und Hash-Tabellen bereitgestellt werden. Jedes Element kann mit verschiedenen Hash-Methoden gesucht und platziert werden. Diese Technik ist in Bezug auf den Zeitkoeffizienten sehr schnell als jede andere Datenstruktur.
Empfohlene Artikel
Dies ist eine Anleitung zur Hashing-Funktion in C. Hier diskutieren wir die Einführung der Hashing-Funktion in C, Was ist eine Hash-Funktion, Arten einer Hash-Funktion usw. Sie können auch unsere anderen vorgeschlagenen Artikel durchgehen, um mehr zu erfahren.
- Hashing in DBMS
- Verschlüsselungsprozess
- Wie installiere ich CakePHP?
- So funktioniert Blockchain
- Hashing-Funktion in Java
- Hashing-Funktion in PHP | Wie man arbeitet?