logo

TechCodeview

Hashing i datastruktur

Introduksjon til hashing i datastruktur:

Hashing er en populær teknikk innen informatikk som innebærer å kartlegge store datasett til verdier med fast lengde. Det er en prosess for å konvertere et datasett med variabel størrelse til et datasett med en fast størrelse. Evnen til å utføre effektive oppslagsoperasjoner gjør hashing til et viktig konsept i datastrukturer.

Hva er Hashing?

En hashing-algoritme brukes til å konvertere en inngang (som en streng eller et heltall) til en utdata med fast størrelse (referert til som en hash-kode eller hash-verdi). Dataene blir deretter lagret og hentet ved å bruke denne hash-verdien som en indeks i en matrise eller hash-tabell. Hash-funksjonen må være deterministisk, noe som garanterer at den alltid vil gi samme resultat for en gitt inngang.

Hashing brukes ofte til å lage en unik identifikator for en del av data, som kan brukes til raskt å slå opp disse dataene i et stort datasett. For eksempel kan en nettleser bruke hashing for å lagre nettstedspassord sikkert. Når en bruker skriver inn passordet sitt, konverterer nettleseren det til en hash-verdi og sammenligner det med den lagrede hash-verdien for å autentisere brukeren.

Hva er en hash-nøkkel?

I sammenheng med hashing er en hash-nøkkel (også kjent som en hash-verdi eller hash-kode) en numerisk eller alfanumerisk representasjon med fast størrelse generert av en hash-algoritme. Det er avledet fra inndataene, for eksempel en tekststreng eller en fil, gjennom en prosess kjent som hashing.

Hashing innebærer å bruke en spesifikk matematisk funksjon på inngangsdataene, som produserer en unik hash-nøkkel som vanligvis er av fast lengde, uavhengig av størrelsen på inngangen. Den resulterende hash-nøkkelen er i hovedsak et digitalt fingeravtrykk av de originale dataene.

Hash-nøkkelen tjener flere formål. Det brukes ofte for dataintegritetskontroller, da selv en liten endring i inndataene vil produsere en vesentlig annen hash-nøkkel. Hash-nøkler brukes også for effektiv datainnhenting og lagring i hashtabeller eller datastrukturer, da de tillater raske oppslags- og sammenligningsoperasjoner.

Hvordan fungerer hashing?

Prosessen med hashing kan deles inn i tre trinn:

  • Inndata: Dataene som skal hashes legges inn i hashingalgoritmen.
  • Hash-funksjon: Hashing-algoritmen tar inndataene og bruker en matematisk funksjon for å generere en hash-verdi med fast størrelse. Hash-funksjonen bør utformes slik at ulike inngangsverdier gir ulike hash-verdier, og små endringer i input gir store endringer i utdata.
  • Utdata: Hash-verdien returneres, som brukes som en indeks for å lagre eller hente data i en datastruktur.

Hashing-algoritmer:

Det er mange hashing-algoritmer, hver med distinkte fordeler og ulemper. De mest populære algoritmene inkluderer følgende:

  • MD5: En mye brukt hashing-algoritme som produserer en 128-bits hash-verdi.
  • SHA-1: En populær hashing-algoritme som produserer en 160-bits hash-verdi.
  • SHA-256: En sikrere hash-algoritme som produserer en 256-bits hash-verdi.
Hashing i datastruktur

Hash funksjon:

Hash-funksjon: En hash-funksjon er en type matematisk operasjon som tar en inngang (eller nøkkel) og gir ut et resultat med fast størrelse kjent som en hash-kode eller hash-verdi. Hash-funksjonen må alltid gi samme hash-kode for samme inngang for å være deterministisk. I tillegg bør hash-funksjonen produsere en unik hash-kode for hver inngang, som er kjent som hash-egenskapen.

Det finnes forskjellige typer hash-funksjoner, inkludert:

    Delingsmetode:

Denne metoden innebærer å dele nøkkelen med tabellstørrelsen og ta resten som hashverdi. For eksempel, hvis tabellstørrelsen er 10 og nøkkelen er 23, vil hashverdien være 3 (23 % 10 = 3).

    Multiplikasjonsmetode:

Denne metoden innebærer å multiplisere nøkkelen med en konstant og ta brøkdelen av produktet som hashverdi. For eksempel, hvis nøkkelen er 23 og konstanten er 0,618, vil hash-verdien være 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

    Universal hashing:

Denne metoden innebærer å bruke en tilfeldig hash-funksjon fra en familie av hash-funksjoner. Dette sikrer at hash-funksjonen ikke er partisk mot noen spesiell inngang og er motstandsdyktig mot angrep.

Kollisjonsoppløsning

En av hovedutfordringene i hashing er håndtering av kollisjoner, som oppstår når to eller flere inngangsverdier produserer samme hashverdi. Det er ulike teknikker som brukes for å løse kollisjoner, inkludert:

  • Kobling: I denne teknikken inneholder hver hash-tabellplass en koblet liste over alle verdiene som har samme hash-verdi. Denne teknikken er enkel og lett å implementere, men den kan føre til dårlig ytelse når de koblede listene blir for lange.
  • Åpen adressering: I denne teknikken, når en kollisjon oppstår, søker algoritmen etter et tomt spor i hash-tabellen ved å undersøke påfølgende spor til et tomt spor blir funnet. Denne teknikken kan være mer effektiv enn kjetting når belastningsfaktoren er lav, men den kan føre til gruppering og dårlig ytelse når belastningsfaktoren er høy.
  • Dobbel hashing: Dette er en variant av åpen adressering som bruker en andre hash-funksjon for å bestemme neste spor som skal undersøkes når en kollisjon oppstår. Denne teknikken kan bidra til å redusere gruppering og forbedre ytelsen.

Eksempel på kollisjonsoppløsning

La oss fortsette med vårt eksempel på en hashtabell med størrelsen 5. Vi ønsker å lagre nøkkelverdi-parene 'John: 123456' og 'Mary: 987654' i hashtabellen. Begge nøklene produserer samme hash-kode på 4, så en kollisjon oppstår.

Vi kan bruke kjetting for å løse kollisjonen. Vi oppretter en koblet liste ved indeks 4 og legger til nøkkelverdi-parene til listen. Hash-tabellen ser nå slik ut:

0:

java streng til int konvertering

1:

2:

3:

4: John: 123456 -> Mary: 987654

returnerer arrays i java

5:

Hash-tabell:

En hashtabell er en datastruktur som lagrer data i en matrise. Vanligvis velges en størrelse for matrisen som er større enn antallet elementer som kan passe inn i hashtabellen. En nøkkel tilordnes en indeks i matrisen ved hjelp av hash-funksjonen.

Hash-funksjonen brukes til å finne indeksen der et element må settes inn i hash-tabellen for å legge til et nytt element. Elementet blir lagt til den indeksen hvis det ikke er en kollisjon. Hvis det er en kollisjon, brukes kollisjonsoppløsningsmetoden for å finne neste tilgjengelige spor i matrisen.

Hash-funksjonen brukes til å finne indeksen som elementet er lagret for å hente den fra hash-tabellen. Hvis elementet ikke finnes i den indeksen, brukes kollisjonsoppløsningsmetoden for å søke etter elementet i den koblede listen (hvis kjetting brukes) eller i neste tilgjengelige spor (hvis åpen adressering brukes).

Hash-tabelloperasjoner

Det er flere operasjoner som kan utføres på en hash-tabell, inkludert:

  • Innsetting: Setter inn et nytt nøkkelverdi-par i hash-tabellen.
  • Sletting: Fjerner et nøkkelverdi-par fra hash-tabellen.
  • Søk: Søker etter et nøkkelverdi-par i hashtabellen.

Opprette en hash-tabell:

Hashing brukes ofte til å bygge hash-tabeller, som er datastrukturer som muliggjør rask innsetting, sletting og gjenfinning av data. Ett eller flere nøkkelverdi-par kan lagres i hver av matrisene med bøttene som utgjør en hash-tabell.

For å lage en hash-tabell, må vi først definere en hash-funksjon som tilordner hver nøkkel til en unik indeks i matrisen. En enkel hash-funksjon kan være å ta summen av ASCII-verdiene til tegnene i nøkkelen og bruke resten når de er delt på størrelsen på matrisen. Imidlertid er denne hash-funksjonen ineffektiv og kan føre til kollisjoner (to nøkler som tilordnes samme indeks).

For å unngå kollisjoner kan vi bruke mer avanserte hash-funksjoner som gir en jevnere fordeling av hash-verdier over matrisen. En populær algoritme er djb2-hash-funksjonen, som bruker bitvise operasjoner for å generere en hash-verdi:

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

Denne hash-funksjonen tar en streng som input og returnerer en hash-verdi med langt heltall uten fortegn. Funksjonen initialiserer en hash-verdi på 5381 og itererer deretter over hvert tegn i strengen, ved hjelp av bitvise operasjoner for å generere en ny hash-verdi. Den endelige hash-verdien returneres.

Hash-tabeller i C++

I C++ gir standardbiblioteket en hashtabellbeholderklasse kalt unordered_map. Unordered_map-beholderen er implementert ved hjelp av en hash-tabell og gir rask tilgang til nøkkelverdi-par. Unordered_map-beholderen bruker en hash-funksjon for å beregne hash-koden til nøklene og bruker deretter åpen adressering for å løse kollisjoner.

For å bruke unordered_map-beholderen i C++, må du inkludere overskriftsfilen. Her er et eksempel på hvordan du oppretter en unordered_map-beholder 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 programmet demonstrerer bruken av unordered_map-beholderen i C++, som er implementert ved hjelp av en hash-tabell og gir rask tilgang til nøkkelverdi-par.
  • Først inkluderer programmet de nødvendige header-filene: og.
  • Deretter oppretter programmet en tom unordered_map-beholder kalt my_map, som har strengnøkler og heltallsverdier. Dette gjøres ved å bruke syntaksen std::unordered_map my_map;
  • Deretter setter programmet inn tre nøkkelverdi-par i my_map-beholderen ved å bruke []-operatoren: 'eple' med en verdi på 10, 'banan' med en verdi på 20 og 'oransje' med en verdi på 30.
  • Dette gjøres ved å bruke syntaksen my_map['apple'] = 10;, my_map['banan'] = 20;, og my_map['orange'] = 30; hhv.
  • Til slutt skriver programmet ut verdien knyttet til 'banan'-nøkkelen ved å bruke []-operatoren og std::cout-objektet.

Programutgang:

Hashing i datastruktur

Sette inn data i en hash-tabell

For å sette inn et nøkkelverdi-par i en hash-tabell, må vi først legge inn en indeks i matrisen for å lagre nøkkelverdi-paret. Hvis en annen nøkkel karter til samme indeks, har vi en kollisjon og må håndtere den på riktig måte. En vanlig metode er å bruke kjeding, der hver bøtte i matrisen inneholder en koblet liste over nøkkelverdi-par som har samme hash-verdi.

Her er et eksempel på hvordan du setter inn et nøkkelverdi-par i en hash-tabell ved hjelp av kjeding:

 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 kalt node, som representerer en enkelt node i hashtabellen.
  • Hver node har tre medlemmer: en char*-nøkkel for å lagre nøkkelen, en int-verdi for å lagre den tilknyttede verdien, og en peker til en annen node kalt ved siden av for å håndtere kollisjoner i hash-tabellen ved hjelp av en koblet liste.
  • En rekke nodepekere kalt hash_table er deklarert med en størrelse på 100. Denne matrisen vil bli brukt til å lagre elementene i hashtabellen.
  • Innsettingsfunksjonen tar en char*-tast og en int-verdi som parametere.
  • Den starter med å beregne hash-verdien for den gitte nøkkelen ved hjelp av hash-funksjonen, som antas å være definert andre steder i programmet.
  • Hash-verdien reduseres deretter for å passe innenfor størrelsen på hash_table-matrisen ved å bruke modulusoperatoren % 100.
  • En ny node opprettes ved hjelp av dynamisk minneallokering (malloc(sizeof(node))), og dens medlemmer (nøkkel, verdi og neste) tildeles henholdsvis den angitte nøkkelen, verdien og NULL.
  • Hvis den tilsvarende sporet i hash_table-matrisen er tom (NULL), noe som indikerer at ingen kollisjon har skjedd, tilordnes den nye noden til det sporet direkte (hash_table[hash_value] = new_node).

Imidlertid, hvis det allerede er en node til stede ved den indeksen i hash_table-matrisen, må funksjonen håndtere kollisjonen. Den krysser den koblede listen fra den gjeldende noden (hash_table[hash_value]) og flytter til neste node til den når slutten (curr_node->neste != NULL). Når slutten av listen er nådd, legges den nye noden til som neste node (curr_node->next = new_node).

Implementering av hashing i C++:

La oss se en implementering av hashing i C++ ved bruk av åpen adressering og lineær sondering for kollisjonsoppløsning. Vi skal implementere en hashtabell som lagrer heltall.

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