TechCodeview

Einführung in das Hashing in der Datenstruktur:

Hashing ist eine beliebte Technik in der Informatik, bei der große Datensätze auf Werte fester Länge abgebildet werden. Dabei handelt es sich um einen Prozess der Konvertierung eines Datensatzes variabler Größe in einen Datensatz fester Größe. Die Fähigkeit, effiziente Suchvorgänge durchzuführen, macht Hashing zu einem wesentlichen Konzept in Datenstrukturen.

Was ist Hashing?

Ein Hashing-Algorithmus wird verwendet, um eine Eingabe (z. B. eine Zeichenfolge oder eine Ganzzahl) in eine Ausgabe fester Größe (als Hash-Code oder Hash-Wert bezeichnet) umzuwandeln. Die Daten werden dann unter Verwendung dieses Hash-Werts als Index in einem Array oder einer Hash-Tabelle gespeichert und abgerufen. Die Hash-Funktion muss deterministisch sein, was garantiert, dass sie für eine bestimmte Eingabe immer das gleiche Ergebnis liefert.

Hashing wird üblicherweise verwendet, um eine eindeutige Kennung für ein Datenelement zu erstellen, die zum schnellen Nachschlagen dieser Daten in einem großen Datensatz verwendet werden kann. Beispielsweise kann ein Webbrowser Hashing verwenden, um Website-Passwörter sicher zu speichern. Wenn ein Benutzer sein Passwort eingibt, wandelt der Browser es in einen Hash-Wert um und vergleicht ihn mit dem gespeicherten Hash-Wert, um den Benutzer zu authentifizieren.

Was ist ein Hash-Schlüssel?

Im Zusammenhang mit Hashing ist ein Hash-Schlüssel (auch als Hash-Wert oder Hash-Code bekannt) eine numerische oder alphanumerische Darstellung fester Größe, die von einem Hashing-Algorithmus generiert wird. Es wird aus den Eingabedaten, beispielsweise einer Textzeichenfolge oder einer Datei, durch einen als Hashing bezeichneten Prozess abgeleitet.

Beim Hashing wird eine bestimmte mathematische Funktion auf die Eingabedaten angewendet, die einen eindeutigen Hash-Schlüssel erzeugt, der normalerweise eine feste Länge hat, unabhängig von der Größe der Eingabe. Der resultierende Hash-Schlüssel ist im Wesentlichen ein digitaler Fingerabdruck der Originaldaten.

Der Hash-Schlüssel dient mehreren Zwecken. Es wird häufig für Datenintegritätsprüfungen verwendet, da selbst eine kleine Änderung der Eingabedaten zu einem deutlich anderen Hash-Schlüssel führt. Hash-Schlüssel werden auch für den effizienten Datenabruf und die Speicherung in Hash-Tabellen oder Datenstrukturen verwendet, da sie schnelle Such- und Vergleichsvorgänge ermöglichen.

Wie funktioniert Hashing?

Der Hashing-Prozess kann in drei Schritte unterteilt werden:

• Eingabe: Die zu hashenden Daten werden in den Hashing-Algorithmus eingegeben.
• Hash-Funktion: Der Hash-Algorithmus nimmt die Eingabedaten und wendet eine mathematische Funktion an, um einen Hash-Wert fester Größe zu generieren. Die Hash-Funktion sollte so konzipiert sein, dass unterschiedliche Eingabewerte unterschiedliche Hash-Werte erzeugen und kleine Änderungen in der Eingabe große Änderungen in der Ausgabe hervorrufen.
• Ausgabe: Der Hash-Wert wird zurückgegeben, der als Index zum Speichern oder Abrufen von Daten in einer Datenstruktur verwendet wird.

Hashing-Algorithmen:

Es gibt zahlreiche Hashing-Algorithmen, jeder mit unterschiedlichen Vor- und Nachteilen. Zu den beliebtesten Algorithmen gehören die folgenden:

• MD5: Ein weit verbreiteter Hashing-Algorithmus, der einen 128-Bit-Hash-Wert erzeugt.
• SHA-1: Ein beliebter Hashing-Algorithmus, der einen 160-Bit-Hash-Wert erzeugt.
• SHA-256: Ein sicherer Hashing-Algorithmus, der einen 256-Bit-Hash-Wert erzeugt.

Hash-Funktion:

Hash-Funktion: Eine Hash-Funktion ist eine Art mathematische Operation, die eine Eingabe (oder einen Schlüssel) entgegennimmt und ein Ergebnis fester Größe ausgibt, das als Hash-Code oder Hash-Wert bezeichnet wird. Um deterministisch zu sein, muss die Hash-Funktion immer den gleichen Hash-Code für die gleiche Eingabe liefern. Darüber hinaus sollte die Hash-Funktion für jede Eingabe einen eindeutigen Hash-Code erzeugen, der als Hash-Eigenschaft bezeichnet wird.

Es gibt verschiedene Arten von Hash-Funktionen, darunter:

Divisionsmethode:

Bei dieser Methode wird der Schlüssel durch die Tabellengröße dividiert und der Rest als Hashwert verwendet. Wenn die Tabellengröße beispielsweise 10 beträgt und der Schlüssel 23 ist, wäre der Hashwert 3 (23 % 10 = 3).

10 von 60

Multiplikationsmethode:

Bei dieser Methode wird der Schlüssel mit einer Konstanten multipliziert und der Bruchteil des Produkts als Hashwert verwendet. Wenn der Schlüssel beispielsweise 23 und die Konstante 0,618 ist, wäre der Hash-Wert 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Universelles Hashing:

Bei dieser Methode wird eine zufällige Hash-Funktion aus einer Familie von Hash-Funktionen verwendet. Dadurch wird sichergestellt, dass die Hash-Funktion nicht auf eine bestimmte Eingabe ausgerichtet ist und resistent gegen Angriffe ist.

Kollisionsauflösung

Eine der größten Herausforderungen beim Hashing ist der Umgang mit Kollisionen, die auftreten, wenn zwei oder mehr Eingabewerte denselben Hashwert erzeugen. Es gibt verschiedene Techniken zur Lösung von Kollisionen, darunter:

• Verkettung: Bei dieser Technik enthält jeder Hash-Tabellenplatz eine verknüpfte Liste aller Werte, die denselben Hash-Wert haben. Diese Technik ist einfach und leicht zu implementieren, kann jedoch zu einer schlechten Leistung führen, wenn die verknüpften Listen zu lang werden.
• Offene Adressierung: Bei dieser Technik sucht der Algorithmus bei einer Kollision nach einem leeren Slot in der Hash-Tabelle, indem er aufeinanderfolgende Slots durchsucht, bis ein leerer Slot gefunden wird. Diese Technik kann bei niedrigem Auslastungsfaktor effizienter sein als die Verkettung, bei hohem Auslastungsfaktor kann sie jedoch zu Clusterbildung und schlechter Leistung führen.
• Doppeltes Hashing: Dies ist eine Variante der offenen Adressierung, die eine zweite Hash-Funktion verwendet, um den nächsten zu prüfenden Slot zu bestimmen, wenn eine Kollision auftritt. Diese Technik kann dazu beitragen, die Clusterbildung zu reduzieren und die Leistung zu verbessern.

Beispiel für Kollisionsauflösung

Fahren wir mit unserem Beispiel einer Hash-Tabelle mit der Größe 5 fort. Wir wollen die Schlüssel-Wert-Paare „John: 123456“ und „Mary: 987654“ in der Hash-Tabelle speichern. Beide Schlüssel erzeugen den gleichen Hash-Code von 4, sodass es zu einer Kollision kommt.

Wir können eine Verkettung verwenden, um die Kollision aufzulösen. Wir erstellen eine verknüpfte Liste bei Index 4 und fügen die Schlüssel-Wert-Paare zur Liste hinzu. Die Hash-Tabelle sieht nun so aus:

0:

1:

2:

Java-Klassendiagramm

3:

4: Johannes: 123456 -> Maria: 987654

5:

Hash-tabelle:

Eine Hash-Tabelle ist eine Datenstruktur, die Daten in einem Array speichert. Normalerweise wird eine Größe für das Array ausgewählt, die größer ist als die Anzahl der Elemente, die in die Hash-Tabelle passen. Mithilfe der Hash-Funktion wird ein Schlüssel einem Index im Array zugeordnet.

Die Hash-Funktion wird verwendet, um den Index zu finden, an dem ein Element in die Hash-Tabelle eingefügt werden muss, um ein neues Element hinzuzufügen. Das Element wird zu diesem Index hinzugefügt, wenn keine Kollision vorliegt. Wenn es zu einer Kollision kommt, wird die Kollisionsauflösungsmethode verwendet, um den nächsten verfügbaren Steckplatz im Array zu finden.

Die Hash-Funktion wird verwendet, um den Index zu finden, in dem das Element gespeichert ist, um ihn aus der Hash-Tabelle abzurufen. Wenn das Element an diesem Index nicht gefunden wird, wird die Kollisionsauflösungsmethode verwendet, um nach dem Element in der verknüpften Liste (wenn Verkettung verwendet wird) oder im nächsten verfügbaren Slot (wenn offene Adressierung verwendet wird) zu suchen.

Hash-Tabellenoperationen

Es gibt mehrere Vorgänge, die für eine Hash-Tabelle ausgeführt werden können, darunter:

• Einfügen: Einfügen eines neuen Schlüssel-Wert-Paares in die Hash-Tabelle.
• Löschen: Entfernen eines Schlüssel-Wert-Paares aus der Hash-Tabelle.
• Suche: Suche nach einem Schlüssel-Wert-Paar in der Hash-Tabelle.

Erstellen einer Hash-Tabelle:

Hashing wird häufig zum Erstellen von Hash-Tabellen verwendet. Hierbei handelt es sich um Datenstrukturen, die das schnelle Einfügen, Löschen und Abrufen von Daten ermöglichen. In jedem der Bucket-Arrays, aus denen eine Hash-Tabelle besteht, können ein oder mehrere Schlüssel-Wert-Paare gespeichert werden.

Um eine Hash-Tabelle zu erstellen, müssen wir zunächst eine Hash-Funktion definieren, die jeden Schlüssel einem eindeutigen Index im Array zuordnet. Eine einfache Hash-Funktion könnte darin bestehen, die Summe der ASCII-Werte der Zeichen im Schlüssel zu nehmen und den Rest zu verwenden, wenn sie durch die Größe des Arrays dividiert wird. Diese Hash-Funktion ist jedoch ineffizient und kann zu Kollisionen führen (zwei Schlüssel, die demselben Index zugeordnet sind).

Um Kollisionen zu vermeiden, können wir erweiterte Hash-Funktionen verwenden, die eine gleichmäßigere Verteilung der Hash-Werte über das Array erzeugen. Ein beliebter Algorithmus ist die djb2-Hash-Funktion, die bitweise Operationen verwendet, um einen Hash-Wert zu generieren:

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

Diese Hash-Funktion verwendet eine Zeichenfolge als Eingabe und gibt einen vorzeichenlosen langen ganzzahligen Hash-Wert zurück. Die Funktion initialisiert einen Hash-Wert von 5381 und iteriert dann über jedes Zeichen in der Zeichenfolge, wobei sie bitweise Operationen verwendet, um einen neuen Hash-Wert zu generieren. Der endgültige Hashwert wird zurückgegeben.

Hash-Tabellen in C++

In C++ stellt die Standardbibliothek eine Hash-Tabellen-Containerklasse namens unordered_map bereit. Der unordered_map-Container wird mithilfe einer Hash-Tabelle implementiert und bietet schnellen Zugriff auf Schlüssel-Wert-Paare. Der unordered_map-Container verwendet eine Hash-Funktion, um den Hash-Code der Schlüssel zu berechnen, und verwendet dann offene Adressierung, um Kollisionen aufzulösen.

Um den unordered_map-Container in C++ zu verwenden, müssen Sie die Header-Datei einbinden. Hier ist ein Beispiel für die Erstellung eines unordered_map-Containers in C++:

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

Erläuterung:

• Dieses Programm demonstriert die Verwendung des unordered_map-Containers in C++, der mithilfe einer Hash-Tabelle implementiert wird und schnellen Zugriff auf Schlüssel-Wert-Paare ermöglicht.
• Zunächst enthält das Programm die erforderlichen Header-Dateien: und.
• Anschließend erstellt das Programm einen leeren unordered_map-Container namens my_map, der Zeichenfolgenschlüssel und Ganzzahlwerte enthält. Dies geschieht mit der Syntax std::unordered_map my_map;
• Als Nächstes fügt das Programm mithilfe des []-Operators drei Schlüssel-Wert-Paare in den my_map-Container ein: „apple“ mit einem Wert von 10, „banana“ mit einem Wert von 20 und „orange“ mit einem Wert von 30.
• Dies geschieht mit der Syntax my_map['apple'] = 10;, my_map['banana'] = 20; und my_map['orange'] = 30; jeweils.
• Schließlich gibt das Programm den mit dem „Banana“-Schlüssel verknüpften Wert mithilfe des []-Operators und des std::cout-Objekts aus.

Programmausgabe:

Einfügen von Daten in eine Hash-Tabelle

Um ein Schlüssel-Wert-Paar in eine Hash-Tabelle einzufügen, müssen wir zunächst einen Index in das Array einfügen, um das Schlüssel-Wert-Paar zu speichern. Wenn ein anderer Schlüssel demselben Index zugeordnet ist, liegt eine Kollision vor und wir müssen entsprechend damit umgehen. Eine gängige Methode ist die Verkettung, bei der jeder Bucket im Array eine verknüpfte Liste von Schlüssel-Wert-Paaren enthält, die denselben Hash-Wert haben.

Hier ist ein Beispiel dafür, wie man mithilfe der Verkettung ein Schlüssel-Wert-Paar in eine Hash-Tabelle einfügt:

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

Erläuterung:

• Zunächst wird eine Struktur namens node definiert, die einen einzelnen Knoten in der Hash-Tabelle darstellt.
• Jeder Knoten hat drei Mitglieder: einen char*-Schlüssel zum Speichern des Schlüssels, einen int-Wert zum Speichern des zugehörigen Werts und einen Zeiger auf einen anderen Knoten namens next, um Kollisionen in der Hash-Tabelle mithilfe einer verknüpften Liste zu verarbeiten.
• Ein Array von Knotenzeigern namens hash_table wird mit einer Größe von 100 deklariert. Dieses Array wird zum Speichern der Elemente der Hash-Tabelle verwendet.
• Die Einfügefunktion benötigt einen char*-Schlüssel und einen int-Wert als Parameter.
• Es beginnt mit der Berechnung des Hash-Werts für den angegebenen Schlüssel mithilfe der Hash-Funktion, von der angenommen wird, dass sie an anderer Stelle im Programm definiert ist.
• Der Hash-Wert wird dann mithilfe des Modulus-Operators % 100 so reduziert, dass er in die Größe des hash_table-Arrays passt.
• Ein neuer Knoten wird mithilfe der dynamischen Speicherzuweisung (malloc(sizeof(node))) erstellt und seinen Mitgliedern (Schlüssel, Wert und Next) werden jeweils der bereitgestellte Schlüssel, Wert und NULL zugewiesen.
• Wenn der entsprechende Slot im Array hash_table leer (NULL) ist, was bedeutet, dass keine Kollision aufgetreten ist, wird der neue Knoten diesem Slot direkt zugewiesen (hash_table[hash_value] = new_node).

Wenn jedoch an diesem Index im Array hash_table bereits ein Knoten vorhanden ist, muss die Funktion die Kollision verarbeiten. Es durchläuft die verknüpfte Liste ausgehend vom aktuellen Knoten (hash_table[hash_value]) und bewegt sich zum nächsten Knoten, bis dieser das Ende erreicht (curr_node->next != NULL). Sobald das Ende der Liste erreicht ist, wird der neue Knoten als nächster Knoten angehängt (curr_node->next = new_node).

Implementierung von Hashing in C++:

Sehen wir uns eine Implementierung von Hashing in C++ an, bei der offene Adressierung und lineare Prüfung zur Kollisionsauflösung verwendet werden. Wir werden eine Hash-Tabelle implementieren, die Ganzzahlen speichert.

Stellvertretender Polizeikommissar

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>