>> ROB BOWDEN: Ahoj.
Jsem Rob, a pojďme hash Tento roztok se.
Takže tady budeme realizovat Obecně hash tabulky.
Vidíme, že struct uzel naší hash tabulka bude vypadat takto.
Takže to bude mít char slovo pole o délce size plus 1.
Nezapomeňte 1 od maxima slovo ve slovníku je 45
znaky, a pak budeme Potřebujeme jeden další znak pro
zpětné lomítko 0.
>> A pak naše hash tabulka v každém kbelík se bude ukládat
spojový seznam uzlů.
Neděláme lineární snímací zde.
A tak, aby odkazy na další prvek v kbelíku, musíme
struct uzel * další.
Takže to je to, co uzel vypadá.
Nyní je zde prohlášení z naší tabulky hash.
Bude to mít 16.384 kbelíky, ale že počet nezáleží.
A konečně budeme mít globální proměnná hashtable_size, které
se chystá odstartovat jako 0, a to bude sledovat, kolik slov
byly v našem slovníku.
Dobrá.
>> Takže pojďme se podívat na zatížení.
Takže všimnout, že zatížení, vrací bool.
Můžete se vrátit true, pokud bylo úspěšné naložený a v opačném případě false.
A to trvá const char * hvězdu slovník, který je slovník
který chceme otevřít.
Takže to je první věc, budeme dělat.
Chystáme se fopen slovník pro čtení, a budeme mít
aby se ujistil, že se podařilo, aby v případě, to se vrátilo NULL, pak ne
úspěšně otevřít slovník a my se musíme vrátit false.
>> Ale za předpokladu, že to úspěšně udělal otevřené, pak chceme přečíst
slovník.
Takže mějte opakování, dokud nenajdeme nějaký důvod, aby se vymanily z této
smyčky, které uvidíme.
Takže mějte opakování, a teď jdeme malloc jeden uzel.
A samozřejmě, musíme k chybě kontroly znovu, takže pokud mallocing neuspěl
a chceme vyložit libovolný uzel, který my stalo malloc před zavřete
slovník a vrátí false.
>> Ale ignorovat, že za předpokladu, že se podařilo, pak chceme použít fscanf
přečíst jediné slovo z naší slovník do našeho uzlu.
Takže pamatujte, že vstupní-> slovo je char Slovo vyrovnávací délky plus velikosti
jedno, že budeme uložit slovo dovnitř
Takže fscanf se chystá k návratu 1 tak dlouho, jak to bylo možné úspěšně číst
slovo ze souboru.
>> Pokud to buď chyba se stane, nebo se dostaneme konec souboru, nebude
vrátí 1 v tom případě, pokud to není vrátí 1, jsme se konečně chystá zlomit
z tohoto cyklu while.
Takže vidíme, že jednou se nám podařilo mít číst slovo do
entry-> slovo, pak jedeme do hash že slovo pomocí našeho hash funkce.
Pojďme se podívat na funkce hash.
>> Takže nemáte opravdu potřebujete to pochopit.
A vlastně, prostě vytáhl to hash funkce z internetu.
Jediná věc, kterou je třeba si uvědomit, je že to trvá const char * slovo,
tak to trvá řetězec jako vstup a vrácením unsigned int jako výstup.
Tak to je vše, funkce hash je, je to bere na vstupu, to vám dává
index do tabulky hash.
Všimněte si, že jsme modding by NUM_BUCKETS takže vrácena hodnota hash
ve skutečnosti je index do tabulky hash a není index za
meze pole.
>> Takže za předpokladu, že hashovací funkce, jedeme hash slovo, které čteme
ze slovníku, a pak jdeme k použití, který má vložit
vstup do hash tabulky.
Nyní, Hashtable hash je aktuální spojový seznam v tabulce hash, a
je velmi pravděpodobné, že je jen NULL.
Chceme vložit náš vstup na začátku tohoto spojového seznamu, a tak
budeme mít naši aktuální položku poukázat na to, co hash tabulky v současné době
body, a pak budeme ukládat v hash tabulce na hash
aktuální záznam.
>> Takže tyto dva řádky úspěšně vložit Vstup na začátku
spojový seznam v tomto indexu v tabulce hash.
Jakmile jsme hotovi s tím, víme, že jsme našli další slovo
slovník a opět zvyšovat.
Tak jsme to dělat, dokud fscanf konečně vrátí něco non 1 na
kterém místě si uvědomit, že musíme vstup zdarma, takže tady jsme malloced
vstup a snažili jsme se, aby si něco přečíst ze slovníku.
A my jsme neměli úspěšně číst něco ze slovníku, ve kterém
případě musíme uvolnit záznam, který my nikdy dát do hash tabulky
a konečně zlomit.
>> Poté, co jsme se vymanit, musíme vidět, dobře, jsme se zlomit, protože tam
byla chyba při čtení ze souboru, nebo jsme se zlomit, protože jsme dosáhli
konec souboru?
Pokud došlo k chybě, pak chceme, aby return false, protože zatížení ne
uspět, a v tomto procesu, chceme vyložit všechna slova, která čteme
v a zavřete soubor slovníku.
Za předpokladu, že jsme se to podaří, pak jsme jen Stále je třeba zavřít slovník
soubor, a nakonec se vrátíte pravda, protože jsme úspěšně vložen
slovník.
A to je pro zatížení.
>> Takže teď zjistit, vzhledem k tomu naložené hash tabulky, bude vypadat takto.
Tak se podívejte, vrací bool, který se chystá uvést, zda
předaný v char * slovo, zda uplynulo-in string je v našem slovníku.
Takže, je-li ve slovníku, je-li v naší hašovací tabulce, vrátíme se
pravda, a pokud to není, vrátíme false.
Vzhledem k tomu, to prošel-in slovo, my jsme bude hash slovo.
>> Nyní důležité si uvědomit, je že v zátěži, věděli jsme, že všechny
slova se bude malá písmena, ale tady, my nejsme tak jistí.
Pokud se podíváme na náš hash funkce, naše hash funkce vlastně
je lowercasing každý znak slova.
Takže bez ohledu na kapitalizace Slovo, náš hash funkce se chystá
vrátit stejný index pro cokoliv kapitalizace je, jak to bude mít
se vrátil k úplně malá verze slova.
Dobrá.
>> Tak to je náš index.
Je to hash tabulka pro toto slovo.
Teď to pro smyčce se děje na více než na spojový seznam
která byla v daném indexu.
Takže všimnete jsme inicializaci vstup poukázat na daném indexu.
Budeme se i nadále při vstupu dělá není rovno NULL, a pamatujte, že
aktualizovat ukazatel v našem propojeném seznamu vstup se rovná entry-> další, takže mají
náš současný vstupní bod do Dalším bodem v propojeném seznamu.
Dobrá.
>> Takže pro každou položku v propojeném seznamu, budeme používat strcasecmp.
Není to strcmp, protože jednou jsme chtějí dělat věci případ necitlivě.
Tak jsme se použít strcasecmp porovnat slovo , který byl předán k této funkci
proti slovu, které je v této položce.
Pokud se vrátí 0, to znamená, že tam byl Zápas, ve kterém případě chceme, aby
return true.
Úspěšně jsme našli Slovo v našem tabulky hash.
>> V případě, že nebyl zápas, pak jsme jít na smyčku znovu a podívat se na
další záznam.
A budeme pokračovat smyčkování zatímco jsou položky v této aplikaci v seznamu.
Co se stane, když se rozejdeme z toho pro smyčce?
To znamená, že jsme neměli najít položku, která uzavřeno toto slovo, v tom případě
vrátíme false což znamená, že naše hash tabulka neobsahuje toto slovo.
A to je pro kontrolu.
Dobrá.
>> Takže pojďme se podívat na velikosti.
Nyní, velikost bude velmi jednoduchá od nezapomeňte v zátěži, pro každé slovo
zjistili jsme, zvýší globální variabilní hashtable_size.
Takže funkce velikost je jen bude vracet, že globální
variabilní, a to je vše.
>> Nyní konečně, musíme uvolnit slovník jednou všechno hotovo.
Tak jak budeme dělat, že?
Právě tady, my smyčky přes všechny kbelíky naší hašovací tabulky.
Takže tam jsou NUM_BUCKETS kbelíky.
A pro každou aplikaci v seznamu v naší hash stůl, jedeme do smyčky přes
celistvost propojeného seznamu uvolní každý prvek.
Nyní musíme být opatrní, tak jsme tady mají dočasnou proměnnou, které je
uložení ukazatele na další prvek v propojeném seznamu.
A pak budeme zdarma aktuální prvek.
>> Musíme si být jisti, že jsme to udělat, protože my nemůže jen tak uvolnit aktuálního prvku
a pak zkuste přejděte na další ukazatele protože jakmile ji osvobodil
paměť se stává neplatným.
Takže musíme držet kolem ukazatel na Další prvek, pak se můžeme osvobodit
aktuální prvek, a pak se můžeme aktualizovat Naše aktuální prvek poukázat na
další prvek.
>> Budeme smyčky, zatímco tam jsou prvky, v tomto propojeném seznamu.
Uděláme to pro všechny propojené seznamy v hash tabulka, a jakmile budeme hotovi
s tím, že jsme zcela vyloženo hash tabulka, a jsme hotovi.
Takže je to nemožné, uvolní se někdy return false, a když jsme hotovi, můžeme
jen vrátit true.