ROB BOWDEN: Hi. Ik ben Rob, en hasj laten we deze oplossing uit. Dus hier gaan we implementeren een algemene hash table. We zien dat de structuur knooppunt van onze hash tafel gaat uitzien. Dus het gaat om een ​​char woord hebben matrix van grootte lengte plus 1. Vergeet niet de 1 omdat de maximale woord in het woordenboek is 45 personages, en dan gaan we naar moet een extra karakter voor de backslash 0. 

En dan is onze hash table in elk emmer gaat slaan een gelinkte lijst van knooppunten. We zijn niet lineair hier indringende doen. En dus om te linken naar het volgende element in de emmer, hebben we een struct knoop * volgende. Dus dat is wat een knooppunt eruit ziet. Nu, hier is de verklaring van onze hash table. Het gaat om 16.384 bakken hebben, maar dat aantal maakt niet echt uit. En tot slot, we gaan de globale variabele hashtable_size die gaat beginnen als 0, en het is gaan om bij te houden hoeveel woorden waren in onze woordenboek. Oke. 

Dus laten we eens een kijkje nemen op belasting. Dus merken dat de belasting, retourneert een bool. U return true als het succesvol was geladen en anders false. En het duurt een const char * sterren woordenboek dat de woordenlijst dat we willen openen. Dus dat is het eerste wat we gaan doen. We gaan naar het woordenboek fopen voor lezen, en we gaan te hebben om ervoor te zorgen dat het gelukt dus als het NULL terug, dan hebben we niet het woordenboek met succes te openen en we moeten return false. 

Maar ervan uitgaande dat het met succes gedaan geopend, dan willen we lezen de woordenboek. Dus houd looping tot we enkele reden om uit te breken van deze lus die we zullen zien. Dus hou looping, en nu gaan we om een ​​enkel knooppunt malloc. En natuurlijk moeten we check fout weer dus als mallocing niet gelukt en we willen elke node die wij lossen gebeurd met malloc voor, sluit de woordenboek en return false. 

Maar negeren dat, uitgaande we gelukt, dan willen we fscanf gebruiken om een ​​enkel woord lezen uit onze woordenboek in onze knooppunt. Dus onthoud dat entry-> woord is de char woord buffer van grootte lengte plus een die we gaan bewaar het woord in Dus fscanf gaat terug 1 zolang zoals het was in staat om succesvol te lezen een Het woord van het bestand. 

Als een van beide een fout gebeurt of we bereiken het einde van het bestand, het zal niet return 1 in dat geval als het niet return 1, we eindelijk gaat breken uit deze while lus. Zo zien we dat als we succes hebben lees een woord in entry-> woord, dan gaan we naar hash dat woord gebruik van onze hash-functie. Laten we eens een kijkje nemen op de hash-functie. 

Zodat je niet echt nodig hebt om dit te begrijpen. En eigenlijk hebben we alleen deze getrokken hash-functie van het internet. Het enige wat je moet erkennen is dat dit duurt een const char * woord, dus het is het nemen van een string als input en retourneren van een unsigned int als output. Dus dat is al een hash-functie is, is het neemt in een input, het geeft je een geeft index in de hash tabel. Merk op dat we modding door NUM_BUCKETS dus de hash-waarde terug eigenlijk is een index in de hash table en niet geïndexeerd dan de grenzen van de array. 

Zo bepaalde hash-functie, we gaan aan het woord die we lezen hash uit het woordenboek en dan gaan we te gebruiken dat moet steek de binnenkomst in de hash tabel. Nu, hash hash is de huidige gelinkte lijst in de hash tabel en het is heel goed mogelijk dat is gewoon NULL. We willen onze toegang aan de voegen begin van deze gelinkte lijst, en dus we gaan onze huidige item hebben wijzen op wat de hash tabel momenteel punten aan en dan gaan we op te slaan in de hash tabel aan het hekje de huidige vermelding. 

Dus deze twee lijnen met succes te voegen de ingang aan het begin van de gelinkte lijst op die index in de hash tabel. Zodra we klaar zijn met dat, we weten dat vonden we een ander woord in de woordenboek en we verhogen opnieuw. Dus houden we dat doen totdat fscanf eindelijk weer iets niet 1 op welk punt herinneren dat we moeten gratis toegang, dus hier, we malloced een binnenkomst en we hebben geprobeerd om iets te lezen uit het woordenboek. En we hebben niet met succes gelezen iets uit het woordenboek waarin geval moeten we het item dat we vrij nooit daadwerkelijk in de hash tabel gezet en uiteindelijk breken. 

Zodra we uit te breken, moeten we zien, nou ja, hebben we breken omdat er was een fout bij het lezen van het bestand, of hebben we breken omdat we bereikt het einde van het bestand? Als er een fout, dan willen we return false omdat belasting niet slagen, en in het proces, we willen lossen alle woorden die we lezen in en sluit het woordenboek bestand. Ervan uitgaande dat we niet slagen, dan kunnen we gewoon nog steeds nodig om het woordenboek te sluiten bestand, en tenslotte return true sinds we hebben met succes geladen de woordenboek. En dat is het voor de belasting. 

Dus nu controleren, gegeven een geladen hash table, gaat er zo uitzien. Dus check, het een bool terug, die zal aangeven of de doorgegeven in char * woord, of de doorgegeven in string is in ons woordenboek. Dus als het in het woordenboek, als het in onze hash table, we zullen terugkeren waar, en als het niet, we zullen valse terugkeren. Gezien deze doorgegeven in woord, we zijn gaan naar het woord hash. 

Nu, een belangrijk ding te herkennen is dat in de belasting, wisten we dat al de woorden zouden kleine letters, maar hier, we zijn niet zo zeker van. Als we een kijkje nemen op onze hash-functie, onze hash-functie eigenlijk wordt lowercasing elk karakter van het woord. Dus ongeacht de kapitalisatie van woord, is onze hash-functie gaat terug dezelfde index voor wat de kapitalisatie is zoals het zou moeten terug voor een volledig kleine versie van het woord. Oke. 

Dus dat is onze index. Het is de hash-tabel voor dit woord. Nu, deze lus gaat de gekoppelde lijst OVER dat was die index. Zo merken we initialiseren binnenkomst te wijzen die index. We gaan blijven terwijl binnenkomst doet niet gelijk NULL, en vergeet niet dat bijwerken van de aanwijzer in onze gelinkte lijst binnenkomst gelijk entry-> volgende, zo hebben onze huidige toegangspunt tot de volgende item in gelinkte lijst. Oke. 

Dus voor elk item in de gelinkte lijst, we gaan strcasecmp gebruiken. Het is niet strcmp want nogmaals, we willen dingen geval ongevoelig doen. We gebruiken dus strcasecmp om het woord te vergelijken die werd doorgegeven aan deze functie tegen het woord dat in deze ingang. Als het weer 0, dat betekent dat er een wedstrijd, waarbij we willen return true. Wij hebben met succes vonden de woord in onze hash table. 

Als er geen match, dan zijn we gaat lus opnieuw en kijk naar de volgende item. En we gaan terwijl er verder looping zijn items in deze gelinkte lijst. Wat gebeurt er als we breken uit deze lus? Dat betekent dat we een ingang niet vinden dat paste dit woord, in welk geval we return false aangeven dat onze hash table heeft dit woord niet bevatten. En dat is het voor controle. Oke. 

Dus laten we eens een kijkje nemen op grootte. Nu, de grootte gaat vrij eenvoudig te zijn sinds herinneren in de belasting, voor elk woord we vonden we opgehoogd een globale variabele hashtable_size. Zodat de grootte functie is gewoon gaan dat de wereldwijde terug variabele, en dat is het. 

Nu eindelijk, moeten we lossen het woordenboek als alles klaar is. Dus hoe gaan we dat doen? Right here, we looping over alle emmers van onze hash table. Dus er zijn NUM_BUCKETS emmers. En voor elke gekoppelde lijst in onze hash tafel, gaan we lus over de onderdelen van de gekoppelde lijst vrijmaken van elk element. Nu moeten we voorzichtig zijn, dus hier zijn we een tijdelijke variabele die opslaan van de pointer naar de volgende element in de gelinkte lijst. En dan gaan we gratis het huidige element. 

We moeten zorgen dat we dit doen omdat we kan niet alleen gratis de huidige element en dan proberen om naar de volgende pointer want zodra we bevrijd het de geheugen wordt ongeldig. Dus moeten we houden rond een pointer naar het volgende element, dan kunnen we gratis de huidige element, en dan kunnen we updaten het actuele element wijzen het volgende element. 

We zullen lus terwijl er elementen in deze gelinkte lijst. We zullen dat doen voor alle gekoppelde lijsten in de hash table, en zodra we klaar zijn met dat, hebben we volledig gelost de hash table, en we zijn klaar. Dus het is onmogelijk voor ontlaadt ooit return false, en als we klaar zijn, we gewoon terug waar.