[Music kucheza]
>> DOUG LLOYD N Kwa sasa wewe kujua mengi kuhusu arrays,
na unajua mengi kuhusu orodha zinazoungwa.
Na tumekuwa kujadili faida na hasara, tumekuwa
kujadiliwa kwamba wanaohusishwa orodha wanaweza kupata kubwa na ndogo,
lakini wao kuchukua zaidi ukubwa.
Arrays ni zaidi ya moja kwa moja kwa kutumia, lakini wao ni restriktiva katika kiasi
kama tuna kuweka ukubwa wa safu mwanzoni kabisa
na kisha sisi ni kukwama kwa hayo.
>> Lakini hiyo ni, tumekuwa pretty much nimechoka yote ya mada yetu
kuhusu orodha wanaohusishwa na arrays.
Au kuwa na sisi?
Labda tunaweza kufanya kitu hata zaidi ya ubunifu.
Na kwamba aina ya lends wazo la meza hash.
>> Hivyo katika meza hash tunakwenda kujaribu kuchanganya safu na orodha wanaohusishwa.
Sisi ni kwenda kuchukua faida wa safu, kama random kupata,
kuwa na uwezo wa tu kwenda safu kipengele 4 au safu kipengele 8
bila ya kuwa na iterate hela.
Hiyo ni pretty kufunga, sawa?
>> Lakini pia wanataka kuwa na takwimu zetu muundo wa kuwa na uwezo wa kukua na kuogopa.
Hatuna haja, hatufanyi wanataka kuwa vikwazo.
Na tunataka kuwa na uwezo kuongeza na kuondoa mambo
kwa urahisi sana, ambayo kama unakumbuka, ni ngumu sana kwa safu.
Na tunaweza kuwaita hii jambo jipya meza hash.
>> Na kama kutekelezwa kwa usahihi, sisi ni aina ya kuchukua
faida ya data zote mbili miundo umefanya tayari kuona,
arrays na orodha wanaohusishwa.
Kuingizwa unaweza kuanza huwa kuelekea theta ya 1.
Theta sisi si kweli kujadiliwa, lakini theta ni tu kesi wastani,
nini hasa kitatokea.
Wewe si daima kwenda na mazingira ya kesi mbaya,
na wewe si daima kwenda na bora kesi, hivyo nini
wastani mazingira?
>> Naam kuingizwa wastani ndani ya meza hash
Unaweza kuanza kupata karibu na wakati mara kwa mara.
Na kufutwa wanaweza kupata karibu na wakati mara kwa mara.
Na chaguo-wanaweza kupata karibu na wakati mara kwa mara.
That's-- hatuna data muundo bado kwamba anaweza kufanya hivyo,
na hivyo hii tayari sauti kama jambo pretty kubwa.
Tumekuwa kweli umepunguza hasara ya kila juu yake mwenyewe.
>> Kupata utendaji huu kuboresha ingawa, sisi
haja ya kufikiri upya jinsi sisi kuongeza data katika muundo.
Hasa tunataka na takwimu yenyewe kutuambia
ambapo ni lazima kwenda katika muundo.
Na kama sisi basi haja ya kuona kama ni katika muundo, ikiwa tunahitaji kupata hiyo,
tunataka kuangalia data tena na kuwa na uwezo wa ufanisi,
kutumia takwimu, nasibu kupata huduma hiyo.
Tu kwa kuangalia data tunapaswa kuwa
wazo la ambapo hasa tuko kwenda kupata hiyo katika meza hash.
>> Sasa upande wa chini ya hash meza ni kwamba wao ni kweli
pretty mbaya wakati kuagiza au kuchagua data.
Na kwa kweli, kama kuanza kuzitumia ili au aina
data kupoteza wote wa faida wewe hapo awali
alikuwa katika suala la kuingizwa na kufutwa.
Wakati inakuwa karibu na theta ya n, na tumekuwa kimsingi
inasimulia katika orodha wanaohusishwa.
Na hivyo sisi tu wanataka kutumia hash meza kama sisi hawajali kuhusu
iwapo data ni Iliyopangwa.
Kwa mazingira ambayo utasikia matumizi yao katika CS50
pengine hawana huduma kwamba data ni Iliyopangwa.
>> Hivyo meza hash ni mchanganyiko ya vipande viwili tofauti
ambayo sisi ni ukoo.
Kwanza ni kazi, ambayo sisi kwa kawaida kuwaita heshi.
Na kwamba heshi ni kwenda kurudi baadhi integer zisizo hasi, ambayo
sisi kwa kawaida kuwaita Msimboreli, sawa?
Kipande cha pili ni safu, ambayo ni uwezo wa kuhifadhi data ya aina sisi
unataka mahali katika muundo data.
Tutaweza kushikilia mbali juu ya wanaohusishwa orodha kipengele kwa sasa
na tu kuanza na misingi ya hash meza ya kupata kichwa yako karibu yake,
na kisha tutaweza labda pigo akili yako wakati kidogo sisi
kuchanganya arrays na orodha kiungo pamoja.
>> Wazo msingi ingawa ni sisi kuchukua baadhi ya data.
Sisi kuendesha kwamba data kwa njia ya heshi.
Na hivyo data ni kusindika na mtemi idadi, sawa?
Na kisha kwa idadi hiyo sisi tu kuhifadhi data
tunataka kuhifadhi katika safu katika eneo hilo.
Hivyo kwa mfano tuna labda huu meza hash ya masharti.
Ni got mambo 10 ndani yake, hivyo tunaweza fit 10 masharti ndani yake.
>> Hebu sema tunataka hash Yohana.
Hivyo John kama data tunataka Insert ndani ya hii meza hash mahali fulani.
Wapi sisi kuiweka?
Naam kawaida kwa safu hadi sasa sisi pengine
ingekuwa kuiweka katika safu eneo 0.
Lakini sasa tuna hii mpya heshi.
>> Na hebu kusema kwamba sisi kukimbia John kwa njia hii kazi hash
na ni mtemi 4.
Naam hapo ndipo tuko atataka kuweka Yohana.
Tunataka kuweka John katika safu eneo 4, kwa sababu kama sisi hash John again--
hebu sema baadaye sisi unataka kutafuta na kuona
kama John ipo katika hash hii table-- zote tunahitaji kufanya
ni kukimbia kwa njia hash sawa kazi, kupata namba 4 nje,
na kuwa na uwezo wa kupata John mara moja katika mfumo wetu wa data.
Hiyo ni nzuri sana.
>> Hebu sema sisi sasa kufanya hivyo tena, tunataka hash Paulo.
Tunataka kuongeza Paul ndani ya hii meza hash.
Hebu kusema kwamba wakati huu sisi kukimbia Paul kupitia heshi,
Msimboreli kwamba ni yanayotokana ni 6.
Naam sasa tunaweza kuweka Paul katika safu eneo 6.
Na kama sisi haja ya kuangalia up kama Paulo yuko huu meza hash,
wote tunahitaji kufanya ni kukimbia Paul kupitia heshi tena
na sisi ni kwenda kupata 6 nje tena.
>> Na kisha sisi tu kuangalia katika safu eneo 6.
Je, Paulo huko?
Kama ni hivyo, yeye ni katika meza hash.
Je, Paulo si huko?
Yeye si katika meza hash.
Ni pretty moja kwa moja.
>> Sasa ni jinsi gani unaweza kufafanua heshi?
Naam kuna kweli hakuna kikomo kwa idadi ya kutokea kazi hash.
Kwa kweli kuna idadi ya kweli, ndio mzuri kwenye mtandao.
Kuna idadi ya kweli, ndio mbaya kweli kweli kwenye mtandao.
Ni pia rahisi sana kuandika moja mbaya.
>> Basi nini hufanya up nzuri kazi hash, sawa?
Naam nzuri heshi lazima kutumia tu data kuwa heshi,
na wote wa data kuwa heshi.
Hivyo hatutaki kutumia kitu, hatuna kuingiza chochote
kingine chochote zaidi data.
Na tunataka kutumia yote ya data.
Hatutaki kutumia tu kipande yake, tunataka kutumia yote.
Kazi hash lazima pia kuwa deterministic.
Hiyo ina maana gani?
Vizuri maana yake ni kwamba kila wakati sisi kupita halisi kipande kimoja cha data
ndani ya heshi sisi daima kupata Msimboreli huo nje.
Kama mimi kupita John katika kazi hash mimi kupata nje 4.
Mimi lazima kuwa na uwezo wa kufanya hivyo 10,000 Mimi na nyakati daima utasikia kupata 4.
Hivyo hakuna idadi random ufanisi inaweza kushiriki katika hash yetu tables--
katika kazi yetu hash.
>> Kazi hash lazima pia enhetligt kusambaza data.
Kama kila wakati wewe kukimbia data kupitia kazi hash kupata Msimboreli 0,
kwamba pengine si kubwa sana, sawa?
Pengine wanataka kubwa mbalimbali ya namba hash.
Pia mambo inaweza kuenea nje katika meza.
Na pia itakuwa kubwa kama kweli data kama hizo, kama John na Jonathan,
labda walikuwa kuenea nje kupima maeneo mbalimbali katika meza hash.
Hiyo itakuwa faida nzuri.
>> Hapa ni mfano wa heshi.
Niliandika hii moja up mapema.
Ni si hasa nzuri heshi
kwa sababu ya kuwa si kweli kubeba kwenda katika hivi sasa.
Lakini unaona nini kinaendelea hapa?
Inaonekana kama sisi ni kutangaza variable kuitwa jumla na kuiandaa sawa na 0.
Na kisha inaonekana mimi nina kufanya kitu hivyo muda mrefu kama strstr [j] si sawa
kwa backslash 0.
Je, Mimi kufanya huko?
>> Hii ni kimsingi tu mwingine njia za utekelezaji [? strl?]
na kuchunguza wakati wewe wameweza kufikiwa mwisho wa kamba.
Hivyo sina kwa kweli mahesabu ya urefu wa kamba,
Mimi tu kutumia wakati mimi kugonga backslash 0 tabia Najua
Nimekuwa kufikiwa mwisho wa kamba.
Na kisha mimi nina kwenda kuweka iterating kupitia kamba kwamba,
kuongeza strstr [j] kwa jumla, na kisha saa mwisho wa siku kwenda na kurudi kiasi mod
HASH_MAX.
>> Kimsingi hash hii yote kazi ni kufanya ni kuongeza up
wote wa maadili ASCII ya kamba yangu, na kisha ni
kurudi baadhi Msimboreli modded na HASH_MAX.
Pengine ni ukubwa wa safu yangu, sawa?
Sitaki kuwa kupata hash codes ikiwa safu yangu ni ya kawaida 10,
Sitaki kuwa kupata codes nje hash 11, 12,
13, siwezi kuweka mambo katika maeneo hayo ya safu,
hiyo inaweza kuwa kinyume cha sheria.
Ningependa kuteseka segmentation kosa.
>> Sasa hapa ni mwingine haraka kando.
Kwa ujumla pengine wewe si kwenda unataka kuandika yako kazi hash mwenyewe.
Ni kweli kidogo ya sanaa, si sayansi.
Na kuna mengi kwamba huenda katika yao.
Biashara, kama nilivyosema, ni kamili ya kazi nzuri kwa kweli hash,
na unapaswa kutumia biashara kwa kupata kazi hash kwa sababu ni kweli
aina tu ya lazima kupoteza muda wa kujenga yako mwenyewe.
>> Unaweza kuandika ndio rahisi kwa madhumuni ya kupima.
Lakini wakati wewe kweli ni kwenda kuanza hashing data na hifadhi hiyo
ndani ya hash meza uko pengine atataka
kutumia baadhi ya kazi kwamba ilitokana kwa ajili yenu, ambayo ipo kwenye mtandao.
Kama huna tu kuwa na uhakika wanaelezea vyanzo yako.
Hakuna sababu kwa plagiarize chochote hapa.
>> Jumuiya ya sayansi ya kompyuta ni dhahiri kuongezeka, na kwa kweli maadili
wazi chanzo, na kwa kweli ni muhimu wanaelezea vyanzo yako ili watu
wanaweza kupata maelezo kwa kazi kwamba wao ni
kufanya kwa manufaa ya jamii.
Hivyo daima kuwa sure-- na si tu kwa ajili hash
kazi, lakini kwa ujumla wakati kutumia kanuni kutoka chanzo nje,
Daima wanaelezea chanzo wako.
Kutoa mikopo kwa mtu ambaye alifanya baadhi ya kazi hivyo huna kwa.
>> OK hivyo hebu kupitia upya hii hash meza kwa ajili ya pili.
Hii ni pale ambapo sisi kushoto mbali baada ya sisi kuingizwa
Yohana na Paulo katika hii meza hash.
Je, unaweza kuona tatizo hapa?
Unaweza kuona mbili.
Lakini hasa, je, kuona tatizo hii inawezekana?
>> Nini kama mimi hash Ringo, na zinageuka kuwa baada ya usindikaji
kwamba data kwa njia ya heshi Ringo pia yanayotokana Msimboreli 6.
Nimekuwa tayari got data kwenye hashcode-- safu eneo 6.
Hivyo ni pengine ni kwenda kuwa kidogo tatizo kwa ajili yangu sasa, sawa?
>> Tunatoa wito huu mgongano.
Na mgongano hutokea wakati watu wawili vipande vya data kukimbia kwa njia ya hash sawa
kazi mavuno Msimboreli huo.
Takribani sisi bado wanataka kupata wawili vipande vya data katika meza hash,
vinginevyo sisi bila kuwa mbio Ringo kiholela kupitia heshi.
Sisi labda wanataka kupata Ringo ndani ya kwamba safu.
>> Je, sisi kufanya hivyo ingawa, kama yeye na Paulo wote wawili mavuno Msimboreli 6?
Hatutaki overwrite Paulo, tunataka Paulo kuwa huko pia.
Kwa hiyo, tunahitaji kutafuta njia ya kupata mambo katika meza hash kwamba
bado kulinda haraka yetu kuingizwa na haraka kuangalia juu.
Na njia moja ya kukabiliana nayo ni kufanya kitu kinachoitwa linear uchunguzi.
>> Kutumia njia hii kama tuna mgongano, vizuri, tunafanya nini?
Naam hatuwezi kumtia safu eneo 6, au chochote Msimboreli ilitokana,
hebu kuweka naye katika Msimboreli pamoja na 1.
Na kama hiyo full hebu kumtia Msimboreli pamoja na 2.
Faida ya kiumbe hiki kama yeye ni si hasa ambapo tunafikiri yeye ni,
na tuna kuanza kutafuta, labda hatuna kwenda mbali mno.
Labda hatuna kutafuta mambo yote n ya meza hash.
Labda tuna kutafuta wanandoa wao.
>> Na hivyo bado tuko kwenye kuchunga kwamba wastani kesi kuwa karibu na 1 vs
karibu na n, hivyo labda kwamba kutakuwa na kazi.
Basi hebu angalia jinsi hii inaweza kufanya kazi nje katika hali halisi.
Na hebu angalia kama labda sisi inaweza kuchunguza Tatizo ambayo inaweza kutokea hapa.
>> Hebu sema sisi hash Bart.
Hivyo sasa sisi ni kwenda kukimbia kuweka mpya ya masharti kupitia heshi,
na sisi kukimbia Bart kupitia hash kazi, sisi kupata Msimboreli 6.
Sisi kuangalia, tunaona 6 ni tupu, ili tuweze kuweka Bart huko.
>> Sasa sisi hash Lisa na kwamba pia inazalisha Msimboreli 6.
Naam sasa kwamba sisi ni kutumia hii linear uchunguzi mbinu sisi kuanza saa 6,
tunaona kwamba 6 ni kamili.
Hatuwezi kuweka Lisa katika 6.
Hivyo wapi sisi kwenda?
Hebu kwenda 7.
7 ya tupu, hivyo kwamba kazi.
Basi hebu kuweka Lisa huko.
>> Sasa sisi hash Homer na sisi kupata 7.
OK vizuri tunajua kwamba 7 kamili sasa, hivyo hatuwezi kuweka Homer huko.
Basi hebu kwenda hadi 8.
Ni 8 inapatikana?
Yeah, na 8 ya karibu na 7, hivyo kama tuna kuanza kutafuta tuko
si kwenda na kwenda mbali sana.
Na hivyo hebu kuweka Homer saa 8.
>> Sasa sisi hash Maggie na anarudi 3, kuwashukuru wema
sisi ni uwezo wa kuweka tu Maggie huko.
Hatuna kufanya lolote aina ya uchunguzi kwa ajili hiyo.
Sasa sisi hash Marge, na Marge pia anarudi 6.
>> Naam 6 ni kamili, 7 ni kamili, 8 ni kamili, 9, wote wanafunzi wa haki kumshukuru Mungu, 9 ni tupu.
Siwezi kuweka Marge saa 9.
Tayari tunaweza kuona kwamba sisi ni mapya kuwa na tatizo hili ambapo sasa tuko
kuanzia kwa kunyoosha mambo aina ya mbali mbali na namba zao hash.
Na kwamba theta ya 1, kwamba wastani kesi ya kuwa wakati mara kwa mara,
ni mapya ya kupata more-- kidogo kuanzia huwa kidogo zaidi
kuelekea theta ya n.
Sisi ni mapya ya kupoteza kwamba faida ya meza hash.
>> Tatizo hili kwamba sisi tu kuona ni kitu kinachoitwa kuunganisha.
Na nini ni mbaya kuhusu kuunganisha ni kwamba mara sasa
na mambo mawili ambayo ni bega kwa upande inafanya kuwa hata zaidi,
una mara mbili nafasi, kwamba wewe ni kwenda
kuwa na mgongano mwingine na kwamba nguzo,
na nguzo kukua kwa moja.
Na wewe utakuwa kuendelea kukua na kuongezeka uwezekano yako ya kuwa na mgongano.
Na hatimaye ni tu kama mbaya kama si kuchagua data wakati wote.
>> Tatizo jingine ingawa ni sisi bado, na hadi sasa hadi hatua hii,
sisi been tu aina ya kuelewa nini meza hash ni,
sisi bado tu na chumba kwa 10 masharti.
Kama tunataka kuendelea hash wananchi wa Springfield,
tunaweza tu kupata 10 kati yao huko.
Na kama sisi kujaribu na kuongeza ya 11 au 12, hatuna mahali pa kuziweka.
Tunaweza tu kuwa inazunguka kuzunguka katika duru kujaribu kupata doa tupu,
na sisi labda kukwama katika kitanzi usio.
>> Hivyo aina hii ya lends kwa wazo ya kitu kinachoitwa chaining.
Na hii ni wapi tunakwenda kuleta orodha wanaohusishwa nyuma katika picha.
Nini kama badala ya kuhifadhi tu data yenyewe katika safu,
kila kipengele cha safu naweza kushikilia vipande mbalimbali ya data?
Vizuri kwamba haina mantiki, sawa?
Tunajua kwamba safu Unaweza tu hold-- kila kipengele cha safu
inaweza tu kushikilia kipande kimoja wa takwimu za aina hiyo data.
>> Lakini nini kama aina hiyo data ni orodha wanaohusishwa, sawa?
Basi nini kama kila kipengele cha safu alikuwa
pointer kichwa cha orodha wanaohusishwa?
Na kisha tunaweza kujenga orodha ya wale wanaohusishwa
na kukua yao kiholela, kwa sababu orodha wanaohusishwa kuruhusu
sisi kukua na kuogopa mengi zaidi smidigt kuliko safu gani.
Basi nini kama sisi sasa kutumia, sisi kujiinua hii, sawa?
Sisi kuanza kukua hii minyororo nje ya maeneo haya safu.
>> Sasa tunaweza fit usio kiasi cha data, au si usio na mipaka,
Kiasi holela wa data, ndani ya hash yetu meza
bila hata kukimbia ndani tatizo la mgongano.
Tumekuwa pia kuondolewa kuunganisha kwa kufanya hivyo.
Na vizuri tunajua kwamba wakati sisi kuingiza ndani ya orodha wanaohusishwa, kama unakumbuka
kutoka sehemu yetu juu ya orodha wanaohusishwa, mmoja- orodha wanaohusishwa na orodha doubly wanaohusishwa,
ni mara kwa mara wakati wa operesheni.
Sisi ni kuongeza tu na mbele.
>> Na kwa ajili ya kuangalia juu, vizuri tunajua ili kuangalia juu katika orodha wanaohusishwa
inaweza kuwa tatizo, sawa?
Tuna kutafuta njia kuanzia mwanzo hadi mwisho.
Hakuna random upatikanaji katika orodha wanaohusishwa.
Lakini kama badala ya kuwa moja wanaohusishwa orodha ambapo chaguo-itakuwa O ya n,
sasa tuna orodha 10 wanaohusishwa, au orodha 1,000 wanaohusishwa,
sasa ni O ya n kugawanywa na 10, au O ya n kugawanywa na 1,000.
>> Na wakati sisi walikuwa wanazungumza kinadharia kuhusu utata
sisi kupuuza constants, katika halisi dunia hayo kwa kweli suala hilo,
sawa?
Sisi kwa kweli utakuwa taarifa kwamba hii hutokea
kuendesha mara 10 kwa kasi, au mara 1,000 kwa kasi,
kwa sababu sisi ni kusambaza moja kwa muda mrefu mlolongo hela minyororo 1,000 ndogo.
Na hivyo kila wakati tuna kutafuta kwa njia ya moja ya minyororo wale tunaweza
kupuuza 999 minyororo sisi hawajali kuhusu, na tu kutafuta kwamba mtu.
>> Ambayo ni juu ya wastani kwa kuwa mara 1,000 mfupi.
Na hivyo sisi bado ni aina ya kuelekea kesi hii wastani kuchunga
ya kuwa wakati mara kwa mara, lakini tu kwa sababu sisi ni leveraging
kugawa na baadhi ya mara kwa mara sababu kubwa.
Hebu angalia jinsi hii huenda kweli kuangalia ingawa.
Hivyo hii ilikuwa hash meza tulikuwa kabla ya sisi alitangaza meza hash kwamba
alikuwa na uwezo wa kuhifadhi 10 masharti.
Sisi siyo kwenda kufanya hivyo tena.
Sisi tayari kujua mapungufu ya njia hiyo.
Sasa hash yetu meza kwenda kuwa safu ya 10 nodes, kuyatumia
na wakuu wa orodha wanaohusishwa.
>> Na hivi sasa ni null.
Kila mmoja wa wale kuyatumia 10 ni batili.
Kuna kitu katika yetu hash meza hivi sasa.
>> Sasa hebu kuanza kuweka baadhi mambo ndani ya hii meza hash.
Na hebu angalia jinsi njia hii ni kwenda kufaidika sisi kidogo.
Hebu sasa hash Joey.
Tutaweza kukimbia kamba Joey kupitia heshi na sisi kurudi 6.
Vizuri tunafanya nini sasa?
>> Naam sasa kufanya kazi na orodha wanaohusishwa, sisi siyo kufanya kazi na arrays.
Na wakati sisi ni kufanya kazi na orodha wanaohusishwa sisi
kujua tunahitaji kuanza dynamically kugawa nafasi na kujenga minyororo.
Hiyo ni aina ya how-- wale ni msingi mambo ya kujenga orodha wanaohusishwa.
Basi hebu dynamically kutenga nafasi kwa Joey,
na kisha hebu kuongeza naye kwa mlolongo.
>> Hivyo sasa kuangalia kile ambacho tumefanya.
Wakati sisi hash Joey tulipata Msimboreli 6.
Sasa pointer katika safu eneo 6 anazungumzia mkuu wa orodha wanaohusishwa,
na sasa hivi ni tu kipengele cha orodha wanaohusishwa.
Na node kwa kuwa orodha wanaohusishwa ni Joey.
>> Hivyo kama sisi haja ya kuangalia juu Joey baadaye, sisi tu hash Joey tena,
tunapata 6 tena kwa sababu yetu kazi hash ni deterministic.
Na kisha sisi kuanza saa kichwa ya orodha wanaohusishwa alisema
kwa safu na eneo 6, na tunaweza iterate
hela kwamba kujaribu kupata Joey.
Na kama sisi kujenga wetu hash meza kwa ufanisi,
na kazi yetu hash ufanisi kusambaza data vizuri,
kwa wastani kila moja ya hizo wanaohusishwa orodha katika kila safu eneo
itakuwa 10/1 ukubwa wa kama sisi tu alikuwa ni kama moja kubwa
wanaohusishwa orodha kwa kila kitu ndani yake.
>> Kama sisi kusambaza kwamba mkubwa wanaohusishwa orodha hela orodha wanaohusishwa 10
kila orodha itakuwa 10/1 Mkono.
Na hivyo mara 10 wepesi kutafuta njia.
Basi hebu kufanya hivyo tena.
Hebu sasa hash Ross.
>> Na hebu sema Ross, wakati sisi kufanya hivyo hash kificho sisi kupata nyuma ni 2.
Naam sasa sisi dynamically kutenga nodi mpya, sisi kuweka Ross katika nodi kwamba,
na tunasema sasa safu eneo 2, badala ya akizungumzia null,
anazungumzia mkuu wa wanaohusishwa orodha ambao nodi tu ni Ross.
Na tunaweza kufanya wakati huu moja zaidi, sisi Unaweza hash Rachel na kupata Msimboreli 4.
malloc nodi mpya, kuweka Rachel katika nodi, na kusema safu eneo
4 sasa anazungumzia kichwa ya orodha wanaohusishwa ambao
kipengele tu hutokea kwa kuwa Rachel.
>> OK lakini kile kinachotokea kama tuna mgongano?
Hebu angalia jinsi sisi kushughulikia migongano kutumia tofauti chaining mbinu.
Hebu hash Phoebe.
Sisi kupata Msimboreli 6.
Katika mfano wetu uliopita sisi walikuwa tu kuhifadhi masharti katika safu.
Hii ilikuwa ni tatizo.
>> Hatutaki kwa clobber Joey, na tumekuwa tayari
kuonekana kuwa tunaweza kupata baadhi ya kuunganisha matatizo kama sisi kujaribu na hatua
kupitia na kuchunguza.
Lakini nini kama sisi tu aina ya kutibu hii njia ile ile, sawa?
Ni kama tu kuongeza kipengele na mkuu wa orodha wanaohusishwa.
Hebu tu malloc nafasi kwa Phoebe.
>> Tutaweza kusema ijayo pointi Phoebe pointer kwa kichwa wa zamani wa orodha wanaohusishwa,
na kisha tu 6 anazungumzia mkuu mpya wa orodha wanaohusishwa.
Na sasa tuangalie, tumekuwa iliyopita Phoebe katika.
Sisi sasa wanaweza kuhifadhi wawili vipengele na Msimboreli 6,
na hatuna matatizo yoyote.
>> Hiyo ni pretty much wote hapo ni chaining.
Na chaining ni dhahiri Njia hiyo ni
kwenda kuwa bora zaidi kwa wewe kama wewe ni hifadhi ya data katika meza hash.
Lakini hii mchanganyiko wa arrays na orodha wanaohusishwa
pamoja na kuunda meza hash kweli kasi inaboresha uwezo wako
kuhifadhi kiasi kikubwa cha data, na haraka sana na kwa ufanisi kutafuta
kupitia data hizo.
>> Bado kuna moja zaidi data ya muundo huko nje
kwamba anaweza hata kuwa kidogo bora katika suala la kuhakikisha
kwamba kuingizwa yetu, kufutwa, na kuangalia juu mara ni hata kwa kasi.
Na tutaweza kuona kwamba katika video juu ya anajaribu.
Mimi nina Doug Lloyd, hii ni CS50.