Çfarë janë tabelat hash (hash table)

[2003tu]

Po mundohem te mesoj hashtable... e pamundur per te kuptuar gje......E kote ,ngado qe ia filloj te mesoj,njelloj kuptoj....
Cfare te bej ?Ju lutem me keshilloni dicka?kam prezantim pas nje jave dhe akoma s kam kuptuar asgje???

ju falenderoj paraprakisht

[qoska]

Me e mira do te ishte te thoje konkretisht se deri ku ke arritur dhe me pas te te "ndriconim" me tutje .

Gjithsesi Wikipedia.org ka disa shpjegime per kete fakt si nga ana matematikore dhe ajo e fushes se programimit.

Per cfare ekzistojne hashtables?
Eshte mjaft e thjeshte ato jane nje menyre per te rritur shpejtesine ne kerkmie, te pakten kjo eshte nga fushat me te perdorura te tyre.

Si e rrisin ato shpejtesine?
Duke shfytezuar disa cilesi matematikore krijohen te ashtequajtura indekse, adresa indirekte, te te dhenave specifike.
Meqe merresh me programim duhet te kesh degjuar per vektoret(arrays) te dhenat e te cilave mund ti aksesoh ne kohe konstante nese ke indeksine e tyre. Pra sic shihet teknika e "hashing" s'este gje tjeter vecse reduktimi i problemit ne nje indeksim te te dhenave ne nje array, te pakten ne formen me te thjeshte te saj.
Sic e thame me siper kjo na garanton nje kohe konstante, por ne fillim na duhet indeksi. Kete indeks e gjeneron nje funksion i cili duhet te kete disa nga keto cilesi: a) ti gjeneroje keto indekse ne nje kohe te pranueshme
b) me te njejtat te dhena te gjeneroje gjithmone te njejtin indeks
c) te evitoje sa me shume perplasjen e indekseve, pasi eshte e mundur qe me te dhena te ndryshme te marrim te njejten vlere nga funksionet. E mete e cila, nese e pamshmangshme, mund te evitohet me nje funksion te dyte "hash" qe aplikohet mbi indeksin e gjeneruar, gjithmone me i thjeshte se funksioni i pare.
etj..

Tani ka shume teknika per hashing dhe per te ta bere me praktike algoritme si md5 jane teknika "hashing one-way" dmth kemi nje funksion qe duke u bazuar ne te dhenat ne hyrje gjeneron nje numer, "indeks", unik.

Per te te dhene dhe nje shembull te thjeshte "hash-i".
Supozojme se do te kemi stringje te dhena nga perdoruesi qe do te kerkohen me vone. Per te rritur kohen e kerkimit ne vendosim te perdorim nje teknike hash-i.
Ne krijojme nje vektor me permasa te perllogaritura me pare. Gjithashtu na duhet te percaktojme dhe funksionin per te gjeneruar indekset me i thjeshti qe mund te perdoret eshte shuma e vlerave numerike te karaktereve ne string.
Psh:
Nese perdoruesi fut stringun, "qoska" atehere funksioni do te kalkuloje vleren e indeskit thjeshte duke mbledhur vlerat numerike te seiciles shkronje pra,
vn() -> funksion qe jep vleren numerike te shkronjes.
vn(q) + vn(o) + vn(s) + vn(k) + vn(a) = vleren
-> po ja fus vlerave kot fare sa per ta konkretizuar me shume shembullin
=> 18 + 22 + 30 + 10 + 1 = 81
tani nese kjo vlere eshte me e madhe indeksi me i madh ne vektor atehere thjesht marrim mbetjen e pjestimit te kesaj vlere me indeksin me te madh te vektorit ose sic mund ta kesh hasur neper librat te ndryshem "modulus" qe zakonisht paraqitet me simbolin "%".

Tani po te duash mund te vazhdosh me tej pasi ky funksion i thjesht mund te gjeneroje shume perplasje, nuk do shume mend per ta kuptuar, dhe te percaktosh nje funksion te dyte i cili perdoret nese indeksi i gjeneruar nga i pari eshte i zene. Ky funksion i dyte mund te shtoje nje numer ose mund ta shumezoje me nje numer vleren fillestare.
Sic e sheh zgjidhjet jane te ndryshem.

Tani mbasi kemi gjetur indeksin ne vektor ketu ruajme nje adrese e cila na tregon ku ndodhet stringu perkates.


Sigurisht qe e gjithe teoria e teknikes se "hash-it" perqendrohet ne cilesite e ketyre funksioneve dhe qe mund te shkoje deri ne matematike shume te avancuar.



nese e gjithe ajo qe te kam shpjeguar me siper nuk te duket perseri e qarte atehere le ta shpjegojme me nje shembull nga jeta reale.


Sistemi postar perdor nje sherbim te quajtur P.O. BOX ku personit te cilit do ti dergosh nje pako i referohesh me ane te nje kodi dhe jo direkte, pra me nje menyre adresimi indirekte.
Kjo e ben me te shpejte sistemimin e kutive ose gjetjen me te shpejte te marresit pasi kemi thjesht nje krahasim kodi, "indeksim" te marresve, qe na con te marresi dhe jo ne fillim te percaktojme qytetin, pastaj lagjen etj.


Kjo eshte pak a shume baza e hashing si teknike se si pastaj ajo zgjerohet ne struktura te ndryshme te dhenash ne informatike eshte dicka me e avancuar pasi kerkon dhe njohjen e strukturave te te dhenave(data structures).

Me te mira.