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