[Muzikos grojimo] Doug LLOYD: Iki šiol jūs žinoti apie masyvų daug, ir žinote apie susijusių sąrašus daug. Ir mes aptarti privalumus ir trūkumus, mes aptarta, kad susijęs sąrašus gali gauti daugiau ir mažesnių, tačiau jie užima daugiau dydį. Masyvai yra daug paprasta naudoti, bet jie ribojanti kiek kaip mes turime nustatyti dydį tuo pat pradžios masyvo ir tada mes pakimba su juo. Bet tai, mes gana daug išnaudotos visos mūsų pranešimus apie susijusių sąrašų ir matricos. Arba mes? Gal mes galime padaryti kažką dar kūrybingi. Ir kad skolina Rūšiuoti iš maišos lentelės idėja. Taigi maišos lentelę mes ketiname pabandyti sujungti masyvą su susietą sąrašą. Mes ketiname imtis privalumus masyvo, pavyzdžiui, laisvą prieigą, kad galėtų tiesiog eikite į masyvą elementas 4 arba masyvo elementas 8 nereikia kartoti visoje. Tai gana greitas, tiesa? Tačiau mes taip pat norime, kad mūsų duomenis struktūra galėtų augti ir trauktis. Mums nereikia, mes do not nori būti apribota. Ir mes norime, kad būtų galima pridėti ir pašalinti dalykus labai lengvai, o jei prisimenate, yra labai kompleksas su masyvo. Ir mes galime tai vadiname naujas dalykas maišos lentelė. Ir jei teisingai įgyvendinami, mes tarsi atsižvelgiant abiejų duomenų privalumai struktūros jūs jau matė, matricas ir susiję sąrašus. Įterpimas gali pradėti linkę link teta 1. Teta mes tikrai ne aptarti, bet teta yra tik vidutinis atvejis, kas iš tikrųjų nutiks. Jūs neprisijungęs visada bus turi blogiausią scenarijų, ir jūs ne visada turėsi Geriausiu atveju, tai kas vidutinis scenarijus? Na vidutinis įterpimo į maišos lentelė gali pradėti priartėti prie pastovaus laiko. Ir išbraukta galite gauti uždaryti iki pastovaus laiko. Ir peržvalgos galite gauti uždaryti iki pastovaus laiko. That's-- neturime duomenų struktūra, kad dar galite tai padaryti, ir todėl tai jau skamba kaip gana didelis dalykas. Mes tikrai sušvelnintas trūkumai kiekvienas savo. Norėdami gauti šią veiklą atnaujinti, nors mes reikia permąstyti, kaip mes pridėti duomenų struktūrai. Tiksliau mes norime, kad Patys duomenys papasakoti kur ji turėtų eiti struktūrą. Ir jei mes tada reikia pamatyti, jei ji yra struktūrą, jei mes turime jį rasti, mes norime pažvelgti į duomenų vėl ir būtų galima veiksmingai, naudojant duomenis, atsitiktinai jį pasiekti. Tiesiog pažvelgti į duomenys turėtume apie tai, kur tiksliai mes idėja ketina jį rasti maišos lentelę. Dabar iš maišos neigiama Lentelėje yra ta, kad jie tikrai gana neblogai užsisakyti ar rūšiavimo duomenis. Ir iš tiesų, jei jūs pradėsite naudoti juos užsisakyti ar rūšiuoti duomenys jūs prarasite visus iš privalumai anksčiau turėjo požiūriu įterpimo ir ištrynimo. Laikas tampa artimesnis teta n, ir mes iš esmės regresavo į susietą sąrašą. Ir taip mes tik norime naudoti maišos stalai jei mes nerūpi ar Duomenys išrikiuoti. Dėl nuo konteksto, kuriame jūs juos naudoti CS50 tikriausiai nerūpi kad Duomenys išrikiuoti. Taigi maišos lentelė derinys iš dviejų skirtingų vienetų su kuriais mes pažįstami. Pirmasis yra funkcija, kuri mes paprastai vadiname maišos funkciją. Ir maišos funkcija ketina grįžti šiek tiek ne neigiamas sveikasis skaičius, kuris mes paprastai vadiname hashCode, gerai? Antrasis gabalas yra masyvo, kuris yra gali saugoti duomenis tipo mes norite patalpinti į duomenų struktūrą. Mes laikykite ant susiję sąrašą elementą dabar ir tiesiog pradėti su vienu pagrindai maišos lentelė gauti savo galvą aplink jį, ir tada mes gal pūsti jūsų protas šiek tiek, kai mes sujungti masyvus ir susieti sąrašus kartu. Pagrindinė idėja, nors yra mes kai kuriuos duomenis. Mes vykdome tą duomenis per maišos funkcija. Ir taip duomenys apdorojami ir jis išspjauna numerį, gerai? Ir tada su šio skaičiaus mes tiesiog laikyti duomenis norime Laikyti masyvo toje vietoje. Taigi, pavyzdžiui mes turime gal tai maišos lentelės eilučių. Jis gavo 10 elementų, taigi mes gali tilpti 10 eilutes į jį. Tarkime, mes norime maišos Joną. Taigi Jono kaip duomenų norime įterpti į šią maišos lentelė kažkur. Kur mes jį? Na paprastai su masyvas šiol mes tikriausiai būtų įdėti jį į masyvą vietoje 0. Bet dabar mes turime šį naują maišos funkciją. Ir tarkim, kad mes paleisti Joną per šį maišos funkcija ir jis išspjauna 4. Na tai kur mes ketinate norite įdėti Joną. Mes norime įdėti Jonui masyvo vietoje 4, nes jei mes maišos Joną again-- tarkim vėliau mes norite ieškoti ir pamatyti jeigu Jonas egzistuoja šiame maišos table-- visi mes turime daryti yra paleisti per tą patį maišos funkcija, gauti skaičius 4 iš, ir gebėti rasti Joną iš karto mūsų duomenų struktūros. Tai gana gerai. Tarkime, dabar mes tai padaryti vėl norime maišos Pauliui. Mes norime pridėti Paulių į šį maišos lentelėje. Tarkime, kad šį kartą mes paleisti Paulius per maišos funkcija, hashCode kuri yra generuojama yra 6. Na, dabar mes galime įdėti Paulių masyve vietoje 6 d. Ir jei mes turime ieškoti, ar Paulius šiame maišos lentelė, viskas, ką reikia padaryti, tai paleisti Paulius per maišos funkcija vėl ir mes ketiname gauti 6 iš naujo. Ir tada mes tiesiog ieškoti ne masyvo vietoje 6 d. Ar Paulius ten? Jei taip, jis į maišos lentelę. Ar Paulius ne ten? Jis ne maišos lentelę. Tai gana paprasta. Dabar, kaip jūs nustatyti maišos funkcija? Na ten tikrai ne riba Galimų maišos funkcijų. Tiesą sakant, ten yra numeris tikrai, tikrai gerų internete. Yra numerių tikrai, tikrai blogų internete. Tai taip pat gana lengva rašyti blogą vieną. Taigi, kas sudaro geras maišos funkcija, tiesa? Na geras maišos funkciją, turi naudoti tik duomenys yra sumaišomas, ir visi duomenys bus sumaišomas. Taigi mes nenorime naudoti anything-- mes neturime įtraukti nieko kitur, išskyrus duomenų. Ir mes nori naudoti visus duomenis. Mes nenorime, tiesiog naudokite gabalas jo, mes nori naudoti visa tai. Maišos funkciją, turi taip pat deterministinis. Ką tai reiškia? Na, tai reiškia, kad kiekvieną kartą mes perduoti tą patį kūrinį duomenų į maišos funkcija visada gauti tą patį hashCode iš. Jei aš praeiti Joną į maišos funkcija man išeiti 4. Būčiau gali padaryti, kad 10000 kartų ir aš visada gausite 4. Taigi nėra atsitiktiniai skaičiai efektyviai gali būti įtraukti į mūsų maišos tables-- mūsų maišos funkcijų. Maišos funkcija taip pat turėtų tolygiai paskirsto duomenis. Jei kiekvieną kartą paleidus duomenis per maišos funkcija gausite hashCode 0, tai tikriausiai ne toks didelis, tiesa? Jūs tikriausiai norite didelis iš maišos kodai asortimentas. Taip pat dalykai gali būti paskirstytas iš visoje lentelėje. Taip pat būtų puiku, jei tikrai panašūs duomenys, pavyzdžiui, Jono ir Jehonatano gal buvo išplitę pasverti skirtingose ​​vietose maišos lentelė. Tai būtų gražus privalumas. Štai maišos funkcija pavyzdys. Parašiau tai vienas anksčiau. Tai nėra itin geras maišos funkcija dėl priežasčių, kurios tikrai ne padengia vyksta į dabar. Bet tu matai, kas vyksta čia? Atrodo, kad mes paskelbti kintamąjį vadinamas suma ir ją nustatyti lygi 0. Ir tada, matyt, aš darau kažką tol, kol strstr [j] nėra lygus į backslash 0. Ką aš darau čia? Tai iš esmės yra tik dar vienas įgyvendinimo būdas [? strl?] ir aptikti, kai jūs pasiekė stygos galą. Taigi aš neturiu, kad iš tikrųjų apskaičiuoti ilgis eilutę, Aš tik naudojant, kai aš paspauskite Backslash 0 charakteris aš žinau Aš pasiekė eilutę pabaigą. Ir tada aš ruošiuosi laikyti Iteracja per tą eilutę, pridėti strstr [J] Apibendrinant, tada ne pabaigos dienos ketina grįžti sumą mod HASH_MAX. Iš esmės visa tai maišos funkcija darote, yra sudėjus visi ASCII verčių mano eilutė, o tada tai grįžti šiek tiek hashCode modded iki HASH_MAX. Tai tikriausiai dydis mano masyvas, tiesa? Aš nenoriu būti gauti maišos kodai, jei mano masyvas dydžio 10 Aš nenoriu, kad būtų gauti iš maišos kodai 11, 12, 13, aš negaliu įdėti daiktus į tie masyvo vietos, kad būtų neteisėtas. Norėčiau patirti segmentavimo kaltės. Dabar čia yra dar vienas greitai panaikinti. Paprastai jūs tikriausiai nesiruošia noriu rašyti savo maišos funkcijas. Tai iš tikrųjų yra šiek tiek menas, o ne mokslas. Ir ten daug, kad eina į juos. Internetas, kaip sakiau, yra pilnas tikrai gerų maišos funkcijų, ir jūs turėtumėte naudoti prie interneto rasti maišos funkcijos, nes tai tikrai tiesiog rūšies nereikalingas laiko švaistymas sukurti savo. Jūs galite rašyti paprastus tuos bandymų tikslais. Bet kai jūs iš tikrųjų ketiname pradėti maišos duomenis ir saugoti į maišos lentelė esate tikriausiai nori naudoti tam funkciją, kuri buvo sukauptos už jus, kad egzistuoja internete. Jei tiesiog įsitikinkite, paminėti savo šaltinius. Nėra jokios priežasties, kad plagijuoti nieko čia. Kompiuteris mokslo bendruomenė tikrai auga, ir tikrai vertybes atviro kodo, ir tai tikrai svarbu paminėti savo šaltinius, kad žmonės galite gauti priskyrimo darbas, kurį jie daro, kad bendruomenės labui. Taigi visada bus sure-- ir ne tik maišos funkcijas, tačiau paprastai, jei jus naudoti kodą iš išorinio šaltinio, visada nurodo savo šaltinį. Duoti kreditą asmeniui, kuris padarė kai kurių darbų, todėl jūs neturite. Gerai, kad galime peržiūrėti šį maišos lentelė sekundę. Tai kur mes palikome išjungti, kai mes įdėta Jonas ir Paulius į šį maišos lentelė. Ar matote problema čia? Jūs galite pamatyti du. Bet visų pirma, tai jums pamatyti šį galimą problemą? Ką daryti, jei aš maišos Ringo, ir ji Pasirodo, kad po apdorojimo kad duomenys per maišos funkcija Ringo pat generuoja hashCode 6. Aš jau turiu duomenis hashcode-- masyvo vietą 6. Taigi, tai tikriausiai bus šiek tiek iš man problema dabar, tiesa? Mes tai vadiname susidūrimas. Ir susidūrimas įvyksta, kai dvi duomenų dalis, eina per tą patį maišos funkcija duoda tą patį hashCode. Matyt mes vis dar norime gauti tiek vienetų duomenis į maišos lentelė, kitaip nebūtų veikia Ringo savavališkai per maišos funkcija. Mes turbūt norite gauti Ringo į tą masyvą. Kaip mes tai darome, nors, jei jis Paulius ir derlius hashCode 6? Mes nenorime, kad perrašyti Paulių norime Paulius būti ten pat. Taigi mums reikia rasti būdą, kaip gauti elementus į maišos lentelę, vis dar išsaugo mūsų Quick įterpimo ir greitai ieškoti. Ir vienas būdas kovoti su juo yra padaryti kažką vadinama linijinis zondavimo. Naudojant šį metodą, jei mes turime Avarija, gerai, ką mes galime padaryti? Na mes negalime įdėti jį į masyvą vietoje 6, ar kas hashCode buvo sukurtas, tegul įdėti jį ne hashCode plius 1 d. Ir jei tai visiškai tegul įdėti jį į hashCode pridėjus 2. Šio būties naudos, jei jis ne ten, kur mes manome jis yra, ir mes turime pradėti ieškoti, gal mes neturime eiti per toli. Gal mes neturime ieškoti visi n elementai maišos lentelė. Gal mes turime ieškoti iš jų pora. Ir taip mes vis dar linksta link kad vidutinis atvejis yra artimas 1 vs Uždaryti n, tai gal, kad bus dirbti. Taigi pažiūrėkime, kaip tai gali dirbti iš tikrųjų. Ir tegul pamatyti, jei mes galime aptikti gal problema, kuri gali atsirasti čia. Tarkime, mes maišos Bart. Taigi dabar mes ketiname paleisti naują rinkinį eilučių per maišos funkcija, ir mes paleisti Bart per maišos funkcija, gauname hashCode 6. Mes pažvelgsime matome 6 yra tuščia, todėl mes galime įdėti Bart ten. Dabar mes maišos Lisa ir kad taip pat sukuria hashCode 6. Na, dabar, kad mes naudojame šią linijinis zondavimo metodą mes pradedame 6, matome, kad 6 yra pilna. Mes negalime įdėti Lisa 6. Taigi, kur mes einame? Vykime į 7. 7 tuščia, kad veikia. Taigi leiskite įdėti Lisa ten. Dabar mes maišos Homeras ir gauname 7. Gerai gerai žinome, kad 7 Full dabar, todėl mes negalime įdėti Homer ten. Taigi eikime į 8. Ar 8 prieinama? Taip, ir 8 glaudus 7, tad jei mes turime pradėti ieškoti mes nesiruošia eiti per toli. Ir todėl galime įdėti Homer ne 8. Dabar mes maišos Maggie ir grąžina 3, ačiū Dievui, mes galime tiesiog įdėti Maggie ten. Neturime daryti bet rūšiuoti zondavimo už tai. Dabar mes maišos Marge ir Marge pat grįžta 6 d. Na 6 yra pilna, 7 pilna, 8 yra pilna, 9, viskas gerai, ačiū Dievui, 9 yra tuščias. Aš galiu įdėti Marge, 9. Jau matome, kad mes pradedant turėti šią problemą, kur dabar mes pradedant ruožas dalykų natūra iš toli nuo savo maišos kodų. Ir kad iš 1 teta, kad vidutinis atvejis yra pastovus laikas, pradeda gauti šiek tiek more-- pradedant linkę šiek tiek daugiau link teta n. Mes pradedame prarasti, kad privalumas maišos lentelėmis. Ši problema, kad mes tik pamačiau yra kažkas vadinamas grupavimas. Ir kas tikrai blogai apie grupavimo, kad kai jums dabar turi du elementus, kurie yra vienas šalia pusėje ji tampa dar labiau tikėtina, turite du kartus tikimybė, kad jūs ketinate turėti kitą susidūrimo su tuo klasterį, o klasteris augs vienas. Ir jūs nuolat auga ir auga Jūsų tikimybė turėti susidūrimo. Ir galiausiai, tai lygiai taip pat blogai nes ne rūšiavimas duomenis ne visiems. Kita problema, nors tai mes vis tiek, ir iki šiol iki šio taško, mes ką tik buvo tarsi suprasti, kas maišos lentelė, mes vis dar turime tik kambarį už 10 stygos. Jei norime ir toliau maišos Springfield piliečiai, mes galime iš jų 10 tik gauti ten. Ir jei mes stengiamės ir pridėkite 11-ąją ar 12, mes neturime vietą įdėti juos. Mes tiesiog negalėjo būti verpimo aplink apskritimai bando rasti tuščią vietą, ir mes gal įstrigti begalinis ciklas. Taigi šis skolina idėja rūšiuoti kažką vadinama Grupavimo. Ir tai, kai mes ketiname duoti susiję sąrašai atgal į nuotrauką. Ką daryti, jei vietoj laikyti tik patys duomenys masyve, kiekvienas masyvo elementas galėtų palaikykite keletą vienetų Duomenų? Gerai, kad nėra prasmės, tiesa? Mes žinome, kad masyvas gali tik hold-- kiekvieną masyvo elementą gali turėti tik vieną gabalas Duomenų tos duomenų tipą. Bet kas, jei tai duomenų tipas yra susijusi sąrašas, tiesa? Taigi ką daryti, jei kas elementas masyve buvo rodyklė į objektą, susietą sąrašą galvos? Ir tada mes galime sukurti susijusius sąrašai ir augti juos savavališkai, nes susiję sąrašai leidžia mums augti ir trauktis daug daugiau lanksčiai nei masyvas daro. Taigi ką daryti, jei mes dabar naudoja, mes sverto tai, tiesa? Mes pradeda augti šias grandines iš šių matricų vietose. Dabar mes galime tilpti begalinė duomenų kiekis, ar ne begalinis, savavališkai dydis duomenys, į mūsų maišos lentelė be galimybės kada nors veikia į susikirtimo problema. Mes taip pat eliminuojami grupavimas pagal tai daryti. Ir gerai žinome, kad, kai mes įterpti į susietą sąrašą, jei jūs prisimenate iš mūsų vaizdo susijusius sąrašus, pavieniui susiję sąrašai ir dvigubai susiję sąrašus, tai pastovus laikas operacija. Užtenka tik pridedant į priekį. Ir ieškoti, gerai mes žinome kad ieškoti susietoje sąrašą gali būti problema, tiesa? Turime ieškoti jis nuo pradžios iki pabaigos. Nėra atsitiktinių prieiga susietą sąrašą. Bet jei užuot vienas susijęs sąrašas, kur peržvalgos būtų O n, dabar mes turime 10, susijusius sąrašus, arba 1,000 susiję sąrašai, dabar tai O n, padalytą iš 10, arba O n, padalytą iš 1,000. Ir nors mes kalbame Teoriškai apie sudėtingumo mes nepaisyti konstantas, nekilnojamojo Pasaulio šie dalykai iš tikrųjų nesvarbu, tiesa? Mes iš tikrųjų pastebėsite kad tai atsitiks paleisti 10 kartų greičiau, arba 1000 kartų greičiau, nes mes platinti vienas ilgas grandinės visoje 1000 mažesnių grandines. Ir taip kiekvieną kartą mes turime ieškoti per vieną iš šių grandines mes gali ignoruoti 999 grandines Mums nerūpi apie, ir tiesiog ieškoti, kad vienas. Kuris yra vidutiniškai būti 1000 kartų trumpesnis. Ir taip, mes vis dar yra tarsi linksta į šį vidutinis atveju buvimo pastovų laiką, bet tik todėl, kad mes sverto dalijant iš kai didžiulis pastoviu daugikliu. Pažiūrėkime, kaip tai gali realiai atrodo nors. Taigi tai buvo maišos lentelė mes turėjome kol mes paskelbė maišos lentelę, buvo galima saugoti 10 eilutes. Mes neketiname daryti, kad nebėra. Mes jau žinome, apribojimai šio metodo. Dabar mūsų maišos lentelės ketina būti kaip 10 mazgų, rodyklės masyvo vadovams, susijusių sąrašus. Ir dabar jis niekinis. Kiekviena iš šių 10 patarimų yra niekinis. Nėra nieko mūsų šalyje maišos lentelė dabar. Dabar pradėkime įdėti šiek tiek dalykų, į šį maišos lentelė. Ir pažiūrėkime, kaip šis metodas yra ketina pasinaudoti mums truputį. Leiskite dabar maišos Joey. Mes bus paleisti eilutę Joey per maišos funkcija ir mes grįžtame 6 d. Na ką mes darome dabar? Na, dabar dirba su susijusių sąrašus, mes ne dirbti su matricomis. Ir kai mes dirbame su susijusių sąrašus mes žinome, mes turime pradėti dinamiškai patalpų skyrimo ir statybos grandines. Tai tarsi how-- tai yra pagrindinis elementai kuriant susietą sąrašą. Taigi leiskite dinamiškai skirti vietos Joey, ir tada tegul pridėti jį prie grandinės. Taigi dabar pažiūrėkite, ką mes padarėme. Kai mes maišos Joey mes turime hashCode 6. Dabar ne masyvo vietoje 6 žymeklis atkreipia į susietą sąrašą galvos, ir dabar tai tik elementas susijęs sąrašą. Ir tuo, kad mazgas susiję sąrašas Joey. Taigi, jei mes turime ieškoti Joey vėliau, mes tiesiog maišos Joey vėl, mes gauname 6 vėl, nes mūsų maišos funkcija yra deterministinis. Ir tada mes pradėti galvos iš susietų sąrašą pažymėti kaip iki masyvo vietoje 6, ir mes galime pakartoti visoje, kad bando rasti Joey. Ir jei mes sukurti mūsų maišos lentelė efektyviai, ir mūsų maišos funkcija efektyviai platinti duomenis gerai, vidutiniškai kiekvienas iš tuos, kurie susiję sąrašus kiekvienam masyvo vietoje bus 1/10 IF dydis mums tiesiog turėjo ją kaip vieną didžiulis susiję sąrašas su viskuo jame. Jei mes platinti, kad didžiulis susijęs Sąrašas visoje 10 susijusių sąrašus kiekviena sąrašas bus 1/10 dydis. Ir taip 10 kartų greitesnis ieškoti per. Taigi leiskite tai padaryti dar kartą. Leiskite dabar maišos Ross. Ir tarkim Ross, kai mes darome, kad maišos kodą gauname atgal yra 2. Na, dabar mes dinamiškai skirdavo Naujas mazgas, mes įdėti Ross toje mazgas, ir sakome dabar masyvo vietą 2, vietoj to, nukreipta į nuliui, atkreipia dėmesį į susieto galvos sąrašas, kurios tik mazgas yra Ross. Ir mes galime tai padaryti dar vieną kartą, mes gali maišos Rachelę ir gauti hashCode 4. malloc naują mazgas, įdėti į Rachelę mazgas ir pasakyti masyvo vietą 4 dabar atkreipia į galvą Susietos sąrašą, kurio tik elementas atsitinka būti Rachelė. Gerai, bet kas atsitiks, jei turime susidūrimo? Pažiūrėkime, kaip mes tvarkome susidūrimų naudojant atskirą Grupavimo metodas. Leiskite maišos Phoebe. Mes gauti hashCode 6. Mūsų ankstesniame pavyzdyje mes buvome tik saugoti masyve eilutes. Tai buvo problema. Mes nenorime, kad Clobber Joey, ir mes jau ve matyti, kad mes galime gauti tam tikrą grupavimą problemų, jei mes pabandyti ir žingsnis per ir zondas. Bet kas, jei mes tiesiog rūšies gydyti tai tas pats būdas, tiesa? Tai kaip pridėti elementą į susietojo sąrašo galvą. Tegul tik malloc erdvę Phoebe. Mes pasakyti Phoebe naujos žymeklį taškų prie senosios galvos susietą sąrašą ir tada 6 tik atkreipia dėmesį į Naujasis vadovas susietą sąrašą. Ir dabar atrodo, mes pakeitėme Phoebe vietą. Dabar mes galime laikyti du elementai su hashCode 6 ir mes neturime jokių problemų. Štai beveik visi ten yra susiejami. Ir susiejami yra tikrai metodas tai bus efektyviausias, jei Jūs saugoti duomenis maišos lentelė. Tačiau šis derinys matricas ir susiję sąrašai kartu, siekiant sudaryti maišos lentelę tikrai žymiai pagerina savo gebėjimą saugoti didelius kiekius duomenų, ir labai greitai ir efektyviai ieškoti per tą duomenis. Yra dar viena daugiau duomenų struktūra ten kad gali būti net šiek tiek geriau kalbant apie garantuojant kad mūsų įterpimo, išbraukta, ir ieškoti laikai yra net greičiau. Ir mes pamatysime, kad dėl bandymų vaizdo įrašą. Aš Doug Lloyd, tai CS50.