>> 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.