hash table c programs implement hash table
Dieses Tutorial erklärt C ++ - Hash-Tabellen und Hash-Maps. Außerdem erfahren Sie mehr über Hash-Tabellenanwendungen und deren Implementierung in C ++:
Hashing ist eine Technik, mit der wir eine große Datenmenge mithilfe einer „Hash-Funktion“ einer kleineren Tabelle zuordnen können.
Mit der Hashing-Technik können wir die Daten im Vergleich zu anderen Suchtechniken wie der linearen und binären Suche schneller und effizienter suchen.
Lassen Sie uns die Hashing-Technik anhand eines Beispiels in diesem Tutorial verstehen.
=> Lesen Sie die Easy C ++ - Schulungsserie durch.
Was du lernen wirst:
Hashing in C ++
Nehmen wir ein Beispiel einer Universitätsbibliothek, in der Tausende von Büchern untergebracht sind. Die Bücher sind nach Themen, Abteilungen usw. geordnet. Dennoch wird jeder Abschnitt zahlreiche Bücher enthalten, was die Suche nach Büchern sehr schwierig macht.
Um diese Schwierigkeit zu überwinden, weisen wir jedem Buch eine eindeutige Nummer oder einen eindeutigen Schlüssel zu, damit wir sofort den Ort des Buches kennen. Dies wird in der Tat durch Hashing erreicht.
Wenn wir mit unserem Bibliotheksbeispiel fortfahren, anstatt jedes Buch anhand seiner Abteilung, seines Fachs, seines Abschnitts usw. zu identifizieren, was zu einer sehr langen Zeichenfolge führen kann, berechnen wir für jedes Buch in der Bibliothek einen eindeutigen ganzzahligen Wert oder Schlüssel mit einer eindeutigen Funktion und Speichern Sie diese Schlüssel in einer separaten Tabelle.
Die oben erwähnte eindeutige Funktion wird als 'Hash-Funktion' und die separate Tabelle als 'Hash-Tabelle' bezeichnet. Eine Hash-Funktion wird verwendet, um den angegebenen Wert einem bestimmten eindeutigen Schlüssel in der Hash-Tabelle zuzuordnen. Dies führt zu einem schnelleren Zugriff auf Elemente. Je effizienter die Hashing-Funktion ist, desto effizienter ist die Zuordnung jedes Elements zum eindeutigen Schlüssel.
Betrachten wir eine Hash-Funktion h (x) das bildet den Wert ab “ x ' beim ' x% 10 ”Im Array. Für die angegebenen Daten können wir eine Hash-Tabelle erstellen, die Schlüssel oder Hash-Codes oder Hashes enthält, wie im folgenden Diagramm gezeigt.
Im obigen Diagramm sehen wir, dass die Einträge im Array mithilfe einer Hash-Funktion ihren Positionen in der Hash-Tabelle zugeordnet werden.
Wir können also sagen, dass das Hashing in zwei Schritten implementiert wird, wie unten erwähnt:
# 1) Der Wert wird mithilfe einer Hash-Funktion in einen eindeutigen Ganzzahlschlüssel oder Hash umgewandelt. Es wird als Index zum Speichern des ursprünglichen Elements verwendet, das in die Hash-Tabelle fällt.
Im obigen Diagramm ist der Wert 1 in der Hash-Tabelle der eindeutige Schlüssel zum Speichern von Element 1 aus dem Datenarray, das auf der linken Seite des Diagramms angegeben ist.
#zwei) Das Element aus dem Datenarray wird in der Hash-Tabelle gespeichert, wo es mit dem Hash-Schlüssel schnell abgerufen werden kann. Im obigen Diagramm haben wir gesehen, dass wir alle Elemente in der Hash-Tabelle gespeichert haben, nachdem wir ihre jeweiligen Positionen mithilfe einer Hash-Funktion berechnet haben. Wir können die folgenden Ausdrücke verwenden, um Hash-Werte und Index abzurufen.
hash = hash_func(key) index = hash % array_sizeHash-Funktion
Wir haben bereits erwähnt, dass die Effizienz des Mappings von der Effizienz der von uns verwendeten Hash-Funktion abhängt.
Eine Hash-Funktion sollte grundsätzlich die folgenden Anforderungen erfüllen:
Top 50 SQL knifflige Interviewfragen pdf
- Einfach zu berechnen: Eine Hash-Funktion sollte einfach zu berechnen sein.
- Weniger Kollision: Wenn Elemente denselben Schlüsselwerten entsprechen, tritt eine Kollision auf. In der verwendeten Hash-Funktion sollten so weit wie möglich minimale Kollisionen auftreten. Da Kollisionen auftreten müssen, müssen wir geeignete Kollisionsauflösungstechniken verwenden, um die Kollisionen zu beseitigen.
- Gleichmäßige Verteilung: Die Hash-Funktion sollte zu einer gleichmäßigen Verteilung der Daten über die Hash-Tabelle führen und dadurch das Clustering verhindern.
Hash-Tabelle C ++
Eine Hash-Tabelle oder eine Hash-Map ist eine Datenstruktur, in der Zeiger auf die Elemente des ursprünglichen Datenarrays gespeichert werden.
In unserem Bibliotheksbeispiel enthält die Hash-Tabelle für die Bibliothek Zeiger auf jedes der Bücher in der Bibliothek.
Einträge in der Hash-Tabelle erleichtern die Suche nach einem bestimmten Element im Array.
Wie bereits gesehen, verwendet die Hash-Tabelle eine Hash-Funktion, um den Index in das Array von Buckets oder Slots zu berechnen, mit denen der gewünschte Wert gefunden werden kann.
Betrachten Sie ein weiteres Beispiel mit folgendem Datenarray:
Angenommen, wir haben eine Hash-Tabelle der Größe 10, wie unten gezeigt:
Verwenden wir nun die unten angegebene Hash-Funktion.
Hash_code = Key_value % size_of_hash_tableDies entspricht Hash_code = Schlüsselwert% 10
Mit der obigen Funktion ordnen wir die Schlüsselwerte den Positionen der Hash-Tabellen zu, wie unten gezeigt.
| Datenelement | Hash-Funktion | Hash-Code |
|---|---|---|
| 22 | 22% 10 = 2 | zwei |
| 25 | 25% 10 = 5 | 5 |
| 27 | 27% 10 = 7 | 7 |
| 46 | 46% 10 = 6 | 6 |
| 70 | 70% 10 = 0 | 0 |
| 89 | 89% 10 = 9 | 9 |
| 31 | 31% 10 = 1 | 1 |
Mit der obigen Tabelle können wir die Hash-Tabelle wie folgt darstellen.
Wenn wir also über die Hash-Tabelle auf ein Element zugreifen müssen, dauert die Suche nur 0 (1) Mal.
Kollision
Normalerweise berechnen wir den Hash-Code mit der Hash-Funktion, damit wir den Schlüsselwert dem Hash-Code in der Hash-Tabelle zuordnen können. Geben Sie im obigen Beispiel des Datenarrays einen Wert 12 ein. In diesem Fall ist der Hashcode für den Schlüsselwert 12 2. (12% 10 = 2).
In der Hash-Tabelle haben wir jedoch bereits eine Zuordnung zum Schlüsselwert 22 für Hash-Code 2, wie unten gezeigt:
Wie oben gezeigt, haben wir denselben Hashcode für zwei Werte, 12 und 22, d. H. 2. Wenn ein oder mehrere Schlüsselwerte derselben Position entsprechen, führt dies zu einer Kollision. Somit ist der Hashcode-Speicherort bereits von einem Schlüsselwert belegt, und es gibt einen anderen Schlüsselwert, der an derselben Position platziert werden muss.
Im Falle von Hashing ist selbst dann eine Kollision vorhanden, wenn wir eine sehr große Hash-Tabelle haben. Dies liegt daran, dass wir im Allgemeinen einen kleinen eindeutigen Wert für einen großen Schlüssel finden. Daher ist es durchaus möglich, dass ein oder mehrere Werte zu einem bestimmten Zeitpunkt denselben Hashcode haben.
Da eine Kollision beim Hashing unvermeidlich ist, sollten wir immer nach Möglichkeiten suchen, die Kollision zu verhindern oder zu beheben. Es gibt verschiedene Kollisionsauflösungstechniken, mit denen wir die beim Hashing auftretende Kollision auflösen können.
Kollisionsauflösungstechniken
Im Folgenden sind die Techniken aufgeführt, mit denen wir Kollisionen in der Hash-Tabelle auflösen können.
Separate Verkettung (Open Hashing)
Dies ist die häufigste Kollisionsauflösungstechnik. Dies wird auch als offenes Hashing bezeichnet und mithilfe einer verknüpften Liste implementiert.
der beste Youtube zu MP4 Konverter
Bei einer separaten Verkettungstechnik ist jeder Eintrag in der Hash-Tabelle eine verknüpfte Liste. Wenn der Schlüssel mit dem Hash-Code übereinstimmt, wird er in eine Liste eingegeben, die diesem bestimmten Hash-Code entspricht. Wenn also zwei Schlüssel denselben Hashcode haben, werden beide Einträge in die verknüpfte Liste eingegeben.
Für das obige Beispiel ist die separate Verkettung unten dargestellt.
Das obige Diagramm zeigt die Verkettung. Hier verwenden wir die Mod (%) Funktion. Wir sehen, dass wenn zwei Schlüsselwerte demselben Hash-Code entsprechen, wir diese Elemente mithilfe einer verknüpften Liste mit diesem Hash-Code verknüpfen.
Wenn die Schlüssel gleichmäßig über die Hash-Tabelle verteilt sind, hängen die durchschnittlichen Kosten für die Suche nach dem bestimmten Schlüssel von der durchschnittlichen Anzahl der Schlüssel in dieser verknüpften Liste ab. Somit bleibt eine getrennte Verkettung auch dann wirksam, wenn die Anzahl der Einträge größer ist als die der Slots.
Der schlimmste Fall für eine separate Verkettung ist, wenn alle Schlüssel dem gleichen Hash-Code entsprechen und daher nur in eine verknüpfte Liste eingefügt werden. Daher müssen wir nach allen Einträgen in der Hash-Tabelle und den Kosten suchen, die proportional zur Anzahl der Schlüssel in der Tabelle sind.
Lineare Prüfung (offene Adressierung / geschlossenes Hashing)
Bei der offenen Adressierung oder der linearen Sondierungstechnik werden alle Eintragsdatensätze in der Hash-Tabelle selbst gespeichert. Wenn der Schlüsselwert einem Hash-Code zugeordnet ist und die Position, auf die der Hash-Code zeigt, nicht belegt ist, wird der Schlüsselwert an dieser Stelle eingefügt.
Wenn die Position bereits belegt ist, wird der Schlüsselwert mithilfe einer Prüfsequenz an der nächsten Position eingefügt, die in der Hash-Tabelle nicht belegt ist.
Bei linearer Prüfung kann sich die Hash-Funktion wie folgt ändern:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Wir sehen, dass im Fall einer linearen Abtastung das Intervall zwischen Schlitzen oder aufeinanderfolgenden Sonden konstant ist, d. H. 1.
Im obigen Diagramm sehen wir das in der 0thOrt, an dem wir 10 mit der Hash-Funktion 'hash = hash% hash_tableSize' eingeben.
Nun entspricht das Element 70 auch der Position 0 in der Hash-Tabelle. Aber dieser Ort ist bereits besetzt. Daher finden wir unter Verwendung der linearen Abtastung die nächste Stelle, die 1 ist. Da diese Stelle nicht besetzt ist, platzieren wir den Schlüssel 70 an dieser Stelle, wie durch einen Pfeil gezeigt.
Die resultierende Hash-Tabelle ist unten gezeigt.
Die lineare Abtastung kann unter dem Problem der 'primären Clusterbildung' leiden, bei der die Möglichkeit besteht, dass die kontinuierlichen Zellen besetzt werden und die Wahrscheinlichkeit des Einfügens eines neuen Elements verringert wird.
Auch wenn zwei Elemente bei der ersten Hash-Funktion den gleichen Wert erhalten, folgen beide Elemente der gleichen Sondensequenz.
Quadratische Prüfung
Die quadratische Abtastung entspricht der linearen Abtastung, mit dem einzigen Unterschied, dass das für die Abtastung verwendete Intervall besteht. Wie der Name schon sagt, verwendet diese Technik einen nichtlinearen oder quadratischen Abstand, um Schlitze zu belegen, wenn eine Kollision auftritt, anstatt einen linearen Abstand.
Bei der quadratischen Abtastung wird das Intervall zwischen den Schlitzen berechnet, indem dem bereits gehashten Index ein beliebiger Polynomwert hinzugefügt wird. Diese Technik reduziert das primäre Clustering in erheblichem Maße, verbessert jedoch das sekundäre Clustering nicht.
Double Hashing
Die Double-Hashing-Technik ähnelt der linearen Abtastung. Der einzige Unterschied zwischen Double-Hashing und linearer Prüfung besteht darin, dass bei der Doppel-Hashing-Technik das für die Prüfung verwendete Intervall unter Verwendung von zwei Hash-Funktionen berechnet wird. Da wir die Hash-Funktion nacheinander auf den Schlüssel anwenden, werden sowohl primäres als auch sekundäres Clustering eliminiert.
Unterschied zwischen Verkettung (Open Hashing) und linearer Prüfung (Open Addressing)
| Verkettung (Open Hashing) | Lineare Prüfung (offene Adressierung) |
|---|---|
| Schlüsselwerte können außerhalb der Tabelle über eine separate verknüpfte Liste gespeichert werden. | Schlüsselwerte sollten nur in der Tabelle gespeichert werden. |
| Die Anzahl der Elemente in der Hash-Tabelle kann die Größe der Hash-Tabelle überschreiten. | Die Anzahl der in der Hash-Tabelle vorhandenen Elemente überschreitet nicht die Anzahl der Indizes in der Hash-Tabelle. |
| Das Löschen ist in der Verkettungstechnik effizient. | Das Löschen kann umständlich sein. Kann vermieden werden, wenn nicht erforderlich. |
| Da für jeden Standort eine separate verknüpfte Liste geführt wird, ist der belegte Speicherplatz groß. | Da alle Einträge in derselben Tabelle gespeichert sind, ist der Platzbedarf geringer. |
Implementierung der C ++ - Hash-Tabelle
Wir können Hashing implementieren, indem wir Arrays oder verknüpfte Listen verwenden, um die Hash-Tabellen zu programmieren. In C ++ gibt es auch eine Funktion namens 'Hash Map', die einer Hash-Tabelle ähnelt, aber jeder Eintrag ist ein Schlüssel-Wert-Paar. In C ++ heißt es Hash Map oder einfach eine Map. Die Hash-Map in C ++ ist normalerweise ungeordnet.
In der Standard Template Library (STL) von C ++ ist ein Header definiert, der die Funktionalität von Maps implementiert. Wir haben abgedeckt STL-Karten ausführlich in unserem Tutorial zu STL.
Die folgende Implementierung dient zum Hashing unter Verwendung der verknüpften Listen als Datenstruktur für die Hash-Tabelle. In dieser Implementierung verwenden wir auch 'Verkettung' als Kollisionsauflösungstechnik.
Was ist die beste PC-Wartungssoftware?
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< Ausgabe:
Hash-Tabelle erstellt:
0 -> 21 -> 14
1 -> 15
zwei
3
4 -> 11
5 -> 12
6
Hash-Tabelle nach Löschen von Schlüssel 12:
0 -> 21 -> 14
1 -> 15
zwei
3
4 -> 11
5
6
Die Ausgabe zeigt eine Hash-Tabelle der Größe 7. Wir verwenden Verkettung, um Kollisionen aufzulösen. Wir zeigen die Hash-Tabelle an, nachdem wir einen der Schlüssel gelöscht haben.
Anwendungen des Hashing
# 1) Überprüfung der Passwörter: Die Überprüfung von Passwörtern erfolgt normalerweise mithilfe kryptografischer Hash-Funktionen. Wenn das Passwort eingegeben wird, berechnet das System den Hash des Passworts und wird dann zur Überprüfung an den Server gesendet. Auf dem Server werden die Hashwerte der ursprünglichen Kennwörter gespeichert.
# 2) Datenstrukturen: Verschiedene Datenstrukturen wie unordered_set und unordered_map in C ++, Wörterbücher in Python oder C #, HashSet und Hash Map in Java verwenden alle Schlüssel-Wert-Paare, wobei Schlüssel eindeutige Werte sind. Die Werte können für verschiedene Schlüssel gleich sein. Hashing wird verwendet, um diese Datenstrukturen zu implementieren.
# 3) Message Digest: Dies ist eine weitere Anwendung, die einen kryptografischen Hash verwendet. Bei Nachrichtenübersichten berechnen wir einen Hash für gesendete und empfangene Daten oder sogar Dateien und vergleichen sie mit den gespeicherten Werten, um sicherzustellen, dass die Datendateien nicht manipuliert werden. Der gebräuchlichste Algorithmus ist hier 'SHA 256'.
# 4) Compiler-Betrieb: Wenn der Compiler ein Programm kompiliert, werden die Schlüsselwörter für die Programmiersprache anders als die anderen Identifikationen gespeichert. Der Compiler verwendet eine Hash-Tabelle zum Speichern dieser Schlüsselwörter.
# 5) Datenbankindizierung: Hash-Tabellen werden für die Datenbankindizierung und festplattenbasierte Datenstrukturen verwendet.
# 6) Assoziative Arrays: Assoziative Arrays sind Arrays, deren Indizes einen anderen Datentyp als ganzzahlige Zeichenfolgen oder andere Objekttypen haben. Hash-Tabellen können zum Implementieren von assoziativen Arrays verwendet werden.
Fazit
Hashing ist die am häufigsten verwendete Datenstruktur, da für Einfüge-, Lösch- und Suchvorgänge die konstante Zeit O (1) benötigt wird. Das Hashing wird hauptsächlich mithilfe einer Hash-Funktion implementiert, die einen eindeutigen kleineren Schlüsselwert für große Dateneinträge berechnet. Wir können Hashing mithilfe von Arrays und verknüpften Listen implementieren.
Immer wenn ein oder mehrere Dateneinträge denselben Schlüsselwerten entsprechen, führt dies zu einer Kollision. Wir haben verschiedene Kollisionsauflösungstechniken gesehen, einschließlich lineares Prüfen, Verketten usw. Wir haben auch die Implementierung von Hashing in C ++ gesehen.
Abschließend können wir sagen, dass Hashing bei weitem die effizienteste Datenstruktur in der Programmierwelt ist.
=> Suchen Sie hier nach der gesamten C ++ - Schulungsserie.
Literatur-Empfehlungen
- So schreiben Sie komplexe Business Logic-Testszenarien mithilfe der Entscheidungstabellen-Technik
- Feldvalidierungstabelle (FVT): Eine Testdesign-Technik für die Feldvalidierung
- QTP-Lernprogramm Nr. 15 - Verwenden von Textbereichs-, Tabellen- und Seitenprüfpunkten in QTP
- KARTEN In STL
- Alles über Router: Routertypen, Routing-Tabelle und IP-Routing
- Top 40 der besten Fragen und Antworten zu MySQL-Interviews (2021 Fragen)
- Top 90 Fragen und Antworten zu SQL-Interviews (NEUESTE)
- Befehle für Unix-Hilfsprogramme: Welche, Man, Find Su, Sudo (Teil D)