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