Jaucējfunkcija
Šajā sadaļā mēs runāsim par jaucējfunkciju, kas palīdz izpildīt datu struktūras datu elementa saistītās atslēgas jaucējkodu, kā minēts tālāk:
Int hashItem ( starpt taustiņu ){
atgriezties taustiņu % galda izmērs ;
}
Masīva indeksa izpildes procesu sauc par jaukšanu. Dažreiz viena veida kods tiek izpildīts, lai ģenerētu vienu un to pašu indeksu, izmantojot tās pašas atslēgas, ko sauc par sadursmēm, kas tiek apstrādātas, izmantojot dažādu ķēdes (saistītu sarakstu izveide) un atvērto adresēšanas stratēģiju ieviešanu.
Hash tabulas darbība programmā C++
Norādes uz reālajām vērtībām tiek saglabātas hash tabulā. Tas izmanto atslēgu, lai meklētu masīva indeksu, kurā vērtības pret atslēgām ir jāsaglabā vēlamajā masīva vietā. Mēs paņēmām jaukšanas tabulu ar izmēru 10, kā minēts tālāk:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Ļaujiet mums nejauši ņemt datus pret dažādām atslēgām un saglabāt šīs atslēgas jaucēj tabulā, vienkārši aprēķinot indeksu. Tātad dati tiek glabāti pret taustiņiem aprēķinātajā indeksā ar jaucējfunkcijas palīdzību. Pieņemsim, ka mēs ņemam datus = {14,25,42,55,63,84} un atslēgas =[ 15,9,5,25,66,75].
Aprēķiniet šo datu indeksu, izmantojot jaucējfunkciju. Indeksa vērtība ir minēta šādi:
| Atslēga | piecpadsmit | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Aprēķināt indeksu | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Dati | 14 | 25 | 42 | 55 | 63 | 84 |
Pēc masīva indeksa izveides ievietojiet datus pret atslēgu konkrēta masīva precīzā indeksā, kā aprakstīts iepriekš.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Pēc tam mēs varam redzēt, ka sadursme notiek, ja divām vai vairākām atslēgām ir vienāds jaucējkods, kā rezultātā tiek iegūts vienāds masīva elementu indekss. Mums ir viens risinājums, lai izvairītos no sadursmes: labas jaukšanas metodes izvēle un precīzas stratēģijas ieviešana.
Tagad apspriedīsim dažādas ieviešanas metodes, izmantojot atbilstošus piemērus.
Piemērs: pievienojiet datus jaukšanas tabulā, izmantojot atvērto jaukšanas paņēmienu
Šajā piemērā mēs izmantojam tādu ieviešanas paņēmienu kā Open Hashing, lai izvairītos no sadursmes jaukšanas tabulā. Atvērtā jaukšanā vai ķēdē mēs izveidojam saistīto sarakstu, lai sasaistītu jaukšanas tabulas vērtības. Šī piemēra koda fragments ir pievienots tālāk, kas apraksta atvērtās jaukšanas paņēmienu:
#include#include
klasē HashTable {
Privāts :
statisks konst starpt galda izmērs = 10 ;
std :: sarakstu < starpt > galdsIr [ galda izmērs ] ;
starpt hashFunc ( starpt taustiņu ) {
atgriezties taustiņu % galda izmērs ;
}
publiski :
nederīgs ievietot ( starpt taustiņu ) {
starpt rādītājs = hashFunc ( taustiņu ) ;
galdsIr [ rādītājs ] . atgrūst ( taustiņu ) ;
}
nederīgs skata tabula ( ) {
priekš ( starpt i = 0 ; i < galda izmērs ; ++ i ) {
std :: cout << '[' << i << ']' ;
priekš ( auto to = galdsIr [ i ] . sākt ( ) ; to ! = galdsIr [ i ] . beigas ( ) ; ++ to ) {
std :: cout << '->' << * to ;
}
std :: cout << std :: endl ;
}
}
} ;
starpt galvenais ( ) {
HashTable hasTable ;
hasTable. ievietot ( piecpadsmit ) ;
hasTable. ievietot ( 33 ) ;
hasTable. ievietot ( 23 ) ;
hasTable. ievietot ( 65 ) ;
hasTable. ievietot ( 3 ) ;
hasTable. skata tabula ( ) ;
atgriezties 0 ;
}
Šis ir ļoti interesants piemērs: mēs izveidojam saistīto sarakstu un ievietojam datus hash tabulā. Pirmkārt, mēs definējam bibliotēkas programmas sākumā. The < sarakstu > bibliotēka tiek izmantota saistītā saraksta ieviešanai. Pēc tam mēs izveidojam klasi ar nosaukumu “HashTable” un izveidojam klases privātos atribūtus kā tabulas izmēru un tabulu masīvu, izmantojot atslēgvārdu “private:”. Atcerieties, ka privātie atribūti nav izmantojami ārpus klases. Šeit mēs ņemam tabulas izmēru kā “10”. Izmantojot to, mēs inicializējam hash metodi un aprēķinām jaukšanas tabulas indeksu. Jaucējfunkcijā mēs nododam hash tabulas atslēgu un izmēru.
Mēs izveidojam dažas nepieciešamās funkcijas un padarām šīs funkcijas publiskas klasē. Atcerieties, ka publiskās funkcijas var izmantot ārpus nodarbības jebkur. Mēs izmantojam atslēgvārdu “public:”, lai sāktu klases publisko daļu . Tā kā mēs vēlamies pievienot jaunus elementus hash tabulai, mēs izveidojam funkciju ar nosaukumu “InsertHash” ar atslēgu kā funkcijas argumentu. Funkcijā 'ievietot' mēs inicializējam indeksa mainīgo. Mēs nododam jaucējfunkciju indeksa mainīgajam. Pēc tam nododiet indeksa mainīgo saistītajam sarakstam tableHas[], izmantojot “push” metodi, lai tabulā ievietotu elementu.
Pēc tam mēs izveidojam funkciju “viewHashTab”, lai parādītu hash tabulu, lai redzētu tikko ievietotos datus. Šajā funkcijā mēs izmantojam cilpu “for”, kas meklē vērtības līdz jaucēj tabulas beigām. Nodrošiniet, lai vērtības tiktu saglabātas tajā pašā indeksā, kas tiek izstrādāts, izmantojot jaucējfunkciju. Ciklā mēs nododam vērtības to attiecīgajā indeksā un beidzam klasi šeit. Funkcijā “galvenā” mēs ņemam klases objektu ar nosaukumu “hasTable”. Ar šī klases objekta palīdzību mēs varam piekļūt ievietošanas metodei, nododot atslēgu metodē. Atslēga, kuru mēs nodevām funkcijā “galvenā”, tiek aprēķināta funkcijā “insert”, kas atgriež indeksa pozīciju hash tabulā. Mēs parādījām hash tabulu, izsaucot funkciju “View” ar objekta “Class” palīdzību.
Šī koda izvade ir pievienota šādi:
Kā redzam, hash tabula ir veiksmīgi izveidota, izmantojot saistīto sarakstu programmā C++. Atvērtā ķēde tiek izmantota, lai izvairītos no viena un tā paša indeksa sadursmes.
Secinājums
Galu galā mēs secinājām, ka hash tabula ir visizplatītākā metode, lai saglabātu un iegūtu atslēgas ar vērtību pāriem, lai efektīvi apstrādātu milzīgus datu apjomus. Sadursmes iespēja hash tabulā ir ļoti augsta, iznīcinot datus un to glabāšanu. Mēs varam pārvarēt šo sadursmi, izmantojot dažādas hash tabulas pārvaldības metodes. Izstrādājot jaucējtabulu C++ valodā, izstrādātāji var palielināt veiktspēju, izmantojot vislabāk piemēroto paņēmienu datu glabāšanai hash tabulā. Mēs ceram, ka šis raksts ir noderīgs, lai izprastu hash tabulu.