Hashing în structura datelor: funcție, tehnici [cu exemple]

Introducere

Hashingul este o structură de date importantă concepută pentru a rezolva problema găsirii și stocării eficiente a datelor într-o matrice. De exemplu, dacă aveți o listă de 20000 de numere și ați dat un număr pentru a căuta în acea listă - veți scana fiecare număr din listă până când găsiți o potrivire.

Este nevoie de o cantitate semnificativă din timpul tău pentru a căuta în întreaga listă și a găsi acel număr specific. Acest proces manual de scanare nu este doar consumator de timp, ci și ineficient. Cu hashing în structura datelor, puteți restrânge căutarea și găsiți numărul în câteva secunde.

Acest blog vă va oferi o înțelegere mai profundă a metodei hash, a tabelelor hash și a sondajului liniar cu exemple.

Ce este hashing în structura datelor?

Hashing în structura de date este o tehnică de mapare a unei părți mari de date în tabele mici folosind o funcție de hashing. Este, de asemenea, cunoscută sub numele de funcție de rezumare a mesajelor. Este o tehnică care identifică în mod unic un articol specific dintr-o colecție de articole similare.

Folosește tabele hash pentru a stoca datele într-un format de matrice. Fiecare valoare din matrice are atribuit un număr de index unic. Tabelele hash folosesc o tehnică pentru a genera aceste numere de index unice pentru fiecare valoare stocată într-un format de matrice. Această tehnică se numește tehnica hash.

Trebuie doar să găsiți indexul articolului dorit, mai degrabă decât să găsiți datele. Cu indexare, puteți scana rapid întreaga listă și puteți prelua elementul dorit. Indexarea ajută, de asemenea, la inserarea operațiunilor atunci când trebuie să inserați date într-o anumită locație. Indiferent cât de mare sau mic este tabelul, puteți actualiza și recupera datele în câteva secunde.

Hashing într-o structură de date este un proces în doi pași.

1. Funcția hash transformă elementul într-un întreg mic sau o valoare hash. Acest număr întreg este folosit ca index pentru a stoca datele originale.
2. Stochează datele într-un tabel hash. Puteți utiliza o cheie hash pentru a localiza rapid datele.

Exemple de hashing în structura datelor

Următoarele sunt exemple reale de hashing în structura de date -

• În școli, profesorul atribuie fiecărui elev un număr unic. Mai târziu, profesorul folosește acel număr de rolă pentru a prelua informații despre acel elev.
• O bibliotecă are un număr infinit de cărți. Bibliotecarul atribuie un număr unic fiecărei cărți. Acest număr unic ajută la identificarea poziției cărților pe raft.

Checkout: Sortare în structura datelor

Funcția Hash

Funcția hash dintr-o structură de date mapează dimensiunea arbitrară a datelor cu datele de dimensiune fixă. Returnează următoarele valori: o valoare întreagă mică (cunoscută și ca valoare hash), coduri hash și sume hash.

hash = hashfunc(cheie)

index = hash % array_size

Funcția has trebuie să îndeplinească următoarele cerințe:

• O funcție hash bună este ușor de calculat.
• O funcție hash bună nu se blochează niciodată în clustering și distribuie cheile uniform pe tabelul hash.
• O funcție hash bună evită coliziunea atunci când două elemente sau elemente sunt atribuite aceleiași valori hash.

Tabel Hash

Hashing în structura de date utilizează tabele hash pentru a stoca perechile cheie-valoare. Tabelul hash utilizează apoi funcția hash pentru a genera un index. Hashing folosește acest index unic pentru a efectua operațiuni de inserare, actualizare și căutare.

Cum funcționează hashingul în structura datelor?

În hashing, funcția de hashing mapează șiruri sau numere la o valoare întreagă mică. Tabelele hash preiau elementul din listă folosind o funcție de hashing. Obiectivul tehnicii hashing este de a distribui datele uniform într-o matrice. Hashingul atribuie tuturor elementelor o cheie unică. Tabelul hash folosește această cheie pentru a accesa datele din listă.

Tabelul hash stochează datele într-o pereche cheie-valoare. Tasta acționează ca o intrare în funcția de hashing. Funcția hashing generează apoi un număr index unic pentru fiecare valoare stocată. Numărul de index păstrează valoarea care corespunde acelei chei. Funcția hash returnează o valoare întreagă mică ca rezultat. Ieșirea funcției hash se numește valoare hash.

Să înțelegem hashingul într-o structură de date cu un exemplu. Imaginați-vă că trebuie să stocați unele elemente (aranjate într-o pereche cheie-valoare) într-un tabel hash cu 30 de celule.

Valorile sunt: ​​(3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Tabelul hash va arăta astfel:

Citiți și: Tipuri de structuri de date în Python

Tehnici de rezolvare a coliziunilor

Hashing în structura de date intră într-o coliziune dacă două chei au același număr de index în tabelul hash. Ciocnirea creează o problemă deoarece fiecare index dintr-un tabel hash ar trebui să stocheze o singură valoare. Hashing în structura de date utilizează mai multe tehnici de rezoluție a coliziunilor pentru a gestiona performanța unui tabel hash.

Sondare liniară

Hashing în structura datelor are ca rezultat un index de matrice care este deja ocupat pentru a stoca o valoare. Într-un astfel de caz, hashingul efectuează o operație de căutare și sondează liniar următoarea celulă goală.

Exemplu de sondare liniară

Imaginați-vă că vi s-a cerut să stocați unele elemente într-un tabel hash de dimensiunea 30. Elementele sunt deja sortate într-un format de pereche cheie-valoare. Valorile date sunt: ​​(3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Hash(n) este indexul calculat folosind o funcție hash și T este dimensiunea tabelului. Dacă indexul slotului = ( hash(n) % T) este plin, atunci căutăm următorul index al slotului adăugând 1 ((hash(n) + 1) % T). Dacă (hash(n) + 1) % T este de asemenea plin, atunci încercăm (hash(n) + 2) % T. Dacă (hash(n) + 2) % T este de asemenea plin, atunci încercăm (hash( n) + 3) % T.

Tabelul hash va arăta astfel:

Hashing dublu

Tehnica hash dublu folosește două funcții hash. A doua funcție hash intră în uz atunci când prima funcție provoacă o coliziune. Oferă un index de compensare pentru a stoca valoarea.

Formula pentru tehnica de hashing dublu este următoarea:

(firstHash(cheie) + i * secondHash(cheie)) % sizeOfTable

Unde i este valoarea offsetului. Această valoare de compensare continuă să fie crescută până când găsește un slot gol.

De exemplu, aveți două funcții hash: h1 și h2. Trebuie să efectuați următorii pași pentru a găsi un slot gol:

1. Verificați dacă hash1 (cheia) este goală. Dacă da, atunci stocați valoarea pe acest slot.
2. Dacă hash1(key) nu este gol, atunci găsiți un alt slot folosind hash2(key).
3. Verificați dacă hash1(key) + hash2(key) este gol. Dacă da, atunci stocați valoarea pe acest slot.
4. Continuați să creșteți contorul și repetați cu hash1(key)+2hash2(key), hash1(key)+3hash2(key) și așa mai departe, până când găsește un slot gol.

Exemplu de hashing dublu

Imaginați-vă că trebuie să stocați unele elemente într-un tabel hash de dimensiunea 20. Valorile date sunt: ​​(16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

Concluzie

Hashingul dublu are un cost de calcul ridicat, dar caută următorul slot liber mai rapid decât metoda de sondare liniară. Exemplele date în articol au doar scop explicativ. Puteți modifica declarațiile de mai sus în funcție de cerințele dvs. În acest blog, am aflat despre conceptul de hashing în structura datelor .

Puteți încerca exemplul pentru a vă consolida cunoștințele privind structura datelor. Dacă sunteți curios să aflați mai multe despre structura datelor , consultați cursul upGrad Executive PG Program în Full Stack Development . Acest curs este conceput pentru profesioniști care lucrează și oferă pregătire riguroasă și plasare la locul de muncă la companii de top.