Rob BOWDEN: Hi. Mimi nina Rob, na hash hebu ufumbuzi huu nje. Hivyo hapa tunakwenda kutekeleza ujumla hash meza. Tunaona kwamba struct node ya hash wetu meza ni kwenda kuangalia kama hii. Hivyo ni kwenda kuwa na neno char safu ya ukubwa urefu pamoja na 1. Usisahau 1 tangu kiwango cha juu neno katika kamusi ni 45 wahusika, na kisha tunakwenda haja moja tabia ya ziada kwa ajili ya backslash 0. 

Na kisha hash wetu meza katika kila ndoo ni kwenda kuhifadhi wanaohusishwa orodha ya nodes. Sisi siyo kufanya linear uchunguzi hapa. Na hivyo katika ili kuendana na ijayo hiki katika ndoo, tunahitaji struct nodi * ijayo. Hivyo kwamba ni nini node inaonekana kama. Sasa, hapa ni tamko ya hash wetu meza. Ni kwenda na 16,384 ndoo, lakini idadi hiyo kweli haina jambo. Na hatimaye, tunakwenda na variable hashtable_size kimataifa, ambayo ni kwenda kuanza mbali kama 0, na ni kwenda kuweka wimbo wa jinsi maneno mengi walikuwa katika kamusi yetu. Sawa. 

Hivyo basi tuangalie mzigo. Hivyo taarifa mzigo kwamba, kuirudisha bool. Kurudi kweli kama ni mafanikio kubeba na uongo vinginevyo. Na inachukua const * Char nyota kamusi, ambayo ni kamusi kwamba tunataka kufungua. Ili jambo la kwanza tunakwenda kufanya. Tunakwenda fopen dictionary for kusoma, na tunakwenda na kuhakikisha kwamba ulifanikiwa hivyo kama ni kurudi NULL, basi hatukuwa mafanikio kufungua kamusi na sisi haja ya kurudi uongo. 

Lakini kuchukua kwamba alifanya mafanikio wazi, basi tunataka kusoma dictionary. Hivyo kuweka wanaoendesha mpaka sisi kupata baadhi ya sababu ya kuvunja nje ya hii kitanzi ambayo tutaweza kuona. Hivyo kuweka wanaoendesha, na sasa tunakwenda kwa malloc node moja. Na bila shaka, tunahitaji makosa kuangalia tena hivyo kama mallocing hakuwa na kufanikiwa na tunataka kupakua node yoyote kwamba sisi kilichotokea kwa malloc kabla ya, karibu na kamusi na kurudi uongo. 

Lakini kupuuza kwamba, kuchukua sisi ilifanikiwa, kisha tunataka kutumia fscanf kusoma neno moja kutoka wetu kamusi ndani ya node yetu. Ili kukumbuka kwamba neno kuingia> ni char neno buffer ya ukubwa urefu pamoja na moja kwamba tunakwenda kuhifadhi neno in Hivyo fscanf ni kwenda na kurudi 1 kwa muda mrefu kama alikuwa na uwezo wa mafanikio kusoma neno kutoka faili. 

Kama ama makosa kinatokea au sisi kufikia mwisho wa faili, itakuwa si kurudi 1 katika kesi ambayo kama hana kurudi 1, sisi ni hatimaye kwenda kuvunja nje ya hii kitanzi wakati. Hivyo tunaona kwamba mara moja sisi kuwa na mafanikio kusoma neno katika kuingia> neno, kisha tunakwenda hash kwamba neno kwa kutumia hash kazi yetu. Hebu tuangalie hash kazi. 

Hivyo si kweli wanahitaji kuelewa hili. Na kwa kweli, sisi tu vunjwa hii hash kazi kutoka internet. Kitu tu unahitaji kutambua ni kwamba hii inahitaji const * Char neno, hivyo ni kuchukua kamba kama pembejeo na kurudi unsigned int kama pato. Ili wote hash kazi ni, ni inachukua katika pembejeo, inakupa index katika meza ya hash. Taarifa kwamba sisi ni modding na NUM_BUCKETS hivyo thamani hash akarudi kweli ni index katika meza ya hash na haina index zaidi ya mipaka ya safu. 

Hivyo kutokana na kwamba heshi, tunakwenda kwa hash neno kwamba sisi kusoma kutoka kamusi na kisha tunakwenda kutumia ambayo ina kuingiza kuingia katika meza hash. Sasa, hashtable hash ni sasa wanaohusishwa katika orodha ya meza hash, na inawezekana sana kwamba ni haki null. Tunataka kuingiza kuingia yetu mwanzo wa orodha hii wanaohusishwa, na hivyo tunakwenda kuwa na kuingia wetu wa sasa uhakika na kile hash meza sasa pointi na kisha tunakwenda kuhifadhi katika hash meza hash kuingia sasa. 

Hivyo mistari hizi mbili mafanikio kuingiza kuingia katika mwanzo wa wanaohusishwa orodha ya kwamba index katika meza hash. Mara baada ya sisi ni kosa na kwamba, tunajua kwamba sisi kupatikana neno lingine katika kamusi na sisi nyongeza tena. Kwa hiyo sisi kuendelea kufanya kwamba mpaka fscanf hatimaye anarudi kitu yasiyo 1 katika ambayo uhakika kukumbuka kwamba tunahitaji kuingia bure, hivyo hapa, sisi malloced kuingia na sisi walijaribu kusoma kitu kutoka kamusi. Na sisi hakuwa mafanikio kusoma kitu kutoka kamusi ambayo kesi tunahitaji kuingia bure kwamba sisi kweli kamwe kuweka katika meza hash na hatimaye kuvunja. 

Mara baada ya sisi kuvunja nje, tunahitaji kuona, vizuri, Je, sisi kuvunja nje kwa sababu kuna ilikuwa makosa kusoma kutoka faili, au Je, sisi kuvunja nje kwa sababu sisi kufikiwa mwisho wa faili? Kama kulikuwa na makosa, kisha tunataka kurudi uongo kwa sababu mzigo hakuwa kufanikiwa, na katika mchakato, tunataka kupakua maneno yote sisi kusoma katika na karibu faili dictionary. Kutokana hatukuwa kufanikiwa, kisha sisi tu bado haja ya karibu kamusi faili, na hatimaye kurudi kweli tangu tumekuwa mafanikio kubeba dictionary. Na kwamba ni kwa ajili ya shehena. 

Hivyo sasa kuangalia, kutokana na kubeba hash meza, ni kwenda kuangalia kama hii. Ili kuangalia, kuirudisha bool, ambayo ni kwenda kuonyesha kama kupita katika char * neno, kama kupita katika string ni katika kamusi yetu. Hivyo kama ni katika kamusi, ikiwa ni katika hash wetu meza, sisi kurudi kweli, na kama siyo, sisi kurudi uongo. Kutokana na kupita katika neno hili, sisi ni kwenda hash neno. 

Sasa, jambo muhimu kutambua ni kwamba katika mzigo, sisi alijua kwamba yote ya maneno walikuwa wanakwenda kuwa kesi ya chini, lakini hapa, sisi siyo hivyo uhakika. Kama sisi kuangalia hash yetu kufanya kazi, hash kazi yetu kweli ni lowercasing kila tabia neno la Mungu. Hivyo bila kujali mtaji wa neno, hash yetu kufanya kazi ni kwenda kurudi sawa index kwa chochote mtaji ni kama ingekuwa kurejea kwa ajili ya kabisa lowercase toleo la neno. Sawa. 

Hivyo kwamba ni index yetu. Ni hash meza kwa neno hili. Sasa, hii kwa kitanzi ni kwenda kwa zaidi ya orodha wanaohusishwa kwamba ilikuwa ni saa index. Hivyo taarifa sisi ni initializing kuingia kwa uhakika na kwamba index. Sisi ni kwenda kuendelea wakati kuingia gani si sawa NULL, na kukumbuka kwamba kuhuisha pointer katika orodha yetu wanaohusishwa kuingia sawa na kuingia> ijayo, hivyo kuwa na kuingia hatua wetu wa sasa na bidhaa ijayo katika orodha wanaohusishwa. Sawa. 

Kwa hiyo kwa kila kuingia katika orodha wanaohusishwa, sisi ni kwenda kutumia strcasecmp. Ni si strcmp kwa sababu mara nyingine tena, sisi wanataka kufanya mambo kesi insensitively. Hivyo sisi kutumia strcasecmp kulinganisha neno kwamba ilipitishwa kwa kazi hii dhidi ya neno ni katika kuingia hii. Kama kuirudisha 0, hiyo ina maana kulikuwa na mechi, katika kesi ambayo tunataka kurudi kweli. Sisi mafanikio kupatikana neno katika hash wetu meza. 

Kama kulikuwa na si mechi, basi sisi ni kwenda kwa kitanzi tena na kuangalia kuingia ijayo. Na tutaweza kuendelea looping wakati kuna ni entries katika orodha hii wanaohusishwa. Kile kinachotokea kama sisi kuvunja nje ya hii kwa kitanzi? Hiyo ina maana sisi hawakuona kuingia kwamba kuendana neno hili, katika kesi ambayo sisi kurudi uongo zinaonyesha kwamba yetu hash meza hakuwa vyenye neno hili. Na kwamba ni kwa ajili ya kuangalia. Sawa. 

Hivyo basi tuangalie kawaida. Sasa, ukubwa ni kwenda kuwa pretty rahisi tangu kumbuka katika mzigo, kwa kila neno sisi kupatikana sisi incremented kimataifa variable hashtable_size. Hivyo ukubwa kazi ni kwenda na kurudi kwamba kimataifa variable, na hiyo ni yake. 

Sasa hatimaye, tunahitaji kupakua kamusi mara moja kila kitu kosa. Hivyo ni jinsi sisi ni kwenda kufanya hivyo? Haki hapa, sisi ni wanaoendesha juu ya yote ndoo ya hash wetu meza. Hivyo kuna NUM_BUCKETS ndoo. Na kwa kila orodha wanaohusishwa katika hash wetu meza, tunakwenda kitanzi juu ya ukamilifu wa orodha wanaohusishwa kumkomboa kila kipengele. Sasa, sisi haja ya kuwa makini, hivyo hapa sisi kuwa na kutofautiana muda kwamba kuhifadhi pointer ijayo hiki katika orodha wanaohusishwa. Na kisha tunakwenda bure hiki sasa. 

Tunahitaji kuwa na uhakika sisi kufanya hivyo tangu sisi huwezi bure hiki sasa na kisha kujaribu kupata pointer ijayo tangu mara moja sisi huru ni kumbukumbu inakuwa batili. Kwa hiyo, tunahitaji kuweka karibu pointer kwa hiki ijayo, basi tunaweza bure hiki sasa, na kisha tunaweza kuboresha hiki wetu wa sasa kwa uhakika na hiki ijayo. 

Tutaweza kitanzi wakati kuna mambo katika orodha hii wanaohusishwa. Tutaweza kufanya hivyo kwa orodha wote wanaohusishwa katika meza hash, na mara moja sisi ni kosa na kwamba, tumekuwa kabisa unloaded meza hash, na sisi ni kosa. Hivyo ni vigumu kwa unloads milele kurudi uongo, na wakati sisi ni kosa, sisi tu kurudi kweli.