Pag-andar ng Hash
Sa seksyong ito, tatalakayin natin ang tungkol sa hash function na tumutulong upang maisagawa ang hash code ng kaugnay na key ng data item sa data structure gaya ng nabanggit sa sumusunod:
Int hashItem ( int susi ){
bumalik susi % laki ng mesa ;
}
Ang proseso ng pagpapatupad ng index ng isang array ay tinatawag na hashing. Minsan, ang parehong uri ng code ay isinasagawa upang makabuo ng parehong index gamit ang parehong mga key na tinatawag na collisions na pinangangasiwaan sa pamamagitan ng iba't ibang chaining (paggawa ng naka-link na listahan) at bukas na pagpapatupad ng mga diskarte sa pagtugon.
Paggawa ng Hash Table sa C++
Ang mga pointer sa mga tunay na halaga ay pinananatili sa hash table. Gumagamit ito ng isang susi upang hanapin ang index ng isang array kung saan ang mga halaga laban sa mga key ay kailangang maimbak sa nais na lokasyon sa isang array. Kinuha namin ang hash table na may sukat na 10 tulad ng nabanggit sa mga sumusunod:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Hayaan kaming random na kumuha ng anumang data laban sa iba't ibang mga key at iimbak ang mga key na ito sa isang hash table sa pamamagitan lamang ng pagkalkula ng index. Kaya, ang data ay naka-imbak laban sa mga susi sa kinakalkula na index sa tulong ng isang hash function. Ipagpalagay na kukuha tayo ng data = {14,25,42,55,63,84} at mga key =[ 15,9,5,25,66,75 ].
Kalkulahin ang index ng mga data na ito gamit ang hash function. Ang halaga ng index ay binanggit sa mga sumusunod:
| Susi | labinlima | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Kalkulahin ang Index | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Data | 14 | 25 | 42 | 55 | 63 | 84 |
Pagkatapos gumawa ng index ng isang array, ilagay ang data laban sa key sa eksaktong index ng isang naibigay na array gaya ng inilarawan dati.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Pagkatapos nito, makikita natin na ang isang banggaan ay nangyayari kung ang dalawa o higit pang mga key ay may parehong hash code na nagreresulta sa parehong index ng mga elemento sa array. Mayroon kaming isang solusyon upang maiwasan ang mga pagkakataon ng banggaan: pagpili ng isang mahusay na paraan ng hash at pagpapatupad ng mga tumpak na diskarte.
Ngayon, talakayin natin ang iba't ibang mga diskarte sa pagpapatupad sa tulong ng mga wastong halimbawa.
Halimbawa: Magdagdag ng Data sa Hash Table Gamit ang Open Hashing Technique
Sa halimbawang ito, kumuha kami ng diskarte sa pagpapatupad tulad ng Open Hashing para maiwasan ang banggaan sa hash table. Sa bukas na hashing o chaining, gumagawa kami ng naka-link na listahan para i-chain ang mga value ng hash table. Ang code snippet ng halimbawang ito ay naka-attach sa sumusunod na naglalarawan sa open hashing technique:
#include#include
klase HashTable {
pribado :
static const int laki ng mesa = 10 ;
std :: listahan < int > tableHas [ laki ng mesa ] ;
int hashFunc ( int susi ) {
bumalik susi % laki ng mesa ;
}
pampubliko :
walang bisa ipasok ( int susi ) {
int index = hashFunc ( susi ) ;
tableHas [ index ] . push_back ( susi ) ;
}
walang bisa viewTable ( ) {
para sa ( int i = 0 ; i < laki ng mesa ; ++ i ) {
std :: cout << '[' << i << ']' ;
para sa ( sasakyan ito = tableHas [ i ] . magsimula ( ) ; ito ! = tableHas [ i ] . wakas ( ) ; ++ ito ) {
std :: cout << ' -> ' << * ito ;
}
std :: cout << std :: endl ;
}
}
} ;
int pangunahing ( ) {
HashTable hasTable ;
hasTable. ipasok ( labinlima ) ;
hasTable. ipasok ( 33 ) ;
hasTable. ipasok ( 23 ) ;
hasTable. ipasok ( 65 ) ;
hasTable. ipasok ( 3 ) ;
hasTable. viewTable ( ) ;
bumalik 0 ;
}
Ito ay isang napaka-kagiliw-giliw na halimbawa: bumuo kami ng isang naka-link na listahan at ipasok ang data sa hash table. Una sa lahat, tinutukoy namin ang mga aklatan sa simula ng programa. Ang < listahan > ginagamit ang library para sa pagpapatupad ng naka-link na listahan. Pagkatapos nito, bumuo kami ng klase na pinangalanang 'HashTable' at gumawa ng mga katangian ng klase na pribado bilang laki ng talahanayan at hanay ng talahanayan gamit ang keyword na 'pribado:'. Tandaan na ang mga pribadong katangian ay hindi magagamit sa labas ng klase. Dito, kinukuha namin ang laki ng talahanayan bilang '10'. Sinisimulan namin ang paraan ng hash gamit ito at kinakalkula ang index ng hash table. Sa hash function, ipinapasa namin ang susi at laki ng hash table.
Bumubuo kami ng ilang kinakailangang function at ginagawang pampubliko ang mga function na ito sa klase. Tandaan na ang mga pampublikong function ay magagamit sa labas ng klase kahit saan. Ginagamit namin ang keyword na 'pampubliko:' upang simulan ang pampublikong bahagi ng klase . Dahil gusto naming magdagdag ng mga bagong elemento sa hash table, gumawa kami ng function na pinangalanang 'InsertHash' na may key bilang argumento ng function. Sa function na 'insert', sinisimulan namin ang index variable. Ipinapasa namin ang hash function sa index variable. Pagkatapos nito, ipasa ang index variable sa naka-link na listahan na tableHas[]gamit ang 'push' na paraan upang magpasok ng isang elemento sa talahanayan.
Pagkatapos nito, bumuo kami ng function na 'viewHashTab' upang ipakita ang hash table upang makita ang bagong ipinasok na data. Sa function na ito, kumuha kami ng 'para sa' loop na naghahanap ng mga halaga hanggang sa dulo ng hash table. Tiyakin na ang mga halaga ay naka-imbak sa parehong index na binuo gamit ang isang hash function. Sa loop, ipinapasa namin ang mga halaga sa kani-kanilang index at tinatapos ang klase dito. Sa 'pangunahing' function, kinukuha namin ang object ng isang klase na pinangalanang 'hasTable'. Sa tulong ng object ng klase na ito, maa-access natin ang paraan ng pagpasok sa pamamagitan ng pagpasa ng susi sa pamamaraan. Ang susi na ipinasa namin sa 'pangunahing' function ay nakalkula sa 'insert' na function na nagbabalik ng posisyon ng index sa hash table. Ipinakita namin ang hash table sa pamamagitan ng pagtawag sa function na 'view' sa tulong ng isang object na 'Class'.
Ang output ng code na ito ay nakalakip sa sumusunod:
Tulad ng nakikita natin, matagumpay na nalikha ang hash table gamit ang naka-link na listahan sa C++. Ang open chaining ay ginagamit upang maiwasan ang banggaan ng parehong index.
Konklusyon
Sa huli, napagpasyahan namin na ang hash table ay ang pinaka-umuusbong na pamamaraan upang mag-imbak at makuha ang mga susi na may mga pares ng halaga upang pangasiwaan ang malaking halaga ng data nang mahusay. Ang mga pagkakataon ng banggaan ay napakataas sa hash table, sinisira ang data at imbakan nito. Malalampasan natin ang banggaan na ito gamit ang iba't ibang pamamaraan ng pamamahala ng hash table. Sa pamamagitan ng pagbuo ng hash table sa C++, maaaring pataasin ng mga developer ang pagganap gamit ang pinakamahusay na angkop na pamamaraan upang iimbak ang data sa hash table. Umaasa kami na ang artikulong ito ay kapaki-pakinabang para sa iyong pag-unawa sa hash table.