Rob Bowden: Hi. Unë jam Rob, dhe të hash le të kjo zgjidhje jashtë. Pra, këtu ne jemi duke shkuar për të zbatuar një tabelë të përgjithshme hash. Ne e shohim se nyja struct të hash tonë tabela do të duket si ky. Pra, kjo do të ketë një fjalë char sërë gjatesi madhësisë plus 1. Mos harroni që nga 1 në maksimum fjalë në fjalor është 45 karaktere, dhe pastaj ne do të nevojë për një karakter shtesë për backslash 0. 

Dhe pastaj tabelën tonë hash në secilin kovë është duke shkuar për të ruajtur një listë e lidhur e nyjeve. Ne nuk jemi duke bërë lineare probing këtu. Dhe kështu që në mënyrë për të lidhur për të ardhshëm element në kovë, ne kemi nevojë për një nyje struct * ardhshme. Pra, kjo është ajo që një nyje duket si. Tani, këtu është deklarata i tryezën tonë hash. Ajo do të ketë 16.384 kova, por se numri nuk ka rëndësi. Dhe në fund, ne do të kemi hashtable_size globale ndryshueshme, e cila do të nisem si 0, dhe kjo është do të mbajnë gjurmët e sa shumë fjalë ishin në fjalorin tonë. Dakord. 

Pra, le të marrin një vështrim në ngarkesë. Pra të vini re se ngarkesës, ajo kthen një bool. Ju kthim i vërtetë në qoftë se ajo ishte sukses ngarkuar dhe false ndryshe. Dhe ajo merr një const char * ylli fjalor, i cili është dictionary që ne duam të hapur. Pra, kjo është gjëja e parë ne jemi duke shkuar për të bërë. Ne jemi duke shkuar për fopen fjalorin për lexim, dhe ne do të kemi për të siguruar që ajo arriti kështu që nëse ajo u kthye NULL, atëherë ne nuk e bëri me sukses të hapur fjalorin dhe ne duhet të kthimit të rreme. 

Por, duke supozuar se ajo e bëri me sukses hapur, atëherë ne duam të lexuar fjalor. Pra, të mbajtur looping deri sa të gjejmë disa arsye për të thyer nga kjo lak të cilat ne do të shohim. Pra mbani looping, dhe tani ne jemi duke shkuar për malloc një nyje të vetme. Dhe sigurisht, ne kemi nevojë për të gabuar kontroll përsëri kështu që nëse mallocing nuk pati sukses dhe ne duam që të shkarkoj ndonjë nyje që ne ndodhur me malloc para, të mbyllur fjalor dhe kthimit të rreme. 

Por duke injoruar se, duke supozuar ne pati sukses, atëherë ne duam të përdorim fscanf për të lexuar një fjalë të vetme nga tonë dictionary në nyje tonë. Pra, mos harroni se fjala e hyrjes-> është char tampon fjalë e gjatësisë madhësisë plus një që ne do të ruajtur fjalën in Pra fscanf do të kthehet 1 për aq kohë si ajo ishte në gjendje për të lexuar me sukses një fjalë nga file. 

Nëse një nga një gabim ndodh apo të arrijmë në fund të skedarit, ajo nuk do të kthehen 1 në të cilin rast në qoftë se ajo nuk ka kthehen me 1, ne jemi më në fund do të thyer nga kjo loop ndërsa. Pra, ne shohim se një herë ne kemi sukses lexoni një fjalë në hyrje-> fjalë, atëherë ne do të hash se fjala përdorur funksionin tonë të hash. Le të bëjmë një vështrim në funksion hash. 

Pra, ju nuk duhet të vërtetë për të kuptuar këtë. Dhe në të vërtetë, ne vetëm u tërhoq këtë hash funksion nga interneti. E vetmja gjë që ju duhet për të njohur është se kjo merr një const char * fjalën, kështu që është duke marrë një varg si input dhe kthyer një int unsigned si prodhim. Pra, kjo është e gjitha një funksion hash është, është ajo merr në një input, kjo ju jep ekber Indeksi në tabelën hash. Vini re që ne jemi modding nga NUM_BUCKETS kështu që vlera e hash kthyer në të vërtetë është një indeks në tabelë hash dhe nuk indeksi përtej caqeve të array. 

Pra, duke pasur parasysh se funksion hash, ne jemi duke shkuar te bej hash fjalën që ne të lexuar nga fjalori dhe pastaj ne do për të përdorur që ka për të futur hyrja në tabelën hash. Tani, hash hashtable është aktual lista e lidhur në tabelë hash, dhe kjo është shumë e mundur që është vetëm NULL. Ne duam të futur hyrjen tonë në fillimi i këtij listën e lidhur, dhe kështu ne do të ketë hyrjen tonë të tanishëm tregojnë për çfarë tryezë hash aktualisht pikë për të dhe pastaj ne jemi duke shkuar për të ruajtur në tabelën hash hash në hyrja aktuale. 

Pra, këto dy linja sukses futur hyrja në fillim të lista e lidhur në atë indeks në tabelën hash. Pasi ne jemi duke bërë me këtë, ne e dimë se kemi gjetur një tjetër fjalë në fjalor dhe ne rritje përsëri. Pra, ne vazhdojmë të bëjmë që deri fscanf më në fund kthehet diçka jo 1 në cilën pikë mos harroni se ne kemi nevojë për të hyrje të lirë, kështu që deri këtu, ne malloced një Hyrja dhe jemi munduar për të lexuar diçka nga fjalori. Dhe ne nuk e ka lexuar me sukses diçka nga fjalori në të cilën rast ne kemi nevojë për të liruar hyrjen që ne kurrë nuk e vënë në të vërtetë në tabelën hash dhe më në fund pushim. 

Pasi ne shpërthen, ne duhet të shohim, mirë, nuk e kemi shpërthen për shkak se ka u lexuar një gabim nga skedari, ose nuk e kemi shpërthen, sepse kemi arritur fundi i dosjes? Nëse ka pasur një gabim, atëherë ne duam të kthimit të rreme për shkak të ngarkesës nuk e bëri të ketë sukses, dhe në proces, ne duam të shkarkoj të gjitha fjalët që kemi lexuar në dhe afër fjalor file. Duke supozuar që pati sukses, atëherë ne vetëm ende nevojë për të mbyllur fjalorin paraqesë, dhe më në fund kthehet e vërtetë që nga ne kemi ngarkuar me sukses fjalor. Dhe kjo është ajo për të ngarkesës. 

Deri tani të kontrolluar, duke pasur parasysh një tavolinë ngarkuar hash, do të duket si ky. Pra shikoni, ajo kthen një bool, e cila do të tregojë nëse kaluar-në char * fjalë, nëse kaluar-në string është në fjalorin tonë. Pra, në qoftë se ajo është në fjalor, nëse është në tabelën hash tonë, ne do të kthehen e vërtetë, dhe nëse ajo nuk është, ne do të kthimit të rreme. Duke pasur parasysh këtë fjalë kaloi-në, ne jemi do të hash fjalën. 

Tani, një gjë e rëndësishme për të njohur është se në ngarkesës, ne e dinim se të gjithë fjalët u do të jetë rasti më i ulët, por këtu, ne nuk jemi aq të sigurt. Nëse do të bëjmë një vështrim në funksion tonë të hash, funksion ynë hash në të vërtetë është lowercasing çdo karakter të fjalës. Pra, pavarësisht nga kapitalizimin e fjalë, funksioni ynë hash do të kthejë të njëjtën indeksin për çfarëdo kapitalizimi është ashtu siç do të kishte kthyer për një krejtësisht të vogla Versioni i fjalës. Dakord. 

Pra, kjo është indeksi tonë. Kjo është tabela hash për këtë fjalë. Tani, kjo për lak është duke shkuar në mbi listën e lidhur që ishte në atë indeks. Pra, vini re, ne jemi të fillimit të hyrjes për pikë në këtë indeks. Ne jemi do të vazhdojë, ndërsa hyrja e bën nuk NULL të barabartë, dhe mos harroni se përditësimin treguesin në listën tonë lidhur Hyrja është e barabartë me hyrje-> ardhshme, kështu që kanë pika jonë e tanishme e hyrjes në Pika tjetër në listën e lidhur. Dakord. 

Kështu që për çdo hyrje në listën e lidhur, ne jemi duke shkuar për të përdorur strcasecmp. Kjo nuk është strcmp sepse edhe një herë, ne dua të bëj gjëra rast insensitively. Pra, ne i përdorim strcasecmp për të krahasuar fjalën që u miratua në këtë funksion kundër fjalës që është në këtë term. Nëse ai kthehet në 0, kjo do të thotë ka pasur një ndeshje, në të cilin rast ne duam të kthim i vërtetë. Ne me sukses gjetur Fjala në tryezën tonë hash. 

Nëse ka nuk ishte një ndeshje, atëherë ne jemi do të lak përsëri dhe të kërkoni në hyrje tjetër. Dhe ne do të vazhdojmë looping ndërsa ka janë të hyra në këtë listën e lidhur. Çfarë ndodh nëse ne pushim nga kjo për lak? Kjo do të thotë ne nuk kemi gjetur një hyrje që përputhet këtë fjalë, në të cilin rast ne kthimit të rreme për të treguar se tonë tabelë hash nuk e përmbajnë këtë fjalë. Dhe kjo është ajo për kontroll. Dakord. 

Pra, le të marrin një vështrim në madhësi. Tani, madhësia do të jetë shumë e thjeshtë që të mbani mend në ngarkesë, për çdo fjalë kemi gjetur ne incremented një globale hashtable_size ndryshueshme. Pra, funksioni madhësia është vetëm do të kthehen që globale variabël, dhe kjo është ajo. 

Tani së fundi, ne kemi nevojë për të shkarkoj fjalor herë është bërë çdo gjë. Pra, si do të shkojmë për të bërë këtë? Këtu, ne jemi looping mbi të gjitha kova e tryezën tonë hash. Pra, ka NUM_BUCKETS kova. Dhe për çdo listën e lidhur të hash tonë tavolinë, ne do të lak mbi tërësia e listës lidhur liruar çdo element. Tani, ne duhet të jemi të kujdesshëm, kështu që këtu ne kanë një ndryshore të përkohshme që është ruajtjen kursorin për të ardhshëm element në lista lidhur. Dhe atëherë ne jemi duke shkuar për të lirë element tanishme. 

Ne duhet të jetë i sigurt që ne e bëjmë këtë që nga viti ne nuk mund vetëm të lirë elementin e tanishëm të dhe pastaj të përpiqet për të hyrë në treguesin e ardhshme që nga një herë ne liruar atë kujtesës bëhet e pavlefshme. Pra, ne kemi nevojë për të mbajtur rreth një tregues për element tjetër, atëherë ne mund të lirë element aktuale, dhe pastaj ne mund të rinovuar element tonë aktuale për pikë për të element tjetër. 

Ne do të loop ndërsa ka elemente në këtë listë e lidhur. Ne do të bëjmë që për të gjitha listat e lidhura në tabela hash, dhe një herë ne jemi duke bërë me se, ne kemi shkarkuar plotësisht tabela hash, dhe ne jemi duke bërë. Kështu që është e pamundur për shkarkon të gjithnjë kthimit të rreme, dhe kur ne jemi bërë, ne vetëm kthim i vërtetë.