ROB BOWDEN: Hei. Jeg er Rob, og la oss hash denne løsningen ut. Så her kommer vi til å implementere en generell hash table. Vi ser at struct node av vår hash tabellen kommer til å se slik ut. Så det kommer til å ha en char ord matrise av størrelse lengde pluss en. Ikke glem en siden den maksimale ord i ordlisten er 45 tegn, og da vi kommer til å trenger en ekstra karakter for den backslash 0. 

Og da er vår hash table i hvert bøtte kommer til å lagre en lenket liste av noder. Vi gjør ikke lineær sondering her. Og så for å koble til den neste element i bøtta, trenger vi en struct node * neste. Så det er hva en node ser ut. Nå, her er erklæringen av vår hash table. Det kommer til å ha 16 384 bøtter, men at antall spiller egentlig ingen rolle. Og til slutt, kommer vi til å ha den global variabel hashtable_size, som kommer til å starte som 0, og det er kommer til å holde styr på hvor mange ord var i vår ordbok. OK. 

Så la oss ta en titt på lasten. Så merker at lasten, den returnerer en bool. Du return true hvis det var vellykket lastet og falsk ellers. Og det tar en const char * stjerners ordboken, som er ordboken at vi ønsker å åpne. Så det er den første tingen vi kommer til å gjøre. Vi kommer til å FÅpne ordboken for lesing, og vi kommer til å ha å sørge for at det lyktes så hvis det returneres NULL, så vi gjorde ikke hell åpne ordboken og vi trenger å returnere false. 

Men forutsatt at det gjorde med hell åpen, så vi ønsker å lese ordbok. Så hold looping til vi finner noen Grunnen til å bryte ut av denne løkke som vi får se. Så hold looping, og nå skal vi til malloc en enkelt node. Og selvfølgelig, må vi feil sjekk igjen så hvis mallocing ikke lykkes og vi ønsker å losse noen node som vi skjedde med malloc før, lukker ordbok og return false. 

Men ignorerer det, forutsatt at vi lyktes, da vi ønsker å bruke fscanf å lese et eneste ord fra vår ordlisten, i vår node. Så husk at entry-> Ordet er røye Ordet buffer størrelse lengde pluss en som vi kommer til å lagre ordet i. Så fscanf kommer til å returnere en så lang som det var i stand til å lese en ord fra filen. 

Hvis enten en feil skjer eller vi nå slutten av filen, vil det ikke returnere en i hvilket tilfelle dersom det ikke skjer returnere en, vi endelig kommer til å bryte ut av denne, mens sløyfen. Så vi ser at når vi har lykkes lese inn et ord i entry-> ord, så vi kommer til hasj at ordet med vår hash-funksjon. La oss ta en titt på hash-funksjon. 

Så du ikke virkelig trenger å forstå dette. Og faktisk, vi bare trakk dette hash-funksjon fra internett. Det eneste du trenger å anerkjenne er at dette tar en const char * ord, så det tar en streng som input og returnere en usignert int som utgang. Så det er alt en hash-funksjon er, er det tar i en inngang, det gir deg en indeks inn i nøkkeltabell. Legg merke til at vi er modding av NUM_BUCKETS så hash-verdi returneres faktisk er en indeks inn i hash table og indekserer ikke utover matrisegrensen. 

Så gitt at hash-funksjon, skal vi til hasj ordet som vi leser fra ordboken og så skal vi å bruke som har å sette inn inntreden i hash table. Nå er hashtabellen hash gjeldende lenket liste i hash table, og det er meget mulig det er bare NULL. Vi ønsker å sette vår inntreden på I begynnelsen av dette lenket liste, og så vi kommer til å ha vår nåværende oppføring peke på hva hash tabellen for øyeblikket poeng til og vi kommer til å lagre i hash table på hash den gjeldende oppføringen. 

Så disse to linjene med hell sette trer ved begynnelsen av lenket liste ved at indeksen i hash tabellen. Når vi er ferdig med det, vi vet at vi fant et annet ord i ordbok og vi øke igjen. Så vi fortsette med det inntil fscanf endelig returnerer noe ikke en på hvilket punkt husk at vi trenger å gratis inngang, så her oppe, vi malloced en oppføring og vi prøvde å lese noe fra ordboken. Og om vi ikke lykkes lese noe fra ordboken der tilfelle vi trenger å frigjøre oppføringen som vi aldri faktisk satt i hash table og til slutt bryte. 

Når vi bryter ut, trenger vi å se, vel, gjorde vi bryte ut fordi det ble en feil ved lesing fra filen, eller gjorde vi bryte ut fordi vi nådd slutten av filen? Hvis det var en feil, så vi ønsker å return false fordi belastningen ikke lykkes, og i prosessen, ønsker vi å losse alle ordene som vi leser inn og lukke ordlistefilen. Antar vi lykkes, så vi bare fortsatt trenger å lukke ordlisten fil, og til slutt returnere sant siden vi har lastet inn ordbok. Og det er det for last. 

Så nå sjekke, gitt en ladd hash table, kommer til å se slik ut. Så sjekk, den returnerer en bool, som kommer til å indikere hvorvidt gått-i char * ord, om gått-i strengen er i vår ordbok. Så hvis det er i ordboken, hvis det er i vår hash table, vil vi komme tilbake sant, og hvis det ikke er det, vi vil returnere false. Gitt dette gått-i ord, er vi kommer til hasj ordet. 

Nå, er en viktig ting å gjenkjenne at i lasten, vi visste at alle ordene skulle skrives med små bokstaver, men her er vi ikke så sikker. Hvis vi tar en titt på vår hash-funksjon, vår hash-funksjon faktisk er lowercasing hvert tegn av ordet. Så uavhengig av kapitalisering av ord, er vår hash-funksjon kommer til å returnere den samme indeksen for uansett kapitalisering er som det ville ha returneres for et helt små bokstaver versjon av ordet. OK. 

Så det er vår indeks. Det er hash table for dette ordet. Nå, dette for loop kommer til over lenkeliste som var på den indeksen. Så oppdager vi initialisering oppføring å peke på at indeksen. Vi kommer til å fortsette mens entry gjør ikke lik NULL, og husk at oppdatere pekeren i vår lenket liste entry tilsvarer entry-> neste, så har vår nåværende inngangspunkt til neste element i lenket liste. OK. 

Så for hver oppføring i lenket liste, vi kommer til å bruke strcasecmp. Det er ikke StrCmp fordi en gang, vi ønsker å gjøre ting saken insensitively. Så vi bruker strcasecmp å sammenligne ordet som ble sendt til denne funksjonen mot ordet som er i dette innlegget. Hvis den gir 0, betyr at det ikke var en kamp, ​​og da ønsker vi å returnere true. Vi vellykket funnet ord i vår hash table. 

Hvis det ikke var en kamp, ​​så vi er kommer til å sløyfe igjen og se på neste oppføring. Og vi vil fortsette looping mens det er oppføringer i denne lenket liste. Hva skjer hvis vi bryter ut av dette for løkke? Det betyr at vi ikke finner en oppføring som matchet dette ordet, i så fall vi return false for å vise at vår hash table inneholdt ikke dette ordet. Og det er det for sjekk. OK. 

Så la oss ta en titt på størrelse. Nå er størrelsen kommer til å være ganske enkel siden husker i lasten, for hvert ord vi fant vi økes en global variable hashtable_size. Så størrelsen funksjon er rett kommer til å returnere den globale variabel, og det er det. 

Nå endelig, trenger vi å losse ordbok når alt er ferdig. Så hvordan skal vi gjøre det? Akkurat her er vi looping over alt bøtter med vår hash table. Så det er NUM_BUCKETS bøtter. Og for hver lenket liste i vår hash bordet, kommer vi til å sløyfe over Helheten av lenket liste frigjør hvert element. Nå må vi være forsiktige, så her er vi har en midlertidig variabel som er lagring av pekeren til den neste element i lenket liste. Og så skal vi gratis det aktuelle elementet. 

Vi må være sikker på at vi gjør dette fordi vi kan ikke bare frigjøre det aktuelle elementet og deretter prøve å få tilgang til neste pekeren siden når vi frigjort det minnet blir ugyldig. Så vi trenger å holde rundt en peker til neste element, så vi kan frigjøre gjeldende element, og da kan vi oppdatere vår nåværende element for å peke på det neste element. 

Vi vil sløyfe mens det er elementer i dette lenket liste. Vi vil gjøre det for alle lenkede lister i hash tabellen, og når vi er ferdige med det, har vi helt losset hash tabellen, og vi er ferdige. Så det er umulig for fjerninger å noensinne return false, og når vi er ferdige, vi bare returnere true.