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.