[MUSIC SPILLE] DAVID MALAN: Dette er CS50. Og dette er både starten og end-- som literally-- nesten slutten av uke seks. 

Jeg tenkte jeg skulle dele en litt av en morsom faktum. Jeg har trukket dette opp fra en siste semesterets datasett. Du husker kanskje at vi ber dere på hver p fastsatt skjema dersom du har sett på nettet eller hvis du har deltatt i person. Og her er dataene. Så i dag var veldig mye forutsigbar. Men vi ønsket å tilbringe litt tid med deg likevel. Vil noen liker å formodning hvorfor dette Grafen er så jaggy, opp ned, opp ned, så konsekvent? Hva gjør hver av toppene og trau representerer? 

PUBLIKUM: [uhørbart] DAVID MALAN: Ja. Og mer morsom måte, gud forby, vi holder en forelesning på en fredag i begynnelsen av semesteret, det er hva vi ser skje. Så i dag, vi tar del i en bit mer om datastrukturer. Og for å gi deg mer av en solid mental modell for problemer på fem, som nå er ute. Feilstavelser, hvor vil vi hånd du en tekstfil noen 100.000 pluss engelske ord, og du kommer til å ha å finne ut hvordan å smart laste dem inn i minnet, i RAM, ved hjelp av noen data strukturen av ditt valg. 

Nå er en slik datastruktur kunne være, men sannsynligvis bør ikke være, ganske forenklede lenket liste, som vi innførte forrige gang. Og en lenket liste hadde minst en fordel i forhold til en matrise. Hva er en fordel med en lenket liste kanskje? 

PUBLIKUM: Insertion. 

DAVID MALAN: Insertion. Hva mener du med det? 

PUBLIKUM: Anywhere sammen listen [uhørbart]. 

DAVID MALAN: Good. Så du kan sette inn et element hvor du vil i midten av listen uten å måtte stokke noe, som vi konkluderte, etter vår sortering diskusjoner, er ikke nødvendigvis en god ting, fordi det tar tid å faktisk flytte alle disse menneskene til venstre eller høyre. Og så med en lenket liste, kan du bare bevilge med malloc, en ny node, og deretter oppdatere et par pointers-- to, tre operasjoner max-- og vi er i stand til å spor noens i hvor som helst i en liste. 

Hva annet var en fordel om en lenket liste? Yeah? 

PUBLIKUM: [uhørbart] DAVID MALAN: Perfect. Perfect. Det er veldig dynamisk. Og at du ikke forplikter, på forhånd, til en viss fast størrelse blings av minne, som du ville ha til med en rekke, oppsiden som er at du kan tildele noder bare på etterspørsel og dermed bruke bare så mye plass som du faktisk trenger. Derimot med en rekke, kanskje du uhell bevilge for lite. Og da er det bare å gå å være en smerte i nakken å omfordele en ny større array, kopiere alt over, frigjøre den gamle array, og deretter gå om virksomheten din. Eller verre, kan du fordele måte mer minne enn du faktisk trenger, og så kommer du til å ha en veldig grisgrendt array, så å si. 

Så en lenket liste gir deg disse fordelene av dynamikk og fleksibilitet med innsettinger og slettinger. Men sikkert det må være en pris som er betalt. Faktisk et av temaene utforskes på quiz null var et par av de avveiningene vi har sett så langt. Så hva er en pris som er betalt eller Ulempen med en lenket liste? Yeah. 

PUBLIKUM: Ingen random access. 

DAVID MALAN: Ingen random access. Men hvem bryr seg? Random access høres ikke overbevisende. 

PUBLIKUM: [uhørbart] DAVID MALAN: Nettopp. Hvis du vil ha en viss algorithm-- og la meg faktisk foreslå binært søk i særdeleshet, hvilke er en vi har brukt ganske bit-- hvis du ikke har random access, du kan ikke gjøre det enkel aritmetikk for å finne ut midt element og hoppe rett til det. Du har i stedet for å begynne på det første element og lineært søke fra venstre til høyre hvis du ønsker å finne midten eller noe annet element. 

PUBLIKUM: Det tar nok mer minne. 

DAVID MALAN: Tar mer minne. Hvor er det ekstra kostet kommer fra i minnet? 

PUBLIKUM: [uhørbart] DAVID MALAN: Nettopp. I dette tilfellet her, vi hadde en lenket liste for heltall, og likevel er vi dobling mengden minne vi trenger ved også å lagre disse pekerne. Nå mindre av en stor avtale som dine structs få større og du lagrer ikke et tall, men kanskje en student eller en annen gjenstand. Men poenget forblir sikkert. Og så en rekke av operasjoner på lenkede lister ble kalt var stor O av N- lineær. Ting som innsetting eller søk eller sletting i tilfelle et element skjedde til å være helt på slutten av listen enten det er sortert eller ikke. 

Noen ganger kan du ha flaks og i så nedre grense på disse operasjonene kanskje også konstant tid hvis du er alltid ser på det første elementet, f.eks. Men til slutt, vi lovet for å oppnå den hellige gral av datastrukturer, eller et anslag av disse, ved hjelp av konstant tid. Kan vi finne elementer eller legge til elementer eller fjerne elementer fra en liste? Vi skal se ganske snart. Og det viser seg at en av de mekanismene vi er kommer til å begynne å bruke i dag, årlig bruk i p satt fem, er faktisk ganske kjent. For eksempel, hvis dette er en gjeng av eksamens bøker, hver av hvilke har en student først navn og etternavn på den, og jeg plukke dem opp fra ved slutten av en undersøkelse, og de er alle ganske mye i en tilfeldig rekkefølge, og vi ønsker å gå om sortering disse eksamenene slik at når gradert det er bare mye enklere og raskere å levere dem ut igjen til studenter alfabetisk. Hva ville instinktene dine være for en haug av eksamener som dette? 

Vel, hvis du er som meg, du kan se at dette er m, så jeg kommer til å liksom sette dette inn i, hvis dette er mitt bord eller min etasje der Jeg sprer ting out-- eller min matrise really-- Jeg kan sette alle Ms der inne. Oh. Her er en A. Så jeg kan sette Som over her. Oh. Her er en annen A. Jeg kommer å sette det over her. Her er en Z. Her er en annen M. Og så Jeg kan begynne å lage hauger som dette. Og så kanskje jeg ville gå inn senere og liksom veldig pirkete-ly sort de enkelte hauger. Men poenget er at jeg ville se på inngangen at jeg er overlevert og jeg ville gjøre noen beregnes beslutning basert på den inngangen. Hvis den starter med A, sette den over der. Hvis den starter med Z, sette den over der, og alt i mellom. 

Så dette er en teknikk som er generelt kjent som hashing-- H-A-S-H-- som betyr vanligvis tar som innspill og hjelp som innspill til å beregne en verdi, vanligvis et tall, og at nummeret er indeksen til en lagrings beholder, som en matrise. Så med andre ord, jeg kan ha en hash-funksjon, som jeg gjør i mitt hode, at hvis jeg ser noen er navn som starter med A, Jeg kommer til å kartlegge at til null i hodet mitt. Og hvis jeg ser noen med Z, jeg er kommer til å kartlegge det til 25 i hodet mitt og deretter sette det inn den siste mest haug. 

Nå, hvis du tenker på ikke hjernen min men et C-program, hva tallene kunne du er avhengig av for å oppnå det samme resultatet? Med andre ord, hvis du hadde ASCII karakter A, hvordan kan du bestemme hva bøtte til å sette den i? Du har sannsynligvis ikke vil sette det inn i bøtte 65, som ville være der borte for ingen god grunn. Hvor ønsker du å sette A i form av sin ASCII-verdi? Hvor ønsker du å gjøre til sin ASCII verdi å komme opp med en smartere bøtte å sette den i? 

PUBLIKUM: Minus A. 

DAVID MALAN: Yeah. Så minus A eller minus spesielt 65 hvis det er en kapital A. Eller 98 dersom det er en liten bokstav a. Og slik som ville tillate oss å, veldig enkelt og veldig arithmetically, sette noe inn i en bøtte sånn. Så det viser seg at vi faktisk gjør dette så godt selv med spørrekonkurranser. 

Så du kanskje husker du sirklet din undervisning stipendiat navn på omslaget. Og TF s navn ble organisert i disse kolonnene alfabetisk, vel, tro det eller ei, når alle 80 pluss av oss kom sammen den andre natt til klasse, det siste trinnet i vår sensureringen er til hasj quizer inn i en stor plass på bakken ved [uhørbart] og å legge alles quizer ut i nøyaktig rekkefølge av deres TF største navn på omslaget, fordi da er det mye enklere for oss å søke gjennom at bruk av lineær søke eller annen form for klokskap for en TF å finne hans eller hennes studentenes quizer. 

Så denne ideen om hashing at du får se er ganske kraftig er faktisk ganske vanlig og svært intuitivt, mye som kanskje dele og erobring var i uke null. Jeg spoler frem til hackathon et par år siden. Dette var Zamyla og et par andre gratulasjons ansatte studenter som de kom. Og vi hadde en hel haug med folding tabeller det med navnelapper. Og vi hadde navneskilt organisert med som som der borte og Zs der borte. Og så en av TFS veldig smart skrev dette som instruksjonene for dagen. Og i uke 12 av semesteret dette alle gjort perfekt forstand og alle visste hva de skal gjøre. Men når du har i kø på samme måte, du implementere samme oppfatningen av en hash. Så la oss formalisere det litt. Her er en matrise. Det er trukket til å være litt wide bare for å skildre, visuelt, at vi kan sette strenger i noe sånt som dette. Og denne matrisen er klart av størrelse 26 totalt. Og ting blir kalt Tabellen vilkårlig. Men dette er bare en kunstners gjengivelse av hva en hash tabell kan være. 

Så en hash table nå kommer til å være et høyere nivå datastruktur. På slutten av dagen vi er i ferd med å se at du kan implementere en hash table, som er mye som check-in line på et hackathon mye som dette Tabellen brukes til sortering eksamen bøker. Men en hash table er slag av dette høye nivået konsept som kan bruke en matrise under panseret til å gjennomføre det, eller det kan brukes en lengde liste, eller enda kanskje noen andre datastrukturer. Og nå som er den theme-- taking noen av disse grunnleggende ingredienser som en matrise og denne bygningen blokkerer nå en lengde liste og se hva annet vi kan bygge på toppen av dem, som ingredienser inn i en oppskrift, som gjør mer og mer interessante og nyttige endelige resultatene. 

Så med hash table vi kan gjennomføre det i minnet billedlig som dette, men hvordan kan det faktisk være kodet opp? Vel, kanskje så enkelt er dette. Hvis KAPASITET i store bokstaver, er bare noen constant-- for eksempel 26, for 26 bokstavene i det alphabet-- Jeg kan kalle min variabel tabellen, og jeg kan hevde at jeg kommer til å sette char stjerner der, eller streng. Så det er så enkelt som dette hvis du ønsker å implementere en hash table. Og likevel, dette er egentlig bare en matrise. Men igjen, en hash Bordet er nå hva vi vil kalle en abstrakt datatype som er bare liksom en konseptuell lagdeling på toppen på noe mer dagligdagse nå liker en matrise. 

Nå, hvordan kan vi gå om å løse problemer? Vel, tidligere hadde jeg luksusen for å ha nok tabellplass her slik at jeg kunne sette quizer hvor som helst jeg ville. Så som kan gå her. Zs kan gå her. Ms kan gå her. Og da jeg hadde litt ekstra plass. Men dette er litt av en utro retten nå fordi denne tabellen, hvis jeg virkelig tenkte på det som en matrise, er bare kommer til å være av noen fast størrelse. 

Så teknisk sett, hvis jeg drar opp en annen student quiz og se, oh, denne personens navn som begynner med en A også, Jeg ønsker slags å sette det der. Men så snart jeg satte den der, hvis denne tabellen faktisk representerer en matrise, Jeg kommer til å være overordnede eller clobbering hvem denne studentens quiz er. Høyre? Hvis dette er en matrise, bare én ting kan gå i hver av disse celler eller elementer. Og så jeg slags har å velge og vrake. 

Nå tidligere Jeg slags jukset og gjorde dette eller jeg bare slags stablet dem over hverandre. Men det kommer ikke til å fly i kode. Så hvor kan jeg sette andre eleven hvis navn er A hvis alt jeg hadde er dette tilgjengelig tabellplass? Og jeg har brukt tre spilleautomater og det ser ut som det er bare noen få andre. Hva kan du gjøre? PUBLIKUM: [uhørbart] DAVID MALAN: Yeah. Kanskje la oss bare holde det enkelt. Høyre? Det passer ikke der jeg ønsker å sette den. Så jeg kommer til å si det teknisk hvor en B ville gå. Nå, selvfølgelig, jeg begynner å male meg selv inn i et hjørne. Hvis jeg får til en student hvis navn er faktisk B, nå B kommer til å bli flyttet litt fremover, som kan skje, Jepp, Hvis dette er en B, nå har det å gå her. 

Og så dette svært raskt kan bli problematisk, men det er en teknikk som faktisk er henvist til som lineær sentret, der du bare vurdere din array å være langs linjen. Og du bare slags sonde eller inspisere alle tilgjengelige element på jakt etter en ledig flekk. Og så snart du finner en, slippe deg det der. 

Nå, prisen blir betalt nå til denne løsningen er hva? Vi har en fast størrelse matrise, og når jeg setter navn inn i det, i hvert fall i utgangspunktet, hva som er kjøretiden til innsetting for å sette studentenes quizer i de rette skuffer? Big O av hva? 

PUBLIKUM: n. DAVID MALAN: Jeg hørte big O av n. Ikke sant. Men vi skal erte hverandre hvorfor i bare et øyeblikk. Hva annet kan det være? 

PUBLIKUM: [uhørbart] DAVID MALAN: Og la meg gjøre det visuelt. Så antar at dette er bokstaven S. 

PUBLIKUM: Det er én. DAVID MALAN: Det er én. Høyre? Dette er en matrise, hvilke betyr at vi har random access. Og hvis vi tenker på dette som null, og dette som 25, og vi innser det, oh, her er mitt innspill S, Jeg kan sikkert konvertere S, en ASCII-tegn, til et tilsvarende antall mellom null og 25 og deretter umiddelbart sette det der det hører hjemme. 

Men selvfølgelig, så snart jeg får til andre personen som har navnet er A eller B eller C til slutt, hvis jeg har brukt lineær sondering som min løsning, kjøretiden til innsetting i verste fall faktisk kommer til å tilfalle inn i hva? Og jeg fikk høre det her riktig tidlig. PUBLIKUM: [uhørbart] DAVID MALAN: Så det er n faktisk en gang du har et tilstrekkelig stort datasett. Så, på den ene side, hvis klyngen er stor nok og dataene dine er sparsom nok, du få denne vakre konstant tid. Men så snart du begynner få flere og flere elementer, og bare statistisk du får flere mennesker med bokstaven En som navnet eller bokstaven B, det kunne potensielt tilfaller til noe mer lineær. Så ikke helt perfekt. Så kan vi gjøre bedre? 

Vel, hva var vår løsning før når vi vil ha mer dynamikk enn noe sånt som en matrise tillatt? PUBLIKUM: [uhørbart] DAVID MALAN: Hva gjorde vi innføre? Yeah. Så en lenket liste. Vel, la oss se hva en koblet Listen kan gjøre for oss i stedet. Vel, la meg foreslå at vi tegne bildet som følger. Nå er dette en annerledes bilde fra et eksempel fra en annen tekst, faktisk, at er faktisk å bruke en matrise av størrelse 31. Og denne forfatteren rett og slett bestemte seg til hasj strenger ikke basert på personens navn, men basert på deres fødselsdatoer. Uavhengig av måneden, de skjønte hvis du er født på den første i en måned eller den 31. i en måned, forfatteren vil hash basert på denne verdien, for derved å spre navnene ut en smule mer enn bare 26 flekker kan tillate. Og kanskje det er litt mer ensartet enn å gå med alfabetiske bokstaver, fordi selvfølgelig er det sannsynligvis flere mennesker i verden med navn som starter med A enn absolutt noen andre bokstaver i alfabetet. Så kanskje dette er litt mer ensartet, forutsatt en jevn fordeling av babyer over en måned. 

Men, selvfølgelig, dette er fortsatt mangelfull. Høyre? Vi har kollisjoner. Flere mennesker i denne datastruktur er fortsatt som har samme fødsels minst du er uavhengig av måned. Men hva har forfatteren gjort? Vel, det ser ut som om vi har en rekke på venstre side trekkes vertikalt, men det er bare en kunstners gjengivelse. Det spiller ingen rolle hvilken retning du tegne en matrise, er det fortsatt en matrise. Hva er dette en rekke tilsynelatende? 

PUBLIKUM: Linked-listen. 

DAVID MALAN: Yeah. Det ser ut som det er en utvalg av lenket liste. Så igjen, til dette punktet sortering å bruke disse datastrukturer nå som ingredienser til mer interessante løsninger, du kan absolutt ta en fundamental, som en matrise, og deretter ta noe mer interessant som en lenket liste og selv sette dem sammen til en enda mer interessant datastruktur. Og ja, dette også ville kalles en hash table, hvorved matrisen er egentlig hash table, men at hash tabellen har kjeder, så å si, som kan vokse eller krympe basert på antall elementer du vil sette inn. 

Nå følgelig hva som er kjøretiden nå? Hvis jeg ønsker å sette inn noen som har bursdag 31. oktober hvor kommer han eller hun gå? OK. Helt nederst der det står 31. Og det er perfekt. Det var konstant tid. Men hva hvis vi finner noen andre som har bursdag er, la oss se, Oktober, november, desember 31? Hvor er han eller hun kommer til å gå? Samme greia. To skritt skjønt. Det er konstant skjønt er det ikke? OK. I øyeblikket er det. Men i det generelle tilfelle, jo flere mennesker vi legger til, sannsynlighets, skal vi å få flere og flere kollisjoner. 

Nå er dette en liten bedre fordi teknisk nå mine kjedene kan være i verste fall hvor lenge? Hvis jeg setter n folk inn i dette mer sofistikert datastruktur, n mennesker, i verste fall kommer det til å være n. Hvorfor? 

PUBLIKUM: Fordi hvis alle har samme bursdag, de kommer til å være en linje. DAVID MALAN: Perfect. Det kan være litt contrived, men virkelig i verste fall hvis alle har samme bursdag, gitt de inngangene du har, du kommer til å ha en massivt lang kjede. Og så, kan du kalle det en hash table, men egentlig er det bare en massiv lenket liste med en hel masse bortkastet plass. Men generelt, hvis vi antar at minst bursdager er uniform-- og det er sannsynligvis ikke. Jeg gjør det opp. Men hvis vi antar, for skyld diskusjonen at de er, da i teorien, hvis Dette er den vertikale representasjon av tabellen, vel så forhåpentligvis du er kommer til å få kjeder som er, vet du, omtrent samme lengde, hvor hver av disse representerer en dag i måneden. 

Nå hvis det er 31 dager i måneden, det betyr at min kjøretid virkelig er stor O av n over 31, som føles bedre enn lineær. Men hva var en av våre forpliktelser et par uker siden når det kom til å uttrykke kjøretiden til en algoritme? Bare bare se på høy ordre sikt. Høyre? 31 er definitivt nyttig. Men dette er fortsatt stor O av n. Men et av temaene av problemet satt fem kommer til å være til erkjenner at absolutt, asymptotisk, teoretisk dette datastruktur er ikke bedre enn bare en massiv lenket liste. Og ja, i verste fall, dette hash table kan tilfalle inn i det. 

Men i den virkelige verden, med oss ​​mennesker at egne Mac eller PC eller hva og kjører virkelige verden programvare på virkelige verden data, hvilken algoritme du kommer til å foretrekke? Den som tar slutt fremgangsmåte eller en som tar n dividert med 31 trinn å finne noen stykke data eller å lete opp litt informasjon? Jeg mener, absolutt de 31 merker en forskjell i den virkelige verden. Det er 31 ganger raskere. Og vi mennesker er sikkert kommer til å sette pris på det. 

Så skjønner motsetningen der mellom faktisk snakke om ting teoretisk og asymptotisk som definitivt har verdi som vi har sett, men i den virkelige verden, Hvis du bryr deg om bare å gjøre menneskelig glad for generelle innganger, du kan godt vil godta det faktum at, ja, dette er lineær, men det er 31 ganger raskere enn lineær kan være. Og enda bedre, vi trenger ikke bare å gjøre noe vilkårlig som en fødselsdato, vi kunne bruke litt mer tid og kløkt og tenke på hva vi kan gjøre, gitt en persons navn og kanskje deres fødselsdato for å kombinere de ingredienser for å finne ut noe som er virkelig mer enhetlig og mindre jaggy, så å si enn dette bildet tiden antyder det kan være. Hvordan kan vi implementere dette i koden? Vel, la meg foreslå at vi bare låne noen syntaks vi har brukt et par ganger så langt. Og jeg kommer til å definere en node, som igjen er en fellesbetegnelse for bare noen container for noen datastruktur. Jeg kommer til å foreslå at en streng som skjer der inne. Men vi kommer til å begynne å ta de som trening hjul av nå. 

Ingen flere CS50 biblioteket egentlig, med mindre du vil å bruke den for den endelige Prosjektet, som er greit, men nå skal vi trekke tilbake gardin og sier det er bare en char stjerne. Så ordet det kommer til å være personens navn i spørsmålet. Og nå har jeg en link her til den neste noden slik at disse representerer hver av nodene i kjeden, eventuelt, av en lenket liste. 

Og nå hvordan kan jeg erklære hash bordet selv? Hvordan erklærer jeg hele denne strukturen? Vel, egentlig, mye som jeg brukte en peker til bare det første element i en liste før, på samme måte kan jeg bare si Jeg trenger bare en haug med pekere å gjennomføre hele denne hash table. Jeg kommer til å ha en rekke kalt tabell for hash table. Det kommer til å være av størrelse kapasitet. Det er hvor mange elementer kan passe i den. Og hvert av disse elementer i denne matrise kommer til å være en node stjerne. Hvorfor? Vel, per dette bildet, hva jeg er implementere hash table som effektivt i begynnelsen er bare denne matrisen som vi har trukket vertikalt, hver av hvis firkanter representerer en peker. At de som har skråstreker gjennom dem er bare null. Og de som har piler som går til høyre er faktiske pekere til faktiske noder, ergo starten på en lenket liste. 

Så her er altså hvordan vi kan implementere en hash tabell som implementerer separat kjeding. Nå kan vi gjøre bedre? Greit jeg lovet sist gang vi kunne oppnå konstant tid. Og jeg slags ga deg konstant tid her, men da sa egentlig ikke konstant tid fordi det er fremdeles avhengig av den totale antall elementer du legge inn i datastrukturen. Men sett at vi gjorde dette. La meg gå tilbake til skjermen over her. La meg også projisere dette opp her, klar skjermen, og antar at jeg gjorde dette. Anta at jeg ønsket å påføre navnet Daven i inn i min datastruktur. 

Så jeg ønsker å sette inn en streng Daven inn i datastrukturen. Hva om jeg ikke bruker en hash table, men jeg bruker noe som er mer trelignende som et familietre, der du har litt rot på toppen og deretter noder og bladene som går nedover og utover. Anta så at jeg vil sette inn Daven s i hva som er i dag en tom liste. Jeg kommer til å gjøre følgende: Jeg er kommer til å skape en node i denne familien trelignende datastruktur som ser litt som denne, hver av hvilke rektangler har, la oss si, for nå 26 elementer i den. Og hver av cellene i denne matrisen kommer å representere bokstaven i et alfabet. 

Spesielt kommer jeg til å behandle dette er A, så B, så C, deretter D, denne her. Så dette kommer til å effektivt representerer bokstaven D. Men for å sette inn alle Daven s nevne jeg trenger å gjøre litt mer. Så jeg først kommer til hasj, så å si. Jeg kommer til å se på den første bokstaven i Daven s, som er åpenbart en D, og jeg kommer til å tildele en node som ser som dette-- en stor rektangel stor nok til å passe hele alfabetet. 

Nå D er gjort. Nå A. D-A-V-E-N er målet. Så nå hva jeg kommer til å gjøre dette. Så snart jeg begynte D varsel det er ingen pekeren der. Det er søppel verdier i øyeblikket, eller jeg kan initialisere den til null. Men la meg holde det gående med denne ideen om å bygge et tre. La meg fordele enda en av disse noder som har 26 elementer i den. 

Og vet du hva? Hvis dette bare er en node i minnet som Jeg opprettet med malloc, ved hjelp av en struct som vi vil snart se, Jeg kommer til å gjøre dette-- Jeg kommer til å trekke en pil fra det som representerte D ned til denne nye node. Og nå, først neste brev i Daven navn, V-- D-A-V-- jeg kommer til å gå videre og tegne en annen node som dette, hvorved, de V-elementer, som her vi vil trekke for instance-- whoops. Vi vil ikke trekke det. Det kommer til å gå her. 

Så skal vi til anser dette for å være V. Og deretter ned her vi kommer til å indeksere ned fra V inn i hva vi vil vurdere E. Og så herfra vi kommer til å gå har en av disse nodene her. Og nå har vi et spørsmål å besvare. Jeg må liksom vise at vi er på slutten av strengen Daven. Så jeg kunne bare la det null. 

Men hva hvis vi har Daven s fullt navn også, som er, som vi har sagt, Davenport? Så hva om Daven er faktisk en delstreng, et prefiks på en mye lengre streng? Vi kan ikke bare permanent sier ingenting kommer å gå dit, fordi vi kunne aldri sette inn et ord som Davenport inn i dette datastruktur 

Så hva vi kunne gjøre i stedet er behandling av hvert av disse elementene så kanskje å ha to elementer på innsiden av dem. Den ene er en peker, ja, som jeg har gjort. Slik at hver av disse boksene er ikke bare en celle. Men hva hvis toppen one-- bunnen ens kommer til å være null, fordi det er ingen Davenport ennå. Hva om den øverste er noen spesiell verdi? Og det kommer til å være litt vanskelig å trekke det på denne størrelsen. Men antar at det er bare en hake. Sjekk. D-A-V-E-N er en streng i dette datastruktur. 

I mellomtiden, hvis jeg hadde mer plass her, kunne jeg gjøre P-O-R-T, og jeg kunne sette innsjekking noden som har bokstaven T helt på slutten. Så dette er et massivt kompleks utseende datastruktur. Og min håndskrift absolutt ikke hjelpe. Men hvis jeg ønsket å sette inn noe annet, vurdere hva vi ville gjøre. Hvis vi ønsket å sette David inn, vi vil følge samme logikk, D-A-V, men nå vil jeg peke på det neste element ikke fra E, men fra jeg til D. Så det kommer til å bli flere noder i dette treet. Vi kommer til å ha samtale malloc mer. Men jeg ønsker ikke å gjøre en komplett rot av dette bildet. Så la oss i stedet se på en som er blitt pre-formulert som dette med ikke prikk, prikk, prikker, men bare forkortede arrays. Men hver av nodene i dette treet her oppe representerer den samme thing-- en rekke Ray størrelse 26. 

Eller hvis vi ønsker å være virkelig riktig nå, hva hvis noen navn som en apostrof, la oss anta at hver node har faktisk som 27 indekser i den, ikke bare 26. Så dette nå kommer til å være en data struktur kalt en trie-- T-R-I-E. En trie, som er visstnok historisk et smart navn for et tre som er optimalisert for gjenfinning, som selvfølgelig er stavet med en jeg-E, så det er trie. Men det er historien om den trie. 

Så en trie er dette trelignende data struktur som et familietre som til slutt oppfører seg sånn. Og her er bare et eksempel på en hel haug med andre personers navn. Men spørsmålet nå på hånden er hva har vi oppnådd ved å innføre uten tvil en mer komplisert datastruktur, og en, ærlig, bruker den mye minne. 

For selv om, i øyeblikket, jeg er bare ved hjelp av D's pekeren og A og V og Es og Ns, Jeg kaster bort en pokker for mye minne. Men hvor jeg tilbringer en ressurs, Jeg pleier å gjøre å få tilbake en annen. Så hvis jeg tilbringer mer plass, hva er nok håp? At jeg tilbringer mindre hva? PUBLIKUM: Mindre tid. DAVID MALAN: Tid. Nå hvorfor kan det være? Vel, hva er innsetting tid, i form av store O nå, av et navn som Daven eller Davenport eller David? Vel, Daven var fem trinn. Davenport ville være ni trinn, så det ville være noen flere trinn. David ville være fem trinn også. Så de er konkrete tall, men sikkert er det en øvre grense på Lengden på noens navn. Og ja, i problemet sett av fem spesifikasjonen, vi kommer til å foreslå at det er noe det er 40-some-odd tegn. 

Realistisk, har ingen en uendelig langt navn, det vil si at lengden av en navngi eller lengden på en streng vi kan har visse tilstanden strukturen er uten tvil hva? Det er konstant. Høyre? Det kan være en stor konstant som 40-noe, men det er konstant. Og det har ingen avhengighet av hvor mange andre navn er i denne datastruktur. Med andre ord, hvis jeg ønsket å nå sette Colton eller Gabriel eller Rob eller Zamyla eller Alison eller Belinda eller noen andre navn fra de ansatte i disse dataene struktur, er kjøretiden med å sette inn andre navn kommer til å være på alle påvirket av hvor mange andre elementer er i datastrukturen allerede? Det er ikke. Høyre? Fordi vi er effektivt ved hjelp Dette multi-layer hash table. Og kjøretiden til en hvilken som helst av disse operasjoner ikke er avhengig av antall elementer som er i datastrukturen eller som eventuelt kommer å være i datastrukturen, men av lengden av det spesifikt? 

Strengen blir settes inn, noe som gjør gjøre dette asymptotisk konstant tid-- big O av en. Og ærlig talt, bare i den virkelige verden, dette betyr å sette inn Daven navn tar som fem trinn, eller Davenport ni trinn, eller David fem trinn. Det er ganske utrolig små løpetider. Og, ja, det er en veldig god ting, spesielt når det er ikke avhengig av den totale antall elementer i det. Så hvordan kan vi implementere dette slags struktur i koden? Det er litt mer kompleks, men fortsatt er det bare en anvendelse av grunnleggende byggesteiner. Jeg kommer til å omdefinere oss node som følger: bool kalt word-- og dette kan kalles noe. Men bool representerer hva jeg trakk som en hake. Ja. Dette er slutten av en streng i dette datastruktur. 

Og, selvfølgelig, noden stjerne Det er med henvisning til barn. Og, ja, akkurat som et familietre, du ville vurdere nodene som henger utenfor av bunnen av en moder element til å være barn. Og slik at barna kommer til å være en matrise på 27, den 27. en bare å være for apostrof. Vi kommer til å sortere av spesiell sak det. Så du kan ha visse navn med apostrofer. Kanskje til og med bindestrek bør gå inn der, men du vil se i p sett fem vi bare omsorg om bokstaver og apostrofer. 

Og så hvordan gjør du representerer datastrukturen i seg selv? Hvordan kan representere deg roten av dette trie, så å si? Vel, akkurat som med en lenket liste, du trenger en peker til det første elementet. Med en trie du trenger bare én Peker til roten av dette trie. Og derfra kan du hasj vei ned dypere og dypere til alle andre knutepunktet i strukturen. Så enkelt med denne boksen vi representerer at struct. 

Nå Meanwhile-- Oh, spørsmålet. 

PUBLIKUM: Hva er bool ord? 

DAVID MALAN: Bool ordet er nettopp dette C inkarnasjon av hva jeg beskrev I denne boksen her, når Jeg begynte å splitte hver av de tabellens elementer i to deler. Den ene er en peker til den neste noden. Den andre har til å bli noe sånt som en avkrysningsboks å si ja, det er en Ordet Daven som ender her, fordi vi ikke ønsker, i øyeblikket, Dave. 

Selv om Dave kommer til å bli en legitime ord, han er ikke i trie ennå. Og D er ikke et ord. Og D-A er ikke et ord eller et navn. Så hake indikerer bare når du treffe denne node er forrige banen tegn faktisk en streng som du har satt inn. Så det er all bool det gjør for oss. 

Eventuelle andre spørsmål på prøver? Yeah. 

PUBLIKUM: Hva er overlapping? Hva hvis du har en Dave og Daven? DAVID MALAN: Perfect. Hva hvis du har en Dave og Daven? Så hvis vi setter inn, sier et kallenavn, for David-- Dave-- D-A-V-E? Dette er faktisk super enkelt. Så vi bare kommer til å ta fire trinn. D-A-V-E. Og hva må jeg gjøre når jeg treffer det fjerde node? Bare kommer til å sjekke. Vi er allerede godt å gå. Ferdig. Fire trinn. Konstant tid asymptotisk. Og nå har vi indikert at både Dave og Daven er strenger i strukturen. Så det er ikke et problem. Og legg merke til hvordan tilstedeværelsen av Daven ikke gjøre det ta noe mer tid eller mindre tid for Dave og vice versa. 

Så hva annet kan vi nå gjøre? Vi har brukt denne metaforen før av skuffer som representerer noe. Men det viser seg at en stabel med magasiner er faktisk demonstrative av en annen abstrakt data type-- et høyere nivå datastrukturen at på slutten av dagen er bare som en matrise eller en lenket liste eller noe mer verdslig. Men det er en mer interessant konseptuelle konsept. En stabel, som disse skuffer her i Mather, er generelt kalt bare at-- en stabel. 

Og i denne type datastruktur du har to operations-- du har en som heter push for legge noe til stakken, som å sette en annen skuff Tilbake på toppen av bunken. Og så pop, som betyr at du ta den øverste skuffen av. Men hva er nøkkelen om en stabel er at det har denne merkelige kjennetegn. Som spisesalen ansatte er omorganisere skuffene for neste måltid, hva som kommer til å være sant om hvordan elevene samhandle med denne datastruktur? PUBLIKUM: De kommer til å sprette en av. DAVID MALAN: De kommer til å pop en av, forhåpentligvis toppen. Ellers er det bare slags dum å gå helt ned til bunnen. Høyre? Datastrukturen ikke virkelig tillate du å ta tak i nederste skuff minst enkelt. Så det er denne merke egenskapen til en stabel at det siste elementet i er kommer til å bli den første ut. Og dataforskere kaller Dette LIFO-- sist inn, først ut. Og det faktisk har interessante programmer. Det er ikke nødvendigvis så opplagt som noen andre, men det kan faktisk være nyttig, og det kan faktisk bli implementert i et par forskjellige måter. 

Så en, og faktisk, la meg ikke til å dykke inn i den. La oss gjøre dette i stedet. La oss se på en som er nesten det samme idé, men det er litt mer rettferdig. Høyre? Hvis du er en av disse fan gutter eller jenter som virkelig liker Apple-produkter og du våknet opp på 3:00 til å stille opp på noen butikk å få den aller nyeste iPhone, du kan ha kø som dette. 

Nå en kø er veldig bevisst navngitt. Det er en linje fordi det er noen rettferdighet til det. Høyre? Det ville slags sugd hvis du har fikk det først på Apple Store men du er effektivt den nederste skuffen fordi Apple ansatte deretter pop den siste personen som fikk faktisk i kø. Så stabler og køer, selv om det funksjonelt de er slag av same-- det er bare denne samlingen av ressurser som finnes i kommer til å vokse og shrink-- det har denne rettferdighet aspekt til det, i hvert fall i den virkelige verden, hvor operasjonene du trener er fundamentalt forskjellig. En stack-- en kø rather-- sies å ha to operasjoner: n køen og d køen. Eller du kan ringe dem en rekke ting. Men du bare ønsker å fange forestillingen om at man legger til og én er til syvende og sist å subtrahere. 

Nå under panseret, både stakken og en kø kunne gjennomføres hvordan? Vi vil ikke gå inn koden det fordi høyere nivå Tanken er liksom mer opplagt. Jeg mener, hva gjør mennesker? Hvis jeg er den første personen på Apple Lagre og dette er inngangsdøren, du vet, jeg kommer til å stå her. Og neste persons kommer til å stå her. Og neste persons kommer til å stå her. Så hva datastruktur gir seg til en kø? 

PUBLIKUM: En kø. DAVID MALAN: Vel, en kø. Jada. Hva annet? 

PUBLIKUM: En lenket liste. 

DAVID MALAN: Et koblet listen du kan implementere. Og en lenket liste er fint fordi da den kan vokse vilkårlig lange motsetning å ha noen fast antall mennesker i butikken. Men kanskje et fast antall plasser er legitim. Fordi hvis de bare har som 20 iPhones på den første dagen, kanskje de trenger bare et utvalg av størrelse 20 for å representere at køen, som er bare å si nå når vi begynner å snakke om disse høyere nivå problemer, du kan gjennomføre det i en rekke måter. Og det er sannsynligvis bare kommer til å være en avveining i rom og tid eller bare i din egen kode kompleksitet. 

Hva med en stabel? Vel, en stabel, vi har sett altfor kan bare være disse skuffene. Og du kan implementere dette en matrise. Men på et tidspunkt hvis du bruker en matrise, hva kommer til å skje med magasinene du prøver å legge ned? OK. Du bare kommer til være i stand til å gå så høyt. Og jeg tror i Mather de er faktisk innfelt i den åpningen. Så ja, det er nesten som Mather bruker en rekke fast størrelse, fordi du bare kan passe så mange skuffer i at åpningen i veggen ned under folks knær. Og slik som kan være sies å være en matrise, men vi kunne sikkert implementere at mer generelt med en lenket liste. 

Vel, hva om en annen datastruktur? La meg trekke opp en annen visuell her. Noe sånt hva med denne her? Hvorfor kan det være nyttig å ha ikke noe så fancy som en trie, som vi så hadde disse svært brede noder, som hver er i en matrise? Men hva hvis vi gjør noe mer ganske enkelt, som en gammel skole familietre, hver av hvis noder her er bare lagrer et nummer. I stedet for et navn eller en etterkommer er bare lagrer et nummer som dette. 

Vel, sjargong vi bruker i datastrukturer er både tries og trær, der en trie, igjen, er bare en som noder er arrays, er fortsatt hva du kanskje bruke fra grunnskolen når du har gjort en familie tree-- blader og rot av treet og barn av foreldre og søsken av disse. Og vi kan gjennomføre et tre, for eksempel, som rett og slett som dette. Et tre, hvis det som en node, en av disse sirklene som har en rekke, det er ikke til å ha en peker, men to. Og så snart du legger til en andre peker, du faktisk kan nå gjøre liksom av to-dimensjonale data strukturer i minnet. Mye som en todimensjonal array, kan du har form av to-dimensjonale lenkede lister, men de som følger et mønster hvor det er ingen sykluser. Det er virkelig et tre med en forelder vei opp her og deretter noen foreldre og barn, og barnebarn og oldebarn. og så videre. 

Men hva er egentlig pen om dette også, bare for å erte deg med en bit av koden, tilbakekalling rekursjon fra en stund tilbake, der du skriver en funksjon som kaller seg. Dette er en vakker mulighet å gjennomføre noe som rekursjon, fordi vurdere dette. 

Dette er et tre. Og jeg har vært litt anal med hvordan Jeg satte heltall inn i gaten. Så mye at den har en spesiell name-- et binært søketre. Nå har vi hørt om binære søk, men kan du jobbe bakover fra denne tingen navn? Hva er mønsteret av hvordan jeg satt heltallene inn i dette treet? Det er ikke tilfeldig. Det er noen mønster. Yeah. 

PUBLIKUM: Small de på venstre. 

DAVID MALAN: Yeah. Mindre de er på venstre side. Større de er på rett. Slik at et sant utsagn er en forelder er større enn dens venstre barn, men mindre enn sin rett barnet. Og det alene er enda en rekursiv verbal definisjon fordi du kan bruke det samme logikken til hver node og det bare bunner ut, en base case hvis du vil, når du treffer en av bladene, så å si, der en permisjon har ingen barn lenger. 

Nå hvordan kan du finne nummeret 44? Du vil starte ved roten og si, hm. 55 er ikke 44 Så gjør jeg ønsker å gå høyre eller ønsker jeg å gå til venstre? Vel, selvsagt ønsker å gå til venstre. Og så er det akkurat som telefonen Boken eksempel i binær søk mer generelt. Men vi implementere det nå litt mer dynamisk enn en matrise kan tillate. Og faktisk, hvis du ønsker å se på koden, ved første øyekast sikker. Det ser ut som en hel haug med linjer. Men det er vakkert enkel. Hvis du ønsker å implementere en funksjon kalles søk hvis formål i livet er å søke etter en verdi som n, er et heltall, og du er gått i ett pointer-- en peker til noden av røttene, heller, for det treet som du kan få tilgang til alt annet, merke til hvor oversiktlig du kan implementere logikken. Hvis treet er null, tydeligvis er det ikke der. La oss bare return false. Høyre? Hvis du leverer det ingenting, det er ingenting der. 

Annet, hvis n er mindre enn treet pil N- nå arrow n, husker vi introduserte super kort om dagen, og det betyr bare de-referanse pekeren og se på feltet kalt n. Så det betyr gå dit og se på feltet kalt n. Så hvis n, verdien du får, er mindre enn verdien i trær heltall, hvor ønsker du å reise? Til venstre. 

Så merker rekursjonen. Jeg returning-- ikke sant. Ikke falske. Jeg er tilbake uansett svaret er fra en samtale til meg selv, passerer en n på nytt, noe som er redundante, men hva er litt annerledes nå? Hvordan skal jeg gjøre problemet mindre? Jeg passerer som den andre argument, ikke roten av treet, men venstre barnet i dette tilfellet. Så jeg har bestått i venstre barnet. 

I mellomtiden, hvis n er større enn noden Jeg er for tiden å se på, Jeg søker på høyre side. Else, hvis treet er ikke null, og hvis elementet er ikke til venstre og det er ikke til høyre, hva er fantastisk tilfelle? Vi har faktisk funnet node i spørsmålet, og så vi returnere true. 

Så vi har bare skrapet overflaten nå noen av disse datastrukturer. I oppgavesettet fem du vil utforske disse ennå videre, og du vil bli gitt design Valget av hvordan du går om dette. Det jeg ønsker å konkludere på er bare en 30 sekunders teaser av hva som venter i neste uke og utover. 

Som vi begin-- heldigvis du kanskje think-- vår overgang sakte fra verden av C og lavere nivå gjennomføring detaljer, til en verden der vi kan ta for gitt at noen andre har endelig implementert disse dataene strukturer for oss, og vi vil begynne å forstå virkelige verden betyr å implementere web-baserte programmer og nettsteder mer generelt og også selve sikkerhets implikasjoner som vi har bare begynt å skrape i overflaten av. Her er hva som venter oss i dagene som kommer. 

[VIDEO PLAYBACK] 

-Han Kom med en melding, med en protokoll all sin egen. Han kom til en verden av grusom brannmurer, uncaring rutere, og farer langt verre enn døden. Han er rask. Han er sterk. Han er TCP / IP, og han fikk adressen. "Warriors of the Net". [END VIDEO PLAYBACK] DAVID MALAN: Kommer neste uke. Vi vil se deg da. [VIDEO PLAYBACK] -Og Nå, "Deep Thoughts" av Daven Farnham. -David Starter alltid forelesninger med, "All right." Hvorfor ikke, "Her er løsningen til denne ukens problem set " eller "Vi gir dere alle en A?" [Ler] [END VIDEO PLAYBACK]