[TÓNLIST spila] DOUG LLOYD: Við nú að þú vita mikið um fylki, og þú veist mikið um tengd listum. Og við höfum ræða kostir og gallar, þá erum við rætt um að tengja skrár er hægt að fá stærri og minni, en þeir taka meira stærð. Fylki eru miklu meira einfalt að nota, en þeir eru takmarkandi eins mikið eins og við höfum til að stilla stærð array í upphafi og þá erum við fastur með það. 

En það er, að við höfum ansi mikið búinn öllum efni okkar um sem tengjast listum og fylki. Eða höfum við? Kannski getum við gert eitthvað jafnvel meira skapandi. Og þessi tegund af lánar hugmyndin um kjötkássa töflunni. 

Svo í kjötkássa töflunni að við ætlum að reyna sameina fjölda með tengda listanum. Við erum að fara að taka kostur fylkisins, eins og af handahófi aðgang, að vera fær um að fara bara að array þáttur 4 eða array þáttur 8 án þess að þurfa að árétta yfir. Það er ansi hratt, ekki satt? 

En við viljum líka að hafa gögn okkar uppbygging vera fær um að vaxa og skreppa. Við þurfum ekki, við gerum ekki langar að vera takmarkaður. Og við viljum vera fær um til að bæta við og fjarlægja hluti mjög auðveldlega, sem ef þú manst, er mjög flókið með fjölda. Og við getum kallað þetta nýr hlutur a kjötkássa borð. 

Og ef rétt útfærð, við erum konar taka kostir beggja gögnum mannvirki sem þú hefur nú þegar séð, fylki og tengd listum. Innsetning getur byrjað að tilhneigingu til þeta af 1. Theta við höfum í raun ekki rætt, en þeta er bara meðaltal ræða, hvað er í raun að fara að gerast. Þú ert ekki alltaf að fara að hafa versta falli, og þú ert ekki alltaf að fara að hafa besta falli, svo er það að meðaltali atburðarás? 

Jæja að meðaltali innsetning í kjötkássa töflunni getur byrjað að fá nærri föstu tíma. Og eyðing er hægt að fá nærri föstu tíma. Og útlit er hægt að fá nærri föstu tíma. That's-- við höfum ekki gögn uppbygging enn sem getur gert það, og svo þetta þegar hljómar eins og a laglegur mikill hlutur. Við höfum í raun draga úr því gallar hvers á eigin spýtur. 

Til að fá þessa frammistöðu uppfærsla þó, við þarf að endurhugsa hvernig við bætum gögn í uppbyggingu. Sérstaklega viljum við Gögnin sjálf að segja okkur þar sem það ætti að fara í uppbyggingu. Og ef við þurfum þá að sjá hvort það er í uppbyggingu, ef við þurfum að finna það, við viljum að líta á gögn aftur og vera fær um að í raun, nota gögn, handahófi aðgang að honum. Bara með því að horfa á gögn sem við ættum að hafa hugmynd um hvar nákvæmlega við erum fara að finna það í kjötkássa töflunni. 

Nú hæðir af kjötkássa Taflan er að þeir eru í raun ansi slæmt á röðun eða flokkun gagna. Og í raun, ef þú byrjar að nota þá til að panta eða tegund gögn sem þú tapa öllum af Kostir Þú áður hafði í skilmálar af innsetningu og eyðingu. Tíminn verður nær þeta n, og við höfum í rauninni hörfuðu í tengda listanum. Og svo við viljum bara að nota kjötkássa töflur ef við ekki sama um hvort gögn eru flokkuð. Fyrir því í hvaða samhengi þú munt nota þær í CS50 þú sennilega ekki sama að gögnin séu flokkuð. 

Svo er kjötkássa borð sambland af tveimur aðskildum stykki sem við erum kunnugir. Í fyrsta lagi er fall, sem við köllum yfirleitt kjötkássa virka. Og það kjötkássa virka er að fara að aftur sumir non-neikvæð heiltala, sem við köllum yfirleitt Tætifall, OK? Annað stykki er fylki, sem er fær um að geyma gögn af gerðinni vér langar að setja inn gögn uppbygging. Við munum halda utan um tengda listanum þáttur nú og bara byrja með grunnatriði a kjötkássa borð að fá höfuð þitt í kringum það, og þá munum við kannski blása hugur þinn svolítið þegar við sameina fylki og tengil listum saman. 

Grunnhugmyndin þó er við tökum nokkur gögn. Við keyra þessi gögn í gegnum kjötkássa virka. Og svo er úr gögnum og það spits út fjölda, OK? Og þá með því að tala við geyma bara gögn við viljum geyma í array á þeim stað. Svo til dæmis að við höfum kannski þetta kjötkássa borð af strengjum. Það fékk 10 þætti í henni, svo við getum passa 10 strengi í það. 

Segjum að við viljum að kjötkássa Jóhannes. Svo John sem gögn sem við viljum að setja í þessum kjötkássa borð einhvers staðar. Hvar eigum við að setja það? Jæja oftast með að array svo langt að við líklega myndi setja það í array stað 0. En nú höfum við þetta nýja kjötkássa virka. 

Og við skulum segja að við að keyra John í gegnum þetta kjötkássa virka og það er spits út 4. Jæja það er þar sem við erum fara til að vilja setja Jóhannes. Við viljum að setja Jóhannes í array stað 4, því ef við kjötkássa Jóhannes again-- skulum segja síðar við langar að leita og sjá ef John til í þessum kjötkássa table-- allt sem við þurfum að gera er að keyra það í gegnum sömu kjötkássa virka, fá númer 4 út, og vera fær um að finna John strax í gögn uppbygging okkar. Það er nokkuð gott. 

Segjum að við gerum nú þetta aftur, viljum við kjötkássa Pál. Við viljum bæta Pál í þessum kjötkássa töflunni. Við skulum segja að þessi tími hlaupum Paul gegnum kjötkássa virka, sem Tætifall sem er myndaður er 6. Jæja nú getum við sett Pál í array stað 6. Og ef við þurfum að horfa upp hvort Paul er í þessu kjötkássa borð, allt sem við þurfum að gera er að keyra Paul gegnum kjötkássa virka aftur og við erum að fara að fá 6 út aftur. 

Og þá erum við að líta bara á array stað 6. Er Paul þarna? Ef svo er, er hann í kjötkássa töflunni. Er Paul ekki þar? Hann er ekki í kjötkássa töflunni. Það er frekar einfalt. 

Nú hvernig þú skilgreinir kjötkássa virka? Jæja það er í raun engin takmörk fyrir því Fjöldi hugsanlegra kjötkássa virka. Í raun er a tala af mjög, virkilega góður sjálfur á internetinu. There er a tala af mjög, virkilega slæmur sjálfur á internetinu. Það er líka frekar auðvelt til að skrifa a slæmur einn. 

Og hvað gerir upp gott kjötkássa virka, ekki satt? Jæja gott kjötkássa virka ætti nota aðeins gögn sem tætt, og öll gögn sem tætt. Þannig að við viljum ekki að nota anything-- við ekki fella ekki neitt annað annað en gögnunum. Og við viljum að nota öll gögn. Við viljum ekki bara að nota stykki um það, viljum við nota allt það. A kjötkássa virka ætti einnig að vera deterministic. Hvað þýðir það? Jæja það þýðir að í hvert skipti sem við fara nákvæmlega sömu stykki af gögn í kjötkássa virka við alltaf fá sömu Tætifall út. Ef ég fara Jóhannes inn í kjötkássa virka ég út 4. Ég ætti að vera fær um að gera það 10.000 sinnum og ég alltaf fá 4. Svo ekki af handahófi tölur í raun Hægt er að taka þátt í kjötkássa okkar tables-- í kjötkássa virka okkar. 

A kjötkássa virka ætti einnig dreifið gögn. Ef hvert skipti sem þú keyrir gögn í gegnum kjötkássa virka þú færð Tætifall 0, það er sennilega ekki svo mikill, ekki satt? Þú vilt sennilega að stór a svið af kjötkássa númerum. Einnig það er hægt að dreifa út um töflunni. Og einnig það væri frábært ef virkilega svipuð gögn, eins og John og Jónatan, kannski voru breiða út til að vega mismunandi stöðum í kjötkássa töflunni. Það væri gott kostur. 

Hér er dæmi um kjötkássa virka. Ég skrifaði þetta einn upp áðan. Það er ekki sérlega gott kjötkássa virka ástæðum sem gera í raun ekki bera að fara inn núna. En sérðu hvað er að gerast hér? Það virðist eins og við erum að lýsa breytu heitir summan og setja það jafn 0. Og þá virðist ég er að gera eitthvað svo lengi sem strstr [J] er ekki jafnt að sviga 0. Hvað er ég að gera það? 

Þetta er í rauninni bara annar leið til að innleiða [? strl?] og greiningu á því hvenær þú hefur náð í lok band. Svo ég þarf ekki að í raun að reikna út lengd strengsins, Ég ætla bara að nota þegar ég lenti í sviga 0 eðli ég veit Ég hef náð enda strengsins. Og þá er ég að fara að halda iterating gegnum strengsins, bæta strstr [J] til að summa, og þá á lok dagsins að fara að skila summu mod HASH_MAX. 

Í grundvallaratriðum allt þetta kjötkássa virka er að gera er að bæta upp allar ASCII gildi band mitt, og þá er það aftur sumir Tætifall modded af HASH_MAX. Það er líklega stærð af array minn, ekki satt? Ég vil ekki vera að fá kjötkássa númer ef array minn er stærð 10, Ég vil ekki að vera að fá út kjötkássa númer 11, 12, 13, ég get ekki sett hlutina í þessum stöðum fylkisins, það væri ólöglegt. Ég myndi þjást skiptingu kenna. 

Nú er hér annar fljótur hliðar. Almennt þú ert líklega ekki að fara að langar til að skrifa eigin kjötkássa þínar aðgerðir. Það er í raun hluti af list, ekki vísindi. Og það er margt sem fer inn í þá. Netið, eins og ég sagði, er fullur af mjög góðum kjötkássa virka, og þú ættir að nota internetið til finna kjötkássa virka vegna þess að það er í raun bara svona óþarfa tímasóun að búa til þinn eigin. 

Þú getur skrifað einföld og prófanir. En þegar þú í raun ert að fara að byrja hass gögn og geyma það í kjötkássa töflunni sem þú ert líklega að fara til að vilja að nota sumir virka sem var mynda fyrir þig, sem er til staðar á internetinu. Ef þú ekki vera bara viss að vitna heimildir þínar. Það er engin ástæða til að plagiarize neitt hér. 

The tölvunarfræði samfélag er örugglega vaxa, og í raun gildi opinn uppspretta, og það er mjög mikilvægt að vitna heimildir þínar þannig að fólk er hægt að fá heiður þeirri vinnu sem þeir eru gera til hagsbóta fyrir samfélagið. Svo alltaf að vera sure-- og ekki bara fyrir kjötkássa virka, en yfirleitt þegar þér nota kóða frá utanaðkomandi uppspretta, alltaf vitnað uppspretta. Gefðu inneign á mann sem gerði sumir af the vinna svo þú þarft ekki að. 

OK þannig að við skulum rifja þetta kjötkássa borð fyrir annað. Þetta er þar sem við fórum burt eftir að við bætist John og Paul í þessum kjötkássa töflunni. Sérðu vandamál hér? Þú gætir séð tvo. En einkum gera þér sjá þessi mögulegu vandamál? 

Hvað ef ég kjötkássa Ringo og það kemur í ljós að eftir vinnslu að gögn um kjötkássa virka Ringo mynda einnig Tætifall 6. Ég hef nú þegar fengið gögn á hashcode-- array staðsetningu 6. Svo það er líklega að fara að vera svolítið um vandamál fyrir mig núna, ekki satt? 

Við köllum þetta árekstur. Og árekstur á sér stað þegar tvær stykki af gögnum keyra í gegnum sama kjötkássa virka skila sömu Tætifall. Væntanlega við viljum samt að fá bæði stykki af gögnum í kjötkássa töflunni, annars myndum við ekki vera að keyra Ringo geðþótta gegnum kjötkássa virka. Við viljum væntanlega að fá Ringo í því fylki. 

Hvernig gerum við það þó, ef hann og Paul bæði ávöxtun Tætifall 6? Við viljum ekki að skrifa Páli við viljum Paul að vera þar líka. Þannig að við þurfum að finna leið til að fá þættir í kjötkássa töflunni sem enn varðveitir Quick okkar innsetningu og fljótur líta upp. Og ein leið til að takast á við það er að gera eitthvað sem kallast línuleg leit. 

Using this aðferð ef við höfum árekstur, vel, hvað gerum við? Jæja við getum ekki sett hann í array stað 6, eða hvað Tætifall var mynda, við skulum setja hann á Tætifall plús 1. Og ef það er fullt skulum setja hann í Tætifall plús 2. Ávinningur af þessari veru ef hann er ekki nákvæmlega hvar við teljum hann er, og við verðum að byrja að leita, kannski við þurfum ekki að fara of langt. Kannski við þurfum ekki að leita allt n þættir kjötkássa töflunni. Kannski verðum við að leita a par af þeim. 

Og svo við erum enn tending átt að meðaltali málið vera nálægt 1 vs nálægt n, svo kannski að ætla að vinna. Þannig að við skulum sjá hvernig þetta gæti virkað út í raun. Og við skulum sjá hvort kannski getum við greint vandamálið sem gæti komið hér. 

Segjum að við kjötkássa Bart. Svo nú erum við að fara að keyra nýja sett af strengjum í gegnum kjötkássa virka, og hlaupum Bart gegnum kjötkássa virka, fáum við Tætifall 6. Við lítum, sjáum við 6 er tóm, þannig að við getum sett Bart þar. 

Nú erum við kjötkássa Lisa og að Einnig býr Tætifall 6. Jæja núna þegar við erum að nota þetta línuleg leit aðferð við að byrja á 6, sjáum við að 6 er fullt. Við getum ekki sett Lisa í 6. Svo þar sem við förum? Við skulum fara til 7. 7 er tóm, svo virkar það. Svo skulum við setja Lisa þar. 

Nú erum við kjötkássa Homer og við fáum 7. OK vel við vitum að 7 er fullur nú, þannig að við getum ekki sett Homer þar. Svo skulum við fara til 8. Er 8 í boði? Já, og 8 er tæplega 7, þannig að ef við verðum að byrja að leita að við erum ekki að fara að þurfa að fara of langt. Og svo skulum setja Homer á 8. 

Nú erum við kjötkássa Maggie og skilar 3, þakka góðvild við erum fær um að setja bara Maggie þar. Við þurfum ekki að gera eitthvað konar leit fyrir það. Nú erum við kjötkássa Marge, og Marge skilar líka 6. 

Jæja 6 er fullt, 7 er fullur, 8 er fullt, 9, allt í lagi að þakka Guði, 9 er tóm. Ég get sett Marge á 9. Nú þegar við sjáum að við erum að byrja að hafa þetta vandamál þar sem nú við erum farin að teygja hlutina konar af langt í burtu frá kjötkássa númerum þeirra. Og að þeta 1, að meðaltali málið að vera stöðug tími, er farin að fá smá more-- farin að hafa smá meira að þeta á n. Við erum farin að missa það Kosturinn við kjötkássa matskeið. 

Þetta vandamál sem við sáum bara er eitthvað sem kallast Þyrping. Og hvað er raunverulega slæmt um Þyrping er að þegar þú nú tvo hluti sem eru hlið við hlið það gerir það enn líklegra, þú þarft tvöfalt tækifæri, sem þú ert að fara að hafa aðra árekstur með því þyrping, og þyrping mun vaxa um einn. Og þú munt halda að vaxa og vaxa líkur á að fá árekstur. Og að lokum er það bara eins og slæmur sem ekki flokka gögnin yfirleitt. 

Önnur vandamál er þó við enn, og svo langt upp að þessum tímapunkti, við höfum bara verið svona skilja hvað kjötkássa borð er, við enn bara pláss fyrir 10 strengi. Ef við viljum halda áfram að kjötkássa íbúar Springfield, við getum aðeins fengið 10 af þeim þar. Og ef við reynum og bæta 11. eða 12., við höfum ekki stað til að setja þær. Við gætum bara að snúast um í hringi að reyna að finna tóma blettur, og við kannski festast í óendanlega lykkju. 

Þannig að þetta tegund af lánar hugmynd eitthvað sem heitir læsa. Og þetta er þar sem við erum að fara að koma tengd listum aftur inn í myndina. Hvað ef í stað þess að geyma bara Gögnin sjálf í array, hvert þáttur í array gæti halda mörg stykki af gögnum? Jæja það er ekki skynsamleg, ekki satt? Við vitum að array getur aðeins hold-- hver þáttur af fjölda getur aðeins halda eitt stykki af gögnum sem gögn tegund. 

En hvað ef að gögn gerð er tengd lista, ekki satt? Svo hvað ef sérhver þáttur í fylkinu var bendi á höfuð tengda listanum? Og þá erum við gætum byggt þær sem tengjast listum og vaxa þeim geðþótta, því tengd listum leyfa okkur að vaxa og skreppa a einhver fjöldi fleiri sveigjanlegan en fylki gerir. Svo hvað ef við notum nú, við að nýta þetta, ekki satt? Við byrjum að vaxa þessar keðjur út af þessum array stöðum. 

Nú við getum passa óendanlega Magn gagna, eða ekki óendanlegur, handahófskennt upphæð gögn, í kjötkássa töflunni okkar án þess nokkurn tíma að keyra í vandamálið á árekstri. Við höfum einnig eytt Þyrping því að gera þetta. Og vel við vitum að þegar við setjum í tengda listanum, ef þú manst frá vídeó okkar á tengd listum, ein tengd listum og tvöfalt tengd listum, það er stöðug tími aðgerð. Við erum bara að bæta við að framan. 

Og fyrir að líta upp, vel við vitum sem líta upp í tengda listanum getur verið vandamál, ekki satt? Við að leita í gegnum það frá upphafi til enda. Það er engin handahófi aðgangur í tengda listanum. En ef í stað þess að hafa einn tengd listi þar sem útlit væri O af N, við höfum nú 10 tengist listum, eða 1.000 tengd listum, nú er það O n deilt með 10, eða O n deilt með 1.000. 

Og á meðan við vorum að tala fræðilega um flókið við lítilsvirðingu fastar, í alvöru Heimurinn þetta máli í raun, ekki satt? Við reyndar vilja taka að þetta gerist að hlaupa 10 sinnum hraðar, eða 1.000 sinnum hraðar, vegna þess að við erum að dreifa einn langan keðja yfir 1.000 smærri keðjur. Og svo í hvert sinn sem við höfum til að leita gegnum einn af þeim keðjur sem við getum hunsa 999 keðjur Við sama um, og bara leita að einn. 

Sem er að meðaltali í vera 1.000 sinnum styttri. Og svo erum við enn konar tending að þessu meðaltali tilfelli af því að vera stöðugt tíma, en aðeins vegna þess að við erum að fá meira deila með von um mikinn stöðugum þáttur. Við skulum sjá hvernig þetta gæti í raun líta þó. Þannig að þetta var kjötkássa borð við höfðum áður en við lýst kjötkássa borð sem var fær um að geyma 10 strengi. Við erum ekki að fara að gera það lengur. Við vitum nú þegar að takmarkanir þeirrar aðferðar. Nú kjötkássa borð okkar er að fara að vera fjölbreytta 10 hnúta, ábendingum að forstöðumenn tengd listum. 

Og núna er það null. Hver einn af þeim 10 ábendingum er null. Það er ekkert í okkar kjötkássa borð núna. 

Nú skulum byrja að setja nokkrar hlutum í þessum kjötkássa töflunni. Og við skulum sjá hvernig þessi aðferð er fara til að njóta okkur svolítið. Skulum nú kjötkássa Joey. Við munum mun keyra band Joey gegnum a kjötkássa virka og við aftur 6. Jæja hvað gerum við nú? 

Jæja nú að vinna með tengd listum, við erum ekki að vinna með fylki. Og þegar við erum að vinna með tengd listum við veit að við þurfum að byrja breytilega úthlutun rúm og byggja keðjur. Það er tegund af how-- þeir eru algerlega þættir byggja tengda listanum. Svo skulum virk úthluta pláss fyrir Joey, og þá skulum bæta honum við keðju. 

Svo nú líta hvað við höfum gert. Þegar við kjötkássa Joey við fengum Tætifall 6. Nú bendillinn á array stað 6 bendir til höfuð tengda listanum, og núna er það eina þáttur í tengda listanum. Og hnút í að tengda listanum er Joey. 

Þannig að ef við þurfum að líta upp Joey síðar, kjötkássa við bara Joey aftur, fáum við 6 aftur því okkar kjötkássa virka er deterministic. Og þá erum við að byrja á höfði af tengda listanum benti að því array stað 6, og við getum árétta yfir að reyna að finna Joey. Og ef við að byggja okkar kjötkássa borð í raun, og kjötkássa virka okkar á áhrifaríkan hátt að dreifa gögn vel, að meðaltali hver þeirra tengd listum á öllum array stað verður 1/10 stærð ef við bara haft það sem eitt gríðarstór tengda listanum með allt í það. 

Ef við dreifa að mikið tengd Listinn yfir 10 tengd listum hver listi verður 1/10 stærð. Og þannig 10 sinnum hraðar að leita í gegnum. Svo skulum gera þetta aftur. Skulum nú kjötkássa Ross. 

Og við skulum segja Ross, þegar við gerum það kjötkássa kóða við komum til baka er 2. Jæja nú erum við að úthluta virk a Ný hnút, setja við Ross í hnút, og við segjum nú array staðsetningu 2, í stað þess að benda á núll, bendir til höfuð tengdur Listinn sem aðeins hnúturinn Ross. Og við getum gert þetta einu sinni, vér getur kjötkássa Rakel og fá Tætifall 4. malloc nýja hnút, setja Rakel í hnúturinn, og segja array stað 4 nú bendir til höfuðs af tengda listanum sem aðeins þáttur gerist að vera Rachel. 

OK en hvað gerist ef við höfum árekstur? Við skulum sjá hvernig við tökum árekstra nota sérstaka læsa aðferð. Skulum kjötkássa Phoebe. Við fáum Tætifall 6. Í fyrra dæminu okkar við vorum bara geyma strengi í array. Þetta var vandamál. 

Við viljum ekki að clobber Joey, og við höfum nú þegar séð að við getum fengið smá Þyrping vandamál ef við reynum og skref gegnum og rannsaka. En hvað ef við bara svona meðhöndla þetta á sama hátt, ekki satt? Það er bara eins og að bæta stak höfuð tengda listanum. Við skulum bara malloc pláss fyrir Phoebe. 

Við munum segja næst bendi Phoebe stig að gamla höfuð tengda listanum, og þá 6 bara bendir til nýr yfirmaður tengda listanum. Og nú líta, að við höfum breytt Phoebe í. Við getum nú geymt tvö þætti með Tætifall 6, og við höfum ekki nein vandamál. 

Það er ansi mikið allt það er að chaining. Og chaining er ákveðið aðferð sem er fara til vera árangursríkur fyrir þig ef þú ert að geyma gögn í kjötkássa töflunni. En þessi blanda af fylki og tengd skrár saman til að mynda kjötkássa töflunni mjög bætir verulega getu þína að geyma mikið magn af gögnum, og mjög fljótt og vel leit í gegnum þessi gögn. 

Það er enn eitt gögn uppbygging þarna úti sem gæti jafnvel verið hluti betri hvað varðar tryggja að okkar innsetning, eyðingu, og líta upp tímar eru jafnvel hraðar. Og við munum sjá að í vídeó á reynir. Ég er Doug Lloyd, þetta er CS50.