[MUSIC SPILLE] DOUG LLOYD: Nå har du vet mye om matriser, og du vet mye om lenkede lister. Og vi har diskutere argumenter for og imot, har vi diskutert som knyttet lister kan få større og mindre, men de tar opp mer størrelse. Arrays er mye mer oversiktlig å bruke, men de er restriktive i så mye som vi har til å angi størrelsen på rekken helt i begynnelsen og da er vi stuck med det. 

Men det er, vi har ganske mye brukt opp alle våre emner om lenkede lister og matriser. Eller har vi? Kanskje vi kan gjøre noe enda mer kreativ. Og den slags låner ideen om en hash table. 

Så i en hash table skal vi prøve kombinere en matrise med en lenket liste. Vi kommer til å ta fordelene i matrisen, slik tilfeldig tilgang, å kunne bare gå til matrise element 4 eller array element 8 uten å iterere over. Det er ganske fort, ikke sant? 

Men vi ønsker også å ha våre data strukturen være i stand til å vokse og krympe. Vi trenger ikke, gjør vi ikke ønsker å være begrenset. Og vi ønsker å kunne å legge til og fjerne ting veldig lett, som om du husker, er meget komplisert med en matrise. Og vi kan kalle dette ny ting en hash table. 

Og hvis implementert riktig, vi liksom ta fordelene ved begge data strukturer du allerede har sett, arrays og koblede lister. Innsetting kan begynne å tenderer mot theta av en. Theta vi har egentlig ikke diskutert, men theta er bare den gjennomsnittlige tilfellet hva som faktisk kommer til å skje. Du er ikke alltid kommer til å har worst case scenario, og du ikke alltid kommer til å ha best case scenario, så hva er gjennomsnittlig scenario? 

Vel en gjennomsnittlig innsetting inn i en hash table kan begynne å komme nær konstant tid. Og sletting kan få nær konstant tid. Og oppslag kan få nær konstant tid. That's-- vi ikke har en data struktur ennå som kan gjøre det, og så dette allerede høres som en ganske stor ting. Vi har virkelig dempet Ulempene ved hver for seg. 

For å få denne ytelsen oppgradere skjønt, vi trenger å tenke gjennom hvordan vi legger til data inn i strukturen. Spesielt ønsker vi at data i seg selv til å fortelle oss hvor den skal gå i strukturen. Og hvis vi da trenger å se om det er i strukturen, hvis vi trenger å finne det, vi ønsker å se på data igjen og være i stand til å effektivt, ved hjelp av data, tilfeldig tilgang til den. Bare ved å se på data vi bør ha en idé om hvor vi er kommer til å finne den i hash tabellen. 

Nå ulemper av en hash Tabellen er at de er veldig ganske dårlig på bestilling eller sortering av data. Og faktisk, hvis du starter å bruke dem til å bestille eller sort data du mister alt av fordeler du tidligere hadde i form av innsetting og sletting. Tiden blir nærmere theta av n, og vi har i utgangspunktet tilbakegang i en lenket liste. Og så vi bare ønsker å bruke hasj tabeller hvis vi ikke bryr oss om om data blir sortert. For i hvilken sammenheng du vil bruke dem i CS50 du sannsynligvis ikke bryr seg at dataene er sortert. 

Så en hash table er en kombinasjon av to atskilte stykker som vi er kjent. Den første er en funksjon, hvilken vi vanligvis kaller en hash-funksjon. Og at hash funksjon skal returnere en ikke-negativt heltall, som vi vanligvis kaller en hashCode, OK? Den andre delen er en matrise, som er i stand til å lagre data av den type vi ønsker å plassere i datastrukturen. Vi vil holde ut på lenket liste element for nå og bare begynne med det grunnleggende av en hash table å få hodet rundt det, og så får vi kanskje blåse tankene dine litt når vi kombinere arrays og link lister sammen. 

Den grunnleggende ideen om er vi ta noen data. Vi kjører som data gjennom hash-funksjon. Og slik at dataene blir prosessert og det spytter ut et tall, OK? Og deretter med det nummeret vi bare lagre data vi ønsker å lagre i matrise på det stedet. Så for eksempel har vi kanskje dette hash table av strenger. Det har 10 elementer i det, så vi kan passe 10 strenger i den. 

La oss si at vi ønsker å hash John. Så John som data vi ønsker å sette inn inn i denne hash table et sted. Der setter vi det? Vel typisk med en rekke så langt vi sannsynligvis ville sette den i matrisen plassering 0. Men nå har vi denne nye hash-funksjon. 

Og la oss si at vi kjører John gjennom denne hash-funksjon og det spytter ut 4. Vel det er der vi er kommer til å ønske å sette John. Vi ønsker å sette John i matrise plassering 4, fordi hvis vi hasj John igjen-- la oss si senere vi ønsker å søke og se Hvis John eksisterer i denne hash table-- alt vi trenger å gjøre kjøres det gjennom den samme hash funksjon, få nummer 4 ut, og være i stand til å finne John umiddelbart i vår datastruktur. Det er ganske bra. 

La oss si at vi nå gjør dette igjen, vil vi til hasj Paul. Vi ønsker å legge til Paul inn i denne hash table. La oss si at denne gangen vi kjører Paul gjennom hash-funksjon, den hashCode som er generert er seks. Vel, nå kan vi sette Paul i matrisen plassering 6. Og hvis vi trenger å slå opp om Paul er i denne hash table, alt vi trenger å gjøre er å kjøre Paul gjennom hash funksjonen igjen og vi kommer til å få seks ut igjen. 

Og så ser vi bare på rekke plassering 6. Er Paul der? I så fall er han i hash tabellen. Er Paul ikke det? Han er ikke i hash tabellen. Det er ganske grei. 

Nå hvordan vil du definere en hash-funksjon? Vel det er egentlig ingen grense for antallet mulige hash-funksjoner. Faktisk er det en rekke virkelig, virkelig gode på internett. Det finnes en rekke virkelig, virkelig dårlige seg på internett. Det er også ganske enkelt å skrive en dårlig en. 

Så hva gjør opp en god hash-funksjon, ikke sant? Vel en god hash-funksjon skal bruker bare dataene som hashet, og alle data blir hashet. Så vi ikke ønsker å bruke anything-- vi ikke innlemme noe annet enn dataene. Og vi ønsker å bruke alle data. Vi ønsker ikke å bare bruke et stykke av det, vi ønsker å bruke alt sammen. En hash-funksjon skal også være deterministisk. Hva betyr det? Vel det betyr at hver gang vi passere nøyaktig samme stykke data inn i hash-funksjon vi alltid få samme hashCode ut. Hvis jeg passerer John inn i hash-funksjon jeg kommer ut fire. Jeg burde være i stand til å gjøre det 10000 ganger, og jeg får alltid fire. Så ingen tilfeldige tall effektivt kan være involvert i vår hash tables-- i våre hash funksjoner. 

En hash-funksjon bør også jevnt distribuere data. Hvis hver gang du kjører data gjennom hash-funksjon du får hashCode 0, det er nok ikke så bra, ikke sant? Du sannsynligvis vil stort et utvalg av hash-koder. Også ting kan spre seg ut gjennom hele tabellen. Og også det ville være flott om virkelig tilsvarende data, som John og Jonathan, kanskje ble spredt til veie forskjellige steder i hash table. Det ville være en fin fordel. 

Her er et eksempel på en hash-funksjon. Jeg skrev dette opp tidligere. Det er ikke en spesielt god hash-funksjon av grunner som ikke egentlig bjørn kommer inn akkurat nå. Men ser du hva som skjer her? Det virker som om vi erklære en variabel kalles sum- og sette den lik 0. Og så tilsynelatende jeg gjør noe så lenge som strstr [j] er ikke lik til backslash 0. Hva gjør jeg det? 

Dette er i utgangspunktet bare en annen måte å implementere [? strl?] og oppdager når du har kommet til slutten av strengen. Så jeg trenger ikke å faktisk beregne lengden av strengen, Jeg bare bruker når jeg treffer backslash 0 karakteren jeg vet Jeg har nådd slutten av strengen. Og så kommer jeg til å holde itera gjennom strengen, legge strstr [j] for å oppsummere, og deretter på slutten av dagen kommer til å returnere sum mod HASH_MAX. 

I utgangspunktet er alt dette hash funksjonen gjør er å legge opp alle verdier av ASCII min streng, og da er det returnere en hashCode modded av HASH_MAX. Det er sannsynligvis størrelsen av min array, ikke sant? Jeg ønsker ikke å være å få hasj koder hvis mitt utvalg er av størrelse 10, Jeg ønsker ikke å være å få ut hash-koder 11, 12, 13, jeg kan ikke sette ting i de steder på matrisen, det ville være ulovlig. Jeg ville lide en segmentering feil. 

Nå her er en annen rask til side. Vanligvis er du sannsynligvis ikke kommer til å ønsker å skrive dine egne hash funksjoner. Det er faktisk litt av en kunst, ikke en vitenskap. Og det er mye som går inn i dem. Internett, som jeg sa, er full av virkelig god hash funksjoner, og du bør bruke internett til å finne hash funksjoner fordi det er virkelig bare slags en unødvendig bortkastet tid å lage dine egne. 

Du kan skrive enkle seg for testformål. Men når du faktisk kommer til å starte hashing data og lagre den inn i en hash table du er sannsynligvis kommer til å ønske å bruke noen funksjon som ble generert for deg, finnes det på internett. Hvis du bare være sikker å sitere kilder. Det er ingen grunn til å plagiere noe her. 

Informatikk samfunnet er definitivt vokser, og virkelig verdier åpen kildekode, og det er veldig viktig å sitere kilder, slik at folk kan få henvisning til det arbeidet som de er gjør til beste for fellesskapet. Så alltid være sure-- og ikke bare for hasj funksjoner, men vanligvis når bruke kode fra en ekstern kilde, alltid sitere kilden. Gi kreditt til den personen som gjorde noe av arbeidet slik at du ikke må. 

OK så la oss se dette hash table for et sekund. Det er der vi igjen av etter at vi satt inn John og Paul i denne hash table. Ser du et problem her? Du kan se to. Men spesielt, gjør du se dette mulig problem? 

Hva om jeg hasj Ringo, og det viser seg at etter behandlingen at data gjennom hash-funksjon Ringo også genererte hashCode 6. Jeg har allerede fått data på hashcode-- rekke plassering 6. Så det er trolig kommer til å være litt av et problem for meg nå, ikke sant? 

Vi kaller dette en kollisjon. Og kollisjonen oppstår når to biter av data kjøres gjennom den samme hash Funksjonen gi samme hashCode. Antagelig vi ønsker fortsatt å få både biter av data inn i hash table, ellers ville vi ikke kjøre Ringo vilkårlig gjennom hash-funksjon. Vi vil antakelig for å få Ringo inn i denne matrisen. 

Hvordan skal vi gjøre det selv, hvis han og Paul både avkastning hashCode 6? Vi ønsker ikke å overskrive Paul, vi ønsker Paul å være der også. Så vi må finne en måte å få elementer inn i hash tabellen som fortsatt bevarer vår raske innsetting og rask titt opp. Og en måte å håndtere det er å gjøre noe som kalles lineær sondering. 

Ved hjelp av denne metoden hvis vi har en kollisjon, vel, hva gjør vi? Vel, vi kan ikke sette ham i matrisen plassering 6, eller hva hashCode ble generert, la oss sette ham på hashCode pluss 1. Og hvis det er fullt la oss satte ham i hashCode pluss to. Fordelen med dette vesenet om han er ikke akkurat der vi tror han er, og vi må begynne å søke, kanskje vi ikke trenger å gå for langt. Kanskje vi ikke trenger å søke alle n elementene i nøkkeltabell. Kanskje vi må søke et par av dem. 

Og så vi er fortsatt tenderer mot at gjennomsnittlig saks være nær en vs nær n, så kanskje det vil fungere. Så la oss se hvordan dette kunne arbeide ut i virkeligheten. Og la oss se om vi kanskje kan oppdage problemet som kan oppstå her. 

La oss si at vi hash Bart. Så nå skal vi kjøre et nytt sett strenger gjennom hash-funksjon, og vi kjører Bart gjennom hash funksjon, får vi hashCode 6. Vi tar en titt, ser vi 6 er tomt, så vi kan sette Bart der. 

Nå hash vi Lisa og at genererer også hashCode 6. Vel nå at vi bruker denne lineær sondering metoden vi starter på 6, Vi ser at 6 er full. Vi kan ikke sette Lisa i 6. Så hvor går vi? La oss gå til syv. 7-er tom, så det fungerer. Så la oss sette Lisa der. 

Nå hash vi Homer og vi får 7. OK godt vi vet at syv fulle nå, slik at vi ikke kan sette Homer der. Så la oss gå til åtte. Er 8 tilgjengelig? Ja, og 8 er nær 7, så hvis vi må begynne å søke vi er ikke nødt til å gå for langt. Og så la oss sette Homer på åtte. 

Nå hash vi Maggie og returnerer 3, takk og lov vi er i stand til å bare sette Maggie der. Vi trenger ikke å gjøre noe slags sondering for det. Nå hash vi Marge, og Marge returnerer også 6. 

Vel 6 er full, 7 er fullt, 8 er full, 9, greit takk Gud, 9 er tom. Jeg kan sette Marge på ni. Allerede ser vi at vi begynner å ha dette problemet der nå er vi begynner å strekke ting slag for langt borte fra sine hash-koder. Og at theta av en, som gjennomsnittlig Ved å være konstant tid, begynner å bli litt mer-- begynner å tendens litt mer mot theta av n. Vi begynner å miste den nytte av hasj tabeller. 

Dette problemet som vi nettopp så er noe som heter clustering. Og hva er virkelig ille om clustering er at når du nå har to elementer som er side etter side det gjør det enda mer sannsynlig, du har dobbelt sjanse, at du kommer å ha en annen kollisjon med at klyngen, og klyngen vil vokse med en. Og du vil holde vokser og vokser sannsynligheten for å ha en kollisjon. Og til slutt er det like ille som ikke sortering av data i det hele tatt. 

Det andre problemet er om vi fortsatt, og så langt opp til dette punktet, Vi har nettopp vært slags forstå hva en hash table er, vi fortsatt bare har plass til 10 strenger. Hvis vi ønsker å fortsette til hasj innbyggerne i Springfield, vi kan bare få 10 av dem i det. Og hvis vi prøver og legge til en 11. eller 12., vi ikke har et sted å sette dem. Vi kunne bare spinne rundt i sirkler prøver å finne et tomt sted, og vi kanskje får problemer i en uendelig loop. 

Så denne typen låner til ideen av noe som kalles kjeding. Og det er her vi kommer til å bringe lenkede lister tilbake inn i bildet. Hva om i stedet for å lagre bare selve dataene i tabellen, hvert element i gruppen kunne holde flere biter av data? Vel det ikke gir mening, ikke sant? Vi vet at en rekke kan bare hold-- hvert element i en matrise kan kun ha en brikke av dataene på den datatype. 

Men hva om den datatypen er en lenket liste, ikke sant? Så hva om hver element i gruppen var en peker til hodet på en lenket liste? Og så kan vi bygge disse koblede lister og vokse dem vilkårlig, fordi lenkede lister tillate oss å vokse og krympe mye mer fleksibelt enn en matrise gjør. Så hva om vi nå bruker, vi utnytte dette, ikke sant? Vi begynner å vokse disse kjedene ut av disse array-stedene. 

Nå kan vi passer en uendelig Mengden av data, eller ikke uendelig, en vilkårlig mengde data, inn i vårt hash table uten noen gang å kjøre inn problemet med kollisjoner. Vi har også eliminert clustering ved å gjøre dette. Og godt vi vet at når vi setter inn inn i en lenket liste, hvis du husker fra vår video på lenkede lister, enkeltvis lenkede lister og dobbelt lenkede lister, det er en konstant tid operasjon. Vi er bare å legge til fronten. 

Og for titt opp, godt vi vet som ser opp i en lenket liste kan være et problem, ikke sant? Vi må søke gjennom det fra begynnelse til slutt. Det er ingen tilfeldig tilgang i en lenket liste. Men hvis stedet for å ha en koblet liste der en lookup ville være O av n, vi nå har 10 lenkede lister, eller 1000 lenkede lister, nå er det O n dividert med 10, eller O n dividert med 1000. 

Og mens vi snakker teoretisk om kompleksitet vi ser bort konstanter, i den virkelige verden disse tingene faktisk betyr noe, ikke sant? Vi har faktisk vil merke at dette skjer for å kjøre 10 ganger raskere, eller 1000 ganger raskere, fordi vi distribuerer en eneste lang kjede over 1.000 mindre kjeder. Og så hver gang vi har til å søke gjennom en av de kjedene vi kan ignorere 999 kjeder vi ikke bryr seg om, og bare søke den. 

Som er på gjennomsnittet til være 1000 ganger kortere. Og så har vi fortsatt er liksom tenderer mot dette gjennomsnittlig saks for å være konstant tid, men bare fordi vi er å utnytte dividere med noen enorme konstant faktor. La oss se hvordan dette kan faktisk ser skjønt. Så dette var den hash table vi hadde før vi erklært en hash tabell som var i stand til å lagre 10 strenger. Vi kommer ikke til å gjøre det lenger. Vi vet allerede at begrensninger av denne metoden. Nå vår hash table kommer til å bli en rekke 10 noder, pekere til hodene på lenkede lister. 

Og akkurat nå er det null. Hver og en av de 10 pekere er null. Det er ingenting i vår hash table akkurat nå. 

Nå la oss begynne å sette noen ting i denne hash table. Og la oss se hvordan denne metoden er kommer til nytte for oss litt. La oss nå hash Joey. Vi vil vil kjøre strengen Joey gjennom en hash-funksjon, og vi kommer tilbake 6. Vel, hva gjør vi nå? 

Vel nå arbeider med koblede lister, Vi jobber ikke med arrays. Og når vi jobber med koblede lister vi vet vi må begynne dynamisk tildeling av plass og byggekjedene. Det er liksom how-- de er kjernen elementer for å bygge en lenket liste. Så la oss dynamisk tildele plass for Joey, og så la oss legge ham til kjeden. 

Så nå ser hva vi har gjort. Når vi hash Joey vi fikk hashCode 6. Nå peker på rekke plassering 6 peker på hodet av en lenket liste, og akkurat nå er det den eneste element i en lenket liste. Og noden i det lenket liste er Joey. 

Så hvis vi må se opp Joey senere, vi bare hasj Joey igjen, vi får 6 igjen fordi vår hash funksjonen er deterministisk. Og da vi starter på hodet av lenket liste pekte til av matrise plassering 6, og vi kan iterere over som prøver å finne Joey. Og hvis vi bygger vår hash table effektivt, og vår hash fungere effektivt for å distribuere data godt, i gjennomsnitt hver av dem knyttet lister på hver rekke plassering vil være 1/10 av størrelsen på hvis vi bare hatt det som en eneste stor lenket liste med alt i det. 

Hvis vi distribuerer den digre linket liste over 10 lenkede lister hver liste vil være 1/10 av størrelsen. Og dermed 10 ganger raskere å søke gjennom. Så la oss gjøre dette igjen. La oss nå hash Ross. 

Og la oss si Ross, når vi gjør det hash koden vi får tilbake er 2. Vel nå vi dynamisk tildele en ny node, setter vi Ross i at node, og vi sier nå matrise plassering 2, i stedet for å peke til null, peker på hodet til en koblet liste hvis eneste node er Ross. Og vi kan gjøre dette en gang til, vi kan hash Rachel og få hashCode fire. malloc en ny node, satt Rachel i noden, og si en rekke plassering 4 nå peker mot hodet av en lenket liste som eneste elementet skjer for å være Rachel. 

OK, men hva skjer hvis vi har en kollisjon? La oss se hvordan vi håndterer kollisjoner bruker separate kjeding metoden. La oss hash Phoebe. Vi får hashCode 6. I vårt forrige eksempel var vi bare lagring av strenger i rekken. Dette var et problem. 

Vi ønsker ikke å clobber Joey, og vi har allerede sett at vi kan få noen clustering problemer hvis vi prøver og trinn gjennom og sonde. Men hva om vi bare slags behandle dette på samme måte, ikke sant? Det er akkurat som å legge et element til hodet på en lenket liste. La oss bare malloc plass for Phoebe. 

Vi vil si Phoebe sin neste Pilen peker til den gamle lederen for lenket liste, og deretter seks bare peker på ny leder av lenket liste. Og nå ser, har vi endret Phoebe i. Vi kan nå lagre to elementer med hashCode 6, og vi ikke har noen problemer. 

Det er ganske mye alt det er å kjeding. Og kjeding er definitivt den metoden som er kommer til å være mest effektive for deg hvis du lagrer data i en hash table. Men denne kombinasjonen av arrays og koblede lister sammen for å danne en nøkkeltabell virkelig dramatisk forbedrer din evne til å lagre store mengder data, og svært raskt og effektivt søk gjennom disse dataene. 

Det er fortsatt en mer datastruktur der ute som kan selv være litt bedre når det gjelder å garantere at vår innsetting, sletting, og ser opp ganger er enda raskere. Og vi vil se at i en video på prøver. Jeg er Doug Lloyd, dette er CS50.