[Muzika] DOUG Lloyd: Deri tani ju dinÃ« shumÃ« rreth vargjeve, dhe ju e dini shumÃ« pÃ«r listat e lidhura. Dhe ne kemi diskutuar pro dhe kundra, ne kemi diskutuar se lidhur listat mund tÃ« merrni mÃ« tÃ« mÃ«dha dhe tÃ« vogla, por ata kÃ«rkojnÃ« mÃ« shumÃ« madhÃ«sinÃ«. Vargjeve janÃ« shumÃ« mÃ« tÃ« hapur pÃ«r tÃ« pÃ«rdorin, por ata janÃ« tÃ« kufizuar nÃ« sa mÃ« shumÃ« si ne kemi pÃ«r tÃ« vendosur madhÃ«sinÃ« e array nÃ« fillim dhe pastaj ne jemi tÃ« mbÃ«rthyer me tÃ«. 

Por kjo Ã«shtÃ«, ne kemi shumÃ« e shumÃ« shteruar tÃ« gjitha temat tona nÃ« lidhje me listat e lidhura dhe vargjeve. Apo kemi? Ndoshta ne mund tÃ« bÃ«jmÃ« diÃ§ka edhe mÃ« shumÃ« krijues. Dhe kjo lloj i jep hua ideja e njÃ« tabelÃ« hash. 

Pra, nÃ« njÃ« tabelÃ« hash ne jemi duke shkuar pÃ«r tÃ« provoni tÃ« kombinuar njÃ« grup me njÃ« listÃ« tÃ« lidhura. Ne jemi duke shkuar pÃ«r tÃ« marrÃ« avantazhet e array, si qasje tÃ« rastit, qenÃ« nÃ« gjendje tÃ« thjesht shkoni nÃ« grup element 4 ose grup element 8 pa pasur nevojÃ« pÃ«r tÃ« iterate nÃ«pÃ«r. Kjo Ã«shtÃ« shumÃ« e shpejtÃ«, e drejtÃ«? 

Por ne gjithashtu duam tÃ« kemi tÃ« dhÃ«nat tona Struktura tÃ« jetÃ« nÃ« gjendje tÃ« rritet dhe tkurret. Ne nuk kemi nevojÃ«, ne nuk e bÃ«jmÃ« duan tÃ« jenÃ« tÃ« kufizuara. Dhe ne duam tÃ« jetÃ« nÃ« gjendje tÃ« shtoni dhe hiqni gjÃ«rat shumÃ« lehtÃ«, e cila nÃ« qoftÃ« se ju kujtohet, Ã«shtÃ« shumÃ« komplekse me njÃ« grup. Dhe ne mund ta quajmÃ« kÃ«tÃ« gjÃ« e re njÃ« tabelÃ« hash. 

Dhe nÃ« qoftÃ« se zbatohet si duhet, ne jemi lloj i marrjes avantazhet e tÃ« dy tÃ« dhÃ«nave Strukturat e keni parÃ« tashmÃ«, vargjeve dhe listat lidhura. Futje mund tÃ« fillojnÃ« tÃ« priren drejt theta e 1. Theta ne nuk kemi diskutuar me tÃ« vÃ«rtetÃ«, por theta Ã«shtÃ« vetÃ«m rasti mesatare, Ã§farÃ« Ã«shtÃ« nÃ« tÃ« vÃ«rtetÃ« do tÃ« ndodhÃ«. Ju nuk jeni gjithmonÃ« do tÃ« kanÃ« skenarin mÃ« tÃ« keq, dhe ju nuk jeni gjithmonÃ« do tÃ« ketÃ« skenari mÃ« i mirÃ«, kÃ«shtu qÃ« Ã§farÃ« Ã«shtÃ« skenari mesatar? 

E pra njÃ« futje mesatare nÃ« njÃ« tabelÃ« hash mund tÃ« filloni pÃ«r tÃ« marrÃ« afÃ«r nÃ« kohÃ« tÃ« vazhdueshme. Dhe fshirje mund tÃ« merrni mbyllur nÃ« kohÃ« tÃ« vazhdueshme. Dhe lookup mund tÃ« merrni mbyllur nÃ« kohÃ« tÃ« vazhdueshme. That's-- ne nuk kemi njÃ« tÃ« dhÃ«nave Struktura ende se mund ta bÃ«jÃ« kÃ«tÃ«, dhe kÃ«shtu qÃ« kjo tashmÃ« tingÃ«llon si njÃ« gjÃ« mjaft e madhe. Ne kemi zbutet vÃ«rtetÃ« disavantazhet e secilit mÃ« vete. 

PÃ«r tÃ« marrÃ« kÃ«tÃ« performancÃ« pÃ«rmirÃ«suar edhe pse, ne duhet tÃ« mendonin se si ne shtoni tÃ« dhÃ«nat nÃ« strukturÃ«n. NÃ« mÃ«nyrÃ« tÃ« veÃ§antÃ« ne dÃ«shironi vetÃ« tÃ« dhÃ«nat pÃ«r tÃ« na tregoni ku ajo duhet tÃ« shkojÃ« nÃ« strukturÃ«n. Dhe nÃ«se atÃ«herÃ« ne kemi nevojÃ« pÃ«r tÃ« parÃ« nÃ«se Ã«shtÃ« nÃ« struktura, nÃ« qoftÃ« se ne kemi nevojÃ« pÃ«r tÃ« gjetur atÃ«, ne duam tÃ« shikojmÃ« nÃ« tÃ« dhÃ«nat e pÃ«rsÃ«ri dhe tÃ« jenÃ« nÃ« gjendje qÃ« nÃ« mÃ«nyrÃ« efektive, duke pÃ«rdorur tÃ« dhÃ«nat, rastÃ«sisht tÃ« hyrÃ« nÃ« tÃ«. VetÃ«m duke shikuar nÃ« tÃ« dhÃ«na ne duhet tÃ« kemi njÃ« ide e ku pikÃ«risht ne jemi do tÃ« gjeni atÃ« nÃ« tabelÃ« hash. 

Tani dobÃ«sitÃ« e njÃ« hash tabelÃ« Ã«shtÃ« se ata janÃ« me tÃ« vÃ«rtetÃ« shumÃ« e keqe nÃ« urdhÃ«rimin ose klasifikim tÃ« dhÃ«nave. Dhe nÃ« fakt, nÃ«se ju filloni tÃ« pÃ«rdorin ato pÃ«r tÃ« porositur ose lloj tÃ« dhÃ«na ju humbni tÃ« gjitha tÃ« PÃ«rparÃ«sitÃ« ju mÃ« parÃ« kishte nÃ« aspektin e futje dhe fshirje. Koha bÃ«het mÃ« afÃ«r theta e n, dhe ne kemi nÃ« thelb ngecur nÃ« njÃ« listÃ« tÃ« lidhura. Dhe kÃ«shtu qÃ« ne vetÃ«m dÃ«shironi tÃ« pÃ«rdorni hash tavolina, nÃ«se ne nuk e kujdesit nÃ« lidhje me nÃ«se tÃ« dhÃ«nat Ã«shtÃ« e renditura. PÃ«r kontekstin nÃ« tÃ« cilin ju do tÃ« pÃ«rdorin ato nÃ« CS50 ju ndoshta nuk e kujdesit se tÃ« dhÃ«nat Ã«shtÃ« e renditura. 

Pra, njÃ« tabelÃ« hash Ã«shtÃ« njÃ« kombinim nga dy pjesÃ« tÃ« dallueshme me tÃ« cilat ne jemi tÃ« njohur. I parÃ« Ã«shtÃ« njÃ« funksion, e cila ne zakonisht e quajmÃ« njÃ« funksion hash. Dhe kjo funksion hash do tÃ« kthehen disa numÃ«r i plotÃ« jo-negativ, i cili ne zakonisht e quajmÃ« njÃ« hashcode, OK? Pjesa e dytÃ« Ã«shtÃ« njÃ« grup, i cili Ã«shtÃ« tÃ« aftÃ« pÃ«r magazinimin e tÃ« dhÃ«nave tÃ« tipit ne doni tÃ« vendosni nÃ« strukturÃ«n e tÃ« dhÃ«nave. Ne do tÃ« mbajÃ« jashtÃ« nÃ« anÃ«n lidhur element listÃ« pÃ«r tani dhe tÃ« fillojÃ« vetÃ«m me bazat e njÃ« hash tryezÃ« pÃ«r tÃ« marrÃ« kokÃ«n tuaj rreth tij, dhe pastaj ne do tÃ« ndoshta goditje mendjen tuaj pak kur ne kombinohen vargjeve dhe listat lidhur sÃ« bashku. 

Ideja themelore pse Ã«shtÃ« qÃ« ne tÃ« marrÃ« disa tÃ« dhÃ«na. Ne tÃ« drejtuar se tÃ« dhÃ«nat pÃ«rmes funksioni hash. Dhe kÃ«shtu tÃ« dhÃ«nat janÃ« pÃ«rpunuar dhe ajo pÃ«shtyn nga njÃ« numÃ«r, nÃ« rregull? Dhe pastaj me atÃ« numÃ«r ne vetÃ«m tÃ« ruajtur tÃ« dhÃ«nat ne duam tÃ« ruajtur nÃ« array nÃ« atÃ« vend. KÃ«shtu pÃ«r shembull, ne kemi ndoshta kjo tabelÃ« hash e strings. Ajo ka 10 elemente nÃ« tÃ«, kÃ«shtu qÃ« ne mund tÃ« pÃ«rshtatet 10 vargjet nÃ« tÃ«. 

Le tÃ« themi se duam tÃ« hash Gjoni. Pra, Gjoni si tÃ« dhÃ«na ne duam tÃ« futur nÃ« kÃ«tÃ« tabelÃ« hash diku. Ku nuk kemi vÃ«nÃ« atÃ«? E pra nÃ« mÃ«nyrÃ« tipike me njÃ« array deri tani ne ndoshta do tÃ« vÃ«nÃ« atÃ« nÃ« vend array 0. Por tani ne kemi kÃ«tÃ« funksion tÃ« ri hash. 

Dhe le tÃ« themi se kemi drejtuar Gjoni pÃ«rmes kÃ«tij funksioni hash dhe kjo Ã«shtÃ« pÃ«shtyn nga 4. E pra kjo Ã«shtÃ« ajo ku ne jemi do tÃ« duan tÃ« vÃ«nÃ« Gjoni. Ne duam tÃ« vÃ«nÃ« Gjonin nÃ« vend array 4, sepse nÃ« qoftÃ« se ne tÃ« hash Gjoni again-- le tÃ« themi mÃ« vonÃ« ne doni tÃ« kÃ«rkoni dhe tÃ« shohin nÃ«se John ekziston nÃ« kÃ«tÃ« hash table-- tÃ« gjithÃ« ne duhet tÃ« bÃ«jmÃ« Ã«shtÃ« drejtuar atÃ« nÃ«pÃ«rmjet tÃ« njÃ«jtin hash funksion, tÃ« marrÃ« numrin 4 nga, dhe tÃ« jetÃ« nÃ« gjendje pÃ«r tÃ« gjetur Gjoni menjÃ«herÃ« nÃ« strukturÃ«n e tÃ« dhÃ«nave tonÃ«. Kjo Ã«shtÃ« shumÃ« e mirÃ«. 

Le tÃ« themi se tani bÃ«jmÃ« kÃ«tÃ« pÃ«rsÃ«ri, ne duam tÃ« hash Palin. Ne duam tÃ« shtoni Palin nÃ« kÃ«tÃ« tabelÃ« hash. Le tÃ« themi se kÃ«tÃ« herÃ« kemi drejtuar Pali pÃ«rmes funksionit hash, hashcode qÃ« Ã«shtÃ« krijuar Ã«shtÃ« 6. E pra tani ne mund tÃ« vÃ«nÃ« Palin nÃ« array vend tÃ« 6. Dhe nÃ« qoftÃ« se ne duhet tÃ« shohim lart nÃ«se Pali Ã«shtÃ« nÃ« kÃ«tÃ« tabelÃ« hash, tÃ« gjithÃ« ne duhet tÃ« bÃ«ni Ã«shtÃ« tÃ« drejtuar Paul pÃ«rmes funksionit hash pÃ«rsÃ«ri dhe ne jemi duke shkuar pÃ«r tÃ« marrÃ« 6 jashtÃ« pÃ«rsÃ«ri. 

Dhe atÃ«herÃ« ne vetÃ«m shikoni nÃ« array vend tÃ« 6. Paul atje? NÃ«se Ã«shtÃ« kÃ«shtu, ai Ã«shtÃ« nÃ« tabelÃ«n hash. Paul nuk ka? Ai nuk Ã«shtÃ« nÃ« tabelÃ«n hash. ÃshtÃ« shumÃ« i thjeshtÃ«. 

Tani si mund tÃ« pÃ«rcaktojÃ« njÃ« funksion hash? E pra nuk ka tÃ« vÃ«rtetÃ« nuk ka kufi tÃ« Numri i funksioneve tÃ« mundshme hash. NÃ« fakt ka njÃ« numÃ«r tÃ« vÃ«rtetÃ«, ato me tÃ« vÃ«rtetÃ« tÃ« mira nÃ« internet. Ka njÃ« numÃ«r tÃ« vÃ«rtetÃ«, ato me tÃ« vÃ«rtetÃ« tÃ« kÃ«qija nÃ« internet. ÃshtÃ« gjithashtu shumÃ« e lehtÃ« pÃ«r tÃ« shkruar njÃ« tÃ« keqe. 

Pra, Ã§farÃ« e bÃ«n njÃ« tÃ« mirÃ« funksion hash, e drejtÃ«? Edhe njÃ« funksion tÃ« mirÃ« hash duhet pÃ«rdorin vetÃ«m tÃ« dhÃ«nat qÃ« janÃ« sheshuar, dhe tÃ« gjitha tÃ« dhÃ«nave tÃ« sheshuar. Pra, ne nuk duam tÃ« pÃ«rdorni anything-- ne nuk pÃ«rfshijnÃ« ndonjÃ« gjÃ« tjetÃ«r pÃ«rveÃ§ tÃ« dhÃ«nave. Dhe ne duam tÃ« pÃ«rdorim tÃ« gjitha tÃ« dhÃ«nave. Ne nuk duam qÃ« tÃ« pÃ«rdorni vetÃ«m njÃ« copÃ« e saj, ne duam tÃ« pÃ«rdorim tÃ« gjithÃ« atÃ«. NjÃ« funksion hash duhet tÃ« jetÃ« gjithashtu determinist. Cfare do te thote ajo? E pra kjo do tÃ« thotÃ« se Ã§do herÃ« kemi kalojÃ« tÃ« njÃ«jtÃ«n pjesÃ« e saktÃ« e tÃ« dhÃ«nave nÃ« funksion hash ne gjithmonÃ« merrni tÃ« njÃ«jtÃ«n hashcode jashtÃ«. NÃ«se unÃ« kaloj Gjonin nÃ« tÃ« funksion hash unÃ« dal 4. UnÃ« duhet tÃ« jetÃ« nÃ« gjendje tÃ« bÃ«jÃ« atÃ« 10,000 herÃ« dhe unÃ« gjithmonÃ« do tÃ« merrni 4. KÃ«shtu qÃ« nuk ka numra tÃ« rastit nÃ« mÃ«nyrÃ« efektive mund tÃ« pÃ«rfshihen nÃ« hash tonÃ« tables-- nÃ« funksionet tona tÃ« hash. 

NjÃ« funksion hash duhet gjithashtu uniforme shpÃ«rndarjen e tÃ« dhÃ«nave. NÃ« qoftÃ« se Ã§do herÃ« qÃ« tÃ« drejtuar tÃ« dhÃ«nat pÃ«rmes funksion hash ju merrni hashcode 0, kjo ndoshta nuk Ã«shtÃ« aq e madhe, apo jo? Ju ndoshta dÃ«shironi tÃ« mÃ«dha njÃ« varg i kodeve hash. Edhe gjÃ«rat mund tÃ« pÃ«rhapet nga tÃ« gjithÃ« nÃ« tryezÃ«. Dhe gjithashtu kjo do tÃ« jetÃ« i madh nÃ« qoftÃ« se me tÃ« vÃ«rtetÃ« tÃ« dhÃ«na tÃ« ngjashme, si Gjoni dhe Jonathanin, ndoshta janÃ« shtrirÃ« pÃ«r tÃ« peshojnÃ« vende tÃ« ndryshme nÃ« tabelÃ« hash. Kjo do tÃ« jetÃ« njÃ« avantazh i bukur. 

Ja njÃ« shembull i njÃ« funksion hash. Kam shkruar kÃ«tÃ« njÃ« tÃ« tillÃ« mÃ« herÃ«t. Kjo nuk Ã«shtÃ« njÃ« veÃ§anÃ«risht i Funksioni i mirÃ« hash pÃ«r arsye qÃ« nuk tÃ« vÃ«rtetÃ« mbajnÃ« shkon nÃ« tÃ« drejtÃ« tani. Por ju e shihni se Ã§farÃ« po ndodh kÃ«tu? Duket sikur ne jemi duke deklaruar njÃ« ndryshore quhet shuma e vendosur atÃ« tÃ« barabartÃ« me 0. Dhe pastaj me sa duket unÃ« jam duke bÃ«rÃ« diÃ§ka pÃ«r aq kohÃ« sa strstr [j] nuk Ã«shtÃ« i barabartÃ« pÃ«r backslash 0. ÃfarÃ« po bÃ«j kÃ«tu? 

Kjo Ã«shtÃ« nÃ« thelb vetÃ«m njÃ« tjetÃ«r MÃ«nyra e zbatimit tÃ« [? strl?] dhe zbulimin kur ju keni arritur nÃ« fund tÃ« vargut. KÃ«shtu qÃ« unÃ« nuk duhet tÃ« vÃ«rtetÃ« tÃ« tÃ« llogaritur gjatÃ«sinÃ« e vargut, UnÃ« jam vetÃ«m duke pÃ«rdorur, kur unÃ« goditi backslash 0 karakter di UnÃ« e kam arritur nÃ« fund tÃ« vargut. Dhe atÃ«herÃ« unÃ« jam duke shkuar pÃ«r tÃ« mbajtur iterating nÃ«pÃ«r atÃ« varg, duke shtuar strstr [J] pÃ«r tÃ« pÃ«rmbledhur, dhe pastaj nÃ« fundi i ditÃ«s do tÃ« kthehen shuma mod HASH_MAX. 

NÃ« thelb tÃ« gjithÃ« kÃ«saj hash Funksioni Ã«shtÃ« duke bÃ«rÃ« Ã«shtÃ« duke shtuar deri tÃ« gjithÃ« nga vlerat e ASCII string im, dhe atÃ«herÃ« Ã«shtÃ« kthyer disa hashcode modded nga HASH_MAX. Kjo Ã«shtÃ« ndoshta e madhÃ«sisÃ« e array tim, e drejtÃ«? UnÃ« nuk dua tÃ« jetÃ« marrÃ« hash Kodet nÃ«se array ime Ã«shtÃ« e madhÃ«sisÃ« 10, UnÃ« nuk dua tÃ« jetÃ« marrÃ« Kodet jashtÃ« hash 11, 12, 13, unÃ« nuk mund tÃ« vÃ«nÃ« gjÃ«rat nÃ« kÃ«to vende e vektorit, qÃ« do tÃ« jetÃ« i paligjshÃ«m. UnÃ« do tÃ« vuajnÃ« njÃ« defekt segmentimit. 

Tani kÃ«tu Ã«shtÃ« njÃ« tjetÃ«r i shpejtÃ« mÃ«njanÃ«. NÃ« pÃ«rgjithÃ«si ju jeni ndoshta nuk do tÃ« dua tÃ« shkruaj funksionet e veta hash tuaja. Kjo Ã«shtÃ« nÃ« fakt njÃ« grimÃ« njÃ« art, jo njÃ« shkencÃ«. Dhe ka shumÃ« qÃ« shkon nÃ« to. Interneti, si i tha, Ã«shtÃ« e plotÃ« i funksioneve tÃ« vÃ«rtetÃ« tÃ« mirÃ« hash, dhe ju duhet tÃ« pÃ«rdorni internetin pÃ«r gjeni funksionet hash, sepse Ã«shtÃ« e vÃ«rtetÃ« vetÃ«m lloj i njÃ« tÃ« panevojshme humbje e kohÃ«s pÃ«r tÃ« krijuar tuaj. 

Ju mund tÃ« shkruani ato tÃ« thjeshta pÃ«r qÃ«llime testimi. Por kur ju tÃ« vÃ«rtetÃ« do tÃ« tÃ« fillojÃ« hashing tÃ« dhÃ«nave dhe ruajtjen atÃ« nÃ« njÃ« tabelÃ« hash ju jeni ndoshta do tÃ« doni tÃ« pÃ«rdorin njÃ« funksion qÃ« Ã«shtÃ« gjeneruar pÃ«r ju, qÃ« ekziston nÃ« internet. NÃ«se ju bÃ«ni tÃ« vetÃ«m tÃ« jetÃ« i sigurt tÃ« pÃ«rmendin burimet tuaja. Nuk ka asnjÃ« arsye pÃ«r tÃ« bÃ«j plagjiaturÃ« asgjÃ« kÃ«tu. 

Komuniteti shkenca kompjuterike Ã«shtÃ« definitivisht nÃ« rritje, dhe me tÃ« vÃ«rtetÃ« vlerat burim tÃ« hapur, dhe kjo Ã«shtÃ« me tÃ« vÃ«rtetÃ« e rÃ«ndÃ«sishme tÃ« citojnÃ« burimet tuaja nÃ« mÃ«nyrÃ« qÃ« njerÃ«zit mund tÃ« merrni atribuim pÃ«r puna qÃ« ata janÃ« duke bÃ«rÃ« pÃ«r tÃ« mirÃ«n e komunitetit. Pra, tÃ« jetÃ« gjithmonÃ« sure-- dhe jo vetÃ«m pÃ«r hash funksionet, por nÃ« pÃ«rgjithÃ«si, kur ju pÃ«rdorni kodin nga njÃ« burim i jashtÃ«m, gjithmonÃ« citojnÃ« burimin tuaj. Japin kredi pÃ«r personin i cili bÃ«ri disa tÃ« punÃ«s kÃ«shtu qÃ« ju nuk keni pÃ«r tÃ«. 

OK kÃ«shtu qÃ« le tÃ« rishqyrtojnÃ« kÃ«tÃ« tabelÃ« hash pÃ«r njÃ« tÃ« dytÃ«. Kjo Ã«shtÃ« ajo ku kemi lÃ«nÃ« off pas ne futur John dhe Paul nÃ« kÃ«tÃ« tabelÃ« hash. A ke parÃ« njÃ« problem kÃ«tu? Ju mund tÃ« shihni dy. Por nÃ« veÃ§anti, a shohin kÃ«tÃ« problem tÃ« mundshÃ«m? 

Ãka nÃ«se unÃ« hash Ringo, dhe ajo rezulton se pas pÃ«rpunimit qÃ« tÃ« dhÃ«nat me anÃ« tÃ« funksionit hash Ringo gjithashtu gjeneruar hashcode 6. UnÃ« kam marrÃ« tashmÃ« tÃ« dhÃ«nave nÃ« hashcode-- array vendndodhjen 6. Pra, kjo ndoshta do tÃ« jetÃ« pak e njÃ« problemi pÃ«r mua tani, apo jo? 

Ne e quajmÃ« kÃ«tÃ« njÃ« pÃ«rplasje. Dhe pÃ«rplasja ndodh kur dy pjesÃ« e tÃ« dhÃ«nave tÃ« drejtuar nÃ«pÃ«r tÃ« njÃ«jtÃ«n hash Funksioni i japin tÃ« njÃ«jtÃ«n hashcode. Me sa duket ne ende duan tÃ« marrin dy pjesÃ« e tÃ« dhÃ«nave nÃ« tabela hash, pÃ«rndryshe ne nuk do tÃ« konkurrojnÃ« Ringo nÃ« mÃ«nyrÃ« arbitrare pÃ«rmes funksionit hash. Ne me sa duket duan tÃ« marrin Ringo nÃ« atÃ« grup. 

Si nuk kemi tÃ« bÃ«jmÃ« atÃ« edhe pse, nÃ« qoftÃ« se ai dhe Pali dyja jepnin hashcode 6? Ne nuk duam tÃ« prishÃ«sh Palin, ne duam Pali tÃ« jenÃ« atje. Pra, ne kemi nevojÃ« pÃ«r tÃ« gjetur njÃ« mÃ«nyrÃ« pÃ«r tÃ« marrÃ« Elementet nÃ« tryezÃ« hash qÃ« ende ruan Quick tonÃ« futje dhe tÃ« shpejtÃ« tÃ« kÃ«rkoni. Dhe njÃ« mÃ«nyrÃ« pÃ«r t'u marrÃ« me tÃ« Ã«shtÃ« qÃ« tÃ« tÃ« bÃ«jÃ« diÃ§ka tÃ« quajtur lineare probing. 

Duke pÃ«rdorur kÃ«tÃ« metodÃ« nÃ« qoftÃ« se ne kemi njÃ« pÃ«rplasje, mirÃ«, Ã§farÃ« bÃ«jmÃ« ne? E pra ne nuk mund ta vÃ«nÃ« atÃ« nÃ« vend array 6, ose Ã§farÃ«do hashcode u gjenerua, le tÃ« vÃ«nÃ« atÃ« nÃ« hashcode plus 1. Dhe nÃ«se kjo Ã«shtÃ« e plotÃ« let vÃ«nÃ« atÃ« nÃ« hashcode plus 2. PÃ«rfitimi i kÃ«saj qenieje, nÃ«se ai Ã«shtÃ« jo saktÃ«sisht ku ne mendojmÃ« se Ã«shtÃ«, dhe ne kemi pÃ«r tÃ« filluar kÃ«rkimin, Ndoshta ne nuk kemi pÃ«r tÃ« shkuar shumÃ« larg. Ndoshta ne nuk kemi pÃ«r tÃ« kÃ«rkuar tÃ« gjitha elementet n e tabelÃ«s hash. Ndoshta ne duhet tÃ« kÃ«rkoni disa prej tyre. 

Dhe kÃ«shtu qÃ« ne jemi ende duke tentuar drejt se rasti mesatare duke qenÃ« afÃ«r 1 vs afÃ«r n, kÃ«shtu qÃ« ndoshta qÃ« do tÃ« punojnÃ«. Pra, le tÃ« shohim se si kjo mund tÃ« punojnÃ« jashtÃ« nÃ« realitet. Dhe le tÃ« shohim nÃ«se ndoshta ne mund tÃ« zbulojÃ« problemi qÃ« mund tÃ« ndodhÃ« kÃ«tu. 

Le tÃ« themi se tÃ« hash Bart. Pra, tani ne jemi duke shkuar pÃ«r tÃ« drejtuar njÃ« seri tÃ« re e tela pÃ«rmes funksionit hash, dhe ne tÃ« drejtuar Bart me anÃ« tÃ« hash funksion, ne kemi marrÃ« hashcode 6. Ne kemi marrÃ« njÃ« sy, ne shohim 6 Ã«shtÃ« bosh, kÃ«shtu qÃ« ne mund tÃ« vÃ«nÃ« Bart atje. 

Tani ne hash Lisa dhe se gjithashtu gjeneron hashcode 6. E pra tani qÃ« ne jemi duke pÃ«rdorur kÃ«tÃ« linear probing metodÃ« ne tÃ« fillojÃ« nÃ« 6, ne shohim se 6 Ã«shtÃ« e plotÃ«. Ne nuk mund tÃ« vÃ«nÃ« Lisa nÃ« 6. Pra, ku do tÃ« shkojmÃ«? Le tÃ« shkojnÃ« nÃ« 7. 7 e bosh, kÃ«shtu qÃ« punon. Pra, le tÃ« vÃ«nÃ« Lisa atje. 

Tani ne hash Homerit dhe ne tÃ« merrni 7. OK edhe ne e dimÃ« se 7 e plotÃ« tani, kÃ«shtu qÃ« ne nuk mund tÃ« vÃ«nÃ« Homerit atje. Pra, le tÃ« shkojÃ« nÃ« 8. ÃshtÃ« 8 nÃ« dispozicion? Po, dhe afÃ«r 8-tÃ« 7, kÃ«shtu qÃ« nÃ«se ne kemi pÃ«r tÃ« filluar kÃ«rkimin jemi nuk do tÃ« ketÃ« pÃ«r tÃ« shkuar shumÃ« larg. Dhe kÃ«shtu le tÃ« vÃ«nÃ« Homerit nÃ« 8. 

Tani ne hash Maggie dhe kthehet 3, lavdi zotit ne jemi nÃ« gjendje pÃ«r tÃ« vetÃ«m tÃ« vÃ«nÃ« Maggie atje. Ne nuk duhet tÃ« bÃ«jmÃ« ndonjÃ« lloj probing pÃ«r atÃ«. Tani ne hash Marge, dhe Marge gjithashtu kthehet 6. 

E pra 6 Ã«shtÃ« e plotÃ«, 7 Ã«shtÃ« e plotÃ«, 8 Ã«shtÃ« e plotÃ«, 9, tÃ« gjithÃ« tÃ« drejtÃ« falÃ«nderoj PerÃ«ndinÃ«, 9 Ã«shtÃ« bosh. UnÃ« mund tÃ« vÃ«nÃ« Marge nÃ« 9. TashmÃ« ne mund tÃ« shohim se ne jemi duke filluar qÃ« tÃ« ketÃ« kÃ«tÃ« problem, ku tani ne jemi filluar tÃ« shtrihet gjÃ«rat lloj e larg nga kodet e tyre hash. Dhe qÃ« theta nga 1, qÃ« mesatarja rast pÃ«r tÃ« qenÃ« kohÃ« konstante, ka filluar tÃ« marrÃ« njÃ« more-- vogÃ«l duke filluar pÃ«r tÃ« tentojnÃ« pak mÃ« shumÃ« drejt theta tÃ« n. Ne jemi duke filluar pÃ«r tÃ« humbur atÃ« PÃ«rparÃ«sia e tabelave hash. 

Ky problem qÃ« ne vetÃ«m e pa Ã«shtÃ« diÃ§ka e quajtur clustering. Dhe Ã§farÃ« Ã«shtÃ« me tÃ« vÃ«rtetÃ« keq pÃ«r clustering Ã«shtÃ« se sapo ju tani kanÃ« dy elemente qÃ« janÃ« krah pÃ«r anÃ«n kjo e bÃ«n atÃ« edhe mÃ« shumÃ« tÃ« ngjarÃ«, ju keni tÃ« dyfishtÃ« mundÃ«si, se ju do tÃ« jeni tÃ« ketÃ« njÃ« tjetÃ«r pÃ«rplasje me kÃ«tÃ« grup, dhe grup do tÃ« rritet nga njÃ«. Dhe ju do tÃ« vazhdojÃ« tÃ« rritet dhe tÃ« rritet mundÃ«sia juaj pÃ«r tÃ« pasur njÃ« pÃ«rplasje. Dhe nÃ« fund ajo Ã«shtÃ« po aq e keqe si mos zgjidhja e tÃ« dhÃ«nave nÃ« tÃ« gjitha. 

Problemi tjetÃ«r edhe pse Ã«shtÃ« ne ende, dhe deri mÃ« tani deri nÃ« kÃ«tÃ« pikÃ«, ne kemi qenÃ« vetÃ«m lloj i kuptuar se Ã§farÃ« njÃ« tabelÃ« hash Ã«shtÃ«, ne ende vetÃ«m kanÃ« vend pÃ«r 10 strings. NÃ« qoftÃ« se ne duam tÃ« vazhdojmÃ« tÃ« hash qytetarÃ«t e Springfield, ne mund tÃ« merrni vetÃ«m 10 prej tyre nÃ« atje. Dhe nÃ« qoftÃ« se ne tÃ« pÃ«rpiqemi dhe tÃ« shtoni njÃ« 11 ose 12, ne nuk kemi njÃ« vend pÃ«r tÃ« vÃ«nÃ« ato. Ne vetÃ«m mund tÃ« jetÃ« tjerrje rreth nÃ« qarqet duke u pÃ«rpjekur pÃ«r tÃ« gjetur njÃ« vend bosh, dhe ne ndoshta merrni mbÃ«rthyer nÃ« njÃ« lak tÃ« pafund. 

Pra, ky lloj i jep hua pÃ«r idesÃ« e diÃ§ka tÃ« quajtur chaining. Dhe kjo Ã«shtÃ« ajo ku ne jemi duke shkuar pÃ«r tÃ« sjellÃ« Listat e lidhura prapa nÃ« foto. ÃfarÃ« nÃ«se nÃ« vend tÃ« ruajtjen vetÃ«m tÃ« dhÃ«nat vetÃ« nÃ« grup, Ã§do element i vektorit mund tÃ« tÃ« mbajÃ« pjesÃ« tÃ« shumta e tÃ« dhÃ«nave? E pra kjo nuk ka kuptim, apo jo? Ne e dimÃ« se njÃ« grup mund tÃ« vetÃ«m hold-- Ã§do element tÃ« njÃ« sÃ«rÃ« mund tÃ« mbajÃ« vetÃ«m njÃ« pjesÃ« e tÃ« dhÃ«nave tÃ« atij lloji tÃ« dhÃ«nave. 

Por Ã§farÃ« nÃ«se kjo lloj e tÃ« dhÃ«nave Ã«shtÃ« njÃ« listÃ« e lidhur, e drejtÃ«? Pra, Ã§farÃ« nÃ«se Ã§do element i vektorit ishte njÃ« tregues nÃ« krye tÃ« listÃ«s tÃ« lidhura? Dhe pastaj ne mund tÃ« ndÃ«rtojmÃ« kÃ«to listat lidhura dhe rriten ata nÃ« mÃ«nyrÃ« arbitrare, sepse listat lidhura lejojÃ« ne tÃ« rritet dhe tkurret shumÃ« mÃ« tepÃ«r fleksibilitet se njÃ« grup bÃ«n. Pra, Ã§farÃ« nÃ«se ne tani pÃ«rdorin, ne levave kjo, apo jo? Ne fillojmÃ« tÃ« rriten kÃ«to zinxhirÃ«t nga kÃ«to vende array. 

Tani ne mund tÃ« pÃ«rshtatet njÃ« infinit Shuma e tÃ« dhÃ«nave, apo jo pafund, njÃ« sasi arbitrare tÃ« tÃ« dhÃ«nave, nÃ« tryezÃ«n tonÃ« hash pa ndonjÃ«herÃ« drejtimin nÃ« problemi i pÃ«rplasjes. Ne kemi eliminuar edhe clustering duke bÃ«rÃ« kÃ«tÃ«. Dhe ne e dimÃ« mirÃ« se kur ne tÃ« futur nÃ« njÃ« listÃ« tÃ« lidhura, nÃ« qoftÃ« se ju kujtohet nga video tonÃ« nÃ« listat e lidhura, veÃ§mas Listat e lidhura dhe listat lidhura dyfish, kjo Ã«shtÃ« njÃ« operacion i vazhdueshÃ«m kohÃ«. Ne jemi vetÃ«m duke shtuar nÃ« pjesÃ«n e pÃ«rparme. 

Dhe pÃ«r look up, edhe ne e dimÃ« qÃ« shikoni nÃ« njÃ« listÃ« tÃ« lidhura mund tÃ« jetÃ« njÃ« problem, e drejtÃ«? Ne duhet tÃ« kÃ«rkoni pÃ«rmes ajo nga fillimi nÃ« fund. Nuk ka asnjÃ« mÃ«nyrÃ« tÃ« rastÃ«sishme qasje nÃ« njÃ« listÃ« tÃ« lidhura. Por nÃ« qoftÃ« se nÃ« vend tÃ« paturit e njÃ« tÃ« tillÃ« lidhur Lista ku njÃ« lookup do tÃ« jetÃ« o tÃ« n, ne tani kemi 10 listave tÃ« lidhura, ose 1.000 listat lidhura, tani Ã«shtÃ« o n i ndarÃ« nga 10, ose o tÃ« n ndarÃ« nga 1,000. 

Dhe, ndÃ«rsa ne ishim duke folur teorikisht nÃ« lidhje me kompleksitetin ne mosrespektimi konstante, nÃ« reale Bota kÃ«to gjÃ«ra nÃ« fakt rÃ«ndÃ«si, e drejtÃ«? Ne fakt do tÃ« vini re se kjo ndodh pÃ«r tÃ« kandiduar 10 herÃ« mÃ« tÃ« shpejtÃ«, ose 1000 herÃ« mÃ« shpejt, sepse ne jemi shpÃ«rndarjen e gjatÃ« zinxhir nÃ«pÃ«r 1000 zinxhirÃ«t mÃ« tÃ« vogla. Dhe kÃ«shtu Ã§do herÃ« qÃ« ne kemi pÃ«r tÃ« kÃ«rkuar pÃ«rmes njÃ« prej kÃ«tyre zinxhirÃ«ve ne mund tÃ« injorojnÃ« 999 zinxhirÃ«t ne nuk e kujdesit nÃ« lidhje me, dhe kÃ«rko vetÃ«m se njÃ«. 

E cila Ã«shtÃ« mesatarisht pÃ«r tÃ« jetÃ« 1,000 herÃ« mÃ« tÃ« shkurtÃ«r. Dhe kÃ«shtu qÃ« ne ende jemi tÃ« lloj duke tentuar drejt kÃ«tÃ« rast mesatare pÃ«r tÃ« qenÃ« kohÃ« tÃ« vazhdueshme, por vetÃ«m pÃ«r shkak se ne jemi leveraging duke e ndarÃ« nga njÃ« faktor i madh konstante. Le tÃ« shohim se si kjo mund tÃ« nÃ« fakt duken pse. Pra, ky ishte tabelÃ« hash kemi pasur para se tÃ« deklaruar njÃ« tabelÃ« hash qÃ« ishte i aftÃ« pÃ«r ruajtjen 10 strings. Ne nuk jemi duke shkuar pÃ«r tÃ« bÃ«rÃ« atÃ« mÃ«. Ne tashmÃ« e dimÃ« Kufizimet e kÃ«saj metode. Tani tabelÃ«n tonÃ« hash do tÃ« jetÃ« njÃ« grup prej 10 nyjet, pointers tÃ« krerÃ«ve tÃ« listave tÃ« lidhura. 

Dhe tani kjo Ã«shtÃ« null. Secili prej kÃ«tyre 10 pointers Ã«shtÃ« i pavlefshÃ«m. Nuk ka asgjÃ« nÃ« tonÃ« hash tryezÃ« tani. 

Tani le tÃ« fillojÃ« pÃ«r tÃ« vÃ«nÃ« disa gjÃ«rat nÃ« kÃ«tÃ« tabelÃ« hash. Dhe le tÃ« shohim se si kjo metodÃ« Ã«shtÃ« do tÃ« na pÃ«rfituar pak. Le tani tÃ« hash Joey. Ne do tÃ« do tÃ« kandidojÃ« string Joey pÃ«rmes njÃ« funksion hash dhe do tÃ« kthehemi 6. E pra Ã§farÃ« bÃ«jmÃ« ne tani? 

E pra tani duke punuar me listat e lidhura, ne nuk jemi duke punuar me vargjeve. Dhe kur ne jemi duke punuar me listat e lidhura ne e di se ne kemi nevojÃ« pÃ«r tÃ« filluar dinamike caktimin hapÃ«sirÃ« ââdhe ndÃ«rtimit zinxhirÃ«t. Kjo Ã«shtÃ« lloj i how-- ato janÃ« thelbi Elementet e ndÃ«rtimit tÃ« njÃ« listÃ« e lidhur. Pra, le tÃ« dinamike ndajÃ« hapÃ«sirÃ« ââpÃ«r Joey, dhe pastaj le tÃ« shtoni atÃ« nÃ« zinxhirin. 

Pra, tani tÃ« shohim se Ã§farÃ« kemi bÃ«rÃ«. Kur ne hash Joey kemi marrÃ« hashcode 6. Tani akrep nÃ« array vend tÃ« 6 vÃ« nÃ« krye tÃ« njÃ« listÃ« tÃ« lidhura, dhe tani kjo Ã«shtÃ« e vetmja element i njÃ« liste tÃ« lidhura. Dhe nyja nÃ« atÃ« listÃ« e lidhur Ã«shtÃ« Joey. 

Pra, nÃ«se ne duhet tÃ« shohim deri Joey mÃ« vonÃ«, ne vetÃ«m tÃ« hash Joey pÃ«rsÃ«ri, ne kemi marrÃ« 6 pÃ«rsÃ«ri sepse tonÃ« funksion hash Ã«shtÃ« determinist. Dhe pastaj ne tÃ« fillojÃ« nÃ« krye e listÃ«s lidhur theksuar pÃ«r nga lokacioni array 6, dhe ne mund iterate tÃ« gjithÃ« se duke u pÃ«rpjekur pÃ«r tÃ« gjetur Joey. Dhe nÃ« qoftÃ« se ne ndÃ«rtojmÃ« tonÃ« hash tryezÃ« nÃ« mÃ«nyrÃ« efektive, dhe funksioni ynÃ« hash nÃ« mÃ«nyrÃ« efektive pÃ«r tÃ« shpÃ«rndarÃ« tÃ« dhÃ«nat e mirÃ«, mesatarisht secili prej atyre tÃ« lidhura Listat nÃ« Ã§do vend array do tÃ« jetÃ« 1/10 madhÃ«sia e nÃ«se ne kishte vetÃ«m atÃ« si njÃ« e vetme e madhe listÃ« e lidhur me Ã§do gjÃ« nÃ« tÃ«. 

NÃ«se ne shpÃ«rndajÃ« se i madh i lidhur Lista e tÃ« gjithÃ« 10 listat e lidhura Ã§do listÃ« do tÃ« jetÃ« 1/10 madhÃ«sia. Dhe kÃ«shtu 10 herÃ« mÃ« tÃ« shpejtÃ« pÃ«r tÃ« kÃ«rkuar pÃ«rmes. Pra, le ta bÃ«jmÃ« kÃ«tÃ« pÃ«rsÃ«ri. Le tani tÃ« hash Ross. 

Dhe le tÃ« themi Ross, kur ne bÃ«jmÃ« atÃ« kodi hash marrim pÃ«rsÃ«ri Ã«shtÃ« 2. E pra tani ne dinamike ndajÃ« njÃ« nyje e re, ne kemi vÃ«nÃ« Ross nÃ« atÃ« nyje, dhe ne themi tani vendndodhja grup 2, nÃ« vend tÃ« duke treguar null, vÃ« nÃ« kokÃ«n e njÃ« i lidhur Lista nyje vetÃ«m i tÃ« cilit Ã«shtÃ« Ross. Dhe ne mund tÃ« bÃ«jmÃ« kÃ«tÃ« edhe njÃ« herÃ« mÃ« shumÃ«, ne mund tÃ« hash RakelÃ«n dhe pÃ«r tÃ« marrÃ« hashcode 4. malloc njÃ« nyje tÃ« re, e vÃ«nÃ« Rachel nÃ« nyjen, dhe thonÃ« se njÃ« vend array 4 tani vÃ« nÃ« kokÃ« nga njÃ« listÃ« e lidhur e tÃ« cilit vetÃ«m element ndodh tÃ« jetÃ« Rachel. 

OK por Ã§farÃ« ndodh nÃ«se ne kemi njÃ« pÃ«rplasje? Le tÃ« shohim se si kemi trajtuar goditjet duke pÃ«rdorur metodÃ«n e veÃ§antÃ« chaining. Le tÃ« hash Phoebe. Ne kemi marrÃ« hashcode 6. NÃ« shembullin tonÃ« tÃ« mÃ«parshme ishim vetÃ«m ruajtjen strings nÃ« rrjet. Ky ishte njÃ« problem. 

Ne nuk duam tÃ« plaÃ§kÃ« Joey, dhe ne kemi tashmÃ« shihet qÃ« ne mund tÃ« merrni disa clustering Problemet nÃ« qoftÃ« se ne tÃ« pÃ«rpiqemi dhe hap pÃ«rmes dhe hetim. Por, Ã§farÃ« nÃ«se ne vetÃ«m lloj i trajtuar kÃ«tÃ« nÃ« tÃ« njÃ«jtÃ«n mÃ«nyrÃ«, apo jo? ÃshtÃ« vetÃ«m si duke shtuar njÃ« element tÃ« nÃ« krye tÃ« njÃ« listÃ« tÃ« lidhura. Le hapÃ«sirÃ« ââvetÃ«m malloc pÃ«r Phoebe. 

Ne do tÃ« themi pikÃ«t e radhÃ«s Phoebe pointer tÃ« kreut tÃ« vjetÃ«r tÃ« listÃ«s lidhur, dhe pastaj 6 vetÃ«m pikÃ« pÃ«r Kreu i ri i listÃ«s sÃ« lidhur. Dhe tani shikoni, ne kemi ndryshuar Phoebe nÃ«. Ne tani mund tÃ« ruajÃ« dy Elementet me hashcode 6, dhe ne nuk kemi ndonjÃ« problem. 

Kjo Ã«shtÃ« shumÃ« e shumÃ« tÃ« gjithÃ« ka te chaining. Dhe chaining Ã«shtÃ« padyshim metodÃ« qÃ« Ã«shtÃ« do tÃ« jetÃ« mÃ« efektive pÃ«r ju, nÃ«se ju jeni ruajtjen e tÃ« dhÃ«nave nÃ« njÃ« tabelÃ« hash. Por ky kombinim i vargjeve dhe listat lidhura sÃ« bashku pÃ«r tÃ« formuar njÃ« tabelÃ« hash tÃ« vÃ«rtetÃ« nÃ« mÃ«nyrÃ« dramatike pÃ«rmirÃ«son aftÃ«sinÃ« tuaj pÃ«r tÃ« ruajtur sasi tÃ« mÃ«dha tÃ« tÃ« dhÃ«nave, dhe shumÃ« shpejt dhe me efikasitet tÃ« kÃ«rkoni nÃ«pÃ«r kÃ«to tÃ« dhÃ«na. 

Ka ende njÃ« mÃ« shumÃ« Struktura e tÃ« dhÃ«nave atje qÃ« mund edhe tÃ« jetÃ« pak mÃ« tÃ« mirÃ« nÃ« aspektin e garantimit se futje tonÃ«, fshirje, dhe Look up kohÃ«t janÃ« edhe mÃ« tÃ« shpejtÃ«. Dhe ne do tÃ« shohim se nÃ« njÃ« video nÃ« pÃ«rpiqet. UnÃ« jam Doug Lloyd, kjo Ã«shtÃ« CS50.