ROB BOWDEN: Hi. Mwen se Rob, ak hash Annou sa a solisyon deyò. Se konsa, isit la nou ap ale nan aplike yon hash tab jeneral. Nou wè ke ne la konstri nan hash nou tab ki pral gade tankou sa a. Se konsa, li la pral fè yon mo Char etalaj de gwosè longè plis 1. pa bliye 1 an depi maksimòm la mo an nan diksyonè a se 45 karaktè, ak Lè sa a, nou pral bezwen yon karaktè anplis pou la antislach 0. 

Lè sa a, tab hash nou yo nan chak bokit ki pral estoke yon lis lye nan nœuds. Nou pa ap fè lineyè sonde isit la. Se konsa, yo nan lòd yo genyen lyen pwochen an eleman nan bokit la, nou bezwen yon konstri ne * kap vini an. Se konsa, se sa ki yon ne sanble. Koulye a, isit la se deklarasyon an nan tablo hash nou an. Li pral gen 16.384 bokit, men ladan nimewo pa reyèlman gen pwoblèm. E finalman, nou pral gen a mondyal hashtable_size varyab, ki ki pral kòmanse desann kòm 0, epi li ale nan kenbe tras nan konbyen mo yo te nan diksyonè nou an. Tout dwa. 

Se konsa, kite a pran yon gade nan chaj. Se konsa, remake ke chaj, li retounen yon bouleen. Ou retounen vre si li te avèk siksè chaje ak fo otreman. Apre sa, li pran yon Char zetwal * CONST diksyonè, ki se diksyonè a ke nou vle louvri. Se konsa, sa a, se premye bagay la nou pral fè. Nou pral fopen diksyonè a pou lekti, epi nou pral gen asire w ke li nan plas Se konsa, si li tounen NULL, lè sa a nou pa t ' avèk siksè louvri diksyonè a e nou bezwen retounen fo. 

Men, an konsideran ke li te fè avèk siksè louvri, lè sa a nou vle li a diksyonè. Se konsa, kenbe loupin jiskaske nou jwenn kèk rezon ki fè yo kraze soti nan sa a bouk ki nou pral wè. Se konsa, kenbe loupin, epi kounye a nou pwal malok yon ne sèl. Ak nan kou, nou bezwen erè chèk ankò Se konsa, si mallocing pa t 'reyisi e nou vle dechaje nenpòt ki ne ke nou rive malok anvan, fèmen a diksyonè epi retounen bay manti. 

Men, inyore ke, an konsideran nou nan plas, lè sa a nou vle sèvi ak fskanf li yon mo yon sèl soti nan nou an diksyonè nan ne nou an. Se konsa, sonje mo sa a antre-> se Char la tanpon mo ki gen yon gwosè longè plis yon sèl ke nou ap ale nan magazen pawòl Bondye a pous Se konsa, fskanf ki pral retounen 1 osi lontan kòm li te kapab avèk siksè li yon mo nan dosye a. 

Si youn nan yon erè k ap pase oswa nou rive nan fen a nan dosye a, li pa pral retounen 1 nan ka sa a si li fè sa pa retounen 1, n ap finalman pral kraze soti nan sa a bouk ti tan. Se konsa, nou wè ke yon fwa nou gen avèk siksè li yon mo nan antre-> mo, Lè sa a, nou pral Hash mo ki lè l sèvi avèk fonksyon hash nou an. Se pou nou pran yon gade nan fonksyon an hash. 

Se konsa, ou pa reyèlman bezwen yo konprann sa a. Apre sa, aktyèlman, nou jis rale sa a Hash fonksyon soti nan entènèt la. Sèl bagay ou bezwen rekonèt se ke sa a pran yon mo CONST * Char, Se konsa, li la pran yon fisèl kòm opinyon ak retounen yon Int siye kòm pwodiksyon. Se konsa, ki nan tout yon fonksyon hash se, se li pran nan yon D ', li ba ou yon endèks nan tablo a hash. Remake nou ap modin pa NUM_BUCKETS Se konsa, valè a hash tounen aktyèlman se yon endèks nan tablo a hash ak fè sa ki pa endèks pi lwen pase a limit nan etalaj la. 

Se konsa, bay yo ke fonksyon hash, nou pwal Hash pawòl Bondye a ke nou li soti nan diksyonè a ak Lè sa a, nou pral yo sèvi ak ki gen insert la antre nan tab la hash. Koulye a, hashtable hash se aktyèl la lis lye nan tablo a hash, ak li trè posib ke se jis NULL. Nou vle insert antre nou an nan la kòmanse nan lis sa a lye, e konsa nou pral gen antre aktyèl nou an lonje dwèt sou sa ki tab la hash kounye a pwen pou ale ak pou Lè sa a, nou pral nan magazen nan tablo a hash nan hash la antre nan aktyèl la. 

Se konsa, de liy sa yo avèk siksè insert antre nan nan kòmansman an nan la lis lye nan ki endèks nan tablo a hash. Yon fwa nou ap fè ak sa, nou konnen ke nou jwenn yon lòt mo nan la diksyonè ak nou enkreman ankò. Se konsa, nou kontinye ap fè sa jouk lè fskanf finalman retounen yon bagay ki 1 nan ki pwen sonje ke nou bezwen rantre lib, se konsa moute isit la, nou malloced yon antre ak nou te eseye li yon bagay soti nan diksyonè a. Apre sa, nou pa t 'avèk siksè li yon bagay soti nan diksyonè a nan sa ki ka nou bezwen libere antre nan ke nou aktyèlman pa janm mete nan tablo a hash epi finalman kase. 

Yon fwa nou kraze soti, nou bezwen wè, byen, t 'nou kraze soti paske se la te yon erè li nan dosye a, oswa t 'nou kraze soti paske nou te rive nan fen a nan dosye a? Si te gen yon erè, lè sa a nou vle retounen fo paske chaj pa t ' reyisi, ak nan pwosesis la, nou vle dechaje tout pawòl sa yo ke nou li nan epi fèmen dosye a diksyonè. Si nou sipoze nou te reyisi, Lè sa a, nou jis toujou bezwen yo fèmen diksyonè a pote, epi finalman retounen vre depi nou te avèk siksè chaje a diksyonè. Epi sa a, li pou chaj. 

Se konsa, koulye tcheke, yo bay yon tab hash chaje, ki pral gade tankou sa a. Se konsa, tcheke, li retounen yon bouleen, ki ki pral endike si la pase-an Char mo *, si wi ou non nan pase-nan fil se nan diksyonè nou an. Se konsa, si li se an nan diksyonè a, si li se nan tablo hash nou yo, nou pral retounen vre, epi si li pa, nou pral retounen bay manti. Bay mo sa a te pase-a, nou ale nan Hash mo a. 

Koulye a, yon bagay enpòtan yo rekonèt se ke nan chaj, nou te konnen ke tout moun nan mo sa yo te ale nan pi ba a, men isit la, nou pa konsa pou sa asire w. Si nou pran yon gade nan fonksyon hash nou an, fonksyon hash nou an aktyèlman se lowercasing chak karaktè nan pawòl Bondye a. Se konsa, kèlkeswa lèt majiskil la nan mo, fonksyon hash nou an, se ale nan retounen endèks la menm pou la kèlkeswa sa lèt majiskil se tankou li ta gen tounen pou yon konplètman miniskil vèsyon an pawòl Bondye a. Tout dwa. 

Se konsa, sa a, se endèks nou an. Li nan tablo a hash pou sa a mo. Koulye a, sa a pou bouk ki pral Plis pase lis la lye sa ki te nan moman sa Konpayi paran yo. Se konsa, remake nou ap inisyalizin antre nan pwen ak sa yo ki endèks. Nou pral kontinye pandan y ap antre fè pa egal NULL, epi sonje ke à konsèy la nan lis lye nou antre egal antre-> kap vini an, konsa gen nou pwen antre aktyèl yo bay la atik pwochen nan lis lye. Tout dwa. 

Se konsa, pou chak antre nan lis la lye, nou pral sèvi ak strcasecmp. Li pa nan strkan paske yon lòt fwa ankò, nou vle fè bagay sa yo ka insensitively. Se konsa, nou sèvi ak strcasecmp yo konpare pawòl Bondye a sa ki te pase bay fonksyon sa a kont pawòl Bondye a ki se nan sa a antre. Si li retounen 0, sa vle di te gen yon match, nan ka sa nou vle retounen vre. Nou jwenn avèk siksè nan mo nan tablo hash nou an. 

Si pa t 'gen yon match, lè sa a nou ap ale nan bouk ankò, li gade nan la pwochen antre. Epitou, n ap kontinye loupin pandan y ap gen yo antre nan lis sa a lye. Kisa k ap pase si nou kraze soti nan sa a pou bouk? Sa vle di nou pa t 'jwenn yon antre ki matche mo sa a, nan ki ka nou retounen fo ke yo endike ke nou tab hash pa t 'gen mo sa a. Epi sa a, li pou chèk la. Tout dwa. 

Se konsa, kite a pran yon gade nan gwosè. Koulye a, gwosè a pwal trè senp depi sonje nan chaj, pou chak mo nou te jwenn nou enkremante yon mondyal varyab hashtable_size. Se konsa, fonksyon an gwosè se jis ale nan retounen ke mondyal varyab, e ke sa a li. 

Koulye a, finalman, nou bezwen dechaje la diksyonè yon fwa tout bagay nan fè. Se konsa, kouman nou pral fè sa? Dwa isit la, nou ap loupin sou tout bokit nan tablo hash nou an. Se konsa, gen NUM_BUCKETS bokit. Epi pou chak lis lye nan hash nou tab, nou pral bouk sou la antye nan lis la lye libere chak eleman. Koulye a, nou bezwen dwe fè atansyon, se konsa isit la nou gen yon varyab pou yon ti tan sa a, se estoke konsèy la pwochen an eleman nan lis la lye. Lè sa a, nou pral gratis eleman aktyèl la. 

Nou bezwen asire w ke nou fè sa depi nou pa ka jis gratis eleman aktyèl la ak Lè sa a, eseye jwenn aksè nan konsèy nan pwochen depi yon fwa nou te libere li nan memwa vin valab. Se konsa, nou bezwen kenbe otou yon konsèy eleman kap vini an, Lè sa a, nou ka libere nan eleman kounye a, ak Lè sa a, nou ka mete eleman aktyèl nou yo lonje dwèt sou eleman nan pwochen an. 

Nou pral bouk pandan y ap gen eleman nan lis sa a lye. Nou pral fè sa pou tout lis lye nan tab la hash, ak yon fwa nou ap fè ak sa, nou te konplètman chaje tab la hash, epi nou ap fè. Se konsa, li enposib pou decharjeman tout tan tout tan retounen fo, ak lè nou ap fè, nou jis retounen vre.