TechCodeview

Introduktion til hashing i datastruktur:

Hashing er en populær teknik inden for datalogi, der involverer kortlægning af store datasæt til værdier med fast længde. Det er en proces med at konvertere et datasæt af variabel størrelse til et datasæt af en fast størrelse. Evnen til at udføre effektive opslagsoperationer gør hashing til et væsentligt koncept i datastrukturer.

Hvad er Hashing?

En hashing-algoritme bruges til at konvertere et input (såsom en streng eller et heltal) til et output med fast størrelse (benævnt en hash-kode eller hash-værdi). Dataene gemmes og hentes derefter ved hjælp af denne hash-værdi som et indeks i en matrix eller hash-tabel. Hash-funktionen skal være deterministisk, hvilket garanterer, at den altid vil give det samme resultat for et givet input.

Hashing bruges almindeligvis til at skabe en unik identifikator for et stykke data, som kan bruges til hurtigt at slå disse data op i et stort datasæt. For eksempel kan en webbrowser bruge hashing til at gemme webstedsadgangskoder sikkert. Når en bruger indtaster sin adgangskode, konverterer browseren den til en hashværdi og sammenligner den med den gemte hashværdi for at godkende brugeren.

Hvad er en hash-nøgle?

I forbindelse med hashing er en hash-nøgle (også kendt som en hash-værdi eller hash-kode) en numerisk eller alfanumerisk repræsentation i fast størrelse genereret af en hash-algoritme. Det er afledt af inputdata, såsom en tekststreng eller en fil, gennem en proces kendt som hashing.

Hashing involverer at anvende en specifik matematisk funktion på inputdataene, som producerer en unik hash-nøgle, der typisk er af fast længde, uanset størrelsen af ​​inputtet. Den resulterende hash-nøgle er i det væsentlige et digitalt fingeraftryk af de originale data.

Hash-nøglen tjener flere formål. Det bruges almindeligvis til dataintegritetstjek, da selv en lille ændring i inputdataene vil producere en væsentlig anderledes hash-nøgle. Hash-nøgler bruges også til effektiv datahentning og lagring i hashtabeller eller datastrukturer, da de tillader hurtige opslag og sammenligningsoperationer.

Hvordan virker hashing?

Processen med hashing kan opdeles i tre trin:

• Input: De data, der skal hash, indtastes i hashing-algoritmen.
• Hash-funktion: Hashing-algoritmen tager inputdataene og anvender en matematisk funktion til at generere en hash-værdi med fast størrelse. Hash-funktionen bør udformes, så forskellige inputværdier giver forskellige hashværdier, og små ændringer i input producerer store ændringer i output.
• Output: Hashværdien returneres, som bruges som et indeks til at gemme eller hente data i en datastruktur.

Hashing-algoritmer:

Der er adskillige hashing-algoritmer, hver med særskilte fordele og ulemper. De mest populære algoritmer omfatter følgende:

• MD5: En meget brugt hashing-algoritme, der producerer en 128-bit hashværdi.
• SHA-1: En populær hashing-algoritme, der producerer en 160-bit hashværdi.
• SHA-256: En mere sikker hash-algoritme, der producerer en 256-bit hash-værdi.

Hash funktion:

Hash-funktion: En hash-funktion er en type matematisk operation, der tager et input (eller nøgle) og udsender et resultat med fast størrelse kendt som en hash-kode eller hash-værdi. Hash-funktionen skal altid give den samme hash-kode for det samme input for at være deterministisk. Derudover skal hash-funktionen producere en unik hash-kode for hvert input, som er kendt som hash-egenskaben.

Der er forskellige typer hash-funktioner, herunder:

Opdelingsmetode:

Denne metode involverer at dividere nøglen med tabelstørrelsen og tage resten som hashværdi. For eksempel, hvis tabelstørrelsen er 10, og nøglen er 23, vil hashværdien være 3 (23 % 10 = 3).

Multiplikationsmetode:

Denne metode involverer at gange nøglen med en konstant og tage brøkdelen af ​​produktet som hashværdi. For eksempel, hvis nøglen er 23, og konstanten er 0,618, vil hashværdien være 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Universal hashing:

Denne metode involverer at bruge en tilfældig hashfunktion fra en familie af hashfunktioner. Dette sikrer, at hash-funktionen ikke er forudindtaget mod noget bestemt input og er modstandsdygtig over for angreb.

Kollisionsopløsning

En af hovedudfordringerne i hashing er håndtering af kollisioner, som opstår, når to eller flere inputværdier producerer den samme hashværdi. Der er forskellige teknikker, der bruges til at løse kollisioner, herunder:

• Kædning: I denne teknik indeholder hver hash-tabelplads en sammenkædet liste over alle de værdier, der har den samme hashværdi. Denne teknik er enkel og nem at implementere, men den kan føre til dårlig ydeevne, når de linkede lister bliver for lange.
• Åben adressering: I denne teknik, når en kollision opstår, søger algoritmen efter en tom plads i hash-tabellen ved at sondere successive slots, indtil en tom plads er fundet. Denne teknik kan være mere effektiv end kæde, når belastningsfaktoren er lav, men den kan føre til klyngedannelse og dårlig ydeevne, når belastningsfaktoren er høj.
• Dobbelt hashing: Dette er en variation af åben adressering, der bruger en anden hash-funktion til at bestemme det næste slot, der skal undersøges, når der opstår en kollision. Denne teknik kan hjælpe med at reducere klyngedannelse og forbedre ydeevnen.

Eksempel på kollisionsopløsning

Lad os fortsætte med vores eksempel på en hash-tabel med en størrelse på 5. Vi ønsker at gemme nøgleværdi-parrene 'John: 123456' og 'Mary: 987654' i hash-tabellen. Begge nøgler producerer den samme hash-kode på 4, så der opstår en kollision.

Vi kan bruge kæde til at løse kollisionen. Vi opretter en sammenkædet liste ved indeks 4 og tilføjer nøgleværdi-parrene til listen. Hash-tabellen ser nu sådan ud:

0:

java streng til int konvertering

1:

2:

3:

4: John: 123456 -> Mary: 987654

java input streng

5:

Hash tabel:

En hash-tabel er en datastruktur, der gemmer data i et array. Typisk vælges en størrelse for arrayet, der er større end antallet af elementer, der kan passe i hash-tabellen. En nøgle tilknyttes et indeks i arrayet ved hjælp af hash-funktionen.

Hash-funktionen bruges til at finde det indeks, hvor et element skal indsættes i hash-tabellen for at tilføje et nyt element. Elementet føjes til det indeks, hvis der ikke er en kollision. Hvis der er en kollision, bruges kollisionsopløsningsmetoden til at finde den næste ledige plads i arrayet.

Hash-funktionen bruges til at finde det indeks, som elementet er gemt, for at hente det fra hash-tabellen. Hvis elementet ikke findes ved det indeks, bruges kollisionsopløsningsmetoden til at søge efter elementet i den sammenkædede liste (hvis der er kædet sammen) eller i det næste tilgængelige slot (hvis åben adressering anvendes).

Hash-tabeloperationer

Der er flere handlinger, der kan udføres på en hash-tabel, herunder:

• Indsættelse: Indsættelse af et nyt nøgle-værdi-par i hash-tabellen.
• Sletning: Fjerner et nøgle-værdi-par fra hash-tabellen.
• Søgning: Søger efter et nøgle-værdi-par i hash-tabellen.

Oprettelse af en Hash-tabel:

Hashing bruges ofte til at bygge hashtabeller, som er datastrukturer, der muliggør hurtig dataindsættelse, sletning og hentning. Et eller flere nøgleværdi-par kan gemmes i hver af de arrays af buckets, der udgør en hash-tabel.

For at oprette en hash-tabel skal vi først definere en hash-funktion, der mapper hver nøgle til et unikt indeks i arrayet. En simpel hash-funktion kan være at tage summen af ​​ASCII-værdierne af tegnene i nøglen og bruge resten, når de divideres med størrelsen af ​​arrayet. Denne hash-funktion er dog ineffektiv og kan føre til kollisioner (to nøgler, der knytter sig til det samme indeks).

For at undgå kollisioner kan vi bruge mere avancerede hash-funktioner, der producerer en mere jævn fordeling af hash-værdier på tværs af arrayet. En populær algoritme er djb2 hash-funktionen, som bruger bitvise operationer til at generere en hashværdi:

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

Denne hash-funktion tager en streng som input og returnerer en hashværdi med langt heltal uden fortegn. Funktionen initialiserer en hashværdi på 5381 og itererer derefter over hvert tegn i strengen ved hjælp af bitvise operationer til at generere en ny hashværdi. Den endelige hash-værdi returneres.

Hash-tabeller i C++

I C++ giver standardbiblioteket en hash-tabelbeholderklasse kaldet unordered_map. Unordered_map-beholderen er implementeret ved hjælp af en hash-tabel og giver hurtig adgang til nøgleværdi-par. Unordered_map-beholderen bruger en hash-funktion til at beregne hash-koden for nøglerne og bruger derefter åben adressering til at løse kollisioner.

For at bruge unordered_map-beholderen i C++, skal du inkludere header-filen. Her er et eksempel på, hvordan man opretter en unordered_map-container i 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; } 

Forklaring:

• Dette program demonstrerer brugen af ​​unordered_map-beholderen i C++, som er implementeret ved hjælp af en hash-tabel og giver hurtig adgang til nøgle-værdi-par.
• For det første inkluderer programmet de nødvendige header-filer: og.
• Derefter opretter programmet en tom unordered_map-beholder kaldet my_map, som har strengnøgler og heltalsværdier. Dette gøres ved hjælp af syntaksen std::unordered_map my_map;
• Dernæst indsætter programmet tre nøgleværdi-par i my_map-beholderen ved hjælp af []-operatoren: 'æble' med værdien 10, 'banan' med værdien 20 og 'orange' med værdien 30.
• Dette gøres ved at bruge syntaksen my_map['apple'] = 10;, my_map['banan'] = 20;, og my_map['orange'] = 30; henholdsvis.
• Til sidst udskriver programmet værdien forbundet med 'banan'-nøglen ved hjælp af []-operatoren og std::cout-objektet.

Program output:

Indsættelse af data i en Hash-tabel

For at indsætte et nøgle-værdi-par i en hash-tabel, skal vi først bruge et indeks i arrayet for at gemme nøgleværdi-parret. Hvis en anden nøgle kortlægger det samme indeks, har vi en kollision og skal håndtere det korrekt. En almindelig metode er at bruge chaining, hvor hver bucket i arrayet indeholder en sammenkædet liste over nøgle-værdi-par, der har den samme hash-værdi.

Her er et eksempel på, hvordan man indsætter et nøgleværdi-par i en hash-tabel ved hjælp af kæde:

 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; } } 

Forklaring:

• Først defineres en struktur kaldet node, som repræsenterer en enkelt node i hash-tabellen.
• Hver node har tre medlemmer: en char*-nøgle til at gemme nøglen, en int-værdi til at gemme den tilknyttede værdi og en pegepind til en anden node kaldet ved siden af ​​for at håndtere kollisioner i hash-tabellen ved hjælp af en sammenkædet liste.
• Et array af nodepointere kaldet hash_table er erklæret med en størrelse på 100. Dette array vil blive brugt til at gemme elementerne i hash-tabellen.
• Indsæt-funktionen tager en char*-tast og en int-værdi som parametre.
• Det starter med at beregne hash-værdien for den givne nøgle ved hjælp af hash-funktionen, som antages at være defineret et andet sted i programmet.
• Hashværdien reduceres derefter for at passe inden for størrelsen af ​​hash_table-arrayet ved hjælp af modulusoperatoren % 100.
• En ny node oprettes ved hjælp af dynamisk hukommelsesallokering (malloc(sizeof(node))), og dens medlemmer (nøgle, værdi og næste) tildeles henholdsvis den angivne nøgle, værdi og NULL.
• Hvis den tilsvarende slot i hash_table-arrayet er tom (NULL), hvilket indikerer, at der ikke er sket nogen kollision, tildeles den nye node til denne slot direkte (hash_table[hash_value] = new_node).

Men hvis der allerede er en node til stede ved det indeks i hash_table-arrayet, skal funktionen håndtere kollisionen. Den krydser den linkede liste fra den aktuelle node (hash_table[hash_value]) og flytter til den næste node, indtil den når slutningen (curr_node->next != NULL). Når slutningen af ​​listen er nået, tilføjes den nye node som den næste node (curr_node->next = new_node).

Implementering af hashing i C++:

Lad os se en implementering af hashing i C++ ved hjælp af åben adressering og lineær sondering til kollisionsopløsning. Vi implementerer en hash-tabel, der gemmer heltal.

 #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;>