ROB BOWDEN: Hi. Ek is Rob, en laat hash hierdie oplossing uit. So hier gaan ons te implementeer 'n algemene hash tafel. Ons sien dat die struct knoop van ons hash tafel gaan lyk soos hierdie. So dit gaan 'n kar woord te hê verskeidenheid van grootte lengte plus 1. Moenie vergeet om die 1 sedert die maksimum woord in die woordeboek is 45 karakters, en dan gaan ons moet 'n ekstra karakter vir die backslash 0. 

En dan is ons hash tafel in elke emmer gaan slaan 'n gekoppel lys van nodes. Ons is nie besig lineêre indringende hier. En so in orde om te skakel na die volgende element in die emmer, moet ons 'n struct knoop * volgende. So dit is wat 'n knoop lyk. Nou, hier is die verklaring van ons hash tafel. Dit gaan 16384 emmers te hê, maar dat die getal nie regtig saak. En ten slotte, gaan ons die globale veranderlike hashtable_size, wat gaan begin af as 0, en dit is gaan om tred te hou hoeveel woorde was in ons woordeboek. Alle regte. 

So kom ons neem 'n blik op las. So sien dat las, dit gee 'n Bool. Jy terugkeer waar as dit was suksesvol gelaai en valse anders. En dit neem 'n konst kar * ster woordeboek, wat is die woordeboek dat ons wil oopmaak. So wat is die eerste ding wat ons gaan doen. Ons gaan die woordeboek fopen vir lees, en ons gaan te hê om seker te maak dat dit daarin geslaag om so as dit NULL teruggekeer het, dan is ons het nie die woordeboek suksesvol oop en ons moet valse om terug te keer. 

Maar die veronderstelling dat dit suksesvol gedoen oop, dan wil ons om te lees die woordeboek. So hou herhaling totdat ons 'n paar rede om te breek uit hierdie lus wat ons sal sien. So hou herhaling, en nou gaan ons 'n enkele nodus malloc. En natuurlik moet ons tjek aan fout weer so as mallocing nie slaag en ons wil 'n knoop wat ons af te laai gebeur malloc voor, sluit die woordeboek en terugkeer onwaar. 

Maar ignoreer dat die aanvaarding van ons geslaag het, dan wil ons gebruik fscanf 'n enkele woord uit te lees ons woordeboek in ons node. So onthou dat entry-> woord is die kar woord buffer grootte lengte plus een wat ons gaan slaan die woord in So fscanf gaan 1 so lank om terug te keer soos dit was in staat om suksesvol te lees 'n woord van die lêer. 

As óf 'n fout gebeur of ons bereik die einde van die lêer, sal dit nie terug 1 in welke geval, indien dit nie terug 1, ons is uiteindelik gaan om te breek uit hierdie while loop. So sien ons dat wanneer ons suksesvol lees 'n woord in entry-> woord, dan gaan ons hash wat die woord met behulp van ons hash funksie. Kom ons neem 'n blik op die hash funksie. 

Sodat jy nie regtig nodig het nie om dit te verstaan. En eintlik, het ons net getrek hierdie hash funksie van die internet. Die enigste ding wat jy nodig het om te erken, is dat dit neem om 'n konst kar * woord, so dit is die neem van 'n string as invoer en terugkeer van 'n unsigned int as uitset. So dit is al wat 'n hash funksie is, is dit neem in 'n invoer, dit gee jou 'n indeks in die hash tafel. Let daarop dat ons modding deur NUM_BUCKETS So het die hash waarde wat eintlik is 'n indeks in die hash tafel en nie verder as die indeks grense van die skikking. 

So gegee dat hash funksie, ons gaan die woord wat ons lees hash uit die woordeboek en dan gaan ons om dit te gebruik het om in te voeg die toetrede tot die hash tafel. Nou, hashtable hash is die huidige gekoppel lys in die hash tafel, en dit is baie moontlik dat net NULL. Ons wil ons inskrywing aan die te voeg begin van hierdie geskakelde lys, en so Ons gaan ons huidige toegang tot 'n verwys na wat die hash tafel tans punte na en dan gaan ons te slaan in die hash tafel by die hash die huidige inskrywing. 

So het hierdie twee lyne suksesvol voeg die inskrywing aan die begin van die gekoppel lys op daardie indeks in die hash tafel. Sodra ons klaar is met dit, ons weet dat ons het 'n ander woord in die woordeboek en ons inkrementeer weer. So ons hou om dit te doen totdat fscanf uiteindelik terug iets nie 1 by watter punt onthou dat ons nodig het om te gratis toegang, so hier het ons 'n malloced inskrywing en ons probeer om iets te lees van die woordeboek. En ons het nie suksesvol gelees iets van die woordeboek waarin geval moet ons die inskrywing dat ons te bevry nooit eintlik sit in die hash tafel en uiteindelik breek. 

Sodra ons breek, het ons nodig het om te sien, wel, het ons breek, want daar is 'n fout met die lees van die lêer, of het ons breek, want ons bereik die einde van die lêer? As daar 'n fout is, dan wil ons terugkeer valse omdat vrag het nie slaag nie, en in die proses, ons wil los al die woorde wat ons lees in en sluit die woordeboek lêer. Veronderstelling ons het daarin slaag, dan het ons net nog steeds nodig om die woordeboek te sluit dien, en uiteindelik terug te keer waar nie, aangesien ons het suksesvol gelaai die woordeboek. En dit is dit vir vrag. 

So nou gaan, gegee 'n gelaaide hash tafel, gaan om te kyk soos hierdie. So gaan, dit gee 'n Bool, wat gaan om aan te dui of die geslaag-in kar * woord, of die geslaag-in string is in ons woordeboek. So indien dit in die woordeboek, indien dit in ons hash tafel, sal ons terugkeer waar, en as dit is nie, Ons sal terugkeer onwaar. Gegewe hierdie geslaag-in woord, ons is gaan om die woord te hash. 

Nou, 'n belangrike ding om te besef is wat in vrag, ons het geweet dat al die woorde gaan laer geval te wees, Maar hier, ons is nie so seker nie. As ons neem 'n blik op ons hash funksie, ons hash funksie eintlik is lowercasing elke karakter van die woord. So, ongeag van die kapitalisasie van woord, is ons hash funksie gaan terugkeer om die dieselfde indeks vir wat ook al die kapitalisasie is as dit sou hê terug vir 'n heeltemal klein weergawe van die woord. Alle regte. 

So dit is ons indeks. Dit is die hash tafel vir hierdie woord. Nou, hierdie lus vir gaan die geskakelde lys te oor Dit was op daardie indeks. So sien ons initializing inskrywing om aan te dui dat die indeks. Ons gaan om voort te gaan, terwyl inskrywing doen nie gelyk NULL, en onthou dat opdatering van die wyser in ons gekoppel lys inskrywing gelyk entry-> langs, so het ons huidige inskrywing punt aan die volgende item in geskakelde lys. Alle regte. 

So vir elke inskrywing in die geskakelde lys, ons gaan strcasecmp te gebruik. Dit is nie strcmp omdat ons weer wil dinge geval insensitively doen. So gebruik ons ​​strcasecmp die woord te vergelyk Dit was vir hierdie funksie geslaag teen die woord wat is in hierdie inskrywing. As dit terugkeer 0, wat beteken dat daar 'n wedstryd, in welke geval ons wil terug waar. Ons het met sukses het die woord in ons hash tafel. 

As daar nie 'n wedstryd, dan is ons gaan loop weer en kyk na die volgende inskrywing. En ons sal voortgaan om herhaling terwyl daar is inskrywings in hierdie verband lys. Wat gebeur as ons breek uit hierdie lus? Dit beteken dat ons nie 'n inskrywing te vind dat ooreenstem met hierdie woord, in welke geval ons terugkeer valse aan te dui dat ons hash tafel het nie hierdie woord bevat. En dit is dit vir check. Alle regte. 

So kom ons neem 'n blik op die grootte. Nou, is die grootte gaan wees redelik maklik sedert onthou in las, vir elke woord ons het ons geinkrementeer 'n globale veranderlike hashtable_size. So het die grootte funksie is net gaan om terug te keer dat die globale veranderlike, en dit is dit. 

Nou uiteindelik, moet ons los die woordeboek sodra alles is gedoen. So hoe gaan ons dit doen? Reg hier, ons herhaling oor die hele emmers van ons hash tafel. So is daar NUM_BUCKETS emmers. En vir elke gekoppel lys in ons hash tafel, gaan ons lus oor die geheel van die geskakelde lys bevry elke element. Nou moet ons versigtig wees, so hier is ons het 'n tydelike veranderlike wat die stoor van die wyser na die volgende element in die geskakelde lys. En dan gaan ons vry Die huidige element. 

Ons moet seker maak ons ​​doen dit omdat ons wees kan nie net vry om die huidige element en probeer dan die volgende wyser om toegang te verkry sedert wanneer ons bevry dit die geheue ongeldig. Dus moet ons om 'n wyser te hou die volgende element, dan kan ons bevry van die huidige element, en dan kan ons werk ons huidige element om aan te dui die volgende element. 

Ons sal loop, terwyl daar is elemente in hierdie verband lys. Ons sal doen wat vir alle gekoppelde lyste in die hash tafel, en sodra ons klaar is met wat, ons het heeltemal afgelaai word die hash tafel, en ons klaar is. Dus is dit onmoontlik vir unloads ooit terugkeer valse, en toe ons klaar is, het ons net terug waar.