[Daqq tal-mużika] Doug LLOYD: Sa issa inti jafu ħafna dwar arrays, u inti taf ħafna dwar listi marbuta. U aħna ħadthom jiddiskutu l vantaġġi u liżvantaġġi, konna diskussi li marbuta listi jistgħu jiksbu akbar u iżgħar, iżda dawn jieħdu aktar daqs. Arrays huma ħafna aktar faċli li użu, iżda dawn qed restrittiva fil kemm kif għandna li jistabbilixxi daqs tal l-array fil-bidu nett u allura aħna qed mwaħħla miegħu. 

Imma dak li, konna pretty ħafna eżawriti kollha ta 'suġġetti tagħna dwar listi konnessi u arrays. Jew ikollhom we? Forsi nistgħu nagħmlu xi ħaġa saħansitra aktar kreattivi. U dik it-tip ta 'jsellef l-idea ta 'tabella hash. 

Allura f'tabella hash aħna qed tmur biex tipprova jikkombinaw firxa ma 'lista marbuta. Aħna qed tmur biex tieħu l-vantaġġi mill-firxa, bħall-aċċess bl-addoċċ, li tista 'biss mur firxa element 4 jew firxa element 8 mingħajr ma jkollhom jtenni madwar. Li pretty fast, id-dritt? 

Iżda aħna wkoll tixtieq li jkollok data tagħna istruttura tkun kapaċi li jikbru u tiċkien. M'għandniex bżonn, aħna ma jridu jiġu ristretti. U irridu nkunu kapaċi li żżid u neħħi l-affarijiet faċilment, li jekk inti recall, hija kumplessa ħafna ma 'firxa. U nistgħu sejħa dan ħaġa ġdida tabella hash. 

U jekk implimentati b'mod korrett, aħna qed tip ta 'teħid il-vantaġġi taż-żewġ data istrutturi inti stajt diġà raw, arrays u listi marbuta. Inserzjoni jistgħu jibdew tendenza lejn theta minn 1. Theta aħna ma diskussi verament, iżda theta huwa biss il-każ medja, dak li attwalment jiġri. Int mhux dejjem se għandhom l-agħar każ, u int mhux dejjem se jkollhom l aħjar każ, hekk x'hemm ix-xenarju medju? 

Well inserzjoni medja fis-tabella hash tista 'tibda li jersaq qrib għal żmien kostanti. U t-tħassir jista 'jikseb qrib għal żmien kostanti. U lookup jistgħu jiksbu qrib għal żmien kostanti. That's-- aħna ma jkollhomx data istruttura li għadha tista 'tagħmel dan, u għalhekk dan diġà ħsejjes bħal ħaġa pretty kbira. Imxejna verament mitigati l żvantaġġi ta 'kull waħdu. 

Biex tikseb din il-prestazzjoni upgrade għalkemm, aħna bżonn naħsbu mill-ġdid kif aħna żid data fl-istruttura. Speċifikament irridu li l- data nnifisha biex tgħidilna fejn għandhom imorru fl-istruttura. U jekk aħna mbagħad bżonn biex tara jekk huwa fil l-istruttura, jekk għandna bżonn issib lilha, irridu nħarsu lejn il-data ġdid u tkun tista 'b'mod effettiv, tintuża d-dejta, każwalment jkollhom aċċess għaliha. Biss billi tħares lejn l- data għandu jkollna idea ta 'fejn eżattament aħna qed ser isibuha fit-tabella hash. 

Issa l-tnaqqis ta 'hash tabella hija li dawn qed verament pretty bad fuq ordni jew issortjar data. U fil-fatt, jekk inti tibda li jużawhom għall-ordni jew it-tip data inti titlef kollha ta 'l- vantaġġi inti qabel kellhom f'termini ta 'inserzjoni u t-tħassir. Il-ħin isir eqreb lejn theta ta n, u konna bażikament naqas f'lista marbuta. U hekk aħna biss tixtieq li tuża hash tabelli jekk aħna ma jimpurtahom jekk id-data huwa magħżul. Għall-kuntest li fih inti ser jużawhom fil CS50 inti probabilment ma 'kura li d-data hija magħżula. 

Allura tabella hash huwa kombinazzjoni ta 'żewġ biċċiet distinti li aħna qed familjari. L-ewwel hija funzjoni, li aħna normalment sejħa funzjoni hash. U dik il-funzjoni hash se ritorn xi numru sħiħ mhux negattiva, li aħna normalment sejħa hashcode, OK? It-tieni biċċa hija firxa, li hija kapaċi maħżuna d- data tat-tip aħna jixtiequ li jpoġġu fl-istruttura tad-data. Aħna ser jżommu off fuq il- marbuta element lista għal issa u biss tibda bil-punti bażiċi ta ' hash tabella li tikseb ras tiegħek madwar dan, u allura aħna ser forsi blow moħħok ftit meta aħna jikkombinaw arrays u listi rabta flimkien. 

L-idea bażika għalkemm huwa nieħdu xi data. We run li d-data permezz il-funzjoni hash. U għalhekk id-data hija pproċessata u spits out numru, OK? U mbagħad b'dak l-għadd aħna biss jaħżen id-data irridu li jaħżnu fil- firxa f'dak il-post. Għalhekk, per eżempju għandna forsi din it-tabella hash ta 'spag. Huwa ltqajna 10 elementi fiha, so nistgħu joqogħdu 10 kordi fiha. 

Ejja ngħidu li rridu hash John. Allura John billi d-data irridu li daħħal fis din it-tabella hash x'imkien. Fejn nistgħu poġġih? Well tipikament ma ' firxa s'issa aħna probabbilment ipoġġiha fil-lokalità firxa 0. Imma issa għandna din il-funzjoni hash ġdid. 

U ejja ngħidu li aħna run John permezz ta 'din il-funzjoni hash u huwa spits out 4. Ukoll li fejn aħna qed tmur jridu jitqiegħdu John. Aħna tixtieq li tqiegħed John f'post firxa 4, għaliex jekk aħna hash John again-- ejja ngħidu wara aħna trid tfittex u tara jekk John teżisti f'dan hash table-- kollha għandna bżonn tagħmel hija mmexxija permezz ta 'l-istess hash funzjoni, jiksbu l-out numru 4, u tkun tista 'ssib John immedjatament fl-istruttura tad-data tagħna. Li pjuttost tajba. 

Ejja ngħidu aħna issa nagħmlu dan għal darb'oħra, irridu li hash Paul. Aħna tixtieq iżżid Paul fis din it-tabella hash. Ejja ngħidu li din id-darba we run Paul permezz tal-funzjoni hash, l hashcode li hija ġġenerata hija ta '6. Ukoll issa nistgħu npoġġu Paul fil-post array 6. U jekk għandna bżonn li wieħed ifittex jekk Paul huwa f'din it-tabella hash, kollha għandna bżonn tagħmel huwa mmexxi Paul permezz tal-funzjoni hash mill-ġdid u aħna qed tmur biex tikseb 6 mill-ġdid. 

U allura aħna biss ħarsa fil-post array 6. Huwa Paul hemmhekk? Jekk iva, hu fit-tabella hash. Huwa Paul ma hemm? Huwa ma fit-tabella hash. Huwa pjuttost sempliċi. 

Issa kif taħseb li jiddefinixxu funzjoni hash? Ukoll hemm verament ebda limitu għall- numru ta 'funzjonijiet possibbli hash. Fil-fatt hemm numru ta 'tassew, dawk verament tajba fuq l-internet. Hemm numru ta 'tassew, dawk verament ħżiena fuq l-internet. Huwa wkoll pjuttost faċli jiktbu waħda ħażina. 

Allura dak li jagħmel up a tajba funzjoni hash, id-dritt? Well funzjoni hash tajba għandhom jużaw biss l-informazzjoni li qed hashed, u kollha tad-data li qed hashed. Allura aħna ma jridu jużaw anything-- aħna ma jinkorporaw xejn inkella barra mit-tagħrif. U aħna tixtieq li tuża kollha tad-data. Aħna ma jridux biss tuża biċċa ta 'dan, aħna tixtieq li tagħmel użu kollu kemm hu. Funzjoni hash għandhom wkoll tkun deterministic. Xi tfisser? Ukoll dan ifisser li kull darba li aħna jgħaddu l-istess biċċa eżatt ta 'data fil-funzjoni hash aħna dejjem jiksbu l-istess hashcode out. Jekk I jgħaddu John fil- funzjoni hash I toħroġ 4. I għandhom ikunu jistgħu jagħmlu dan 10,000 ħinijiet u jien ser dejjem nikseb 4. Allura l-ebda każwali numri effettiv jistgħu jiġu involuti fl hash tagħna tables-- fil-funzjonijiet hash tagħna. 

Funzjoni hash għandha wkoll uniformi tqassam data. Jekk kull darba li inti tmexxi data permezz tal- funzjoni hash ikollok l-hashcode 0, li probabbilment mhux daqshekk kbir, id-dritt? Inti probabilment jridu big firxa ta 'kodiċijiet hash. Ukoll affarijiet jistgħu jinfirxu kemm matul il-mejda. U wkoll ikun kbir jekk verament data simili, bħal John u Jonathan, forsi kienu mifruxa li jintiżnu postijiet differenti fit-tabella hash. Dan ikun ta 'vantaġġ sbieħ. 

Hawn eżempju ta 'funzjoni hash. I kiteb dan wieħed up qabel. Mhuwiex partikolarment funzjoni hash tajba għal raġunijiet li ma verament iġorru nidħlu dritt issa. Imma inti tara x'inhu għaddej hawn? Jidher simili aħna qed tiddikjara varjabbli imsejħa somma u dan ikun iffissat ugwali għal 0. U allura apparentement qed nagħmel xi ħaġa sakemm strstr [j] mhijiex ugwali li backslash 0. What am I tagħmel hemmhekk? 

Dan huwa bażikament biss ieħor Mod ta 'implimentazzjoni [? STRL?] u skoperta meta inti stajt laħqu t-tmiem tas-sekwenza. So I ma jkollhomx biex effettivament jikkalkulaw it-tul tas-sekwenza, Jien biss jużaw meta I hit l- backslash 0 karattru Naf Stajt laħqu t-tmiem tas-sekwenza. U allura jien ser iżommu mtennija permezz ta 'dak string, żżid strstr [j] fi ftit kliem, u mbagħad fl- aħħar tal-ġurnata se jirritorna mod somma HASH_MAX. 

Bażikament dan kollu hash funzjoni qed tagħmel qed iżżid up kollha tal-valuri ASCII ta string tiegħi, u allura huwa jirritornaw xi hashcode Modded mill HASH_MAX. Huwa probabbilment l-daqs ta array tiegħi, id-dritt? Ma rridx li jkollna hash kodiċijiet jekk firxa tiegħi huwa ta 'daqs 10, Ma rridx li tkun jkollna kodiċijiet barra hash 11, 12, 13, I ma tista 'tpoġġi l-affarijiet fil f'dawn il-postijiet ta 'l-array, li jkun illegali. I d jsofru tort segmentazzjoni. 

Issa hawnhekk hija ieħor malajr aside. Ġeneralment int probabilment mhux se jridu jiktbu funzjonijiet tiegħek hash stess. Huwa fil-fatt daqsxejn ta arti, mhux xjenza. U hemm ħafna li tmur ġo fihom. L-internet, bħal I said, huwa sħiħa tal-funzjonijiet hash verament tajba, u għandek tuża l-internet biex Sib l-funzjonijiet hash għaliex dan huwa verament biss it-tip ta 'bla bżonn ħela ta 'ħin biex joħolqu tiegħek. 

Tista 'tikteb dawk sempliċi għal skopijiet li jittestjaw. Imma meta inti fil-fatt se tibda hashing data u maħżuna fis-tabella hash int probabbilment tmur jridu li tuża xi funzjoni li kien iġġenerat għalik, li teżisti fuq l-internet. Jekk inti biss tkun ċert li jiċċitaw sorsi tiegħek. M'hemm l-ebda raġuni biex plagiarize xejn hawn. 

Il-komunità tax-xjenza tal-kompjuter hija definittivament tikber, u verament valuri sors miftuħ, u huwa verament importanti li jiċċitaw sorsi tiegħek sabiex in-nies jistgħu jiksbu attribuzzjoni għall ix-xogħol li dawn qed tagħmel għall-benefiċċju tal-komunità. Allura dejjem tkun sure-- u mhux biss għall hash funzjonijiet, iżda ġeneralment meta inti jużaw kodiċi minn sors barra, dejjem jiċċitaw sors tiegħek. Agħti kreditu lill-persuna li għamlet xi xogħol sabiex inti ma għandekx. 

OK so ejja rriveduti dan tabella hash għat-tieni. Dan huwa fejn aħna jitħalla off wara we inserit John u Paul fis din it-tabella hash. Inti tara problema hawn? Inti tista 'tara tnejn. Iżda b'mod partikolari, do you tara din il-problema? 

X'jiġri jekk I hash Ringo, u Jirriżulta li wara l-ipproċessar li d-data permezz tal-funzjoni hash Ringo iġġenerat ukoll l hashcode 6. Stajt diġà kisbu data fil post array hashcode-- 6. Allura huwa probabbilment se tkun daqsxejn ta 'problema għalija issa, id-dritt? 

Aħna nsejħu dan ħabta. U l-ħabta ssir meta żewġ biċċiet ta 'data jgħaddi mill-istess hash funzjoni jagħtu l-istess hashcode. Preżumibbilment aħna xorta rridu nġibu kemm biċċiet ta 'data fit-tabella ta hash, inkella aħna mhux se tkun qed taħdem Ringo arbitrarju permezz tal-funzjoni hash. Aħna preżumibbilment rridu nġibu Ringo f'dak firxa. 

Kif nistgħu nagħmlu dan għalkemm, jekk hu u Paul kemm rendiment hashcode 6? Aħna ma rridux li jissostitwixxu Paul, irridu Paul li jkun hemm wisq. Allura għandna bżonn issib mod biex jiksbu elementi fit-tabella ta hash li xorta tippreserva quick tagħna inserzjoni u malajr ħarsa up. U mod wieħed biex jittrattaw dan huwa li jagħmel xi ħaġa imsejħa lineari probing. 

Meta tuża dan il-metodu jekk ikollna kolliżjoni, ukoll, dak li nagħmlu? Well aħna ma tista 'tpoġġi lilu fil-post array 6, jew kwalunkwe hashcode ġie ġġenerat, ejja tpoġġi lilu fil hashcode flimkien ma '1. U jekk dan huwa sħiħa ta let jniżżlu hashcode plus 2. Il-benefiċċju ta 'dan benessri jekk hu mhux eżattament fejn naħsbu hu, u għandna nibdew tiftix, forsi aħna ma jkollhom imorru wisq 'il bogħod. Forsi aħna ma jkollhomx biex tfittex elementi kollha N tar-tabella hash. Forsi irridu tfittxija ftit minnhom. 

U hekk aħna qed għadhom tendenza lejn F'dak il-każ medja li huma qrib 1 vs qrib n, hekk forsi li ser jaħdmu. Mela ejja ara kif dan jista 'jaħdem barra fir-realtà. U ejja ara jekk forsi nistgħu jikxfu l-problema li tista 'sseħħ hawn. 

Ejja ngħidu aħna hash Bart. Allura issa aħna qed tmur biex imexxu sett ġdid ta 'spag permezz tal-funzjoni hash, u aħna run Bart permezz tal-hash funzjoni, irridu jiksbu hashcode 6. Aħna tagħti ħarsa, naraw 6 huwa vojta, hekk aħna tista 'tpoġġi Bart hemmhekk. 

Issa aħna hash Lisa u li jiġġenera wkoll hashcode 6. Ukoll issa li aħna qed jużaw dan lineari probing metodu nibdew fuq 6, naraw li 6 hija sħiħa. Aħna ma tista 'tpoġġi Lisa f'6. Għalhekk, fejn do we go? Ejja ħa mmorru sa 7. 7 ta vojta, b'tali mod li jaħdem. Mela ejja tpoġġi Lisa hemmhekk. 

Issa aħna hash Homer u nikbru 7. OK ukoll nafu li 7 ta sħiħa issa, hekk aħna ma tista 'tpoġġi Homer hemmhekk. Mela ejja mur 8. Huwa 8 disponibbli? Yeah, u qrib 8 għal 7, hekk jekk għandna nibdew tiftix aħna qed mhux se jkollhom imorru wisq 'il bogħod. U hekk ejja tpoġġi Homer fi 8. 

Issa aħna hash Maggie u prospetti 3, nirringrazzja goodness aħna kapaċi biss jitqiegħed Maggie hemmhekk. Aħna ma jkollhom jagħmlu xi tip ta 'probing għal dan. Issa aħna hash Marge, u Marge prospetti wkoll 6. 

Ukoll 6 hija sħiħa, 7 hija sħiħa, 8 hija sħiħa, 9, id-dritt nirringrazzjaw 'l Alla, 9 ikun vojt. I tista 'tpoġġi Marge fid-9. Diġà nistgħu naraw li aħna qed jibdew li jkollhom din il-problema fejn issa aħna qed jibdew biex tistira affarijiet tip tal bogħod minn kodiċi hash tagħhom. U li theta ta '1, dik il-medja każ li jkun żmien kostanti, qed tibda tikseb more-- ftit jibdew tendenza ftit aktar lejn theta ta n. Aħna qed jibdew jitilfu dak vantaġġ ta 'tabelli hash. 

Din il-problema li aħna biss raw hija xi ħaġa imsejħa clustering. U x'hemm tassew ħżiena dwar clustering hija li ladarba inti issa żewġ elementi li qegħdin ħdejn sekondarji jagħmilha saħansitra aktar probabbli, inti għandek doppju tal- ċans, li int ser li jkollhom ħabta ieħor ma 'dak cluster, u l cluster se tikber minn wieħed. U tkun taf jibqgħu jikbru u li qed jikber probabbiltà tiegħek li jkollhom ħabta. U eventwalment huwa biss bħala ħżiena ma issortjar id-dejta fil-livelli kollha. 

Il-problema l-oħra għalkemm hija aħna xorta, u s'issa sa dan il-punt, aħna ħadthom biss ġew tip ta ' fehim dak tabella hash hija, aħna xorta jkollhom biss kamra għal 10 kordi. Jekk irridu li jkomplu hash iċ-ċittadini ta Springfield, nistgħu biss jiksbu 10 minnhom fil hemmhekk. U jekk nippruvaw u żid 11 jew 12, aħna ma jkollhomx post li jpoġġuhom. Nistgħu biss għażil madwar ċrieki jippruvaw isibu post vojt, u aħna forsi jeħlu fi loop infinita. 

Allura dan it-tip ta 'jsellef lill-idea ta 'xi ħaġa imsejħa ikkatenar. U dan huwa fejn aħna qed tmur biex iġibu listi marbuta lura fil-istampa. X'jiġri jekk minflok ħażna biss id-data nnifisha fil-firxa, kull element tal-firxa tista istiva biċċiet multipli ta 'data? Ukoll li ma jagħmilx sens, id-dritt? Aħna nafu li firxa tista 'biss hold-- kull element ta 'firxa tista 'żżomm biss biċċa waħda ta 'data ta' dak it-tip tad-data. 

Imma x'jiġri jekk dak it-tip tad-data hija lista marbut, right? Allura dak jekk kull element tad-firxa kienet a pointer lill-kap ta 'lista marbuta? U allura nistgħu nibnu dawk il-listi marbuta u jikbru minnhom arbitrarju, minħabba listi marbuta jippermettu ahna jikbru u tiċkien ħafna aktar flessibbli minn firxa ma. Allura dak li jekk aħna issa jużaw, aħna lieva dan, id-dritt? Aħna jibdew jikbru dawn il-ktajjen minn dawn il-lokalitajiet array. 

Issa nistgħu tajbin infinita ammont ta 'data, jew le infinita, ammont arbitrarja ta data, in-mejda hash tagħna mingħajr qatt tmexxija fis il-problema ta 'kolliżjoni. Imxejna wkoll eliminati clustering billi tagħmel dan. U tajjeb nafu li meta aħna daħħal fi lista marbuta, jekk inti recall mill-video tagħna fuq il-listi marbuta, weħidhom listi konnessi u listi marbuta doppjament, huwa operazzjoni żmien kostanti. Aħna biss li jżid mal-front. 

U għall-ħarsa up, ukoll aħna nafu li wieħed ifittex f'lista marbut tista 'tkun problema, id-dritt? Irridu tfittxija permezz mill bidu sat-tmiem. M'hemm l-ebda każwali aċċess f'lista marbuta. Iżda jekk minflok li wieħed marbut lista fejn lookup tkun O ta 'n- issa għandna 10-listi marbuta, jew 1,000 listi marbuta, issa huwa O ta 'n maqsum f'10, jew O ta 'n diviż bil 1000. 

U filwaqt li konna nitkellmu teoretikament dwar kumplessità aħna tinjora kostanti, fil-veru dinja dawn l-affarijiet fil-fatt jimpurtax, id-dritt? Aħna fil-fatt se avviż li dan jiġri biex imexxu 10 darbiet aktar mgħaġġla, jew 1,000 darba aktar mgħaġġla, għaliex aħna qed iqassmu waħda twila katina madwar 1,000 ktajjen iżgħar. U hekk kull darba irridu tfittxija permezz ta 'waħda minn dawk il-ktajjen li nistgħu jinjora l-ktajjen 999 aħna ma jimpurtahom dwar, u biss tfittxija li wieħed. 

Li bħala medja huwa li jkun 1,000 darba iqsar. U hekk aħna xorta huma tip ta ' tendenza lejn dan il-każ medja li jkunu ħin kostanti, iżda biss għaliex aħna qed jużaw diviż minn xi fattur kostanti enormi. Ejja naraw kif dan jista fil-fatt tfittex għalkemm. Allura dan kien il-mejda hash kellna qabel we ddikjarat tabella hash li kien kapaċi li jaħżen 10 kordi. Aħna mhux se tagħmel dan aktar. Aħna diġà jafu l- limitazzjonijiet ta 'dak il-metodu. Issa tabella hash tagħna li għaddej biex tkun firxa ta '10 nodi, pointers lill-kapijiet ta 'listi marbuta. 

U d-dritt issa huwa null. Kull waħda minn dawk il-10 pointers huwa null. M'hemm xejn fil tagħna hash tabella dritt issa. 

Issa ejja nibdew li jqajjem xi affarijiet fis din it-tabella hash. U ejja naraw kif dan il-metodu huwa se jibbenefikaw us ftit. Ejja issa hash Joey. Aħna ser se titmexxa l string Joey permezz funzjoni hash u nerġgħu lura 6. Well dak li nagħmlu issa? 

Ukoll issa li jaħdmu b'listi marbuta, aħna mhux qed jaħdmu ma 'arrays. U meta aħna qed jaħdmu ma 'listi marbuta aħna jafu jeħtieġ li nibdew dinamikament allokazzjoni ta 'spazju u l-bini ktajjen. C'est tip ta 'how-- dawk huma l-qalba elementi ta 'bini ta' lista marbuta. Mela ejja dinamiku jalloka spazju għal Joey, u mbagħad ejja żid lilu għall-katina. 

Allura issa nħarsu dak li aħna ghamilt. Meta aħna hash Joey sirna l-hashcode 6. Issa l-pointer fuq post firxa 6 jindika l-kap ta 'lista marbuta, u d-dritt issa huwa l-uniku element ta 'lista marbuta. U l-node f'dak Lista marbuta hija Joey. 

Mela jekk irridu li wieħed ifittex Joey wara, aħna biss hash Joey mill-ġdid, nikbru 6 mill-ġdid minħabba tagħna funzjoni hash hija deterministic. U allura aħna tibda fil-ras tal-lista marbuta osservat mill-post array 6, u nistgħu jtenni madwar li jippruvaw isibu Joey. U jekk aħna nibnu tagħna hash tabella effettiv, u l-funzjoni hash tagħna b'mod effettiv li jiddistribwixxu data tajjeb, fuq medja kull wieħed minn dawk marbuta listi f'kull post array se jkun 1/10-daqs ta 'jekk irridu biss kellhom bħala enormi wieħed lista marbuta ma 'kollox fiha. 

Jekk aħna jiddistribwixxu li marbuta enormi Lista madwar 10 listi marbuta kull lista se jkun 1/10-daqs. U b'hekk 10 darbiet aktar mgħaġġla li tfittex. Mela ejja tagħmel dan mill-ġdid. Ejja issa hash Ross. 

U ejja ngħidu Ross, meta nagħmlu dan il-kodiċi tal-hash nikbru lura huwa ta '2. Ukoll issa aħna dinamikament jallokaw node ġdid, npoġġux Ross f'dak node, u aħna ngħidu issa lokazzjoni firxa 2, minflok tipponta lejn null, jindika l-kap ta 'marbut lista li node biss huwa Ross. U nistgħu nagħmlu dan wieħed aktar ħin, aħna jistgħu hash Rachel u jiksbu hashcode 4. malloc node ġdid, tpoġġi Rachel fil l node, u jgħidu post array 4 issa juri l-kap ta 'lista marbuta li biss element jiġri li jkun Rachel. 

OK imma x'jiġri jekk għandna ħabta? Ejja naraw kif aħna nittrattaw ħabtiet użu tal-metodu chaining separata. Ejja hash Phoebe. Irridu jiksbu l-hashcode 6. Fl-eżempju preċedenti tagħna aħna kienu biss ħażna tal-kordi fl-array. Din kienet problema. 

Aħna ma rridux li clobber Joey, u konna diġà jidher li nistgħu nikseb xi raggruppament problemi jekk nippruvaw u pass permezz ta 'u sonda. Imma dak jekk aħna biss tip ta ' jittratta dan l-istess mod, id-dritt? Huwa biss bħal żieda ta 'element lill-kap ta 'lista marbuta. Ejja ispazju biss malloc għall Phoebe. 

Aħna ser jgħidu punti Phoebe tal pointer li jmiss lill-kap antika tal-lista marbuta, u mbagħad 6 biss juri l- kap il-ġdid tal-lista marbuta. U issa nħarsu, konna inbidlet Phoebe in. Aħna issa jista 'jaħżen tnejn elementi li hashcode 6, u aħna ma jkollhom xi problemi. 

Li pretty ħafna kollha hemm biex chaining. U chaining huwa definittivament il-metodu li l- ser ikunu aktar effettivi għalik jekk inti qed jaħżnu data fit-tabella hash. Iżda din il-kombinazzjoni ta ' arrays u listi marbuta flimkien biex jiffurmaw tabella hash verament drammatiku ittejjeb l-abbiltà tiegħek li jaħżnu ammonti kbar ta 'data, u malajr ħafna u b'mod effiċjenti tfittxija permezz ta 'dak id-data. 

Hemm għadu wieħed aktar istruttura tad-data hemmhekk li jista 'anke jkun daqsxejn aħjar f'termini ta 'garanzija ta li inserzjoni tagħna, tħassir, u tfittex up ħinijiet huma aktar malajr. U aħna ser tara li fil-video fuq jipprova. Jien Doug Lloyd, dan huwa CS50.