hash table c programs implement hash table
Acest tutorial explică tabelele Hash C ++ și hărțile Hash. Veți afla, de asemenea, despre aplicațiile și implementarea tabelului Hash în C ++:
Hashing-ul este o tehnică prin care putem asocia o cantitate mare de date la un tabel mai mic folosind o „funcție hash”.
Folosind tehnica de hashing, putem căuta datele mai rapid și mai eficient în comparație cu alte tehnici de căutare, cum ar fi căutarea liniară și binară.
Să înțelegem tehnica de hashing cu un exemplu în acest tutorial.
=> Citiți seria Easy C ++ Training.
Ce veți învăța:
Hashing în C ++
Să luăm un exemplu de bibliotecă universitară care găzduiește mii de cărți. Cărțile sunt aranjate în funcție de subiecte, departamente etc. Dar totuși, fiecare secțiune va avea numeroase cărți, ceea ce face căutarea cărților extrem de dificilă.
Astfel, pentru a depăși această dificultate, atribuim un număr sau o cheie unică fiecărei cărți, astfel încât să știm instantaneu locația cărții. Acest lucru se realizează într-adevăr prin hashing.
Continuând cu exemplul bibliotecii noastre, în loc să identificăm fiecare carte pe baza departamentului, subiectului, secțiunii etc. care poate duce la un șir foarte lung, calculăm o valoare întreagă unică sau o cheie pentru fiecare carte din bibliotecă folosind o funcție unică și stocați aceste chei într-un tabel separat.
Funcția unică menționată mai sus se numește „funcția Hash” și tabelul separat se numește „Hash Table”. O funcție hash este utilizată pentru a asocia valoarea dată la o anumită cheie unică din tabelul Hash. Acest lucru duce la un acces mai rapid la elemente. Cu cât este mai eficientă funcția de hash, cu atât mai eficientă va fi maparea fiecărui element la cheia unică.
Să luăm în considerare o funcție hash h (x) care mapează valoarea „ X 'La' x% 10 ”În matrice. Pentru datele date, putem construi un tabel hash care conține chei sau coduri Hash sau Hash așa cum se arată în diagrama de mai jos.
În diagrama de mai sus, putem vedea că intrările din matrice sunt mapate la pozițiile lor în tabelul hash folosind o funcție hash.
Astfel, putem spune că hashing-ul este implementat folosind doi pași, după cum se menționează mai jos:
# 1) Valoarea este convertită într-o cheie întreagă unică sau hash utilizând o funcție hash. Este folosit ca un index pentru a stoca elementul original, care se încadrează în tabelul hash.
În diagrama de mai sus, valoarea 1 din tabelul hash este cheia unică pentru stocarea elementului 1 din matricea de date dată pe LHS-ul diagramei.
#Două) Elementul din matricea de date este stocat în tabelul hash unde poate fi recuperat rapid folosind cheia hash. În diagrama de mai sus, am văzut că am stocat toate elementele în tabelul hash după ce am calculat locațiile respective folosind o funcție hash. Putem folosi următoarele expresii pentru a prelua valorile și indexul hash.
hash = hash_func(key) index = hash % array_sizeFuncția Hash
Am menționat deja că eficiența mapării depinde de eficiența funcției hash pe care o folosim.
O funcție hash ar trebui să îndeplinească următoarele cerințe:
- Ușor de calculat: O funcție hash ar trebui să fie ușor de calculat cheile unice.
- Mai puțină coliziune: Când elementele echivalează cu aceleași valori cheie, are loc o coliziune. Ar trebui să existe coliziuni minime, pe cât posibil, în funcția hash care este utilizată. Întrucât coliziunile vor avea loc, trebuie să folosim tehnici adecvate de rezolvare a coliziunilor pentru a avea grijă de coliziuni.
- Distributie uniforma: Funcția Hash ar trebui să aibă ca rezultat o distribuție uniformă a datelor de-a lungul tabelului hash și astfel să prevină gruparea.
Hash Table C ++
Tabelul Hash sau o hartă hash este o structură de date care stochează indicii către elementele matricei de date originale.
În exemplul nostru de bibliotecă, tabelul hash pentru bibliotecă va conține indicii către fiecare dintre cărțile din bibliotecă.
Dacă aveți intrări în tabelul hash, este mai ușor să căutați un anumit element din matrice.
După cum s-a văzut deja, tabelul hash folosește o funcție hash pentru a calcula indexul în matricea de găleți sau sloturi cu ajutorul cărora se poate găsi valoarea dorită.
Luați în considerare un alt exemplu cu următoarea matrice de date:
Să presupunem că avem un tabel hash de dimensiunea 10 așa cum se arată mai jos:
Acum să folosim funcția hash dată mai jos.
Hash_code = Key_value % size_of_hash_tableAcest lucru va echivala cu Hash_code = Key_value% 10
Folosind funcția de mai sus, mapăm valorile cheie la locațiile tabelului hash așa cum se arată mai jos.
| Element de date | Funcția Hash | Hash_code |
|---|---|---|
| 22 | 22% 10 = 2 | Două |
| 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 |
Folosind tabelul de mai sus, putem reprezenta tabelul hash după cum urmează.
Astfel, atunci când trebuie să accesăm un element din tabelul hash, va dura doar O (1) pentru a face căutarea.
Coliziune
De obicei, calculăm codul hash folosind funcția hash, astfel încât să putem asocia valoarea cheii la codul hash din tabelul hash. În exemplul de mai sus al matricei de date, să introducem o valoare 12. În acest caz, codul hash_ pentru valoarea cheii 12 va fi 2. (12% 10 = 2).
Dar în tabelul hash, avem deja o mapare la valoarea cheie 22 pentru hash_code 2 așa cum se arată mai jos:
După cum se arată mai sus, avem același cod hash pentru două valori, 12 și 22, adică 2. Când una sau mai multe valori cheie echivalează cu aceeași locație, rezultă o coliziune. Astfel, locația codului hash este deja ocupată de o valoare cheie și există o altă valoare cheie care trebuie plasată în aceeași locație.
În cazul hashului, chiar dacă avem un tabel hash de dimensiuni foarte mari, atunci o coliziune va fi obligatorie acolo. Acest lucru se datorează faptului că găsim o mică valoare unică pentru o cheie mare în general, prin urmare este complet posibil ca una sau mai multe valori să aibă același cod hash la un moment dat.
Având în vedere că o coliziune este inevitabilă în hashing, ar trebui să căutăm întotdeauna modalități de prevenire sau rezolvare a coliziunii. Există diverse tehnici de rezolvare a coliziunilor pe care le putem folosi pentru a rezolva coliziunea care are loc în timpul hashului.
Tehnici de rezolvare a coliziunilor
Următoarele sunt tehnicile pe care le putem folosi pentru a rezolva coliziunea în tabelul hash.
Înlănțuire separată (Hashing deschis)
Aceasta este cea mai comună tehnică de rezoluție a coliziunilor. Acest lucru este, de asemenea, cunoscut sub numele de hash deschis și este implementat folosind o listă legată.
Într-o tehnică de înlănțuire separată, fiecare intrare din tabelul hash este o listă legată. Când cheia se potrivește cu codul hash, este introdusă într-o listă corespunzătoare acelui cod hash particular. Astfel, atunci când două taste au același cod hash, atunci ambele intrări sunt introduse în lista legată.
Pentru exemplul de mai sus, Înlănțuirea separată este reprezentată mai jos.
Diagrama de mai sus reprezintă înlănțuirea. Aici folosim funcția mod (%). Vedem că atunci când două valori cheie echivalează cu același cod hash, atunci legăm aceste elemente la acel cod hash folosind o listă legată.
Dacă cheile sunt distribuite uniform în tabelul de hash, costul mediu al căutării pentru cheia respectivă depinde de numărul mediu de chei din acea listă legată. Astfel, înlănțuirea separată rămâne eficientă chiar și atunci când există o creștere a numărului de intrări decât sloturile.
Cel mai rău caz pentru înlănțuirea separată este atunci când toate tastele echivalează cu același cod hash și astfel sunt inserate într-o singură listă legată. Prin urmare, trebuie să căutăm toate intrările din tabelul hash și costul care sunt proporționale cu numărul de taste din tabel.
Sondare liniară (adresare deschisă / Hashing închis)
În tehnica de adresare deschisă sau de sondare liniară, toate înregistrările de intrare sunt stocate chiar în tabelul hash. Când valoarea cheie-hărți la un cod hash și poziția indicată de cod hash este neocupată, atunci valoarea cheii este inserată în acea locație.
Dacă poziția este deja ocupată, atunci folosind o secvență de sondare, valoarea cheii este inserată în următoarea poziție, care este neocupată în tabelul hash.
Pentru sondarea liniară, funcția hash se poate modifica așa cum se arată mai jos:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Vedem că, în cazul sondării liniare, intervalul dintre sloturi sau sondele succesive este constant, adică 1.
furnizori de conturi de e-mail gratuite în SUA
În diagrama de mai sus, vedem că în 0alocație introducem 10 folosind funcția hash „hash = hash% hash_tableSize”.
Acum elementul 70 echivalează și cu locația 0 din tabelul hash. Dar acea locație este deja ocupată. Prin urmare, folosind sondarea liniară vom găsi următoarea locație care este 1. Deoarece această locație este neocupată, plasăm cheia 70 în această locație așa cum se arată folosind o săgeată.
Tabelul Hash rezultat este prezentat mai jos.
Sondajul liniar poate suferi de problema „clusterizării primare”, în care există șansa ca celulele continue să fie ocupate și probabilitatea de a insera un element nou se reduce.
De asemenea, dacă două elemente obțin aceeași valoare la prima funcție hash, atunci ambele elemente vor urma aceeași secvență a sondei.
Sondare quadratică
Sondarea quadratică este aceeași cu sondarea liniară, singura diferență fiind intervalul utilizat pentru sondare. După cum sugerează și numele, această tehnică folosește distanță neliniară sau pătratică pentru a ocupa sloturile atunci când are loc o coliziune în locul distanței liniare.
În sondarea pătratică, intervalul dintre sloturi este calculat prin adăugarea unei valori polinomiale arbitrare la indexul deja hash. Această tehnică reduce clusterizarea primară într-o măsură semnificativă, dar nu se îmbunătățește la clusterizarea secundară.
Hashing dublu
Tehnica dublei hashing este similară cu sondarea liniară. Singura diferență între dublarea hashului și sondarea liniară este că, în tehnica dublă hash, intervalul utilizat pentru sondare este calculat folosind două funcții hash. Deoarece aplicăm funcția hash la cheie una după alta, aceasta elimină clusterizarea primară, precum și clusterizarea secundară.
Diferența dintre înlănțuire (Hashing deschis) și sondare liniară (adresare deschisă)
| Înlănțuire (Hashing deschis) | Sondare liniară (adresare deschisă) |
|---|---|
| Valorile cheie pot fi stocate în afara tabelului utilizând o listă legată separat. | Valorile cheie trebuie stocate numai în tabel. |
| Numărul de elemente din tabelul hash poate depăși dimensiunea tabelului hash. | Numărul de elemente prezente în tabelul hash nu va depăși numărul de indici din tabelul hash. |
| Ștergerea este eficientă în tehnica de înlănțuire. | Ștergerea poate fi greoaie. Poate fi evitat dacă nu este necesar. |
| Deoarece se menține o listă legată separată pentru fiecare locație, spațiul ocupat este mare. | Deoarece toate intrările sunt găzduite în același tabel, spațiul ocupat este mai mic. |
Implementarea tabelului Hash C ++
Putem implementa hashing folosind tablouri sau liste legate pentru a programa tabelele de hash. În C ++ avem, de asemenea, o caracteristică numită „hartă hash”, care este o structură similară cu un tabel hash, dar fiecare intrare este o pereche cheie-valoare. În C ++ se numește harta hash sau pur și simplu o hartă. Harta Hash în C ++ este de obicei neordonată.
Există un antet definit în Biblioteca de șabloane standard (STL) a C ++ care implementează funcționalitatea hărților. Am acoperit Hărți STL în detaliu în tutorialul nostru despre STL.
Următoarea implementare este pentru hash folosind listele legate ca structură de date pentru tabelul hash. De asemenea, folosim „Înlănțuirea” ca tehnică de rezoluție a coliziunilor în această implementare.
#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:'< Ieșire:
S-a creat tabelul Hash:
0 -> 21 -> 14
1 -> 15
Două
3
4 -> 11
5 -> 12
6
Hash table după ștergerea cheii 12:
0 -> 21 -> 14
1 -> 15
Două
3
4 -> 11
5
6
Ieșirea arată un tabel hash care este creat de dimensiunea 7. Folosim înlănțuirea pentru a rezolva coliziunea. Afișăm tabelul hash după ștergerea uneia dintre taste.
Aplicații de Hashing
# 1) Verificarea parolelor: Verificarea parolelor se face de obicei utilizând funcții hash criptografice. Când parola este introdusă, sistemul calculează hash-ul parolei și este apoi trimis la server pentru verificare. Pe server, valorile hash ale parolelor originale sunt stocate.
# 2) Structuri de date: Diferite structuri de date cum ar fi unordered_set și unordered_map în C ++, dicționarele în python sau C #, HashSet și harta hash în Java utilizează toate perechi cheie-valoare în care cheile sunt valori unice. Valorile pot fi aceleași pentru taste diferite. Hashing este utilizat pentru a implementa aceste structuri de date.
# 3) Rezumatul mesajului: Aceasta este încă o altă aplicație care folosește un hash criptografic. În rezumatele mesajelor, calculăm un hash pentru datele trimise și primite sau chiar fișiere și le comparăm cu valorile stocate pentru a ne asigura că fișierele de date nu sunt modificate. Cel mai comun algoritm aici este „SHA 256”.
# 4) Funcționarea compilatorului: Când compilatorul compilează un program, cuvintele cheie pentru limbajul de programare sunt stocate diferit de celelalte identificări. Compilatorul folosește un tabel hash pentru stocarea acestor cuvinte cheie.
# 5) Indexarea bazei de date: Tabelele Hash sunt utilizate pentru indexarea bazelor de date și structurile de date bazate pe disc.
# 6) Matrice asociative: Tablourile asociative sunt matrici ale căror indici sunt de tipul de date, altele decât șiruri de tip întreg sau alte tipuri de obiecte. Tabelele Hash pot fi utilizate pentru implementarea matricilor asociative.
Concluzie
Hashing este cea mai utilizată structură de date, deoarece este nevoie de timp constant O (1) pentru operațiuni de inserare, ștergere și căutare. Hashing-ul este în mare parte implementat utilizând o funcție hash care calculează o valoare cheie unică mai mică pentru intrări de date mari. Putem implementa hashing folosind tablouri și liste legate.
Ori de câte ori una sau mai multe intrări de date echivalează cu aceleași valori ale cheilor, rezultă o coliziune. Am văzut diverse tehnici de rezoluție a coliziunilor, inclusiv sondare liniară, înlănțuire etc. Am văzut, de asemenea, implementarea hashului în C ++.
În concluzie, putem spune că hashing-ul este de departe cea mai eficientă structură de date din lumea programării.
=> Căutați întreaga serie de formare C ++ aici.
Lectură recomandată
- Cum se scrie scenarii complexe de testare a logicii de afaceri folosind tehnica tabelului de decizii
- Tabel de validare a câmpului (FVT): o tehnică de proiectare a testului pentru validarea câmpului
- Tutorial QTP # 15 - Utilizarea punctelor de verificare a zonei de text, a tabelului și a paginii în QTP
- MAPS În STL
- Totul despre routere: tipuri de routere, tabel de rutare și rutare IP
- Top 40 Cele mai bune întrebări și răspunsuri la interviu MySQL (2021 întrebări)
- Top 90 întrebări și răspunsuri la interviul SQL (ULTIMELE)
- Comenzi Unix Utilities Programs: Which, Man, Find Su, Sudo (Partea D)