Funkcija zgoščevanja
V tem razdelku bomo razpravljali o zgoščevalni funkciji, ki pomaga izvesti zgoščevalno kodo povezanega ključa podatkovne postavke v podatkovni strukturi, kot je navedeno v naslednjem:
Int hashitem ( int ključ ){
vrnitev ključ % velikost mize ;
}
Postopek izvajanja indeksa matrike se imenuje zgoščevanje. Včasih se izvede ista vrsta kode za generiranje istega indeksa z uporabo istih ključev, imenovanih trki, ki se obravnavajo z drugačnim veriženjem (ustvarjanje povezanih seznamov) in izvajanjem odprtih strategij naslavljanja.
Delovanje zgoščene tabele v C++
Kazalci na realne vrednosti so shranjeni v zgoščeni tabeli. Uporablja ključ za iskanje indeksa matrike, pri kateri je treba vrednosti glede na ključe shraniti na želeno mesto v matriki. Vzeli smo zgoščeno tabelo z velikostjo 10, kot je navedeno v nadaljevanju:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Vzemimo naključno vse podatke glede na različne ključe in shranimo te ključe v zgoščeno tabelo tako, da samo izračunamo indeks. Podatki so torej shranjeni glede na ključe v izračunanem indeksu s pomočjo zgoščevalne funkcije. Recimo, da vzamemo podatke = {14,25,42,55,63,84} in ključe = [ 15,9,5,25,66,75 ].
Izračunajte indeks teh podatkov s funkcijo zgoščevanja. Vrednost indeksa je navedena v naslednjem:
| Ključ | petnajst | 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 |
| podatki | 14 | 25 | 42 | 55 | 63 | 84 |
Ko ustvarite indeks matrike, postavite podatke proti ključu na natančen indeks dane matrike, kot je opisano prej.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Po tem lahko vidimo, da pride do trka, če imata dva ali več ključev enako zgoščeno kodo, kar ima za posledico enak indeks elementov v matriki. Imamo eno rešitev, da se izognemo možnostim trčenja: izbiro dobre metode zgoščevanja in izvajanje natančnih strategij.
Zdaj pa razpravljajmo o različnih tehnikah izvajanja s pomočjo ustreznih primerov.
Primer: dodajte podatke v zgoščevalno tabelo z uporabo odprte tehnike zgoščevanja
V tem primeru uporabimo tehniko implementacije, kot je Open Hashing, da preprečimo kolizijo v tabeli zgoščevanja. Pri odprtem zgoščevanju ali veriženju ustvarimo povezan seznam, da verižimo vrednosti zgoščevalne tabele. Delček kode tega primera je priložen v nadaljevanju, ki opisuje tehniko odprtega zgoščevanja:
#include#include
razred HashTable {
zasebno :
statična konst int tableSize = 10 ;
std :: seznam < int > tableHas [ tableSize ] ;
int hashFunc ( int ključ ) {
vrnitev ključ % tableSize ;
}
javnosti :
praznina vstavi ( int ključ ) {
int kazalo = hashFunc ( ključ ) ;
tableHas [ kazalo ] . porini nazaj ( ključ ) ;
}
praznina viewTable ( ) {
za ( int jaz = 0 ; jaz < tableSize ; ++ jaz ) {
std :: cout << '[' << jaz << ']' ;
za ( avto to = tableHas [ jaz ] . začeti ( ) ; to ! = tableHas [ jaz ] . konec ( ) ; ++ to ) {
std :: cout << ' -> ' << * to ;
}
std :: cout << std :: konec ;
}
}
} ;
int glavni ( ) {
HashTable hasTable ;
hasTable. vstavi ( petnajst ) ;
hasTable. vstavi ( 33 ) ;
hasTable. vstavi ( 23 ) ;
hasTable. vstavi ( 65 ) ;
hasTable. vstavi ( 3 ) ;
hasTable. viewTable ( ) ;
vrnitev 0 ;
}
To je zelo zanimiv primer: sestavimo povezan seznam in vstavimo podatke v zgoščeno tabelo. Najprej na začetku programa določimo knjižnice. The < seznam > knjižnica se uporablja za izvedbo povezanega seznama. Po tem zgradimo razred z imenom »HashTable« in ustvarimo atribute razreda, ki so zasebni kot velikost tabele in niz tabele s ključno besedo »private:«. Ne pozabite, da zasebni atributi niso uporabni zunaj razreda. Tukaj vzamemo velikost tabele kot '10'. S tem inicializiramo metodo zgoščevanja in izračunamo indeks zgoščene tabele. V zgoščevalni funkciji posredujemo ključ in velikost zgoščevalne tabele.
Izdelamo nekaj zahtevanih funkcij in te funkcije objavimo v razredu. Ne pozabite, da so javne funkcije uporabne zunaj razreda kjer koli. Za začetek javnega dela razreda uporabljamo ključno besedo »public:«. . Ker želimo v razpršilno tabelo dodati nove elemente, ustvarimo funkcijo z imenom »InsertHash« s ključem kot argumentom funkcije. V funkciji “insert” inicializiramo indeksno spremenljivko. Zgoščevalno funkcijo posredujemo indeksni spremenljivki. Po tem posredujte indeksno spremenljivko povezanemu seznamu tableHas[] z uporabo metode »push«, da vstavite element v tabelo.
Po tem zgradimo funkcijo »viewHashTab« za prikaz zgoščene tabele za ogled na novo vstavljenih podatkov. V tej funkciji uporabimo zanko 'za', ki išče vrednosti do konca zgoščene tabele. Zagotovite, da so vrednosti shranjene v istem indeksu, kot so razvite s funkcijo zgoščevanja. V zanki posredujemo vrednosti na njihovem ustreznem indeksu in tukaj zaključimo razred. V funkciji “main” vzamemo objekt razreda z imenom “hasTable”. S pomočjo tega predmeta razreda lahko dostopamo do metode vstavljanja s posredovanjem ključa v metodi. Ključ, ki smo ga posredovali v funkciji »main«, je izračunan v funkciji »insert«, ki vrne položaj indeksa v zgoščeni tabeli. Zgoščeno tabelo smo prikazali s klicem funkcije “view” s pomočjo predmeta “Class”.
Izhod te kode je priložen v naslednjem:
Kot lahko vidimo, je zgoščena tabela uspešno ustvarjena z uporabo povezanega seznama v C++. Odprto veriženje se uporablja za izogibanje koliziji istega indeksa.
Zaključek
Na koncu smo ugotovili, da je zgoščevalna tabela najpogostejša tehnika za shranjevanje in pridobivanje ključev s pari vrednosti za učinkovito obdelavo ogromnih količin podatkov. Možnosti kolizije v zgoščevalni tabeli so zelo visoke, kar uniči podatke in njihovo shranjevanje. To kolizijo lahko premagamo z različnimi tehnikami upravljanja zgoščene tabele. Z razvojem zgoščevalne tabele v C++ lahko razvijalci povečajo zmogljivost z uporabo najprimernejše tehnike za shranjevanje podatkov v zgoščevalno tabelo. Upamo, da vam bo ta članek pomagal razumeti zgoščevalno tabelo.