ROB BOWDEN: Hej. Jeg er Rob, og lad os hash denne løsning. Så her vi kommer til at gennemføre en generel hash tabel. Vi ser, at struct node i vores hash Tabellen kommer til at se sådan ud. Så det kommer til at have en char ord vifte af størrelse længde plus 1. Glem ikke 1, da den maksimale ord i ordbogen er 45 tegn, og så vil vi har brug for en ekstra karakter for backslash 0. 

Og så er vores hash tabel i hver spand vil gemme en forbundet nodeliste. Vi laver ikke lineær probing her. Og så for at linke til den næste element i spanden, vi har brug for en struct node * næste. Så det er hvad en knude ser ud. Nu, her er den erklæring vores hash tabellen. Det kommer til at have 16.384 spande, men dette nummer er faktisk ligegyldigt. Og endelig, vi kommer til at have den global variabel hashtable_size, som kommer til at starte som 0, og det er kommer til at holde styr på, hvor mange ord var i vores ordbog. Ok. 

Så lad os tage et kig på belastning. Så bemærke, at last, den returnerer en bool. Du vender tilbage sandt, hvis det var lykkedes lastet og falsk ellers. Og det tager en const char * stjerne ordbog, som ordbogen at vi ønsker at åbne. Så det er den første ting vi kommer til at gøre. Vi kommer til at fopen ordbogen for læsning, og vi er nødt til at sørge for, at det lykkedes så hvis det returnerede NULL, så vi ikke gjorde held åbne ordbogen og vi er nødt til at returnere falsk. 

Men det antages, at den gjorde med succes åben, så vi ønsker at læse ordbogen. Så hold looping indtil vi finder nogle grund til at bryde ud af denne løkke, som vi vil se. Så holde looping, og nu skal vi at allokere en enkelt node. Og selvfølgelig er vi nødt til fejl kontrol igen, så hvis mallocing ikke lykkedes og vi ønsker at losse enhver knude, som vi sket med malloc før, lukke ordbog og returnere falsk. 

Men at ignorere det, antager vi lykkedes, så vi ønsker at bruge fscanf at læse et enkelt ord fra vores ordbogen til vores knude. Så husk, at entry-> Ordet er char ord buffer størrelse længde plus en, som vi kommer til at gemme ord i. Så fscanf kommer til at returnere 1, så længe som det var i stand til at læse en ord fra filen. 

Hvis enten en fejl sker, eller vi nå slutningen af ​​filen, vil det ikke returnere 1, i hvilket tilfælde, hvis den ikke gør det returnere 1, vi endelig kommer til at bryde ud af dette, mens løkken. Så vi kan se, at når vi har med succes læse et ord i entry-> ord, så vi kommer til at hash at ordet ved hjælp af vores hash funktion. Lad os tage et kig på hash-funktionen. 

Så du behøver ikke virkelig har brug for at forstå dette. Og faktisk, vi bare trak dette hash funktion fra internettet. Det eneste, du skal erkende, er at det tager en const char * ord, så det tager en streng som input og returnere en usigneret int som output. Så det hele er en hash-funktion er, er det tager i et input, det giver dig en indekset i hash tabellen. Bemærk, at vi er modding af NUM_BUCKETS så den hash værdi, der returneres faktisk er et indeks i hash tabellen og indekserer ikke ud over grænserne for array. 

Så da hash funktion, vi kommer at hash det ord, vi læser fra ordbogen og så vil vi at bruge, der har at indsætte indrejse i hash tabellen. Nu Hashtable hash er den aktuelle linkede liste i hash tabellen, og det er meget muligt, at er bare NULL. Vi ønsker at indsætte vores indtræden på det begyndelsen af ​​denne linkede liste, og så vi vil have vores aktuelle post pege på, hvad hash tabellen i øjeblikket point til og så vi kommer til at gemme i hash tabellen på hash den aktuelle indtastning. 

Så disse to linjer held indsætte posten i begyndelsen af forbundet listen på det pågældende indeks i hash tabellen. Når vi er færdig med det, vi kender at vi fandt et andet ord i ordbog og vi tilvækst igen. Så vi holde gør, at indtil fscanf Endelig returnerer noget ikke 1 ved hvilket punkt huske, at vi er nødt til gratis adgang, så op her, vi malloced en indrejse og vi forsøgte at læse noget fra ordbogen. Og vi havde ikke held læst noget fra ordbogen, hvor tilfælde har vi brug for at frigøre den post, vi faktisk aldrig sat i hash tabellen og endelig at bryde. 

Når vi bryder ud, er vi nødt til at se, ja, vi bryde ud, fordi der var en fejl ved læsning fra filen, eller vi bryder ud, fordi vi nåede slutningen af ​​fil? Hvis der var en fejl, da vi ønsker at return false fordi belastningen ikke lykkes, og i den proces, vi ønsker at losse alle de ord, som vi læser ind og lukke ordbogen fil. Hvis man antager, vi lykkes, så vi bare stadig nødt til at lukke ordbogen fil, og endelig returnere sandt, da vi har indlæst ordbogen. Og det er det for belastning. 

Så nu kontrollere, givet en ladt hash tabel, kommer til at se sådan ud. Så tjek det returnerer en bool, der kommer til at angive, om passerede-in char * ord, hvorvidt den passerede-i streng er i vores ordbog. Så hvis det er i ordbogen, hvis det er i vores hash tabel, vi vil vende tilbage sandt, og hvis det ikke er, vi vil vende tilbage falsk. I betragtning af denne passerede-i ord, er vi kommer til hash ordet. 

Nu, en vigtig ting at erkende, er at i lasten, vidste vi, at alle de ord, skulle være lavere fald men her er vi ikke så sikker. Hvis vi tager et kig på vores hash funktion, vores hash-funktionen faktisk er lowercasing hver karakter af ordet. Så uanset kapitalisering af ord, er vores hash funktion, der går til returnere det samme indeks for uanset kapitalisering er som det ville have vendt tilbage til en helt små bogstaver version af ord. Ok. 

Så det er vores indeks. Det er hash tabellen for dette ord. Nu, dette for-løkke går til over den linkede liste der var på dette indeks. Så opdager vi initialiseres indgang at pege på dette indeks. Vi kommer til at fortsætte, mens indgang gør ikke lig NULL, og husk, at opdatering af markøren i vores linkede liste entry lig entry-> næste, så har vores nuværende indgang til Næste punkt på linkede liste. Ok. 

Så for hver post i den linkede liste, vi kommer til at bruge strcasecmp. Det er ikke strcmp fordi vi endnu en gang ønsker at gøre tingene tilfælde ufølsomt. Så vi bruger strcasecmp at sammenligne ordet som blev overført til denne funktion imod det ord, er i denne post. Hvis den returnerer 0, som betyder, at der var en kamp, ​​i hvilket tilfælde vil vi returnere sandt. Vi har med held fundet ord i vores hash tabel. 

Hvis der ikke var en kamp, ​​så er vi gå til loop igen og se på næste post. Og vi vil fortsætte looping mens der er poster i denne linkede liste. Hvad sker der, hvis vi bryder ud af denne for-løkke? Det betyder, at vi ikke finde en post, der matches dette ord, i hvilket tilfælde vi vender tilbage falsk for at angive, at vores hash tabel ikke indeholder dette ord. Og det er det for check. Ok. 

Så lad os tage et kig på størrelse. Nu størrelse kommer til at være temmelig simpel da huske i belastning, for hvert ord vi fandt vi øges en global variabel hashtable_size. Så størrelsen funktion er kun vil vende tilbage, at den globale variabel, og det er det. 

Nu endelig er vi nødt til at losse ordbog når alt er gjort. Så hvordan skal vi gøre det? Lige her, vi springer over alle spande af vores hash tabel. Så der er NUM_BUCKETS spande. Og for hver linkede liste i vores hash tabel, vi kommer til at sløjfe over hele den linkede liste frigøre hvert element. Nu er vi nødt til at være forsigtig, så her vi have en midlertidig variabel, der er lagring markøren til den næste element i den linkede liste. Og så vil vi fri det aktuelle element. 

Vi er nødt til at være sikker på, vi gør dette, da vi kan ikke bare frigøre det aktuelle element og derefter prøve at gå til det næste pointer siden når vi befriede det hukommelse bliver ugyldig. Så vi nødt til at holde omkring en pegepind til det næste element, så vi kan frigøre aktuelle element, og så vi kan opdatere vores aktuelle element til at pege på det næste element. 

Vi vil sløjfe, mens der er elementer i denne linkede liste. Vi vil gøre det for alle sammenkædede lister hash tabellen, og når vi er færdig med det, har vi helt losses hash tabellen, og vi er færdige. Så det er umuligt for losser til nogensinde returnere falsk, og når vi er færdige, vi bare returnere sandt.