Hash funkcija
U ovom odjeljku raspravljat ćemo o hash funkciji koja pomaže u izvršavanju hash koda povezanog ključa podatkovne stavke u podatkovnoj strukturi kao što je spomenuto u nastavku:
Int hashItem ( int ključ ){
povratak ključ % veličina stola ;
}
Proces izvršavanja indeksa niza naziva se raspršivanje. Ponekad se ista vrsta koda izvršava za generiranje istog indeksa korištenjem istih ključeva koji se nazivaju kolizije, a kojima se rukuje kroz različito ulančavanje (stvaranje povezanog popisa) i implementaciju otvorenih strategija adresiranja.
Rad Hash tablice u C++
Pokazivači na stvarne vrijednosti čuvaju se u hash tablici. Koristi ključ za traženje indeksa niza u kojem vrijednosti prema ključevima trebaju biti pohranjene na željenom mjestu u nizu. Uzeli smo hash tablicu veličine 10 kao što je spomenuto u nastavku:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Uzmimo nasumično sve podatke prema različitim ključevima i pohranimo te ključeve u hash tablicu samo izračunavanjem indeksa. Dakle, podaci se pohranjuju prema ključevima u izračunatom indeksu uz pomoć hash funkcije. Pretpostavimo da uzmemo podatke = {14,25,42,55,63,84} i ključeve = [ 15,9,5,25,66,75 ].
Izračunajte indeks ovih podataka pomoću hash funkcije. Vrijednost indeksa navedena je u nastavku:
| Ključ | petnaest | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Izračunajte indeks | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Podaci | 14 | 25 | 42 | 55 | 63 | 84 |
Nakon stvaranja indeksa niza, postavite podatke nasuprot ključu na točnom indeksu danog niza kao što je prethodno opisano.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Nakon toga možemo vidjeti da dolazi do kolizije ako dva ili više ključeva imaju isti hash kod što rezultira istim indeksom elemenata u nizu. Imamo jedno rješenje za izbjegavanje mogućnosti sudara: odabir dobre metode raspršivanja i implementacija točnih strategija.
Raspravimo sada o različitim tehnikama implementacije uz pomoć odgovarajućih primjera.
Primjer: dodajte podatke u hash tablicu pomoću tehnike otvorenog hashiranja
U ovom primjeru koristimo tehniku implementacije kao što je Open Hashing kako bismo izbjegli koliziju u hash tablici. U otvorenom raspršivanju ili ulančavanju stvaramo povezani popis za ulančavanje vrijednosti hash tablice. Isječak koda ovog primjera priložen je u nastavku koji opisuje tehniku otvorenog raspršivanja:
#include#include
razreda HashTable {
privatna :
statički konst int veličina tablice = 10 ;
std :: popis < int > stol ima [ veličina tablice ] ;
int hashFunc ( int ključ ) {
povratak ključ % veličina tablice ;
}
javnost :
poništiti umetnuti ( int ključ ) {
int indeks = hashFunc ( ključ ) ;
stol ima [ indeks ] . odgurnuti ( ključ ) ;
}
poništiti viewTable ( ) {
za ( int ja = 0 ; ja < veličina tablice ; ++ ja ) {
std :: cout << '[' << ja << ']' ;
za ( auto to = stol ima [ ja ] . početi ( ) ; to ! = stol ima [ ja ] . kraj ( ) ; ++ to ) {
std :: cout << ' -> ' << * to ;
}
std :: cout << std :: endl ;
}
}
} ;
int glavni ( ) {
HashTable hasTable ;
hasTable. umetnuti ( petnaest ) ;
hasTable. umetnuti ( 33 ) ;
hasTable. umetnuti ( 23 ) ;
hasTable. umetnuti ( 65 ) ;
hasTable. umetnuti ( 3 ) ;
hasTable. viewTable ( ) ;
povratak 0 ;
}
Ovo je vrlo zanimljiv primjer: gradimo povezani popis i umećemo podatke u hash tablicu. Prije svega, definiramo biblioteke na početku programa. The < popis > biblioteka se koristi za implementaciju povezanog popisa. Nakon toga gradimo klasu pod nazivom 'HashTable' i stvaramo atribute klase koji su privatni kao veličina tablice i niz tablice pomoću ključne riječi 'private:'. Zapamtite da se privatni atributi ne mogu koristiti izvan klase. Ovdje uzimamo veličinu tablice kao '10'. Pomoću toga inicijaliziramo hash metodu i izračunavamo indeks hash tablice. U hash funkciji prosljeđujemo ključ i veličinu hash tablice.
Gradimo nekoliko potrebnih funkcija i te funkcije objavljujemo u razredu. Zapamtite da se javne funkcije mogu koristiti izvan razreda bilo gdje. Koristimo ključnu riječ “public:” za početak javnog dijela klase . Budući da želimo dodati nove elemente u hash tablicu, stvaramo funkciju pod nazivom 'InsertHash' s ključem kao argumentom funkcije. U funkciji “insert” inicijaliziramo indeksnu varijablu. Prosljeđujemo hash funkciju varijabli indeksa. Nakon toga proslijedite varijablu indeksa povezanom popisu tableHas[] koristeći metodu 'push' za umetanje elementa u tablicu.
Nakon toga gradimo funkciju 'viewHashTab' za prikaz hash tablice kako bismo vidjeli novoumetnute podatke. U ovoj funkciji koristimo petlju 'for' koja pretražuje vrijednosti do kraja hash tablice. Osigurajte da su vrijednosti pohranjene na istom indeksu koji su razvijeni pomoću hash funkcije. U petlji prosljeđujemo vrijednosti na njihovim odgovarajućim indeksima i ovdje završavamo klasu. U funkciji “main” uzimamo objekt klase pod nazivom “hasTable”. Uz pomoć ovog objekta klase, možemo pristupiti metodi umetanja prosljeđivanjem ključa u metodi. Ključ koji smo proslijedili u funkciji 'main' izračunat je u funkciji 'insert' koja vraća poziciju indeksa u hash tablici. Prikazali smo hash tablicu pozivanjem funkcije “view” uz pomoć objekta “Class”.
Izlaz ovog koda je priložen u sljedećem:
Kao što vidimo, hash tablica je uspješno kreirana korištenjem povezane liste u C++. Otvoreno ulančavanje koristi se kako bi se izbjegla kolizija istog indeksa.
Zaključak
Na kraju smo zaključili da je hash tablica najčešća tehnika za pohranu i dobivanje ključeva s parovima vrijednosti za učinkovito rukovanje ogromnim količinama podataka. Šanse za koliziju su vrlo visoke u hash tablici, uništavajući podatke i njihovu pohranu. Ovu koliziju možemo prevladati korištenjem različitih tehnika upravljanja hash tablicom. Razvijanjem hash tablice u C++-u, programeri mogu povećati performanse korištenjem najbolje prikladne tehnike za pohranu podataka u hash tablicu. Nadamo se da će vam ovaj članak pomoći u razumijevanju hash tablice.