Maišos funkcija
Šiame skyriuje aptarsime maišos funkciją, kuri padeda vykdyti atitinkamo duomenų elemento rakto maišos kodą duomenų struktūroje, kaip nurodyta toliau:
Int hashItem ( tarpt Raktas ){
grąžinti Raktas % stalo dydis ;
}
Masyvo indekso vykdymo procesas vadinamas maiša. Kartais to paties tipo kodas vykdomas, kad būtų sukurtas tas pats indeksas, naudojant tuos pačius raktus, vadinamus susidūrimais, kurie tvarkomi naudojant skirtingą grandininę (susietojo sąrašo kūrimą) ir įgyvendinant atviras adresavimo strategijas.
Maišos lentelės darbas C++ kalboje
Rodyklės į tikrąsias reikšmes saugomos maišos lentelėje. Jis naudoja raktą, kad surastų masyvo indeksą, kuriame raktų reikšmės turi būti saugomos norimoje masyvo vietoje. Mes paėmėme 10 dydžio maišos lentelę, kaip nurodyta toliau:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Atsitiktinai paimkime bet kokius duomenis pagal skirtingus raktus ir išsaugokime šiuos raktus maišos lentelėje, tiesiog apskaičiuodami indeksą. Taigi, naudojant maišos funkciją, duomenys saugomi pagal apskaičiuoto indekso raktus. Tarkime, kad imsime duomenis = {14,25,42,55,63,84}, o raktus =[ 15,9,5,25,66,75].
Apskaičiuokite šių duomenų indeksą naudodami maišos funkciją. Indekso reikšmė nurodyta taip:
| Raktas | penkiolika | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Apskaičiuokite indeksą | 15 %10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Duomenys | 14 | 25 | 42 | 55 | 63 | 84 |
Sukūrę masyvo indeksą, įdėkite duomenis prieš raktą į tikslią nurodyto masyvo indeksą, kaip aprašyta anksčiau.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Po to matome, kad susidūrimas įvyksta, jei du ar daugiau raktų turi tą patį maišos kodą, dėl kurio gaunamas tas pats masyvo elementų indeksas. Turime vieną išeitį, kad išvengtume susidūrimo: pasirinkti gerą maišos metodą ir įgyvendinti tikslias strategijas.
Dabar pateikdami tinkamus pavyzdžius aptarkime skirtingus įgyvendinimo būdus.
Pavyzdys: įtraukite duomenis į maišos lentelę naudodami atvirosios maišos techniką
Šiame pavyzdyje mes naudojame tokį diegimo metodą kaip Open Hashing, kad išvengtume susidūrimo maišos lentelėje. Atviroje maišos arba grandinės sistemoje sukuriame susietą sąrašą, kad sujungtume maišos lentelės reikšmes. Šio pavyzdžio kodo fragmentas pridedamas toliau, kuriame aprašoma atviros maišos technika:
#include#include
klasė HashTable {
privatus :
statinis konst tarpt stalo dydis = 10 ;
std :: sąrašą < tarpt > stalasTuri [ stalo dydis ] ;
tarpt hashFunc ( tarpt Raktas ) {
grąžinti Raktas % stalo dydis ;
}
viešas :
tuštuma Įdėti ( tarpt Raktas ) {
tarpt indeksas = hashFunc ( Raktas ) ;
stalasTuri [ indeksas ] . pastumti atgal ( Raktas ) ;
}
tuštuma peržiūros lentelė ( ) {
dėl ( tarpt i = 0 ; i < stalo dydis ; ++ i ) {
std :: cout << '[' << i << ']' ;
dėl ( automatinis tai = stalasTuri [ i ] . pradėti ( ) ; tai ! = stalasTuri [ i ] . galas ( ) ; ++ tai ) {
std :: cout << ' -> ' << * tai ;
}
std :: cout << std :: endl ;
}
}
} ;
tarpt pagrindinis ( ) {
HashTable hasTable ;
hasTable. Įdėti ( penkiolika ) ;
hasTable. Įdėti ( 33 ) ;
hasTable. Įdėti ( 23 ) ;
hasTable. Įdėti ( 65 ) ;
hasTable. Įdėti ( 3 ) ;
hasTable. peržiūros lentelė ( ) ;
grąžinti 0 ;
}
Tai labai įdomus pavyzdys: sudarome susietą sąrašą ir įterpiame duomenis į maišos lentelę. Visų pirma, programos pradžioje apibrėžiame bibliotekas. The < sąrašą > biblioteka naudojama susietam sąrašui įgyvendinti. Po to sukuriame klasę pavadinimu „HashTable“ ir sukuriame privatų klasės atributus kaip lentelės dydį ir lentelės masyvą, naudodami raktinį žodį „private:“. Atminkite, kad privatūs atributai negali būti naudojami už klasės ribų. Čia mes laikome lentelės dydį „10“. Naudodami tai inicijuojame maišos metodą ir apskaičiuojame maišos lentelės indeksą. Maišos funkcijoje perduodame maišos lentelės raktą ir dydį.
Sukuriame kelias reikalingas funkcijas ir jas viešiname klasėje. Atminkite, kad viešąsias funkcijas galima naudoti už klasės ribų bet kur. Mes naudojame raktinį žodį „public:“, kad pradėtume viešą klasės dalį . Kadangi norime į maišos lentelę įtraukti naujų elementų, sukuriame funkciją pavadinimu „InsertHash“ su raktu kaip funkcijos argumentu. Funkcijoje „įterpti“ inicijuojame indekso kintamąjį. Perduodame maišos funkciją indekso kintamajam. Po to perduokite indekso kintamąjį į susietą sąrašą tableHas[], naudodami „push“ metodą, kad įterptumėte elementą į lentelę.
Po to sukuriame funkciją „viewHashTab“, kad būtų rodoma maišos lentelė, kad būtų galima pamatyti naujai įterptus duomenis. Šioje funkcijoje paimame „for“ kilpą, kuri ieško verčių iki maišos lentelės pabaigos. Įsitikinkite, kad reikšmės yra saugomos tame pačiame indekse, kuris sukuriamas naudojant maišos funkciją. Ciklo metu perduodame reikšmes atitinkamame indekse ir baigiame klasę čia. „Pagrindinėje“ funkcijoje paimame klasės objektą, pavadintą „hasTable“. Šio klasės objekto pagalba galime pasiekti įterpimo metodą, perduodami metodo raktą. Raktas, kurį perdavėme „pagrindinėje“ funkcijoje, apskaičiuojamas naudojant funkciją „įterpti“, kuri grąžina indekso poziciją maišos lentelėje. Maišos lentelę parodėme iškviesdami funkciją „View“ naudodami objektą „Klasė“.
Šio kodo išvestis pridedama taip:
Kaip matome, maišos lentelė sėkmingai sukurta naudojant susietą sąrašą C++. Atvira grandinė naudojama siekiant išvengti to paties indekso susidūrimo.
Išvada
Galiausiai padarėme išvadą, kad maišos lentelė yra labiausiai paplitęs būdas saugoti ir gauti raktus su verčių poromis, kad būtų galima efektyviai tvarkyti didžiulius duomenų kiekius. Susidūrimo tikimybė maišos lentelėje yra labai didelė, sunaikinant duomenis ir jų saugojimą. Šį susidūrimą galime įveikti naudodami skirtingus maišos lentelės valdymo būdus. Kurdami maišos lentelę C++, kūrėjai gali padidinti našumą naudodami tinkamiausią techniką duomenų saugojimui maišos lentelėje. Tikimės, kad šis straipsnis padės suprasti maišos lentelę.