>> 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.