Funcția Hash
În această secțiune, vom discuta despre funcția hash care ajută la executarea codului hash al cheii aferente elementului de date din structura de date, așa cum este menționat în cele ce urmează:
Int hashItem ( int cheie ){
întoarcere cheie % dimensiunea mesei ;
}
Procesul de executare a indexului unui tablou se numește hashing. Uneori, același tip de cod este executat pentru a genera același index folosind aceleași chei numite coliziuni, care este gestionat prin diferite înlănțuiri (crearea listelor legate) și implementarea strategiilor de adresare deschisă.
Funcționarea tabelului Hash în C++
Indicatorii către valorile reale sunt păstrați în tabelul hash. Folosește o cheie pentru a căuta indexul unei matrice la care valorile față de chei trebuie să fie stocate în locația dorită dintr-o matrice. Am luat tabelul hash cu dimensiunea 10, așa cum se menționează în cele ce urmează:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Să luăm aleatoriu orice date pe diferite chei și să stocăm aceste chei într-un tabel hash, doar calculând indexul. Deci, datele sunt stocate pe cheile din indexul calculat cu ajutorul unei funcții hash. Să presupunem că luăm o dată = {14,25,42,55,63,84} și cheile =[ 15,9,5,25,66,75 ].
Calculați indicele acestor date folosind funcția hash. Valoarea indicelui este menționată în următoarele:
| Cheie | cincisprezece | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Calculați indicele | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Date | 14 | 25 | 42 | 55 | 63 | 84 |
După crearea indexului unei matrice, plasați datele pe cheie pe indexul exact al unei matrice date, așa cum este descris anterior.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
După aceea, putem vedea că are loc o coliziune dacă două sau mai multe chei au același cod hash, ceea ce are ca rezultat același index al elementelor din matrice. Avem o soluție pentru a evita șansele de coliziune: selectarea unei bune metode hash și implementarea strategiilor precise.
Acum, să discutăm despre diferitele tehnici de implementare cu ajutorul exemplelor adecvate.
Exemplu: Adăugați o date într-un tabel Hash utilizând o tehnică de hashing deschisă
În acest exemplu, luăm o tehnică de implementare precum Open Hashing pentru a evita coliziunea în tabelul hash. În hashing deschis sau înlănțuire, creăm o listă legată pentru a înlănțui valorile tabelului hash. Fragmentul de cod al acestui exemplu este atașat în cele ce urmează, care descrie tehnica de hashing deschis:
#include#include
clasă HashTable {
privat :
static const int tableSize = 10 ;
std :: listă < int > tableHas [ tableSize ] ;
int hashFunc ( int cheie ) {
întoarcere cheie % tableSize ;
}
public :
gol introduce ( int cheie ) {
int index = hashFunc ( cheie ) ;
tableHas [ index ] . împinge înapoi ( cheie ) ;
}
gol viewTable ( ) {
pentru ( int i = 0 ; i < tableSize ; ++ i ) {
std :: cout << '[' << i << ']' ;
pentru ( auto aceasta = tableHas [ i ] . ÎNCEPE ( ) ; aceasta ! = tableHas [ i ] . Sfârşit ( ) ; ++ aceasta ) {
std :: cout << ' -> ' << * aceasta ;
}
std :: cout << std :: endl ;
}
}
} ;
int principal ( ) {
HashTable areTable ;
areTable. introduce ( cincisprezece ) ;
areTable. introduce ( 33 ) ;
areTable. introduce ( 23 ) ;
areTable. introduce ( 65 ) ;
areTable. introduce ( 3 ) ;
areTable. viewTable ( ) ;
întoarcere 0 ;
}
Acesta este un exemplu foarte interesant: construim o listă legată și introducem datele în tabelul hash. În primul rând, definim bibliotecile la începutul programului. The < listă > biblioteca este utilizată pentru implementarea listelor legate. După aceea, construim o clasă numită „HashTable” și creăm atributele clasei care sunt private ca dimensiune tabelului și matrice de tabel folosind cuvântul cheie „private:”. Amintiți-vă că atributele private nu sunt utilizabile în afara clasei. Aici, luăm dimensiunea tabelului ca fiind „10”. Inițializam metoda hash folosind aceasta și calculăm indexul tabelului hash. În funcția hash, trecem cheia și dimensiunea tabelului hash.
Construim câteva funcții necesare și facem publice aceste funcții în clasă. Amintiți-vă că funcțiile publice sunt utilizabile în afara clasei oriunde. Folosim cuvântul cheie „public:” pentru a începe porțiunea publică a clasei . Deoarece dorim să adăugăm elemente noi la tabelul hash, creăm o funcție numită „InsertHash” cu o cheie ca argument al funcției. În funcția „inserare”, inițializam variabila index. Trecem funcția hash variabilei index. După aceea, treceți variabila index listei conectate tableHas[]folosind metoda „push” pentru a insera un element în tabel.
După aceea, construim o funcție „viewHashTab” pentru a afișa tabelul hash pentru a vedea datele nou introduse. În această funcție, luăm o buclă „for” care caută valorile până la sfârșitul tabelului hash. Asigurați-vă că valorile sunt stocate la același index care este dezvoltat folosind o funcție hash. În buclă, trecem valorile la indexul lor respectiv și încheiem clasa aici. În funcția „main”, luăm obiectul unei clase numite „hasTable”. Cu ajutorul acestui obiect de clasă, putem accesa metoda de inserare prin trecerea cheii în metodă. Cheia pe care am trecut-o în funcția „principală” este calculată în funcția „inserare” care returnează poziția indexului în tabelul hash. Am afișat tabelul hash apelând funcția „view” cu ajutorul unui obiect „Class”.
Ieșirea acestui cod este atașată în următoarele:
După cum putem vedea, tabelul hash este creat cu succes folosind lista legată în C++. Înlănțuirea deschisă este utilizată pentru a evita coliziunea aceluiași indice.
Concluzie
În cele din urmă, am ajuns la concluzia că un tabel hash este cea mai emergentă tehnică de stocare și obținere a cheilor cu perechi valori pentru a gestiona cantități uriașe de date în mod eficient. Șansele de coliziune sunt foarte mari în tabelul hash, distrugând datele și stocarea acestora. Putem depăși această coliziune folosind diferite tehnici de gestionare a tabelelor hash. Prin dezvoltarea tabelului hash în C++, dezvoltatorii pot crește performanța folosind cea mai bună tehnică potrivită pentru a stoca datele în tabelul hash. Sperăm că acest articol este util pentru înțelegerea tabelului hash.