ROB BOWDEN: Ahoj. Som Rob, a poďme hash Tento roztok sa. Takže tu budeme realizovať Všeobecne hash tabuľky. Vidíme, že struct uzol našej hash tabuľka bude vyzerať takto. Takže to bude mať char slovo pole o dĺžke size plus 1. Nezabudnite 1 od maxima slovo v slovníku je 45 znaky, a potom budeme Potrebujeme jeden ďalší znak pre spätné lomítko 0. 

A potom naše hash tabuľka v každom vedro sa bude ukladať spájať zoznam uzlov. Nerobíme lineárne snímacie tu. A tak, aby odkazy na ďalšie prvok v vedre, musíme struct uzol * ďalšie. Takže to je to, čo uzol vyzerá. Teraz je tu vyhlásenie z našej tabuľky hash. Bude to mať 16.384 vedierka, ale že počet nezáleží. A konečne budeme mať globálna premenná hashtable_size, ktoré sa chystá odštartovať ako 0, a to bude sledovať, koľko slov boli v našom slovníku. Dobrá. 

Takže poďme sa pozrieť na zaťaženie. Takže všimnúť, že zaťaženie, vracia bool. Môžete sa vrátiť true, ak bolo úspešné naložený a v opačnom prípade false. A to trvá const char * hviezdu slovník, ktorý je slovník ktorý chceme otvoriť. Takže to je prvá vec, budeme robiť. Chystáme sa fopen slovník čítanie, a budeme mať aby sa ubezpečil, že sa podarilo, aby v prípade, to sa vrátilo NULL, potom nie úspešne otvoriť slovník a my sa musíme vrátiť false. 

Ale za predpokladu, že to úspešne urobil otvorené, potom chceme prečítať slovník. Takže majte opakovanie, kým nenájdeme nejaký dôvod, aby sa vymanili z tejto slučky, ktoré uvidíme. Takže majte opakovanie, a teraz ideme malloc jeden uzol. A samozrejme, musíme k chybe kontroly znovu, takže ak mallocing neuspel a chceme vyložiť ľubovoľný uzol, ktorý my stalo malloc pred zavrite slovník a vráti false. 

Ale ignorovať, že za predpokladu, že sa podarilo, potom chceme použiť fscanf prečítať jediné slovo z našej slovník do nášho uzla. Takže pamätajte, že vstupné-> slovo je char Slovo vyrovnávacej dĺžky plus veľkosti jedno, že budeme uložiť slovo dovnútra Takže fscanf sa chystá na návrat 1 tak dlho, ako to bolo možné úspešne čítať slovo zo súboru. 

Pokiaľ to buď chyba sa stane, alebo sa dostaneme koniec súboru, nebude vráti 1 v tom prípade, ak to nie je vráti 1, sme sa konečne chystá zlomiť z tohto cyklu while. Takže vidíme, že raz sa nám podarilo mať čítať slovo do entry-> slovo, potom ideme do hash že slovo pomocou nášho hash funkcie. Poďme sa pozrieť na funkcia hash. 

Takže nemáte naozaj potrebujete to pochopiť. A vlastne, proste vytiahol to hash funkcie z internetu. Jediná vec, ktorú je potrebné si uvedomiť, je že to trvá const char * slovo, tak to trvá reťazec ako vstup a vrátením unsigned int ako výstup. Tak to je všetko, funkcia hash je, je to berie na vstupe, to vám dáva index do tabuľky hash. Všimnite si, že sme modding by NUM_BUCKETS takže vrátená hodnota hash v skutočnosti je index do tabuľky hash a nie je index za medze poľa. 

Takže za predpokladu, že ich haš funkcie, ideme hash slovo, ktoré čítame zo slovníka, a potom ideme na použitie, ktorý má vložiť vstup do hash tabuľky. Teraz, Hashtable hash je aktuálne spájať zoznam v tabuľke hash, a je veľmi pravdepodobné, že je len NULL. Chceme vložiť náš vstup na začiatku tohto spojovaceho zoznamu, a tak budeme mať našu aktuálnu položku poukazujú na to, čo hash tabuľky v súčasnej dobe body, a potom budeme ukladať v hash tabuľke na hash aktuálny záznam. 

Takže tieto dva riadky úspešne vložiť Vstup na začiatku spájať zoznam v tomto indexe v tabuľke hash. Akonáhle sme hotoví s tým, vieme, že sme našli ďalšie slovo slovník a opäť zvyšovať. Tak sme to robiť, kým fscanf konečne vráti niečo non 1 na ktorom mieste si uvedomiť, že musíme vstup zadarmo, takže tu sme malloced vstup a snažili sme sa, aby si niečo prečítať zo slovníka. A my sme nemali úspešne čítať niečo zo slovníka, v ktorom prípade musíme uvoľniť záznam, ktorý my nikdy dať do hash tabuľky a konečne zlomiť. 

Potom, čo sme sa vymaniť, musíme vidieť, dobre, sme sa zlomiť, pretože tam bola chyba pri čítaní zo súboru, alebo sme sa zlomiť, pretože sme dosiahli koniec súboru? Ak došlo k chybe, potom chceme, aby return false, pretože zaťaženie nie uspieť, a v tomto procese, chceme vyložiť všetky slová, ktoré čítame v a zatvorte súbor slovníka. Za predpokladu, že sme sa to podarí, potom sme len Stále je potrebné zavrieť slovník súbor, a nakoniec sa vrátite pravda, pretože sme úspešne vložený slovník. A to je pre zaťaženie. 

Takže teraz zistiť, vzhľadom k tomu naložené hash tabuľky, bude vyzerať takto. Tak sa pozrite, vracia bool, ktorý sa chystá uviesť, či odovzdaný v char * slovo, či uplynulo-in string je v našom slovníku. Takže, ak je v slovníku, je-li v našej hašovacej tabuľke, vrátime sa pravda, a ak to nie je, vrátime false. Vzhľadom k tomu, to prešiel-in slovo, my sme bude hash slovo. 

Teraz dôležité si uvedomiť, je že v záťaži, vedeli sme, že všetky slová sa bude malé písmená, ale tu, my nie sme tak istí. Ak sa pozrieme na náš hash funkcie, naše hash funkcia vlastne je lowercasing každý znak slová. Takže bez ohľadu na kapitalizácie Slovo, náš hash funkcie sa chystá vrátiť rovnaký index pre čokoľvek kapitalizácie je, ako to bude mať sa vrátil k úplne malá verzie slová. Dobrá. 

Tak to je náš index. Je to hash tabuľka pre toto slovo. Teraz to pre slučke sa deje na viac než na komunikačné zoznam ktorá bola v danom indexe. Takže všimnete sme inicializácii vstup poukázať na danom indexe. Budeme sa aj naďalej pri vstupe robí nie je rovné NULL, a pamätajte, že aktualizovať ukazovateľ v našom prepojenom zoznamu vstup sa rovná entry-> ďalšie, takže majú náš súčasný vstupný bod do Ďalším bodom v prepojenom zozname. Dobrá. 

Takže pre každú položku v prepojenom zoznamu, budeme používať strcasecmp. Nie je to strcmp, pretože raz sme chcú robiť veci prípad necitlivo. Tak sme sa použiť strcasecmp porovnať slovo , Ktorý bol odovzdaný k tejto funkcii proti slovu, ktoré je v tejto položke. Ak sa vráti 0, to znamená, že tam bol Zápas, v ktorom prípade chceme, aby return true. Úspešne sme našli Slovo v našom tabuľky hash. 

V prípade, že nebol zápas, potom sme ísť na slučku znova a pozrieť sa na ďalší záznam. A budeme pokračovať smyčkování zatiaľ čo sú položky v tejto aplikácii v zozname. Čo sa stane, keď sa rozídeme z toho pre sláčiky? To znamená, že sme nemali nájsť položku, ktorá uzavreté toto slovo, v tom prípade vrátime false čo znamená, že naše hash tabuľka neobsahuje toto slovo. A to je pre kontrolu. Dobrá. 

Takže poďme sa pozrieť na veľkosti. Teraz, veľkosť bude veľmi jednoduchá od nezabudnite v záťaži, pre každé slovo zistili sme, zvýši globálne variabilný hashtable_size. Takže funkcia veľkosť je len bude vracať, že globálna variabilný, a to je všetko. 

Teraz konečne, musíme uvoľniť slovník raz všetko hotové. Tak ako budeme robiť, že? Práve tu, my slučky cez všetky vedierka našej hašovacej tabuľky. Takže tam sú NUM_BUCKETS vedierka. A pre každú aplikáciu v zozname v našej hash stôl, ideme do slučky cez celistvosť prepojeného zoznamu uvoľní každý prvok. Teraz musíme byť opatrní, tak sme tu majú dočasnú premennú, ktoré je uloženie ukazovatele na ďalšie prvok v prepojenom zozname. A potom budeme zadarmo aktuálny prvok. 

Musíme si byť istí, že sme to urobiť, pretože my nemôže len tak uvoľniť aktuálneho prvku a potom skúste prejdite na ďalšie ukazovatele pretože akonáhle ju oslobodil pamäť sa stáva neplatným. Takže musíme držať okolo ukazovateľ na Ďalší prvok, potom sa môžeme oslobodiť aktuálny prvok, a potom sa môžeme aktualizovať Naše aktuálne prvok poukázať na ďalší prvok. 

Budeme slučky, zatiaľ čo tam sú prvky, v tomto prepojenom zozname. Urobíme to pre všetky prepojené zoznamy v hash tabuľka, a akonáhle budeme hotoví s tým, že sme úplne vyložený hash tabuľka, a sme hotoví. Takže je to nemožné, uvoľní sa niekedy return false, a keď sme hotoví, môžeme len vrátiť true.