1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Hi.

3
00:00:13,050 --> 00:00:16,210
Rwy'n Rob, a hash gadewch i
ateb hyn.

4
00:00:16,210 --> 00:00:20,070
Felly dyma ni yn mynd i weithredu
tabl hash cyffredinol.

5
00:00:20,070 --> 00:00:24,090
Rydym yn gweld bod y nod strwythur ein hash
tabl yn mynd i edrych fel hyn.

6
00:00:24,090 --> 00:00:28,710
Felly, mae'n mynd i gael gair torgoch
amrywiaeth o hyd maint ac 1.

7
00:00:28,710 --> 00:00:32,259
Peidiwch ag anghofio y 1 ers yr uchafswm
gair yn y geiriadur yn 45

8
00:00:32,259 --> 00:00:35,110
cymeriadau, ac yna rydym yn mynd i
angen un cymeriad ychwanegol ar gyfer y

9
00:00:35,110 --> 00:00:37,070
slaes 0.

10
00:00:37,070 --> 00:00:40,870
>> Ac yna mae ein tabl hash ym mhob
bwced yn mynd i storio

11
00:00:40,870 --> 00:00:42,320
rhestr gysylltiedig o nodau.

12
00:00:42,320 --> 00:00:44,420
Nid ydym yn gwneud llinol stilio yma.

13
00:00:44,420 --> 00:00:48,430
Ac felly er mwyn cysylltu i'r nesaf
elfen yn y bwced, mae angen

14
00:00:48,430 --> 00:00:51,110
nod strwythur * nesaf.

15
00:00:51,110 --> 00:00:53,090
Felly, dyna beth yw nod yn edrych.

16
00:00:53,090 --> 00:00:56,180
Yn awr, dyma y datganiad
ein tabl hash.

17
00:00:56,180 --> 00:01:01,910
Mae'n mynd i gael 16,384 bwcedi, ond
Nid y rhif hwnnw yn wirioneddol bwysig.

18
00:01:01,910 --> 00:01:05,450
Ac yn olaf, rydym yn mynd i gael y
hashtable_size amrywiol byd-eang, sy'n

19
00:01:05,450 --> 00:01:08,640
yn mynd i ddechrau fel 0, ac mae'n
yn mynd i gadw golwg ar faint o eiriau

20
00:01:08,640 --> 00:01:10,080
Roedd yn ein geiriadur.

21
00:01:10,080 --> 00:01:10,760
Mae pob hawl.

22
00:01:10,760 --> 00:01:13,190
>> Felly, gadewch i ni edrych ar lwyth.

23
00:01:13,190 --> 00:01:16,390
Felly, yn sylwi bod llwyth,
mae'n dychwelyd i bool.

24
00:01:16,390 --> 00:01:20,530
Byddwch yn dychwelyd yn wir os oedd yn llwyddiannus
lwytho a ffug fel arall.

25
00:01:20,530 --> 00:01:23,990
Ac mae'n cymryd seren * torgoch Etholaeth
geiriadur, sef y geiriadur

26
00:01:23,990 --> 00:01:25,280
yr ydym am ei agor.

27
00:01:25,280 --> 00:01:27,170
Felly, dyna'r peth cyntaf
rydym yn mynd i'w wneud.

28
00:01:27,170 --> 00:01:30,420
Rydym yn mynd i fopen geiriadur ar gyfer
darllen, ac rydym yn mynd i gael

29
00:01:30,420 --> 00:01:34,700
i wneud yn siŵr ei fod yn llwyddo felly os
dychwelodd NULL, yna ni wnaethom

30
00:01:34,700 --> 00:01:37,440
agor y geiriadur yn llwyddiannus
ac mae angen inni ddychwelyd ffug.

31
00:01:37,440 --> 00:01:41,580
>> Ond gan dybio bod y gwnaeth yn llwyddiannus
agored, yna rydym yn awyddus i ddarllen y

32
00:01:41,580 --> 00:01:42,400
geiriadur.

33
00:01:42,400 --> 00:01:46,210
Felly cadwch dolennu nes i ni ddod o hyd i
rheswm i dorri allan o hyn

34
00:01:46,210 --> 00:01:47,570
ddolen y byddwn yn ei weld.

35
00:01:47,570 --> 00:01:51,780
Felly cadwch dolennu, ac yn awr rydym yn mynd
i malloc un nod sengl.

36
00:01:51,780 --> 00:01:56,800
Ac wrth gwrs, mae angen i ni gwall siec
eto felly os nad mallocing lwyddodd

37
00:01:56,800 --> 00:02:00,660
ac rydym am i ddadlwytho unrhyw nod yr ydym yn
ddigwyddodd i malloc o'r blaen, cau'r

38
00:02:00,660 --> 00:02:02,590
geiriadur a dychwelyd ffug.

39
00:02:02,590 --> 00:02:07,440
>> Ond ac anwybyddu hynny, gan dybio ein bod
llwyddo, yna rydym eisiau defnyddio fscanf

40
00:02:07,440 --> 00:02:12,400
i ddarllen un gair gan ein
eiriadur yn ein nod.

41
00:02:12,400 --> 00:02:17,310
Felly cofiwch y gair hwnnw mynediad-> yw'r torgoch
byffer gair hyd maint yn ogystal â

42
00:02:17,310 --> 00:02:20,300
un yr ydym yn mynd i
storio'r gair i mewn

43
00:02:20,300 --> 00:02:25,280
Felly fscanf yn mynd i ddychwelyd 1 ar yr amod
gan ei bod yn gallu darllen yn llwyddiannus

44
00:02:25,280 --> 00:02:26,750
Gair gan y ffeil.

45
00:02:26,750 --> 00:02:31,030
>> Os yw naill ai camgymeriad yn digwydd neu os byddwn yn cyrraedd
diwedd y ffeil, ni fydd yn

46
00:02:31,030 --> 00:02:34,950
dychwelyd 1 ac yn yr achos os nad yw'n
dychwelyd 1, rydym yn y pen draw yn mynd i dorri

47
00:02:34,950 --> 00:02:37,280
allan o hyn dolen amser.

48
00:02:37,280 --> 00:02:42,770
Felly, rydym yn gweld bod unwaith y byddwn wedi llwyddo i
darllen gair yn

49
00:02:42,770 --> 00:02:48,270
mynediad-> gair, yna rydym yn mynd i hash
y geiriau gan ddefnyddio ein swyddogaeth hash.

50
00:02:48,270 --> 00:02:49,580
Gadewch i ni edrych ar
y swyddogaeth hash.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> Felly peidiwch 'n sylweddol angen i chi
i ddeall hyn.

53
00:02:55,610 --> 00:02:59,460
Ac mewn gwirionedd, rydym yn unig tynnu hwn
hash swyddogaeth o'r rhyngrwyd.

54
00:02:59,460 --> 00:03:04,010
Yr unig beth sydd angen i chi ei gydnabod yn
bod hyn yn cymryd torgoch * gair Etholaeth,

55
00:03:04,010 --> 00:03:08,960
felly mae'n cymryd llinyn fel mewnbwn a
dychwelyd yn int heb eu harwyddo fel allbwn.

56
00:03:08,960 --> 00:03:12,360
Felly dyna i gyd swyddogaeth hash yw, a yw'n
cymryd mewn mewnbwn, mae'n rhoi i chi yn

57
00:03:12,360 --> 00:03:14,490
mynegai yn y tabl hash.

58
00:03:14,490 --> 00:03:18,530
Sylwch ein bod yn modding gan NUM_BUCKETS
felly mae'r gwerth hash a ddychwelwyd

59
00:03:18,530 --> 00:03:21,730
mewn gwirionedd yn fynegai yn y tabl hash
ac nid yw'n mynegai y tu hwnt i'r

60
00:03:21,730 --> 00:03:24,320
ffiniau y rhesi.

61
00:03:24,320 --> 00:03:27,855
>> Felly, o ystyried bod swyddogaeth hash, rydym yn mynd
i hash y gair yr ydym yn darllen

62
00:03:27,855 --> 00:03:31,700
gan y geiriadur, ac yna rydym yn mynd
i ddefnyddio'r rhaid i mewnosoder y

63
00:03:31,700 --> 00:03:33,750
mynediad yn y tabl hash.

64
00:03:33,750 --> 00:03:38,830
Yn awr, hash hashtable yw'r cerrynt
rhestr gysylltiedig yn y tabl hash, a

65
00:03:38,830 --> 00:03:41,410
mae'n bosibl iawn bod yn unig NULL.

66
00:03:41,410 --> 00:03:45,640
Rydym am i fewnosod ein cofnod yn y
dechrau y rhestr gysylltiedig, ac yn y blaen

67
00:03:45,640 --> 00:03:48,910
rydym yn mynd i gael ein cofnod cyfredol
dynnu sylw at yr hyn y mae'r tabl hash ar hyn o bryd

68
00:03:48,910 --> 00:03:54,030
pwyntiau ac yna rydym yn mynd i storio
yn y tabl hash yn y hash

69
00:03:54,030 --> 00:03:55,350
y cofnod ar hyn o bryd.

70
00:03:55,350 --> 00:03:59,320
>> Felly mae'r rhain ddwy linell mewnosod yn llwyddiannus
y cofnod ar ddechrau'r

71
00:03:59,320 --> 00:04:02,270
rhestr gysylltiedig ar y mynegai
yn y tabl hash.

72
00:04:02,270 --> 00:04:04,900
Unwaith y byddwn yn ei wneud â hynny, rydym yn gwybod
ein bod yn dod o hyd i air arall yn y

73
00:04:04,900 --> 00:04:07,800
geiriadur ac rydym yn cynyddiad eto.

74
00:04:07,800 --> 00:04:13,960
Felly rydym yn cadw gwneud hynny hyd nes y fscanf
yn olaf dychwelyd rhywbeth nad ydynt yn 1 yn

75
00:04:13,960 --> 00:04:18,560
mae pwynt cofiwch fod angen i ni
mynediad am ddim, felly i fyny yma, rydym yn malloced yn

76
00:04:18,560 --> 00:04:21,329
mynediad ac rydym yn ceisio darllen rhywbeth
gan y geiriadur.

77
00:04:21,329 --> 00:04:24,110
Ac nid ydym yn darllen yn llwyddiannus
rhywbeth o'r geiriadur lle

78
00:04:24,110 --> 00:04:27,440
achos mae angen i ni ryddhau'r cofnod yr ydym yn
peidiwch byth â rhoi mewn gwirionedd yn y tabl hash

79
00:04:27,440 --> 00:04:29,110
ac yn olaf torri.

80
00:04:29,110 --> 00:04:32,750
>> Unwaith y byddwn yn torri allan, mae angen i ni weld, yn dda,
wnaethom ni dorri allan oherwydd nad

81
00:04:32,750 --> 00:04:35,840
Roedd gwall wrth darllen o ffeil, neu
oedd ydym yn ei dorri allan oherwydd i ni gyrraedd

82
00:04:35,840 --> 00:04:37,120
diwedd y ffeil?

83
00:04:37,120 --> 00:04:40,150
Os oedd camgymeriad, yna rydym am
dychwelyd ffug oherwydd nad oedd llwyth

84
00:04:40,150 --> 00:04:43,260
lwyddo, ac yn y broses, rydym am
ddadlwytho holl eiriau yr ydym yn darllen

85
00:04:43,260 --> 00:04:45,670
yn a chau'r ffeil geiriadur.

86
00:04:45,670 --> 00:04:48,740
Gan dybio y byddwn yn llwyddo, yna rydym yn unig
dal i fod angen i gau'r geiriadur

87
00:04:48,740 --> 00:04:51,970
ffeilio, ac yn olaf yn dychwelyd yn wir ers
rydym wedi llwytho yn llwyddiannus

88
00:04:51,970 --> 00:04:53,040
geiriadur.

89
00:04:53,040 --> 00:04:54,420
A dyna ni ar gyfer llwyth.

90
00:04:54,420 --> 00:04:59,020
>> Felly nawr wirio, o ystyried tabl hash llwytho,
yn mynd i edrych fel hyn.

91
00:04:59,020 --> 00:05:02,690
Felly siec, mae'n dychwelyd i bool, a oedd yn
yn mynd i nodi a yw'r

92
00:05:02,690 --> 00:05:07,530
pasio i mewn torgoch * gair, a yw'r
llinyn pasio i mewn yn ein geiriadur.

93
00:05:07,530 --> 00:05:10,530
Felly, os yw yn y geiriadur, os yw'n
yn ein tabl hash, byddwn yn dychwelyd

94
00:05:10,530 --> 00:05:13,380
yn wir, ac os nad yw'n,
byddwn yn dychwelyd ffug.

95
00:05:13,380 --> 00:05:17,770
O ystyried y gair pasio i mewn, rydym yn
mynd i hash y gair.

96
00:05:17,770 --> 00:05:22,020
>> Yn awr, mae peth pwysig i'w gydnabod yw
bod yn llwyth, yr oeddem yn gwybod bod yr holl

97
00:05:22,020 --> 00:05:25,820
y geiriau yn mynd i fod yn llythrennau bach,
ond yma, nid ydym yn mor siŵr.

98
00:05:25,820 --> 00:05:29,510
Os byddwn yn edrych ar ein swyddogaeth hash,
ein swyddogaeth hash mewn gwirionedd

99
00:05:29,510 --> 00:05:32,700
yn lowercasing pob cymeriad
y gair.

100
00:05:32,700 --> 00:05:37,580
Felly, beth bynnag y cyfalafu
gair, mae ein swyddogaeth hash yn mynd i

101
00:05:37,580 --> 00:05:42,270
dychwelyd yr un mynegai ar gyfer beth bynnag fo'r
cyfalafu fel y byddai'n cael

102
00:05:42,270 --> 00:05:45,280
dychwelyd ar gyfer hollol llythrennau bach
fersiwn o'r gair.

103
00:05:45,280 --> 00:05:45,950
Mae pob hawl.

104
00:05:45,950 --> 00:05:47,410
>> Felly dyna ein mynegai.

105
00:05:47,410 --> 00:05:49,790
Mae'n y tabl hash gyfer y gair hwn.

106
00:05:49,790 --> 00:05:52,940
Yn awr, mae hyn ar gyfer dolen yn mynd
i dros y rhestr gysylltiedig

107
00:05:52,940 --> 00:05:55,000
a oedd ar y mynegai.

108
00:05:55,000 --> 00:05:59,630
Felly, yn sylwi ein bod yn ymgychwyn mynediad
i dynnu sylw at y mynegai.

109
00:05:59,630 --> 00:06:03,480
Rydym yn mynd i barhau tra mynediad yn
Nid yw NULL cyfartal, a chofiwch fod

110
00:06:03,480 --> 00:06:08,350
diweddaru'r pwyntydd yn ein rhestr gysylltiedig
mynediad hafal mynediad-> nesaf, felly mae'n rhaid

111
00:06:08,350 --> 00:06:13,840
ein man mynediad presennol i'r
eitem nesaf yn y rhestr cysylltiedig.

112
00:06:13,840 --> 00:06:14,400
Mae pob hawl.

113
00:06:14,400 --> 00:06:19,150
>> Felly, ar gyfer pob cofnod yn y rhestr gysylltiedig,
rydym yn mynd i ddefnyddio strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Dyw hi ddim yn strcmp oherwydd unwaith eto, rydym yn
eisiau gwneud pethau achos ansensitif.

115
00:06:23,780 --> 00:06:28,830
Felly, rydym yn defnyddio strcasecmp i gymharu'r gair
a oedd yn trosglwyddo i'r swyddogaeth hon

116
00:06:28,830 --> 00:06:31,860
yn erbyn y gair sy'n
yn y cofnod hwn.

117
00:06:31,860 --> 00:06:35,570
Os bydd yn dychwelyd 0, mae hynny'n golygu nad oedd
gêm, ac yn yr achos yr ydym am ei

118
00:06:35,570 --> 00:06:36,630
dychwelyd yn wir.

119
00:06:36,630 --> 00:06:39,590
Rydym yn dod o hyd yn llwyddiannus y
gair yn ein tabl hash.

120
00:06:39,590 --> 00:06:43,040
>> Os nad oedd yn cyfateb, yna rydym yn
mynd i'r ddolen eto ac edrych ar y

121
00:06:43,040 --> 00:06:43,990
cofnod nesaf.

122
00:06:43,990 --> 00:06:47,640
A byddwn yn parhau dolennu er bod
yn cofnodion yn y rhestr cysylltiedig.

123
00:06:47,640 --> 00:06:50,160
Beth fydd yn digwydd os byddwn yn torri
allan o hyn ar gyfer dolen?

124
00:06:50,160 --> 00:06:55,110
Mae hynny'n golygu nad ydym yn dod o hyd i gofnod y
cyfateb gair hwn, ac yn yr achos

125
00:06:55,110 --> 00:07:00,220
byddwn yn dychwelyd ffug i ddangos bod ein
Nid yw tabl hash oedd yn cynnwys y gair hwn.

126
00:07:00,220 --> 00:07:01,910
A dyna ni am siec.

127
00:07:01,910 --> 00:07:02,540
Mae pob hawl.

128
00:07:02,540 --> 00:07:04,790
>> Felly, gadewch i ni edrych ar faint.

129
00:07:04,790 --> 00:07:09,280
Nawr, maint yn mynd i fod yn eithaf syml
ers cofio yn llwyth, i bob gair

130
00:07:09,280 --> 00:07:12,880
rydym yn dod o hyd i ni gynyddrannedig yn fyd-eang
hashtable_size amrywiol.

131
00:07:12,880 --> 00:07:15,830
Felly, y swyddogaeth maint yn unig
mynd i ddychwelyd y byd-eang

132
00:07:15,830 --> 00:07:18,150
amrywiol, a dyna ni.

133
00:07:18,150 --> 00:07:22,300
>> Nawr yn olaf, mae angen i ddadlwytho'r
geiriadur unwaith popeth ei wneud.

134
00:07:22,300 --> 00:07:25,340
Felly, sut ydym yn mynd i wneud hynny?

135
00:07:25,340 --> 00:07:30,440
I'r dde yma, rydym yn dolennu dros yr holl
bwcedi ein tabl hash.

136
00:07:30,440 --> 00:07:33,240
Felly mae bwcedi NUM_BUCKETS.

137
00:07:33,240 --> 00:07:37,490
Ac ar gyfer pob rhestr gysylltiedig yn ein hash
bwrdd, rydyn ni'n mynd i ddolen dros y

138
00:07:37,490 --> 00:07:41,070
gyfanrwydd y rhestr cysylltiedig
rhyddhau pob elfen.

139
00:07:41,070 --> 00:07:46,070
Yn awr, mae angen i ni fod yn ofalus, felly dyma ni
cael newidyn dros dro sy'n

140
00:07:46,070 --> 00:07:49,740
storio y pwyntydd i'r nesaf
elfen yn y rhestr cysylltiedig.

141
00:07:49,740 --> 00:07:52,140
Ac yna rydym yn mynd i rhad ac am ddim
yr elfen gyfredol.

142
00:07:52,140 --> 00:07:55,990
>> 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

143
00:07:55,990 --> 00:07:59,260
ac yna ceisiwch i gael mynediad i'r pwyntydd nesaf
ers ar ôl i ni ei rhyddhau y

144
00:07:59,260 --> 00:08:00,870
cof yn dod yn annilys.

145
00:08:00,870 --> 00:08:04,990
Felly mae angen i gadw o gwmpas pwyntydd i
i'r elfen nesaf, yna gallwn ryddhau'r

146
00:08:04,990 --> 00:08:08,360
elfen ar hyn o bryd, ac yna gallwn ddiweddaru
ein bodd yn bresennol i dynnu sylw at

147
00:08:08,360 --> 00:08:09,590
i'r elfen nesaf.

148
00:08:09,590 --> 00:08:12,770
>> Rydym yn bydd dolen er bod elfennau
yn y rhestr gysylltiedig.

149
00:08:12,770 --> 00:08:16,450
Byddwn yn gwneud hynny ar gyfer pob rhestr cysylltiedig yn
y tabl hash, ac unwaith y byddwn yn ei wneud

150
00:08:16,450 --> 00:08:20,180
â hynny, rydym wedi dadlwytho yn gyfan gwbl
y tabl hash, ac yr ydym yn ei wneud.

151
00:08:20,180 --> 00:08:24,050
Felly, mae'n amhosibl i dadlwytho i byth
dychwelyd ffug, a phan fyddwn yn ei wneud, rydym yn

152
00:08:24,050 --> 00:08:25,320
dim ond dychwelyd yn wir.

153
00:08:25,320 --> 00:08:27,563