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
Mwen se Rob, ak hash Annou
sa a solisyon deyò.

4
00:00:16,210 --> 00:00:20,070
Se konsa, isit la nou ap ale nan aplike
yon hash tab jeneral.

5
00:00:20,070 --> 00:00:24,090
Nou wè ke ne la konstri nan hash nou
tab ki pral gade tankou sa a.

6
00:00:24,090 --> 00:00:28,710
Se konsa, li la pral fè yon mo Char
etalaj de gwosè longè plis 1.

7
00:00:28,710 --> 00:00:32,259
pa bliye 1 an depi maksimòm la
mo an nan diksyonè a se 45

8
00:00:32,259 --> 00:00:35,110
karaktè, ak Lè sa a, nou pral
bezwen yon karaktè anplis pou la

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

10
00:00:37,070 --> 00:00:40,870
>> Lè sa a, tab hash nou yo nan chak
bokit ki pral estoke yon

11
00:00:40,870 --> 00:00:42,320
lis lye nan nœuds.

12
00:00:42,320 --> 00:00:44,420
Nou pa ap fè lineyè sonde isit la.

13
00:00:44,420 --> 00:00:48,430
Se konsa, yo nan lòd yo genyen lyen pwochen an
eleman nan bokit la, nou bezwen yon

14
00:00:48,430 --> 00:00:51,110
konstri ne * kap vini an.

15
00:00:51,110 --> 00:00:53,090
Se konsa, se sa ki yon ne sanble.

16
00:00:53,090 --> 00:00:56,180
Koulye a, isit la se deklarasyon an
nan tablo hash nou an.

17
00:00:56,180 --> 00:01:01,910
Li pral gen 16.384 bokit, men
ladan nimewo pa reyèlman gen pwoblèm.

18
00:01:01,910 --> 00:01:05,450
E finalman, nou pral gen a
mondyal hashtable_size varyab, ki

19
00:01:05,450 --> 00:01:08,640
ki pral kòmanse desann kòm 0, epi li
ale nan kenbe tras nan konbyen mo

20
00:01:08,640 --> 00:01:10,080
yo te nan diksyonè nou an.

21
00:01:10,080 --> 00:01:10,760
Tout dwa.

22
00:01:10,760 --> 00:01:13,190
>> Se konsa, kite a pran yon gade nan chaj.

23
00:01:13,190 --> 00:01:16,390
Se konsa, remake ke chaj,
li retounen yon bouleen.

24
00:01:16,390 --> 00:01:20,530
Ou retounen vre si li te avèk siksè
chaje ak fo otreman.

25
00:01:20,530 --> 00:01:23,990
Apre sa, li pran yon Char zetwal * CONST
diksyonè, ki se diksyonè a

26
00:01:23,990 --> 00:01:25,280
ke nou vle louvri.

27
00:01:25,280 --> 00:01:27,170
Se konsa, sa a, se premye bagay la
nou pral fè.

28
00:01:27,170 --> 00:01:30,420
Nou pral fopen diksyonè a pou
lekti, epi nou pral gen

29
00:01:30,420 --> 00:01:34,700
asire w ke li nan plas Se konsa, si
li tounen NULL, lè sa a nou pa t '

30
00:01:34,700 --> 00:01:37,440
avèk siksè louvri diksyonè a
e nou bezwen retounen fo.

31
00:01:37,440 --> 00:01:41,580
>> Men, an konsideran ke li te fè avèk siksè
louvri, lè sa a nou vle li a

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

33
00:01:42,400 --> 00:01:46,210
Se konsa, kenbe loupin jiskaske nou jwenn kèk
rezon ki fè yo kraze soti nan sa a

34
00:01:46,210 --> 00:01:47,570
bouk ki nou pral wè.

35
00:01:47,570 --> 00:01:51,780
Se konsa, kenbe loupin, epi kounye a nou pwal
malok yon ne sèl.

36
00:01:51,780 --> 00:01:56,800
Ak nan kou, nou bezwen erè chèk
ankò Se konsa, si mallocing pa t 'reyisi

37
00:01:56,800 --> 00:02:00,660
e nou vle dechaje nenpòt ki ne ke nou
rive malok anvan, fèmen a

38
00:02:00,660 --> 00:02:02,590
diksyonè epi retounen bay manti.

39
00:02:02,590 --> 00:02:07,440
>> Men, inyore ke, an konsideran nou
nan plas, lè sa a nou vle sèvi ak fskanf

40
00:02:07,440 --> 00:02:12,400
li yon mo yon sèl soti nan nou an
diksyonè nan ne nou an.

41
00:02:12,400 --> 00:02:17,310
Se konsa, sonje mo sa a antre-> se Char la
tanpon mo ki gen yon gwosè longè plis

42
00:02:17,310 --> 00:02:20,300
yon sèl ke nou ap ale nan
magazen pawòl Bondye a pous

43
00:02:20,300 --> 00:02:25,280
Se konsa, fskanf ki pral retounen 1 osi lontan
kòm li te kapab avèk siksè li yon

44
00:02:25,280 --> 00:02:26,750
mo nan dosye a.

45
00:02:26,750 --> 00:02:31,030
>> Si youn nan yon erè k ap pase oswa nou rive nan
fen a nan dosye a, li pa pral

46
00:02:31,030 --> 00:02:34,950
retounen 1 nan ka sa a si li fè sa pa
retounen 1, n ap finalman pral kraze

47
00:02:34,950 --> 00:02:37,280
soti nan sa a bouk ti tan.

48
00:02:37,280 --> 00:02:42,770
Se konsa, nou wè ke yon fwa nou gen avèk siksè
li yon mo nan

49
00:02:42,770 --> 00:02:48,270
antre-> mo, Lè sa a, nou pral Hash
mo ki lè l sèvi avèk fonksyon hash nou an.

50
00:02:48,270 --> 00:02:49,580
Se pou nou pran yon gade nan
fonksyon an hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Se konsa, ou pa reyèlman bezwen
yo konprann sa a.

53
00:02:55,610 --> 00:02:59,460
Apre sa, aktyèlman, nou jis rale sa a
Hash fonksyon soti nan entènèt la.

54
00:02:59,460 --> 00:03:04,010
Sèl bagay ou bezwen rekonèt se
ke sa a pran yon mo CONST * Char,

55
00:03:04,010 --> 00:03:08,960
Se konsa, li la pran yon fisèl kòm opinyon ak
retounen yon Int siye kòm pwodiksyon.

56
00:03:08,960 --> 00:03:12,360
Se konsa, ki nan tout yon fonksyon hash se, se li
pran nan yon D ', li ba ou yon

57
00:03:12,360 --> 00:03:14,490
endèks nan tablo a hash.

58
00:03:14,490 --> 00:03:18,530
Remake nou ap modin pa NUM_BUCKETS
Se konsa, valè a hash tounen

59
00:03:18,530 --> 00:03:21,730
aktyèlman se yon endèks nan tablo a hash
ak fè sa ki pa endèks pi lwen pase a

60
00:03:21,730 --> 00:03:24,320
limit nan etalaj la.

61
00:03:24,320 --> 00:03:27,855
>> Se konsa, bay yo ke fonksyon hash, nou pwal
Hash pawòl Bondye a ke nou li

62
00:03:27,855 --> 00:03:31,700
soti nan diksyonè a ak Lè sa a, nou pral
yo sèvi ak ki gen insert la

63
00:03:31,700 --> 00:03:33,750
antre nan tab la hash.

64
00:03:33,750 --> 00:03:38,830
Koulye a, hashtable hash se aktyèl la
lis lye nan tablo a hash, ak

65
00:03:38,830 --> 00:03:41,410
li trè posib ke se jis NULL.

66
00:03:41,410 --> 00:03:45,640
Nou vle insert antre nou an nan la
kòmanse nan lis sa a lye, e konsa

67
00:03:45,640 --> 00:03:48,910
nou pral gen antre aktyèl nou an
lonje dwèt sou sa ki tab la hash kounye a

68
00:03:48,910 --> 00:03:54,030
pwen pou ale ak pou Lè sa a, nou pral nan magazen
nan tablo a hash nan hash la

69
00:03:54,030 --> 00:03:55,350
antre nan aktyèl la.

70
00:03:55,350 --> 00:03:59,320
>> Se konsa, de liy sa yo avèk siksè insert
antre nan nan kòmansman an nan la

71
00:03:59,320 --> 00:04:02,270
lis lye nan ki endèks
nan tablo a hash.

72
00:04:02,270 --> 00:04:04,900
Yon fwa nou ap fè ak sa, nou konnen
ke nou jwenn yon lòt mo nan la

73
00:04:04,900 --> 00:04:07,800
diksyonè ak nou enkreman ankò.

74
00:04:07,800 --> 00:04:13,960
Se konsa, nou kontinye ap fè sa jouk lè fskanf
finalman retounen yon bagay ki 1 nan

75
00:04:13,960 --> 00:04:18,560
ki pwen sonje ke nou bezwen
rantre lib, se konsa moute isit la, nou malloced yon

76
00:04:18,560 --> 00:04:21,329
antre ak nou te eseye li yon bagay
soti nan diksyonè a.

77
00:04:21,329 --> 00:04:24,110
Apre sa, nou pa t 'avèk siksè li
yon bagay soti nan diksyonè a nan sa ki

78
00:04:24,110 --> 00:04:27,440
ka nou bezwen libere antre nan ke nou
aktyèlman pa janm mete nan tablo a hash

79
00:04:27,440 --> 00:04:29,110
epi finalman kase.

80
00:04:29,110 --> 00:04:32,750
>> Yon fwa nou kraze soti, nou bezwen wè, byen,
t 'nou kraze soti paske se la

81
00:04:32,750 --> 00:04:35,840
te yon erè li nan dosye a, oswa
t 'nou kraze soti paske nou te rive nan

82
00:04:35,840 --> 00:04:37,120
fen a nan dosye a?

83
00:04:37,120 --> 00:04:40,150
Si te gen yon erè, lè sa a nou vle
retounen fo paske chaj pa t '

84
00:04:40,150 --> 00:04:43,260
reyisi, ak nan pwosesis la, nou vle
dechaje tout pawòl sa yo ke nou li

85
00:04:43,260 --> 00:04:45,670
nan epi fèmen dosye a diksyonè.

86
00:04:45,670 --> 00:04:48,740
Si nou sipoze nou te reyisi, Lè sa a, nou jis
toujou bezwen yo fèmen diksyonè a

87
00:04:48,740 --> 00:04:51,970
pote, epi finalman retounen vre depi
nou te avèk siksè chaje a

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

89
00:04:53,040 --> 00:04:54,420
Epi sa a, li pou chaj.

90
00:04:54,420 --> 00:04:59,020
>> Se konsa, koulye tcheke, yo bay yon tab hash chaje,
ki pral gade tankou sa a.

91
00:04:59,020 --> 00:05:02,690
Se konsa, tcheke, li retounen yon bouleen, ki
ki pral endike si la

92
00:05:02,690 --> 00:05:07,530
pase-an Char mo *, si wi ou non nan
pase-nan fil se nan diksyonè nou an.

93
00:05:07,530 --> 00:05:10,530
Se konsa, si li se an nan diksyonè a, si li se
nan tablo hash nou yo, nou pral retounen

94
00:05:10,530 --> 00:05:13,380
vre, epi si li pa,
nou pral retounen bay manti.

95
00:05:13,380 --> 00:05:17,770
Bay mo sa a te pase-a, nou
ale nan Hash mo a.

96
00:05:17,770 --> 00:05:22,020
>> Koulye a, yon bagay enpòtan yo rekonèt se
ke nan chaj, nou te konnen ke tout moun nan

97
00:05:22,020 --> 00:05:25,820
mo sa yo te ale nan pi ba a,
men isit la, nou pa konsa pou sa asire w.

98
00:05:25,820 --> 00:05:29,510
Si nou pran yon gade nan fonksyon hash nou an,
fonksyon hash nou an aktyèlman

99
00:05:29,510 --> 00:05:32,700
se lowercasing chak karaktè
nan pawòl Bondye a.

100
00:05:32,700 --> 00:05:37,580
Se konsa, kèlkeswa lèt majiskil la nan
mo, fonksyon hash nou an, se ale nan

101
00:05:37,580 --> 00:05:42,270
retounen endèks la menm pou la kèlkeswa sa
lèt majiskil se tankou li ta gen

102
00:05:42,270 --> 00:05:45,280
tounen pou yon konplètman miniskil
vèsyon an pawòl Bondye a.

103
00:05:45,280 --> 00:05:45,950
Tout dwa.

104
00:05:45,950 --> 00:05:47,410
>> Se konsa, sa a, se endèks nou an.

105
00:05:47,410 --> 00:05:49,790
Li nan tablo a hash pou sa a mo.

106
00:05:49,790 --> 00:05:52,940
Koulye a, sa a pou bouk ki pral
Plis pase lis la lye

107
00:05:52,940 --> 00:05:55,000
sa ki te nan moman sa Konpayi paran yo.

108
00:05:55,000 --> 00:05:59,630
Se konsa, remake nou ap inisyalizin antre
nan pwen ak sa yo ki endèks.

109
00:05:59,630 --> 00:06:03,480
Nou pral kontinye pandan y ap antre fè
pa egal NULL, epi sonje ke

110
00:06:03,480 --> 00:06:08,350
à konsèy la nan lis lye nou
antre egal antre-> kap vini an, konsa gen

111
00:06:08,350 --> 00:06:13,840
nou pwen antre aktyèl yo bay la
atik pwochen nan lis lye.

112
00:06:13,840 --> 00:06:14,400
Tout dwa.

113
00:06:14,400 --> 00:06:19,150
>> Se konsa, pou chak antre nan lis la lye,
nou pral sèvi ak strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Li pa nan strkan paske yon lòt fwa ankò, nou
vle fè bagay sa yo ka insensitively.

115
00:06:23,780 --> 00:06:28,830
Se konsa, nou sèvi ak strcasecmp yo konpare pawòl Bondye a
sa ki te pase bay fonksyon sa a

116
00:06:28,830 --> 00:06:31,860
kont pawòl Bondye a ki
se nan sa a antre.

117
00:06:31,860 --> 00:06:35,570
Si li retounen 0, sa vle di te gen
yon match, nan ka sa nou vle

118
00:06:35,570 --> 00:06:36,630
retounen vre.

119
00:06:36,630 --> 00:06:39,590
Nou jwenn avèk siksè nan
mo nan tablo hash nou an.

120
00:06:39,590 --> 00:06:43,040
>> Si pa t 'gen yon match, lè sa a nou ap
ale nan bouk ankò, li gade nan la

121
00:06:43,040 --> 00:06:43,990
pwochen antre.

122
00:06:43,990 --> 00:06:47,640
Epitou, n ap kontinye loupin pandan y ap gen
yo antre nan lis sa a lye.

123
00:06:47,640 --> 00:06:50,160
Kisa k ap pase si nou kraze
soti nan sa a pou bouk?

124
00:06:50,160 --> 00:06:55,110
Sa vle di nou pa t 'jwenn yon antre ki
matche mo sa a, nan ki ka

125
00:06:55,110 --> 00:07:00,220
nou retounen fo ke yo endike ke nou
tab hash pa t 'gen mo sa a.

126
00:07:00,220 --> 00:07:01,910
Epi sa a, li pou chèk la.

127
00:07:01,910 --> 00:07:02,540
Tout dwa.

128
00:07:02,540 --> 00:07:04,790
>> Se konsa, kite a pran yon gade nan gwosè.

129
00:07:04,790 --> 00:07:09,280
Koulye a, gwosè a pwal trè senp
depi sonje nan chaj, pou chak mo

130
00:07:09,280 --> 00:07:12,880
nou te jwenn nou enkremante yon mondyal
varyab hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Se konsa, fonksyon an gwosè se jis
ale nan retounen ke mondyal

132
00:07:15,830 --> 00:07:18,150
varyab, e ke sa a li.

133
00:07:18,150 --> 00:07:22,300
>> Koulye a, finalman, nou bezwen dechaje la
diksyonè yon fwa tout bagay nan fè.

134
00:07:22,300 --> 00:07:25,340
Se konsa, kouman nou pral fè sa?

135
00:07:25,340 --> 00:07:30,440
Dwa isit la, nou ap loupin sou tout
bokit nan tablo hash nou an.

136
00:07:30,440 --> 00:07:33,240
Se konsa, gen NUM_BUCKETS bokit.

137
00:07:33,240 --> 00:07:37,490
Epi pou chak lis lye nan hash nou
tab, nou pral bouk sou la

138
00:07:37,490 --> 00:07:41,070
antye nan lis la lye
libere chak eleman.

139
00:07:41,070 --> 00:07:46,070
Koulye a, nou bezwen dwe fè atansyon, se konsa isit la nou
gen yon varyab pou yon ti tan sa a, se

140
00:07:46,070 --> 00:07:49,740
estoke konsèy la pwochen an
eleman nan lis la lye.

141
00:07:49,740 --> 00:07:52,140
Lè sa a, nou pral gratis
eleman aktyèl la.

142
00:07:52,140 --> 00:07:55,990
>> Nou bezwen asire w ke nou fè sa depi nou
pa ka jis gratis eleman aktyèl la

143
00:07:55,990 --> 00:07:59,260
ak Lè sa a, eseye jwenn aksè nan konsèy nan pwochen
depi yon fwa nou te libere li nan

144
00:07:59,260 --> 00:08:00,870
memwa vin valab.

145
00:08:00,870 --> 00:08:04,990
Se konsa, nou bezwen kenbe otou yon konsèy
eleman kap vini an, Lè sa a, nou ka libere nan

146
00:08:04,990 --> 00:08:08,360
eleman kounye a, ak Lè sa a, nou ka mete
eleman aktyèl nou yo lonje dwèt sou

147
00:08:08,360 --> 00:08:09,590
eleman nan pwochen an.

148
00:08:09,590 --> 00:08:12,770
>> Nou pral bouk pandan y ap gen eleman
nan lis sa a lye.

149
00:08:12,770 --> 00:08:16,450
Nou pral fè sa pou tout lis lye nan
tab la hash, ak yon fwa nou ap fè

150
00:08:16,450 --> 00:08:20,180
ak sa, nou te konplètman chaje
tab la hash, epi nou ap fè.

151
00:08:20,180 --> 00:08:24,050
Se konsa, li enposib pou decharjeman tout tan tout tan
retounen fo, ak lè nou ap fè, nou

152
00:08:24,050 --> 00:08:25,320
jis retounen vre.

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