ROB BOWDEN: Dia duit. Tá mé Rob, agus a ligean ar hash an réiteach seo amach. Mar sin anseo táimid ag dul a chur i bhfeidhm tábla hash ginearálta. Feicimid go bhfuil an nód struct ar ár hash Tá tábla ag dul chun breathnú cosúil le seo. Mar sin, tá sé ag dul a bheith acu focal ruabhreac sraith de fhad méid móide 1. Ná déan dearmad ar 1 ó an t-uasmhéid Is é an focal san fhoclóir 45 carachtair, agus ansin táimid ag dul chun Ní mór carachtar breise amháin don cúlslais 0. 

Agus ansin ár tábla hash i ngach Tá buicéad ag dul a stóráil ar liosta nasctha de nóid. Ní Táimid ag déanamh líneach deacra anseo. Agus mar sin d'fhonn a nascadh leis an chéad cheann eile eilimint sa buicéad, ní mór dúinn a nód struct * chugainn. Mar sin, go bhfuil an méid Breathnaíonn nód cosúil. Anois, tá anseo an dearbhú ar ár tábla hash. Tá sé ag dul a bheith 16,384 buicéid, ach nach líon ábhar i ndáiríre. Agus ar deireadh, táimid ag dul a bheith acu ar an hashtable_size athróg domhanda, a Tá dul chun tús a chur amach mar 0, agus tá sé dul súil a choinneáil cé mhéad focail bhí ár foclóir. Gach ceart. 

Mar sin, a ligean ar ghlacadh le breathnú ar ualach. Mar sin, faoi deara go ualach, tuairisceáin sé bool. Tá tú ar ais fíor má bhí sé rathúil luchtaithe agus bréagach ar shlí eile. Agus a thógann sé ruabhric CONST * réalta foclóir, a bhfuil an foclóir gur mhaith linn a oscailt. Mar sin, go bhfuil an chéad rud táimid ag dul a dhéanamh. Táimid ag dul a fopen an foclóir do léamh, agus táimid ag dul a bheith acu a dhéanamh cinnte go bhfuil d'éirigh sé sin má d'fhill sé NULLComment, ansin ní raibh muid rathúil an foclóir a oscailt agus ní mór dúinn a thabhairt ar ais bréagach. 

Ach ag glacadh leis go raibh sé go rathúil oscailte, ansin ba mhaith linn a léamh ar an foclóir. Mar sin a choinneáil go dtí go bhfaighidh muid roinnt looping chúis a bhriseadh amach as an lúb a beidh orainn a fheiceáil. Mar sin a choinneáil looping, agus anois táimid ag dul a malloc nód amháin. Agus ar ndóigh, ní mór dúinn a sheiceáil earráid arís mar sin más rud é nach raibh mallocing éireoidh agus ba mhaith linn a dhíluchtú ar bith nód go bhfuil muid a tharla do malloc roimh, dún an foclóir agus seol ar ais bréagach. 

Ach neamhaird a bhfuil, ag glacadh leis againn d'éirigh leis, ansin ba mhaith linn a úsáid fscanf focal amháin a léamh as ár dictionary isteach inár nód. Mar sin, cuimhnigh go bhfuil focal iontráil-> Is é an ruabhreac Maolán focal ar fhad méid móide ceann a táimid ag dul chun stóráil an focal isteach Mar sin, tá fscanf ag dul a thabhairt ar ais 1 chomh fada mar a bhí sé in ann a léamh go rathúil le focal as an gcomhad. 

Má tharlaíonn ceachtar earráid nó a bhaint amach againn an deireadh an chomhaid, ní bheidh sé ar ais 1 sa chás sin más rud é nach ndéanann sé ar ais 1, táimid ag dul ar deireadh a bhriseadh amach as an lúb fad. Mar sin, a fheicimid go bhfuil nuair a bhíonn againn go rathúil Léigh focal isteach iontráil-> focal, ansin tá muid ag dul a hash an focal sin ag baint úsáide as ár n-fheidhm hash. A ligean ar ghlacadh le breathnú ar an fheidhm hash. 

Mar sin, ní gá duit i ndáiríre a thuiscint seo. Agus i ndáiríre, tharraing muid díreach tar éis seo hash fheidhm seo ón idirlíon. Is é an rud ach ní mór duit a aithint go nglacann an ruabhric CONST * focal, mar sin tá sé ag cur ar shraith mar ionchur agus filleadh ar an slánuimhir gan síniú mar aschur. Mar sin, sin uile feidhm hash é, tá sé Bíonn i ionchur, tugann sé tú innéacs isteach sa tábla hash. Fógra go bhfuil muid ag modding ag NUM_BUCKETS mar sin an luach hash ar ais i ndáiríre innéacs isteach sa tábla hash agus ní dhéanann innéacs thar an theorainn an eagar. 

Mar sin, ós rud é go feidhm hash, táimid ag dul a hash an focal a léamh againn as an bhfoclóir, agus ansin táimid ag dul úsáid a bhaint as go bhfuil a chur isteach ar an iontráil isteach sa tábla hash. Anois, tá hash hashtable reatha liosta nasctha sa tábla hash, agus tá sé an-is féidir go díreach NULLComment. Ba mhaith linn a chur isteach ar ár iontrála ag na tús an liosta seo nasctha, agus mar sin táimid ag dul go bhfuil ár n-iontráil reatha pointe cad é an tábla hash láthair pointí a agus ansin táimid ag dul a stóráil sa tábla hash ag an hash an iontráil reatha. 

Mar sin, an dá líne isteach go rathúil an iontráil ag tús na liosta nasctha ag an innéacs sa tábla hash. Nuair a bhíonn muid ag déanamh leis sin, tá a fhios againn go raibh muid focal eile sa foclóir agus táimid incrimint arís. Mar sin, a choinneáil orainn é sin a dhéanamh go dtí go fscanf tuairisceáin ar deireadh rud éigin nach 1 ag a pointe cuimhnigh gur gá dúinn a isteach saor in aisce, mar sin suas anseo, malloced againn iontráil agus rinneamar iarracht rud éigin a léamh as an bhfoclóir. Agus ní raibh muid ag léamh go rathúil rud éigin as an foclóir a cás is gá dúinn saor in aisce leis an iontráil go ndéanaimid riamh a chur i ndáiríre isteach sa tábla hash agus ar deireadh a bhriseadh. 

Nuair a briseadh muid amach, is gá dúinn a fheiceáil, go maith, raibh muid briseadh amach toisc go ndearnadh earráid ag léamh as an gcomhad, nó raibh muid briseadh amach mar gheall ar shroich muid an deireadh an chomhaid? Má bhí earráid, ansin ba mhaith linn a tuairisceán bréige toisc nach raibh ualach iarracht, agus sa phróiseas, ba mhaith linn a Díluchtaigh na focail go léir a léamh againn i agus an comhad a dhúnadh foclóir. Ag glacadh leis raibh muid éireoidh, ansin dúinn ach gá fós a dhúnadh ar an bhfoclóir comhad, agus ar deireadh ar ais fíor ó tá muid luchtaithe go rathúil ar an foclóir. Agus sin é do ualach. 

Mar sin a sheiceáil anois, tugtar tábla hash luchtaithe, Tá dul chun breathnú cosúil le seo. Mar sin a sheiceáil, tuairisceáin sé bool, a ag dul a chur in iúl cé acu an ritheadh-i ruabhric * focal, cibé acu an Is ritheadh-i dteaghrán i ár foclóir. Mar sin, má tá sé sa bhfoclóir, má tá sé in ár tábla hash, beidh muid ar ais fíor, agus más rud é nach bhfuil sé, Beidh muid ar ais bréagach. Mar gheall ar an focal ritheadh-i, tá muid ag dul go dtí an focal hash. 

Anois, tá an rud is tábhachtaí a aithint gur i ualach, bhí a fhios againn go léir Bhí na focail ag dul a bheith cás níos ísle, ach anseo, nach bhfuil muid chomh cinnte. Má chur orainn le breathnú ar ár n-fheidhm hash, ár n-fheidhm hash iarbhír Tá gach carachtar lowercasing an focal. Mar sin, beag beann ar an caipitlithe de focal, is é ár fheidhm hash ag dul go dtí ar ais an t-innéacs céanna cibé an Is caipitlithe mar a bheadh ​​sé a bheith thoghfar do litreacha beaga go hiomlán leagan den fhocal. Gach ceart. 

Mar sin, go bhfuil ár innéacs. Tá sé an tábla hash don fhocal seo. Anois, tá sé seo le haghaidh lúb leanúnach go dtí os cionn an liosta nasctha go raibh ag an innéacs. Mar sin, faoi deara againn ag initializing iontráil a chur in iúl leis an innéacs. Táimid ag dul chun leanúint ar aghaidh agus a dhéanann iontráil Ní NULLComment comhionann, agus cuimhnigh go cothrom le dáta an pointeoir i ár liosta nasctha is ionann iontráil isteach-> seo chugainn, ionas go mbeidh ár pointe iontrála reatha go dtí an chéad mhír eile ar an liosta nasctha. Gach ceart. 

Mar sin, le haghaidh gach iontrála ar an liosta nasctha, táimid ag dul strcasecmp a úsáid. Níl sé strcmp mar aon uair arís, táimid ag ag iarraidh a dhéanamh rudaí cás neamh-mhothálach. Mar sin, úsáidimid strcasecmp an focal a chur i gcomparáid gur ritheadh ​​an fheidhm seo i gcoinne an focal go Is san iontráil seo. Má tuairisceáin sé 0, ciallaíonn sé go raibh ar chluiche, agus sa chás sin ba mhaith linn a ar ais fíor. Fuair ​​muid go rathúil leis an focal i ár tábla hash. 

Más rud é nach raibh aon rud oiriúnach, ansin tá muid ag dul go dtí lúb arís agus féach ar an iontráil seo chugainn. Agus beidh muid ag leanúint ar aghaidh looping cé go Tá iontrálacha sa liosta seo nasctha. Cad a tharlaíonn má bhriseann muid as seo lúb? Ciallaíonn sé sin nach raibh againn teacht ar iontráil a mheaitseáil focal seo, agus sa chás sin táimid ar ais bréagach a chur in iúl go bhfuil ár Ní raibh tábla hais bhfuil an focal seo. Agus sin é do sheiceáil. Gach ceart. 

Mar sin, a ligean ar ghlacadh le breathnú ar an méid. Anois, tá méid dul a bheith simplí go leor cuimhnigh ós rud é i ualach, do gach focal fuair muid incrimintithe muid domhanda hashtable_size athraitheach. Mar sin, is é an fheidhm méid ach ag dul a thabhairt ar ais go domhanda athróg, agus go bhfuil sé. 

Anois, ar deireadh, ní mór dúinn a dhíluchtú foclóir nuair a tá gach rud a dhéanamh. Mar sin, conas a bhfuil muid ag dul a dhéanamh sin? Ceart anseo, tá muid looping thar gach buicéid ar ár tábla hash. Mar sin, tá NUM_BUCKETS buicéid. Agus do gach liosta nasctha in ár hash tábla, táimid ag dul chun lúb thar an go hiomlán ar an liosta nasctha freeing gach gné. Anois, ní mór dúinn a bheith cúramach, mar sin anseo táimid ag Tá athróg sealadach go stóráil an pointeoir chuig an chéad cheann eile eilimint sa liosta nasctha. Agus ansin táimid ag dul go dtí saor in aisce an eilimint atá ann faoi láthair. 

Ní mór dúinn a bheith cinnte a dhéanaimid é seo ós rud é againn Ní féidir ach saor in aisce leis an eilimint atá ann faoi láthair agus ansin déan iarracht rochtain a fháil ar an pointeoir eile ós rud é aon uair amháin freed muid é an thiocfaidh chun bheith neamhbhailí cuimhne. Mar sin, ní mór dúinn a choinneáil timpeall ar pointeoir go an chéad bhall eile, ansin is féidir linn a saor in aisce ar an eilimint atá ann faoi láthair, agus ansin is féidir linn a thabhairt cothrom le dáta ár n-eilimint ann faoi láthair a chur in iúl do an chéad bhall eile. 

Beidh muid lúb cé go bhfuil gnéithe sa liosta seo nasctha. Beidh muid é sin a dhéanamh do gach liosta nasctha i an tábla hais, agus nuair a táimid ag déanamh leis sin, tá muid á díluchtú go hiomlán an tábla hais, agus táimid ag déanamh. Mar sin, tá sé dodhéanta do unloads a riamh tuairisceán bréige, agus nuair a táimid ag déanamh, táimid ag ach ar ais fíor.