[Musik spiller] DOUG LLOYD: Ved nu du ved en masse om arrays, og du ved en masse om hægtede lister. Og vi har diskutere fordele og ulemper, vi har diskuteret, der er knyttet lister kan få større og mindre, men de fylder mere størrelse. Arrays er meget mere ligetil at bruge, men de er restriktive i så meget som vi er nødt til at indstille størrelsen på arrayet i begyndelsen og så er vi fast med det. 

Men det er, vi har temmelig meget udtømt alle vores emner om hægtede lister og arrays. Eller har vi? Måske kan vi gøre noget endnu mere kreative. Og den slags låner tanken om en hash tabel. 

Så i en hash tabel vil vi forsøge kombinere et array med en sammenkædet liste. Vi kommer til at tage fordelene af array'et, som random access, at være i stand til at bare gå til matrix element 4 eller arrayelement 8 uden at skulle gentage tværs. Det er temmelig hurtigt, ikke? 

Men vi ønsker også at have vores data struktur kunne vokse og skrumpe. Vi har ikke brug for, vi ikke ønsker at være begrænset. Og vi ønsker at kunne at tilføje og fjerne ting meget let, som hvis du husker, er meget kompleks med et array. Og vi kan kalde denne ny ting en hash tabel. 

Og hvis den gennemføres korrekt, vi slags tager fordelene ved både data strukturer, som du allerede har set, arrays og hægtede lister. Indsættelse kan begynde at tenderer mod theta 1. Theta har vi ikke rigtig diskuteret, men theta er bare den gennemsnitlige fald hvad der rent faktisk kommer til at ske. Du er ikke altid vil har det værst tænkelige scenarie, og du ikke altid vil have bedste fald, så hvad er den gennemsnitlige scenario? 

Nå en gennemsnitlig indsættelse i en hashtabel kan begynde at komme tæt på konstant tid. Og sletning kan få tæt på konstant tid. Og opslag kan få tæt på konstant tid. That's-- vi ikke har et data struktur endnu, der kan gøre det, og så dette allerede lyder som en temmelig stor ting. Vi har virkelig afbødes den ulemper ved hver på egen hånd. 

For at få denne ydelse opgradere selv, vi nødt til at genoverveje, hvordan vi tilføjer data i strukturen. Konkret ønsker vi data, selv at fortælle os hvor det skal gå i strukturen. Og hvis vi så nødt til at se, om det er i strukturen, hvis vi har brug for at finde det, vi ønsker at se på data igen og være i stand til effektivt, ved hjælp af data, tilfældigt adgang til den. Bare ved at se på data, som vi skal have en idé om, hvor præcis er vi kommer til at finde det i hash-tabellen. 

Nu ulempen ved en hash bordet er, at de er virkelig temmelig dårlig til at bestille eller sortering af data. Og i virkeligheden, hvis du starter at bruge dem til orden eller sortere data, mister du alle de fordele, du tidligere havde i form af indsættelse og sletning. Tiden bliver tættere på theta på n, og vi har set svandt i en sammenkædet liste. Og så vi kun ønsker at bruge hash tabeller, hvis vi ikke bekymrer sig om hvorvidt dataene er sorteret. For den sammenhæng, hvori du skal bruge dem i CS50 du sandsynligvis er ligeglad at dataene er sorteret. 

Så en hash tabel er en kombination af to adskilte stykker som vi kender. Den første er en funktion, som vi normalt kalder en hash-funktion. Og at hash-funktion vil vende tilbage en ikke-negativt heltal, som vi normalt kalder en hashCode, OK? Det andet stykke er et array, som er stand til at lagre data af typen vi ønsker at placere i datastrukturen. Vi vil holde ud på den sammenkædet liste element for nu og bare starte med det grundlæggende i en hash tabel til at få dit hoved omkring det, og så vil vi måske blæse dit sind en lille smule, når vi kombinere arrays og link lister sammen. 

Den grundlæggende idé om er vi tager nogle data. Vi kører, at data gennem hash-funktionen. Og så data behandles og det spytter et tal, OK? Og derefter med dette nummer vi bare gemme data vi ønsker at gemme i vifte på det sted. Så for eksempel har vi måske denne hash tabel af strenge. Det har fået 10 elementer i det, så vi kan passe 10 strygere i den. 

Lad os sige, at vi ønsker at hash John. Så John som de data, vi vil indsætte i denne hash tabellen sted. Hvor skal vi sætte det? Nå typisk med en vifte hidtil vi sandsynligvis ville sætte det i matrix placering 0. Men nu har vi denne nye hash funktion. 

Og lad os sige, at vi kører John gennem denne hash-funktion og det er spytter 4. Nå det er, hvor vi er lyst til at sætte John. Vi ønsker at sætte John i matrix placering 4, for hvis vi hash John igen-- lad os sige senere vi vil søge og se hvis John eksisterer i denne hash table-- alt, hvad vi behøver at gøre køres det gennem den samme hash funktion, få nummeret 4, og være i stand til at finde John straks i vores datastruktur. Det er temmelig godt. 

Lad os sige, at vi nu gør det igen, vi ønsker at hash Paul. Vi ønsker at tilføje Paul i denne hash tabellen. Lad os sige, at vi denne gang køre Paul gennem hash-funktionen, den hashCode, der genereres er 6. Nå nu kan vi sætte Paulus i arrayet placeringen 6. Og hvis vi har brug for at slå op, om Paulus er i denne hash tabel, alt, hvad vi skal gøre, er at køre Paul gennem hash-funktionen igen og vi kommer til at få 6 ud igen. 

Og så har vi bare se ved opstilling placering 6. Er Paul der? Hvis ja, han er i hash tabellen. Er Paulus ikke er der? Han er ikke i hash tabellen. Det er ret ligetil. 

Nu hvordan kan du definere en hash-funktion? Tja der er virkelig ingen grænse for Antallet af mulige hashfunktioner. Faktisk er der en række virkelig, virkelig gode på internettet. Der er en række virkelig, virkelig dårlige på internettet. Det er også ret nemt at skrive en dårlig en. 

Så hvad gør en god hash-funktionen, ikke? Nå en god hash-funktion bør bruger kun de data, der hashed, og alle de data, der hashed. Så vi ønsker ikke at bruge anything-- vi ikke indarbejde noget andet end dataene. Og vi ønsker at bruge alle data. Vi ønsker ikke at bare bruge et stykke af det, vi ønsker at bruge det hele. En hash-funktionen skal også være deterministisk. Hvad betyder det? Nå det betyder, at hver gang vi passere nøjagtig samme stykke data ind i hash-funktionen vi altid får den samme hashCode ud. Hvis jeg passerer Johannes ind i hash-funktion jeg kommer ud 4. Jeg skulle være i stand til at gøre det 10.000 gange, og jeg vil altid få 4. Så ingen tilfældige tal effektivt kan inddrages i vores hash tables-- i vores hashfunktioner. 

En hash-funktionen skal også ensartet at fordele data. Hvis hver gang du kører data via hash-funktionen får du hashCode 0, det er nok ikke så stor, højre? Du ønsker sikkert at store en række hash-koder. Også ting kan spredes i hele tabellen. Og også det ville være dejligt, hvis virkelig lignende data, som John og Jonathan, måske blev spredt ud til at veje forskellige steder i hash tabellen. Det ville være en god fordel. 

Her er et eksempel på en hash-funktion. Jeg skrev denne ene op tidligere. Det er ikke en særlig god hashfunktion af årsager, der ikke rigtig bære at gå ind lige nu. Men ser du, hvad der foregår her? Det ser ud som vi erklære en variabel kaldet sum og sætte den lig med 0. Og så åbenbart jeg gør noget så længe strstr [j] er ikke lig at backslash 0. Hvad gør jeg der? 

Dette er dybest set bare et andet måde at gennemføre [? strl?] og afsløre når du har nået enden af ​​strengen. Så jeg behøver ikke at faktisk beregne længden af ​​strengen, Jeg er bare at bruge, når jeg ramte backslash 0 tegn jeg kender Jeg har nået slutningen af ​​strengen. Og så jeg har tænkt mig at holde iteration gennem denne streng, tilføjer strstr [j] for at opsummere, og derefter på slutningen af ​​dagen vil returnere summen mod HASH_MAX. 

Dybest set alt dette hash funktion gør, er at tilføje op alle de ASCII værdier min snor, og så er det returnere nogle hashCode modded af HASH_MAX. Det er nok på størrelse af min matrix, ikke? Jeg ønsker ikke at være at få hash koder, hvis min array er i størrelse 10, Jeg ønsker ikke at være at få ud hash-kode 11, 12, 13, kan jeg ikke sætte tingene i de steder af opstillingen, det ville være ulovligt. Jeg ville lide en segmentering fejl. 

Nu her er en anden hurtig til side. Generelt er du sandsynligvis ikke kommer til at ønsker at skrive dine egne hash funktioner. Det er faktisk lidt af en kunst, ikke en videnskab. Og der er en masse, der går ind i dem. Internettet, som jeg sagde, er fuld rigtig gode hashfunktioner, og du skal bruge internettet til at find hashfunktioner fordi det er virkelig lige slags en unødvendig spild af tid at oprette din egen. 

Du kan skrive enkle til testformål. Men når du rent faktisk kommer til at begynde hashing af data og lagring ind i en hash tabel, du er sandsynligvis vil ønsker at bruge en funktion, der blev genereret for dig, der findes på internettet. Hvis du bare være sikker at citere dine kilder. Der er ingen grund til at plagiere noget her. 

Den datalogi samfund er afgjort voksende, og virkelig værdier open source, og det er virkelig vigtigt at citere dine kilder, så folk kan få tilskrivning til det arbejde, de er gør til gavn for samfundet. Så altid være sure-- og ikke kun for hash funktioner, men generelt, når man bruge kode fra en ekstern kilde, altid nævne din kilde. Give kredit til den person, der gjorde en del af arbejdet, så du ikke behøver at. 

OK, så lad os revidere denne hash tabel til en anden. Det er her, vi forlod off efter vi indsat John og Paul ind i denne hash tabellen. Kan du se et problem her? Du kan se to. Men i særdeleshed, har du se dette mulige problem? 

Hvad hvis jeg hash Ringo, og det viser sig, at efter forarbejdning at data gennem hash-funktionen Ringo også genereret hashCode 6. Jeg har allerede fået data hashcode-- matrix placering 6. Så det er sandsynligvis kommer til at være en smule af et problem for mig nu, ikke? 

Vi kalder det en kollision. Og kollisionen sker, når to stykker af data løber gennem den samme hash Funktionen giver den samme hashCode. Formodentlig vi stadig ønsker at få både stykker af data til hash tabellen, ellers ville vi ikke køre Ringo vilkårligt gennem hash-funktionen. Vi formentlig ønsker at få Ringo i den opstilling. 

Hvordan gør vi det selv, hvis han og Paul begge udbytte hashCode 6? Vi ønsker ikke at overskrive Paul, vi ønsker Paulus at være der også. Så vi har brug for at finde en måde at få elementer i hash tabel, stadig bevarer vores hurtige indsættelse og hurtigt kig op. Og en måde at håndtere det er at gøre noget, der hedder lineær sondering. 

Ved hjælp af denne metode, hvis vi har en kollision, ja, hvad gør vi? Nå vi kan ikke sætte ham i matrix placering 6, eller hvad hashCode blev genereret, lad os sætte ham på hashCode plus 1. Og hvis der er fuld lad os sætte ham i hashCode plus 2. Fordelen ved dette væsen, hvis han er ikke præcis, hvor vi tror, ​​han er, og vi er nødt til at begynde at søge, måske vi behøver ikke at gå for vidt. Måske har vi ikke at søge alle n elementer af hash tabellen. Måske vi nødt til at søge et par af dem. 

Og så vi er stadig en tendens i retning af at den gennemsnitlige fald være tæt på 1 vs tæt på n, så måske kommer til at arbejde. Så lad os se, hvordan dette kan arbejde ud i virkeligheden. Og lad os se om måske kan vi afsløre det problem, at der kan forekomme her. 

Lad os sige, at vi hash Bart. Så nu vil vi til at køre et nyt sæt af strenge gennem hash-funktionen, og vi kører Bart gennem hash funktion, får vi hashCode 6. Vi tager et kig, ser vi 6 tom, så vi kan sætte Bart der. 

Nu er vi hash Lisa, og at også genererer hashCode 6. Nå nu, at vi bruger denne lineære sondering metode vi starter ved 6, ser vi, at 6 er fuld. Vi kan ikke sætte Lisa i 6. Så hvor skal vi hen? Lad os gå til 7. 7 tomme, så der virker. Så lad os sætte Lisa der. 

Nu er vi hash Homer og vi får 7. OK godt vi ved, at 7 fulde nu, så kan vi ikke sætte Homer der. Så lad os gå til 8. Er 8 til rådighed? Ja, og 8 er tæt på 7, så hvis vi er nødt til at begynde at søge vi er ikke vil have til at gå for vidt. Og så lad os sætte Homer 8. 

Nu er vi hash Maggie og returnerer 3, gudskelov vi er i stand til at bare sætte Maggie der. Vi behøver ikke at gøre noget slags sondering for. Nu er vi hash Marge, og Marge også returnerer 6. 

Nå 6 er fuld, 7 er fuld, 8 er fuld, 9, okay gudskelov 9 er tom. Jeg kan sætte Marge ved 9. Vi kan allerede se, at vi er begyndt at have dette problem, hvor nu er vi begynder at strække ting form langt væk fra deres hash-koder. Og at theta på 1, det gennemsnitlige tilfælde af at være konstant tid, er begyndt at få lidt more-- begynder at tendens lidt mere mod theta på n. Vi er begyndt at miste denne fordel af hash-tabeller. 

Dette problem, som vi lige har set er noget, der hedder klyngedannelse. Og hvad er virkelig dårligt om klyngedannelse er, at når du nu har to elementer, der ved siden af side gør det endnu mere sandsynligt, du har dobbelt chance, at du vil at have en anden kollision med denne klynge, og klyngen vil vokse med en. Og du vil holde voksende og voksende din sandsynligheden for at have en kollision. Og i sidste ende er det lige så slemt som ikke sortere data overhovedet. 

Det andet problem er dog, at vi stadig, og så videre op til dette punkt, Vi har netop været en slags at forstå, hvad en hash tabel er, vi stadig kun har plads til 10 strenge. Hvis vi ønsker at fortsætte med at hash borgerne i Springfield, Vi kan kun få 10 af dem derinde. Og hvis vi forsøge at tilføje en 11. eller 12., vi ikke har et sted at sætte dem. Vi kunne bare være spinning rundt i cirkler forsøger at finde et tomt sted, og vi måske går i stå i en uendelig løkke. 

Så denne slags låner til idéen af noget, der hedder kæde. Og det er her, vi kommer til at bringe hægtede lister tilbage ind i billedet. Hvad hvis stedet for at lagre lige selve dataene i arrayet, hvert element i arrayet kunne holde flere stykker af data? Nå det giver ikke mening, ikke? Vi ved, at et array kan kun hold-- hvert element i et array kan kun holde et stykke af data for denne datatype. 

Men hvad hvis det datatype er en linket liste, ikke? Så hvad nu hvis hver element i arrayet var en pointer til lederen af ​​en linket liste? Og så kunne vi bygge disse hægtede lister og dyrke dem vilkårligt, fordi hægtede lister tillader os til at vokse og skrumpe meget mere fleksibelt end et array gør. Så hvad nu hvis vi nu bruger, vi udnytte dette, ikke? Vi begynder at vokse disse kæder ud af disse Array steder. 

Nu kan vi passer en uendelig datamængde, eller ikke uendelig, en vilkårlig mængde data ind i vores hash tabel uden at løbe ind problemet med kollision. Vi har også fjernet klyngedannelse ved at gøre dette. Og godt vi ved, at når vi indsætter ind i en linket liste, hvis du husker fra vores video på hægtede lister, enkeltvis forbundne lister og dobbelt hægtede lister, det er en konstant tid operation. Vi er blot at tilføje til fronten. 

Og for udseende op, godt vi kender at slå op i en sammenkædet liste kan være et problem, ikke? Vi er nødt til at søge gennem det fra start til slut. Der er ingen tilfældig adgang i en sammenkædet liste. Men hvis man i stedet for at have en tilknytning liste, hvor et opslag ville være O i n, vi nu har 10 hægtede lister, eller 1.000 hægtede lister, nu er det O n divideret med 10, eller O n divideret med 1.000. 

Og mens vi talte teoretisk om kompleksitet vi bort konstanter, i den virkelige verden disse ting rent faktisk noget, højre? Vi vil faktisk mærke at dette sker at køre 10 gange hurtigere, eller 1.000 gange hurtigere, fordi vi distribuerer en lang kæde på tværs af 1.000 mindre kæder. Og så hver gang vi nødt til at søge gennem en af ​​disse kæder, vi kan ignorere de 999 kæder, vi er ligeglade om, og bare søge at en. 

Som i gennemsnit til være 1000 gange kortere. Og så vi stadig er slags tendens i retning af dette gennemsnit sag for at være konstant tid, men kun fordi vi udnytte dividere med nogle enorme konstant faktor. Lad os se, hvordan dette kan faktisk ser dog. Så det var hash tabellen havde vi før vi erklærede en hash tabel, var i stand til at lagre 10 strenge. Vi kommer ikke til at gøre det længere. Vi kender allerede begrænsninger af denne metode. Nu er vores hash tabellen kommer til at være en vifte af 10 noder, pointers til lederne af hægtede lister. 

Og lige nu er det nul. Hver enkelt af de 10 pejlemærker er null. Der er ikke noget i vores hash tabellen lige nu. 

Lad os begynde at sætte nogle ting i denne hash tabel. Og lad os se, hvordan denne metode er kommer til at gavne os lidt. Lad os nu hash Joey. Vi vil vil køre strengen Joey gennem en hash-funktion, og vi vender tilbage 6. Nå, hvad gør vi nu? 

Nå nu arbejder med hægtede lister, vi ikke arbejder med arrays. Og når vi arbejder med forbundne lister vi ved, at vi er nødt til at starte dynamisk tildeling af plads og bygge kæder. Det er slags how-- disse er kernen elementer af at opbygge en linket liste. Så lad os dynamisk afsætte plads til Joey, og så lad os tilføje ham til kæden. 

Så nu ser, hvad vi har gjort. Når vi hash Joey fik vi hashCode 6. Nu markøren på arrayet placering 6 peger på lederen af ​​en linket liste, og lige nu er det den eneste element i en sammenkædet liste. Og knudepunktet ved, at linket liste er Joey. 

Så hvis vi har brug for at slå op Joey senere, vi bare hash Joey igen, vi får 6 igen fordi vores hash-funktionen er deterministisk. Og så starter vi i spidsen af den linkede liste pegede til med matrix placering 6, og vi kan gentage tværs, der forsøger at finde Joey. Og hvis vi bygger vores hash tabel effektivt, og vores hash-funktionen effektivt at distribuere data godt, i gennemsnit hver af dem der er knyttet lister på hver matrix placering vil være 1/10 af størrelsen på hvis vi lige haft det som en enkelt stor linket liste med alt i det. 

Hvis vi distribuerer, at enorme knyttet liste over 10 hægtede lister hver liste vil være 1/10 af størrelsen. Og dermed 10 gange hurtigere at søge igennem. Så lad os gøre det igen. Lad os nu hash Ross. 

Og lad os sige Ross, når vi gør det hash kode, vi får tilbage er 2. Nå nu er vi dynamisk allokere en ny knude, vi sætter Ross i den knude, og vi siger nu vifte placering 2, i stedet for at pege til null, peger på hovedet af en knyttet liste hvis eneste node er Ross. Og vi kan gøre det en gang mere, vi kan hash Rachel og få hashCode 4. malloc en ny knude, sætte Rachel i node, og sige en række placering 4 nu peger på hovedet en sammenkædet liste, hvis eneste element sker for at være Rachel. 

OK, men hvad sker der, hvis vi har en kollision? Lad os se, hvordan vi håndterer kollisioner ved hjælp af den separate kæde metode. Lad os hash Phoebe. Vi får hashCode 6. I vores tidligere eksempel var vi lige lagring af strenge i arrayet. Dette var et problem. 

Vi ønsker ikke at tæske Joey, og vi har allerede set, at vi kan få nogle clustering problemer, hvis vi forsøger og trin gennem og probe. Men hvad nu, hvis vi bare lidt behandle denne på samme måde, ikke? Det er ligesom at tilføje et element til lederen af ​​en linket liste. Lad os bare malloc plads til Phoebe. 

Vi vil sige Phoebe næste pointer punkter til den gamle leder af den linkede liste, og derefter 6 lige peger på nye leder af den linkede liste. Og nu ser vi har ændret Phoebe i. Vi kan nu gemme to elementer med hashCode 6, og vi har ikke nogen problemer. 

Det er temmelig meget alle der er at kæde. Og kæde er afgjort den metode, der er vil være mest effektiv for dig, hvis du gemmer data i en hash-tabel. Men denne kombination af arrays og hægtede lister sammen for at danne en hashtabel virkelig dramatisk forbedrer din evne til at lagre store mængder data, og meget hurtigt og effektivt søge gennem disse data. 

Der er stadig en mere datastruktur derude der kan endda være en smule bedre med hensyn til at sikre at vores insertion, deletion og ser op tider er endnu hurtigere. Og vi vil se, at i en video på forsøg. Jeg er Doug Lloyd, det er CS50.