ROB BOWDEN: Hi. Rwy'n Rob, a hash gadewch i ateb hyn. Felly dyma ni yn mynd i weithredu tabl hash cyffredinol. Rydym yn gweld bod y nod strwythur ein hash tabl yn mynd i edrych fel hyn. Felly, mae'n mynd i gael gair torgoch amrywiaeth o hyd maint ac 1. Peidiwch ag anghofio y 1 ers yr uchafswm gair yn y geiriadur yn 45 cymeriadau, ac yna rydym yn mynd i angen un cymeriad ychwanegol ar gyfer y slaes 0. 

Ac yna mae ein tabl hash ym mhob bwced yn mynd i storio rhestr gysylltiedig o nodau. Nid ydym yn gwneud llinol stilio yma. Ac felly er mwyn cysylltu i'r nesaf elfen yn y bwced, mae angen nod strwythur * nesaf. Felly, dyna beth yw nod yn edrych. Yn awr, dyma y datganiad ein tabl hash. Mae'n mynd i gael 16,384 bwcedi, ond Nid y rhif hwnnw yn wirioneddol bwysig. Ac yn olaf, rydym yn mynd i gael y hashtable_size amrywiol byd-eang, sy'n yn mynd i ddechrau fel 0, ac mae'n yn mynd i gadw golwg ar faint o eiriau Roedd yn ein geiriadur. Mae pob hawl. 

Felly, gadewch i ni edrych ar lwyth. Felly, yn sylwi bod llwyth, mae'n dychwelyd i bool. Byddwch yn dychwelyd yn wir os oedd yn llwyddiannus lwytho a ffug fel arall. Ac mae'n cymryd seren * torgoch Etholaeth geiriadur, sef y geiriadur yr ydym am ei agor. Felly, dyna'r peth cyntaf rydym yn mynd i'w wneud. Rydym yn mynd i fopen geiriadur ar gyfer darllen, ac rydym yn mynd i gael i wneud yn siŵr ei fod yn llwyddo felly os dychwelodd NULL, yna ni wnaethom agor y geiriadur yn llwyddiannus ac mae angen inni ddychwelyd ffug. 

Ond gan dybio bod y gwnaeth yn llwyddiannus agored, yna rydym yn awyddus i ddarllen y geiriadur. Felly cadwch dolennu nes i ni ddod o hyd i rheswm i dorri allan o hyn ddolen y byddwn yn ei weld. Felly cadwch dolennu, ac yn awr rydym yn mynd i malloc un nod sengl. Ac wrth gwrs, mae angen i ni gwall siec eto felly os nad mallocing lwyddodd ac rydym am i ddadlwytho unrhyw nod yr ydym yn ddigwyddodd i malloc o'r blaen, cau'r geiriadur a dychwelyd ffug. 

Ond ac anwybyddu hynny, gan dybio ein bod llwyddo, yna rydym eisiau defnyddio fscanf i ddarllen un gair gan ein eiriadur yn ein nod. Felly cofiwch y gair hwnnw mynediad-> yw'r torgoch byffer gair hyd maint yn ogystal â un yr ydym yn mynd i storio'r gair i mewn Felly fscanf yn mynd i ddychwelyd 1 ar yr amod gan ei bod yn gallu darllen yn llwyddiannus Gair gan y ffeil. 

Os yw naill ai camgymeriad yn digwydd neu os byddwn yn cyrraedd diwedd y ffeil, ni fydd yn dychwelyd 1 ac yn yr achos os nad yw'n dychwelyd 1, rydym yn y pen draw yn mynd i dorri allan o hyn dolen amser. Felly, rydym yn gweld bod unwaith y byddwn wedi llwyddo i darllen gair yn mynediad-> gair, yna rydym yn mynd i hash y geiriau gan ddefnyddio ein swyddogaeth hash. Gadewch i ni edrych ar y swyddogaeth hash. 

Felly peidiwch 'n sylweddol angen i chi i ddeall hyn. Ac mewn gwirionedd, rydym yn unig tynnu hwn hash swyddogaeth o'r rhyngrwyd. Yr unig beth sydd angen i chi ei gydnabod yn bod hyn yn cymryd torgoch * gair Etholaeth, felly mae'n cymryd llinyn fel mewnbwn a dychwelyd yn int heb eu harwyddo fel allbwn. Felly dyna i gyd swyddogaeth hash yw, a yw'n cymryd mewn mewnbwn, mae'n rhoi i chi yn mynegai yn y tabl hash. Sylwch ein bod yn modding gan NUM_BUCKETS felly mae'r gwerth hash a ddychwelwyd mewn gwirionedd yn fynegai yn y tabl hash ac nid yw'n mynegai y tu hwnt i'r ffiniau y rhesi. 

Felly, o ystyried bod swyddogaeth hash, rydym yn mynd i hash y gair yr ydym yn darllen gan y geiriadur, ac yna rydym yn mynd i ddefnyddio'r rhaid i mewnosoder y mynediad yn y tabl hash. Yn awr, hash hashtable yw'r cerrynt rhestr gysylltiedig yn y tabl hash, a mae'n bosibl iawn bod yn unig NULL. Rydym am i fewnosod ein cofnod yn y dechrau y rhestr gysylltiedig, ac yn y blaen rydym yn mynd i gael ein cofnod cyfredol dynnu sylw at yr hyn y mae'r tabl hash ar hyn o bryd pwyntiau ac yna rydym yn mynd i storio yn y tabl hash yn y hash y cofnod ar hyn o bryd. 

Felly mae'r rhain ddwy linell mewnosod yn llwyddiannus y cofnod ar ddechrau'r rhestr gysylltiedig ar y mynegai yn y tabl hash. Unwaith y byddwn yn ei wneud â hynny, rydym yn gwybod ein bod yn dod o hyd i air arall yn y geiriadur ac rydym yn cynyddiad eto. Felly rydym yn cadw gwneud hynny hyd nes y fscanf yn olaf dychwelyd rhywbeth nad ydynt yn 1 yn mae pwynt cofiwch fod angen i ni mynediad am ddim, felly i fyny yma, rydym yn malloced yn mynediad ac rydym yn ceisio darllen rhywbeth gan y geiriadur. Ac nid ydym yn darllen yn llwyddiannus rhywbeth o'r geiriadur lle achos mae angen i ni ryddhau'r cofnod yr ydym yn peidiwch byth â rhoi mewn gwirionedd yn y tabl hash ac yn olaf torri. 

Unwaith y byddwn yn torri allan, mae angen i ni weld, yn dda, wnaethom ni dorri allan oherwydd nad Roedd gwall wrth darllen o ffeil, neu oedd ydym yn ei dorri allan oherwydd i ni gyrraedd diwedd y ffeil? Os oedd camgymeriad, yna rydym am dychwelyd ffug oherwydd nad oedd llwyth lwyddo, ac yn y broses, rydym am ddadlwytho holl eiriau yr ydym yn darllen yn a chau'r ffeil geiriadur. Gan dybio y byddwn yn llwyddo, yna rydym yn unig dal i fod angen i gau'r geiriadur ffeilio, ac yn olaf yn dychwelyd yn wir ers rydym wedi llwytho yn llwyddiannus geiriadur. A dyna ni ar gyfer llwyth. 

Felly nawr wirio, o ystyried tabl hash llwytho, yn mynd i edrych fel hyn. Felly siec, mae'n dychwelyd i bool, a oedd yn yn mynd i nodi a yw'r pasio i mewn torgoch * gair, a yw'r llinyn pasio i mewn yn ein geiriadur. Felly, os yw yn y geiriadur, os yw'n yn ein tabl hash, byddwn yn dychwelyd yn wir, ac os nad yw'n, byddwn yn dychwelyd ffug. O ystyried y gair pasio i mewn, rydym yn mynd i hash y gair. 

Yn awr, mae peth pwysig i'w gydnabod yw bod yn llwyth, yr oeddem yn gwybod bod yr holl y geiriau yn mynd i fod yn llythrennau bach, ond yma, nid ydym yn mor siŵr. Os byddwn yn edrych ar ein swyddogaeth hash, ein swyddogaeth hash mewn gwirionedd yn lowercasing pob cymeriad y gair. Felly, beth bynnag y cyfalafu gair, mae ein swyddogaeth hash yn mynd i dychwelyd yr un mynegai ar gyfer beth bynnag fo'r cyfalafu fel y byddai'n cael dychwelyd ar gyfer hollol llythrennau bach fersiwn o'r gair. Mae pob hawl. 

Felly dyna ein mynegai. Mae'n y tabl hash gyfer y gair hwn. Yn awr, mae hyn ar gyfer dolen yn mynd i dros y rhestr gysylltiedig a oedd ar y mynegai. Felly, yn sylwi ein bod yn ymgychwyn mynediad i dynnu sylw at y mynegai. Rydym yn mynd i barhau tra mynediad yn Nid yw NULL cyfartal, a chofiwch fod diweddaru'r pwyntydd yn ein rhestr gysylltiedig mynediad hafal mynediad-> nesaf, felly mae'n rhaid ein man mynediad presennol i'r eitem nesaf yn y rhestr cysylltiedig. Mae pob hawl. 

Felly, ar gyfer pob cofnod yn y rhestr gysylltiedig, rydym yn mynd i ddefnyddio strcasecmp. Dyw hi ddim yn strcmp oherwydd unwaith eto, rydym yn eisiau gwneud pethau achos ansensitif. Felly, rydym yn defnyddio strcasecmp i gymharu'r gair a oedd yn trosglwyddo i'r swyddogaeth hon yn erbyn y gair sy'n yn y cofnod hwn. Os bydd yn dychwelyd 0, mae hynny'n golygu nad oedd gêm, ac yn yr achos yr ydym am ei dychwelyd yn wir. Rydym yn dod o hyd yn llwyddiannus y gair yn ein tabl hash. 

Os nad oedd yn cyfateb, yna rydym yn mynd i'r ddolen eto ac edrych ar y cofnod nesaf. A byddwn yn parhau dolennu er bod yn cofnodion yn y rhestr cysylltiedig. Beth fydd yn digwydd os byddwn yn torri allan o hyn ar gyfer dolen? Mae hynny'n golygu nad ydym yn dod o hyd i gofnod y cyfateb gair hwn, ac yn yr achos byddwn yn dychwelyd ffug i ddangos bod ein Nid yw tabl hash oedd yn cynnwys y gair hwn. A dyna ni am siec. Mae pob hawl. 

Felly, gadewch i ni edrych ar faint. Nawr, maint yn mynd i fod yn eithaf syml ers cofio yn llwyth, i bob gair rydym yn dod o hyd i ni gynyddrannedig yn fyd-eang hashtable_size amrywiol. Felly, y swyddogaeth maint yn unig mynd i ddychwelyd y byd-eang amrywiol, a dyna ni. 

Nawr yn olaf, mae angen i ddadlwytho'r geiriadur unwaith popeth ei wneud. Felly, sut ydym yn mynd i wneud hynny? I'r dde yma, rydym yn dolennu dros yr holl bwcedi ein tabl hash. Felly mae bwcedi NUM_BUCKETS. Ac ar gyfer pob rhestr gysylltiedig yn ein hash bwrdd, rydyn ni'n mynd i ddolen dros y gyfanrwydd y rhestr cysylltiedig rhyddhau pob elfen. Yn awr, mae angen i ni fod yn ofalus, felly dyma ni cael newidyn dros dro sy'n storio y pwyntydd i'r nesaf elfen yn y rhestr cysylltiedig. Ac yna rydym yn mynd i rhad ac am ddim yr elfen gyfredol. 

Mae angen i ni fod yn sicr rydym yn gwneud hyn ers i ni Ni all dim ond rhad ac am ddim yr elfen gyfredol ac yna ceisiwch i gael mynediad i'r pwyntydd nesaf ers ar ôl i ni ei rhyddhau y cof yn dod yn annilys. Felly mae angen i gadw o gwmpas pwyntydd i i'r elfen nesaf, yna gallwn ryddhau'r elfen ar hyn o bryd, ac yna gallwn ddiweddaru ein bodd yn bresennol i dynnu sylw at i'r elfen nesaf. 

Rydym yn bydd dolen er bod elfennau yn y rhestr gysylltiedig. Byddwn yn gwneud hynny ar gyfer pob rhestr cysylltiedig yn y tabl hash, ac unwaith y byddwn yn ei wneud â hynny, rydym wedi dadlwytho yn gyfan gwbl y tabl hash, ac yr ydym yn ei wneud. Felly, mae'n amhosibl i dadlwytho i byth dychwelyd ffug, a phan fyddwn yn ei wneud, rydym yn dim ond dychwelyd yn wir.