1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:01,900
[MIZIK jwe]

3
00:00:01,900 --> 00:00:05,710

4
00:00:05,710 --> 00:00:09,150
>> Doug Lloyd: Lè kounye a ou
konnen anpil sou ranje,

5
00:00:09,150 --> 00:00:11,610
epi ou konnen anpil bagay sou lis lye.

6
00:00:11,610 --> 00:00:13,650
Epi nou te diskite sou nan
Les ak inconvénients, nou te

7
00:00:13,650 --> 00:00:16,620
diskite ki lye lis
ka jwenn pi gwo ak pi piti,

8
00:00:16,620 --> 00:00:18,630
men yo pran plis gwosè.

9
00:00:18,630 --> 00:00:22,359
Ranje yo se pi plis dwat yo
sèvi ak, men yo ap restriksyon nan kòm anpil

10
00:00:22,359 --> 00:00:24,900
jan nou gen yo mete gwosè a nan
etalaj la nan konmansman an anpil

11
00:00:24,900 --> 00:00:26,910
ak Lè sa a nou ap kole ak li.

12
00:00:26,910 --> 00:00:30,470
>> Men, sa a, nou te bèl anpil
fin itilize tout nan sijè nou an

13
00:00:30,470 --> 00:00:33,040
sou lis lye ak ranje.

14
00:00:33,040 --> 00:00:34,950
Oswa ki gen nou ye?

15
00:00:34,950 --> 00:00:37,720
Petèt nou ka fè yon bagay
menm plis kreyatif.

16
00:00:37,720 --> 00:00:40,950
Ak ki sòt de prête
lide a nan yon tab regle.

17
00:00:40,950 --> 00:00:46,680
>> Se konsa, nan yon tab regle nou ap ale nan eseye
konbine yon etalaj ak yon lis lye.

18
00:00:46,680 --> 00:00:49,520
Nou ap pral pran avantaj ki genyen nan
nan etalaj la, tankou aksè o aza,

19
00:00:49,520 --> 00:00:53,510
ke yo te kapab jis ale nan etalaj
eleman 4 oswa etalaj eleman 8

20
00:00:53,510 --> 00:00:55,560
san yo pa gen repekte nan tout.

21
00:00:55,560 --> 00:00:57,260
Sa a trè vit, dwa?

22
00:00:57,260 --> 00:01:00,714
>> Men, nou menm tou nou vle gen done nou an
estrikti kapab grandi ak retresi.

23
00:01:00,714 --> 00:01:02,630
Nou pa bezwen, nou pa fè sa
vle jwenn restriksyon.

24
00:01:02,630 --> 00:01:04,588
E nou vle yo dwe kapab
ajoute epi retire bagay

25
00:01:04,588 --> 00:01:08,430
trè fasil, ki si ou sonje,
se yon bagay ki konplèks ak yon etalaj.

26
00:01:08,430 --> 00:01:11,650
Apre sa, nou ka rele sa a
bagay nouvo yon tab regle.

27
00:01:11,650 --> 00:01:15,190
>> Men, si aplike kòrèkteman,
nou ap sòt de pran

28
00:01:15,190 --> 00:01:18,150
avantaj ki genyen nan tou de done
estrikti ou te deja wè,

29
00:01:18,150 --> 00:01:19,880
ranje e li bay lis lye.

30
00:01:19,880 --> 00:01:23,070
Ensèsyon ka kòmanse
yo gen tandans nan direksyon Theta nan 1.

31
00:01:23,070 --> 00:01:26,207
Theta nou pa te reyèlman diskite,
men Theta se jis ka a mwayèn,

32
00:01:26,207 --> 00:01:27,540
sa k ap aktyèlman pral rive.

33
00:01:27,540 --> 00:01:29,680
W ap pa toujou ale nan
gen senaryo a ka pi mal la,

34
00:01:29,680 --> 00:01:32,555
ak w ap pa toujou ale nan gen
senaryo a ka pi bon, se konsa sa ki nan

35
00:01:32,555 --> 00:01:33,900
senaryo an mwayèn?

36
00:01:33,900 --> 00:01:36,500
>> Oke yon ensèsyon jou mwayèn
nan yon tab regle

37
00:01:36,500 --> 00:01:39,370
ka kòmanse yo ka resevwa fèmen zan tan konstan.

38
00:01:39,370 --> 00:01:41,570
Apre sa, sipresyon ka jwenn
fèmen zan tan konstan.

39
00:01:41,570 --> 00:01:44,440
Apre sa, Passage ka jwenn
fèmen zan tan konstan.

40
00:01:44,440 --> 00:01:48,600
That's-- nou pa gen yon done
estrikti ankò ki ka fè sa,

41
00:01:48,600 --> 00:01:51,180
ak pou sa a deja son
tankou yon bagay trè gwo.

42
00:01:51,180 --> 00:01:57,010
Nou te vrèman atténué nan
dezavantaj nan chak sou pwòp li yo.

43
00:01:57,010 --> 00:01:59,160
>> Pou jwenn sa a pèfòmans
ajou menm si, nou

44
00:01:59,160 --> 00:02:03,580
bezwen repanse fason nou ajoute
done nan estrikti an.

45
00:02:03,580 --> 00:02:07,380
Espesyalman nou vle a
done tèt li nan di nou

46
00:02:07,380 --> 00:02:09,725
kote li ta dwe ale nan estrikti a.

47
00:02:09,725 --> 00:02:12,850
Men, si nou Lè sa a, bezwen wè si li nan nan
estrikti a, si nou bezwen jwenn li,

48
00:02:12,850 --> 00:02:16,610
nou vle fè yon gade nan done yo
ankò epi yo dwe kapab efektivman,

49
00:02:16,610 --> 00:02:18,910
lè l sèvi avèk done yo, owaza aksè li.

50
00:02:18,910 --> 00:02:20,700
Jis pa gade nan
done nou ta dwe gen

51
00:02:20,700 --> 00:02:25,890
yon lide sou ki kote egzakteman nou ap
ale nan jwenn li nan tablo a regle.

52
00:02:25,890 --> 00:02:28,770
>> Koulye a, anba kote an nan yon regle
tab se yo ke yo ap reyèlman

53
00:02:28,770 --> 00:02:31,770
trè move nan kòmann-nan oswa klasman done.

54
00:02:31,770 --> 00:02:34,970
Ak an reyalite, si ou kòmanse
yo sèvi ak yo nan lòd oswa sòt

55
00:02:34,970 --> 00:02:37,990
done ou pèdi tout nan la
avantaj ou te deja

56
00:02:37,990 --> 00:02:40,710
te gen an tèm de ensèsyon ak sipresyon.

57
00:02:40,710 --> 00:02:44,060
Lè a vin pi pre
Theta nan n, epi nou te fondamantalman

58
00:02:44,060 --> 00:02:45,530
regression nan yon lis lye.

59
00:02:45,530 --> 00:02:48,850
Se konsa, nou sèlman vle sèvi ak regle
tab si nou pa pran swen sou

60
00:02:48,850 --> 00:02:51,490
si wi ou non done se Klase.

61
00:02:51,490 --> 00:02:54,290
Pou kontèks la nan ki
ou pral sèvi ak yo nan CS50

62
00:02:54,290 --> 00:02:58,900
pwobableman ou pa pran swen
ke done a ap Ranje.

63
00:02:58,900 --> 00:03:03,170
>> Se konsa, yon tab regle se yon konbinezon
nan de moso diferan

64
00:03:03,170 --> 00:03:04,980
ak ki nou ap yo konnen yo.

65
00:03:04,980 --> 00:03:07,930
Premye a se yon fonksyon, ki
anjeneral nou rele yon fonksyon regle.

66
00:03:07,930 --> 00:03:11,760
Epi sa fonksyon regle ki pral
retounen kèk nonb antye relatif ki pa negatif, ki

67
00:03:11,760 --> 00:03:14,870
anjeneral nou rele yon hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Moso nan dezyèm se yon etalaj, ki se
kapab nan estoke done nan nou an di ki

69
00:03:20,230 --> 00:03:22,190
vle mete nan estrikti a done.

70
00:03:22,190 --> 00:03:24,310
Nou pral kenbe sou sou mòn lan
lye eleman lis pou kounye a

71
00:03:24,310 --> 00:03:27,810
ak jis kòmanse ak Basics yo nan yon
Hash tab yo ka resevwa tèt ou bò kote l ',

72
00:03:27,810 --> 00:03:30,210
ak Lè sa a nou pral petèt kònen
lide ou yon ti jan lè nou

73
00:03:30,210 --> 00:03:32,920
konbine ranje e li bay lis lyen ansanm.

74
00:03:32,920 --> 00:03:35,590
>> Lide a debaz menm si
se nou pran kèk done.

75
00:03:35,590 --> 00:03:37,860
Nou kouri ke done a
fonksyon an regle.

76
00:03:37,860 --> 00:03:41,980
Se konsa, se done yo trete
epi li krache soti yon nimewo, OK?

77
00:03:41,980 --> 00:03:44,890
Lè sa a, ak sa nimewo
nou jis magazen done yo

78
00:03:44,890 --> 00:03:48,930
nou vle nan magazen an nan
etalaj nan ki kote.

79
00:03:48,930 --> 00:03:53,990
Se konsa, pou egzanp nou gen petèt
sa a tab regle nan strings.

80
00:03:53,990 --> 00:03:57,350
Li nan te resevwa 10 eleman nan li, se konsa
nou ka anfòm 10 strings nan li.

81
00:03:57,350 --> 00:03:59,320
>> Se pou nou di nou vle Hash Jan.

82
00:03:59,320 --> 00:04:02,979
Se konsa, Jan kòm done a nou vle insert
nan sa a tab regle yon kote.

83
00:04:02,979 --> 00:04:03,770
Ki kote nou mete l '?

84
00:04:03,770 --> 00:04:05,728
Oke tipikman ak yon
etalaj byen lwen tèlman nou pwobableman

85
00:04:05,728 --> 00:04:07,610
ta mete l 'nan etalaj kote 0.

86
00:04:07,610 --> 00:04:09,960
Men koulye a, nou gen fonksyon regle nouvo sa a.

87
00:04:09,960 --> 00:04:13,180
>> Li kite yo di ke nou kouri John
a fonksyon regle sa a

88
00:04:13,180 --> 00:04:15,417
ak li a krache soti 4.

89
00:04:15,417 --> 00:04:17,500
Oke sa a, se kote nou ap
ale nan vle mete Jan.

90
00:04:17,500 --> 00:04:22,050
Nou vle mete Jan Batis nan kote etalaj
4, paske si nou Hash Jan again--

91
00:04:22,050 --> 00:04:23,810
kite a di pita nou
vle fè rechèch ak wè

92
00:04:23,810 --> 00:04:26,960
si Jan egziste nan regle sa a
table-- tout sa nou bezwen fè

93
00:04:26,960 --> 00:04:30,310
se kouri l 'nan menm regle nan
fonksyon, jwenn nimewo 4 soti nan,

94
00:04:30,310 --> 00:04:33,929
yo epi yo dwe kapab jwenn Jan
imedyatman nan estrikti done nou an.

95
00:04:33,929 --> 00:04:34,720
Sa a trè bon.

96
00:04:34,720 --> 00:04:36,928
>> Se pou nou di kounye a nou fè sa
ankò, nou vle Hash Pòl.

97
00:04:36,928 --> 00:04:39,446
Nou vle ajoute Pòl
nan sa a tab regle.

98
00:04:39,446 --> 00:04:42,070
Se pou nou di ke tan sa a nou kouri
Pòl nan fonksyon an regle,

99
00:04:42,070 --> 00:04:44,600
hashcode sa a, ki te pwodwi se 6.

100
00:04:44,600 --> 00:04:47,340
Oke kounye a nou ka mete Pòl
nan kote a etalaj 6.

101
00:04:47,340 --> 00:04:50,040
Men, si nou bezwen yo gade jiska si wi ou non
Pòl se nan sa a tab regle,

102
00:04:50,040 --> 00:04:53,900
tout sa nou bezwen fè se kouri Pòl
a fonksyon an regle ankò

103
00:04:53,900 --> 00:04:55,830
epi nou ap ale nan jwenn 6 soti ankò.

104
00:04:55,830 --> 00:04:57,590
>> Lè sa a, nou jis gade
a etalaj kote 6.

105
00:04:57,590 --> 00:04:58,910
Èske Pòl la?

106
00:04:58,910 --> 00:05:00,160
Si se konsa, li se nan tablo a regle.

107
00:05:00,160 --> 00:05:01,875
Èske Pòl pa genyen?

108
00:05:01,875 --> 00:05:03,000
Li se pa nan tablo a regle.

109
00:05:03,000 --> 00:05:05,720
Li trè senp.

110
00:05:05,720 --> 00:05:07,770
>> Koulye a, ki jan ou defini yon fonksyon regle?

111
00:05:07,770 --> 00:05:11,460
Oke gen nan reyèlman pa gen okenn limit nan la
Nimewo nan fonksyon regle posib.

112
00:05:11,460 --> 00:05:14,350
An reyalite gen nan yon kantite reyèlman,
yo menm reyèlman bon sou entènèt la.

113
00:05:14,350 --> 00:05:17,560
Genyen yon kantite reyèlman,
reyèlman move yo menm sou entènèt la.

114
00:05:17,560 --> 00:05:21,080
Li la tou trè fasil
yo ekri yon yon sèl move.

115
00:05:21,080 --> 00:05:23,760
>> Se konsa, sa fè moute yon bon
fonksyon regle, dwa?

116
00:05:23,760 --> 00:05:27,280
Oke yon fonksyon regle bon ta dwe
sèvi ak sèlman done yo ke yo te ache,

117
00:05:27,280 --> 00:05:29,420
ak tout nan done yo ke yo te ache.

118
00:05:29,420 --> 00:05:32,500
Se konsa, nou pa vle sèvi ak anything--
nou pa enkòpore anyen

119
00:05:32,500 --> 00:05:35,560
lòt lòt pase done yo.

120
00:05:35,560 --> 00:05:37,080
Apre sa, nou vle sèvi ak tout nan done yo.

121
00:05:37,080 --> 00:05:39,830
Nou pa vle jis itilize yon moso
nan li, nou vle sèvi ak tout nan li.

122
00:05:39,830 --> 00:05:41,710
Yon fonksyon regle ta dwe
tou ap detèrminist.

123
00:05:41,710 --> 00:05:42,550
Ki sa sa vle di?

124
00:05:42,550 --> 00:05:46,200
Oke sa vle di ke chak fwa nou
pase egzak moso nan menm nan done

125
00:05:46,200 --> 00:05:50,040
nan fonksyon an regle nou toujou
jwenn menm hashcode a soti.

126
00:05:50,040 --> 00:05:52,870
Si m 'pase Jan Batis nan la
fonksyon regle mwen jwenn soti 4.

127
00:05:52,870 --> 00:05:56,110
Mwen ta dwe kapab fè sa 10,000
fwa epi mwen pral toujou jwenn 4.

128
00:05:56,110 --> 00:06:00,810
Konsa pa gen nimewo o aza efektivman
ka patisipe nan regle nou an tables--

129
00:06:00,810 --> 00:06:02,750
nan fonksyon regle nou an.

130
00:06:02,750 --> 00:06:05,750
>> Yon fonksyon regle ta dwe tou
egzakteman menm jan distribye done.

131
00:06:05,750 --> 00:06:09,700
Si chak fwa ou kouri nan done nan
fonksyon regle ou jwenn hashcode nan 0,

132
00:06:09,700 --> 00:06:11,200
sa a, se pwobableman pa tèlman gwo, dwa?

133
00:06:11,200 --> 00:06:14,600
Ou pwobableman vle gwo
yon seri de kòd regle.

134
00:06:14,600 --> 00:06:17,190
Epitou bagay sa yo ka ka gaye
soti nan tout tab la.

135
00:06:17,190 --> 00:06:23,210
Epi tou li ta gwo si reyèlman
done ki similè yo, tankou Jan ak Jonatan,

136
00:06:23,210 --> 00:06:26,320
petèt yo te gaye soti nan peze
diferan pozisyon nan tablo a regle.

137
00:06:26,320 --> 00:06:28,750
Ki ta ka yon avantaj bèl.

138
00:06:28,750 --> 00:06:31,250
>> Isit la nan yon egzanp sou yon fonksyon regle.

139
00:06:31,250 --> 00:06:33,150
Mwen te ekri yon sèl sa a moute pi bonè.

140
00:06:33,150 --> 00:06:35,047
Li pa yon patikilyèman
bon fonksyon regle

141
00:06:35,047 --> 00:06:37,380
pou rezon ki fè pa reyèlman
pote ale nan kounye a.

142
00:06:37,380 --> 00:06:41,040
Men, ou wè sa ki k ap pase sou isit la?

143
00:06:41,040 --> 00:06:44,420
Li sanble tankou nou ap deklare yon varyab
rele sòm ak anviwònman li egal a 0.

144
00:06:44,420 --> 00:06:50,010
Lè sa a, aparamman mwen fè yon bagay
toutotan strstr [j] se pa egal

145
00:06:50,010 --> 00:06:52,490
antislach 0.

146
00:06:52,490 --> 00:06:54,870
Kisa mwen fè la?

147
00:06:54,870 --> 00:06:57,440
>> Sa a se fondamantalman jis yon lòt
fason pou mete ann aplikasyon [? strl?]

148
00:06:57,440 --> 00:06:59,773
ak detekte lè ou te
rive jwenn nan fen fisèl la.

149
00:06:59,773 --> 00:07:02,480
Se konsa, mwen pa bezwen aktyèlman
kalkile longè a nan fisèl la,

150
00:07:02,480 --> 00:07:05,640
Mwen jis lè l sèvi avèk lè m 'frape nan
antislach 0 karaktè mwen konnen

151
00:07:05,640 --> 00:07:07,185
Mwen te rive jwenn nan fen fisèl la.

152
00:07:07,185 --> 00:07:09,560
Lè sa a, mwen pral kenbe
iteration nan ki fisèl,

153
00:07:09,560 --> 00:07:15,310
ajoute strstr [j] ak sòm, ak Lè sa nan la
fen nan jounen an pral retounen sòm mod

154
00:07:15,310 --> 00:07:16,200
HASH_MAX.

155
00:07:16,200 --> 00:07:18,700
>> Fondamantalman tout regle sa a
fonksyon ap fè se ajoute moute

156
00:07:18,700 --> 00:07:23,450
tout nan valè yo ASCII a
fisèl mwen, ak Lè sa a li a

157
00:07:23,450 --> 00:07:26,390
retounen kèk hashcode
modded pa HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Li pwobableman gwosè a
nan etalaj mwen, dwa?

159
00:07:29,790 --> 00:07:33,160
Mwen pa vle yo dwe ap resevwa regle
kòd si etalaj mwen an se nan gwosè 10,

160
00:07:33,160 --> 00:07:35,712
Mwen pa vle yo dwe ap resevwa
soti kòd regle 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, mwen pa ka mete bagay sa yo nan
moun kote nan etalaj la,

162
00:07:38,690 --> 00:07:39,790
ki ta ka ilegal.

163
00:07:39,790 --> 00:07:42,130
Mwen ta soufri yon fay segmentation.

164
00:07:42,130 --> 00:07:45,230
>> Koulye a isit la se yon lòt rapid sou kote.

165
00:07:45,230 --> 00:07:48,470
Anjeneral w ap pwobableman pa ale nan
vle ekri ou fonksyon regle pwòp.

166
00:07:48,470 --> 00:07:50,997
Li se aktyèlman yon ti jan nan
yon atis, se pa yon syans.

167
00:07:50,997 --> 00:07:52,580
Apre sa, gen nan yon anpil ki ale nan yo.

168
00:07:52,580 --> 00:07:55,288
Entènèt la, tankou mwen te di, se tout
nan fonksyon regle reyèlman bon,

169
00:07:55,288 --> 00:07:58,470
epi ou ta dwe sèvi ak entènèt la
jwenn fonksyon regle paske li nan reyèlman

170
00:07:58,470 --> 00:08:03,230
jis kalite yon nesesè
fatra nan tan yo kreye pwòp ou yo.

171
00:08:03,230 --> 00:08:05,490
>> Ou ka ekri yo menm senp
pou rezon tès.

172
00:08:05,490 --> 00:08:08,323
Men, lè ou aktyèlman yo ale nan
kòmanse achin done epi estoke li

173
00:08:08,323 --> 00:08:10,780
nan yon tab regle ou se
pwobableman ale nan vle

174
00:08:10,780 --> 00:08:14,580
sèvi ak kèk fonksyon ki te pwodwi
pou ou, ki egziste sou entènèt la.

175
00:08:14,580 --> 00:08:17,240
Si ou jis asire w ke
site sous ou yo.

176
00:08:17,240 --> 00:08:21,740
Gen nan pa gen rezon ki fè nou
plajye anyen isit la.

177
00:08:21,740 --> 00:08:25,370
>> Kominote a syans òdinatè se
definitivman ap grandi, ak reyèlman valè

178
00:08:25,370 --> 00:08:28,796
sous louvri, epi li vrèman enpòtan
site sous ou pou ke gen moun ki

179
00:08:28,796 --> 00:08:30,670
ka jwenn Wikimedia pou
travay la ke yo ap

180
00:08:30,670 --> 00:08:32,312
ap fè benefis nan kominote a.

181
00:08:32,312 --> 00:08:34,020
Se konsa, toujou gen sure--
epi li pa jis pou regle

182
00:08:34,020 --> 00:08:37,270
fonksyon, men jeneralman lè ou
itilize Kòd soti nan yon sous deyò,

183
00:08:37,270 --> 00:08:38,299
toujou site sous ou yo.

184
00:08:38,299 --> 00:08:43,500
Bay kredi nan moun nan ki moun ki fè
kèk nan travay la pou w pa gen.

185
00:08:43,500 --> 00:08:46,720
>> OK kidonk kite a revize sa a
regle tab pou yon dezyèm fwa.

186
00:08:46,720 --> 00:08:48,780
Sa a se kote nou te kite
koupe apre nou eleman

187
00:08:48,780 --> 00:08:53,300
Jan ak Pòl nan sa a tab regle.

188
00:08:53,300 --> 00:08:55,180
Ou wè yon pwoblèm isit la?

189
00:08:55,180 --> 00:08:58,410
Ou ta ka wè de.

190
00:08:58,410 --> 00:09:02,240
Men, an patikilye, ou
wè pwoblèm sa a posib?

191
00:09:02,240 --> 00:09:06,770
>> E si mwen Hash Ringo, epi li
sanble ke apre nou fin travay

192
00:09:06,770 --> 00:09:14,000
ke done a fonksyon an regle
Ringo tou pwodwi hashcode nan 6.

193
00:09:14,000 --> 00:09:16,810
Mwen te deja te resevwa done nan
hashcode-- kote etalaj 6.

194
00:09:16,810 --> 00:09:22,000
Se konsa, li la pwobableman pral fè yon ti jan
nan yon pwoblèm pou m 'koulye a, dwa?

195
00:09:22,000 --> 00:09:23,060
>> Nou rele sa a yon kolizyon.

196
00:09:23,060 --> 00:09:26,460
Apre sa, kolizyon an rive lè de
moso nan done kouri nan menm regle nan

197
00:09:26,460 --> 00:09:29,200
fonksyon sede menm hashcode la.

198
00:09:29,200 --> 00:09:32,850
Assume nou toujou vle jwenn tou de
moso nan done nan tablo a regle,

199
00:09:32,850 --> 00:09:36,330
otreman nou pa ta dwe kouri Ringo
abitrèman nan fonksyon an regle.

200
00:09:36,330 --> 00:09:40,870
Nou prezimableman vle jwenn
Ringo nan ki etalaj.

201
00:09:40,870 --> 00:09:46,070
>> Ki jan nou fè l 'menm si, si li
ak Pòl tou de sede hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Nou pa vle recouvrir Pòl,
nou vle Pòl yo dwe la tou.

203
00:09:49,520 --> 00:09:52,790
Se konsa, nou bezwen jwenn yon fason yo ka resevwa
eleman an tab la regle ki

204
00:09:52,790 --> 00:09:56,550
toujou prezève rapid nou an
ensèsyon ak rapid gade yo.

205
00:09:56,550 --> 00:10:01,350
Apre sa, yon fason fè fas ak li se
fè yon bagay yo rele lineyè sonde.

206
00:10:01,350 --> 00:10:04,170
>> Lè l sèvi avèk metòd sa a si nou gen yon
kolizyon, byen, sa nou fè?

207
00:10:04,170 --> 00:10:08,580
Oke nou pa ka mete l 'nan kote etalaj
6, oswa kèlkeswa sa hashcode te pwodwi,

208
00:10:08,580 --> 00:10:10,820
se pou yo mete l 'nan hashcode plis 1.

209
00:10:10,820 --> 00:10:13,670
Men, si sa a, se kite plen nan
mete l 'nan hashcode plis 2.

210
00:10:13,670 --> 00:10:17,420
Benefis la pou yo te sa a si li se
pa egzakteman ki kote nou panse se li ki,

211
00:10:17,420 --> 00:10:20,850
e nou gen yo kòmanse chèche,
petèt nou pa gen ale twò lwen.

212
00:10:20,850 --> 00:10:23,900
Petèt nou pa gen nan rechèch
tout eleman n nan tablo a regle.

213
00:10:23,900 --> 00:10:25,790
Petèt nou gen nan rechèch
yon koup la yo.

214
00:10:25,790 --> 00:10:30,680
>> Se konsa, nou ap toujou okipe nan direksyon pou
ke mwayèn ka ke yo te fèmen nan 1 vs

215
00:10:30,680 --> 00:10:34,280
fèmen nan n, se konsa petèt ki pral travay.

216
00:10:34,280 --> 00:10:38,010
Se konsa, kite a wè ki jan sa a
ta ka travay soti nan reyalite.

217
00:10:38,010 --> 00:10:41,460
Li kite yo wè si petèt nou kapab detekte
pwoblèm nan ki ta ka rive isit la.

218
00:10:41,460 --> 00:10:42,540
>> Se pou nou di nou Hash Bart.

219
00:10:42,540 --> 00:10:45,581
Se konsa, kounye a nou ap ale nan kouri nan yon seri nouvo
nan strings nan fonksyon an regle,

220
00:10:45,581 --> 00:10:48,460
epi nou kouri Bart a regle nan
fonksyon, nou jwenn hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Nou pran yon gade, nou wè 6 se
vid, se konsa nou ka mete Bart a.

222
00:10:52,100 --> 00:10:55,410
>> Koulye a, nou Hash Lisa ak ki
tou jenere hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Oke kounye a ke nou ap sèvi ak sa a
lineyè sonde metòd nou kòmanse nan 6,

224
00:10:58,330 --> 00:10:59,330
nou wè ke 6 se plen.

225
00:10:59,330 --> 00:11:00,990
Nou pa ka mete Lisa nan 6.

226
00:11:00,990 --> 00:11:02,090
Se konsa, kote nou ale?

227
00:11:02,090 --> 00:11:03,280
Ann ale nan 7.

228
00:11:03,280 --> 00:11:04,610
7 la vid, se konsa ke travay.

229
00:11:04,610 --> 00:11:06,510
Se konsa nou mete Lisa la.

230
00:11:06,510 --> 00:11:10,200
>> Koulye a, nou Hash Homer e nou jwenn 7.

231
00:11:10,200 --> 00:11:13,380
OK byen nou konnen ke plen 7 la
kounye a, se konsa nou pa ka mete Homer a.

232
00:11:13,380 --> 00:11:14,850
Se konsa, kite a ale nan 8.

233
00:11:14,850 --> 00:11:15,664
Se 8 disponib?

234
00:11:15,664 --> 00:11:18,330
Yeah, ak fèmen 8 nan a 7, Se konsa, si
nou gen yo kòmanse chèche nou ap

235
00:11:18,330 --> 00:11:20,020
pa ale nan gen yo ale twò lwen.

236
00:11:20,020 --> 00:11:22,860
Se konsa, kite a mete Homer nan 8.

237
00:11:22,860 --> 00:11:25,151
>> Koulye a, nou Hash Maggie ak
retounen 3, bonte remèsye

238
00:11:25,151 --> 00:11:26,650
nou ap kapab jis mete Maggie la.

239
00:11:26,650 --> 00:11:29,070
Nou pa gen fè nenpòt ki
sòt de sonde pou sa.

240
00:11:29,070 --> 00:11:32,000
Koulye a, nou Hash Marge, ak
Marge tou retounen 6.

241
00:11:32,000 --> 00:11:39,560
>> Oke 6 se plen, 7 se plen, 8 se plen,
9, tout dwa di Bondye mèsi, 9 a vid.

242
00:11:39,560 --> 00:11:41,600
Mwen ka mete Marge nan 9.

243
00:11:41,600 --> 00:11:45,280
Deja nou ka wè ke nou ap kòmanse
gen pwoblèm sa a kote kounye a nou ap

244
00:11:45,280 --> 00:11:48,780
kòmanse detire bagay kalite
a byen lwen soti nan kòd regle yo.

245
00:11:48,780 --> 00:11:52,960
Epi sa Theta nan 1, ki mwayèn
ka pou yo te tan konstan,

246
00:11:52,960 --> 00:11:56,560
se kòmanse yo ka resevwa yon ti kras more--
kòmanse gen tandans yon ti kras plis

247
00:11:56,560 --> 00:11:58,050
nan direksyon pou Theta nan n.

248
00:11:58,050 --> 00:12:01,270
Nou ap kòmanse pèdi ki
avantaj de tab regle.

249
00:12:01,270 --> 00:12:03,902
>> Sa a pwoblèm ke nou jis te wè
se yon bagay yo rele clustering.

250
00:12:03,902 --> 00:12:06,360
Ak sa ki nan vrèman move sou
clustering se ke yon fwa ou kounye a

251
00:12:06,360 --> 00:12:09,606
gen de eleman ki kòt a
bò li fè li menm plis chans,

252
00:12:09,606 --> 00:12:11,480
ou gen doub la
chans, ke w ap ale

253
00:12:11,480 --> 00:12:13,516
gen yon lòt kolizyon
ak sa gwoup,

254
00:12:13,516 --> 00:12:14,890
ak gwoup la ap grandi pa yon sèl.

255
00:12:14,890 --> 00:12:19,640
Men, ou pral kenbe k ap grandi ak ap grandi
chans ou a gen yon kolizyon.

256
00:12:19,640 --> 00:12:24,470
Ak evantyèlman li nan jis tankou move
yo pa Fouye done yo nan tout.

257
00:12:24,470 --> 00:12:27,590
>> Pwoblèm nan lòt menm si se nou
toujou, ak byen lwen tèlman jiska pwen sa a,

258
00:12:27,590 --> 00:12:30,336
nou te jis te sòt de
konprann sa yon tab regle se,

259
00:12:30,336 --> 00:12:31,960
nou toujou sèlman gen plas pou 10 strings.

260
00:12:31,960 --> 00:12:37,030
Si nou vle pou l kontinye Hash
sitwayen yo nan Springfield,

261
00:12:37,030 --> 00:12:38,790
nou ka sèlman jwenn 10 nan yo nan la.

262
00:12:38,790 --> 00:12:42,619
Men, si nou eseye epi ajoute yon 11yèm oswa 12yèm,
nou pa gen yon kote yo mete yo.

263
00:12:42,619 --> 00:12:45,660
Nou te kapab jis pou k ap vire alantou an
ti sèk ap eseye jwenn yon plas vid,

264
00:12:45,660 --> 00:12:49,000
epi nou petèt jwenn kole
nan yon bouk enfini.

265
00:12:49,000 --> 00:12:51,810
>> Se konsa, sa a sòt de confer lide nan
a yon bagay yo rele Anchènman.

266
00:12:51,810 --> 00:12:55,790
Lè sa a se kote nou ap ale nan pote
lye lis tounen nan imaj la.

267
00:12:55,790 --> 00:13:01,300
E si olye pou yo estoke jis
done yo tèt li nan etalaj la,

268
00:13:01,300 --> 00:13:04,471
chak eleman nan etalaj la te kapab
kenbe moso miltip nan done?

269
00:13:04,471 --> 00:13:05,970
Oke ki pa fè sans, dwa?

270
00:13:05,970 --> 00:13:09,280
Nou konnen ke yon etalaj ka sèlman
hold-- chak eleman nan yon etalaj

271
00:13:09,280 --> 00:13:12,930
ka sèlman kenbe yon sèl pyès
nan done a ki kalite done.

272
00:13:12,930 --> 00:13:16,750
>> Men, sa ki si sa kalite done
se yon lis lye, dwa?

273
00:13:16,750 --> 00:13:19,830
Se konsa, sa si chak
eleman nan etalaj la te

274
00:13:19,830 --> 00:13:22,790
yon konsèy nan tèt la nan yon lis lye?

275
00:13:22,790 --> 00:13:24,680
Lè sa a, nou te ka bati
moun lis lye

276
00:13:24,680 --> 00:13:27,120
ak grandi yo abitrèman,
paske lis lye pèmèt

277
00:13:27,120 --> 00:13:32,090
nou yo grandi ak retresi yon anpil plis
genyèn flexibilité pase yon etalaj fè.

278
00:13:32,090 --> 00:13:34,210
Se konsa, sa si nou kounye a itilize,
nou ogmante sa a, dwa?

279
00:13:34,210 --> 00:13:37,760
Nou kòmanse grandi chenn sa yo
soti nan lokal etalaj sa yo.

280
00:13:37,760 --> 00:13:40,740
>> Koulye a, nou ka anfòm yon enfini
kantite lajan pou done, oswa ou pa enfini,

281
00:13:40,740 --> 00:13:44,170
yon kantite lajan abitrè nan
done, nan tab regle nou an

282
00:13:44,170 --> 00:13:47,760
san yo pa janm kouri nan
pwoblèm nan nan kolizyon.

283
00:13:47,760 --> 00:13:50,740
Nou te tou elimine
clustering pa fè sa.

284
00:13:50,740 --> 00:13:54,380
Ak byen nou konnen ke lè nou Insert
nan yon lis lye, si ou sonje

285
00:13:54,380 --> 00:13:57,779
soti nan videyo nou an sou lis lye, separeman
lis lye e li bay lis doubl lye,

286
00:13:57,779 --> 00:13:59,070
li nan yon operasyon tan konstan.

287
00:13:59,070 --> 00:14:00,710
Nou jis ap ajoute nan devan an.

288
00:14:00,710 --> 00:14:04,400
>> Se pou gade leve, nou konnen byen
ki gade moute nan yon lis lye

289
00:14:04,400 --> 00:14:05,785
kapab yon pwoblèm, dwa?

290
00:14:05,785 --> 00:14:07,910
Nou dwe rechèch nan
li depi nan konmansman nan fen.

291
00:14:07,910 --> 00:14:10,460
Gen nan pa gen o aza
aksè nan yon lis lye.

292
00:14:10,460 --> 00:14:15,610
Men, si olye pou yo gen yon sèl lye
lis kote yon Passage ta dwe O nan n,

293
00:14:15,610 --> 00:14:19,590
nou genyen kounye a 10 lis lye,
oswa 1,000 lis lye,

294
00:14:19,590 --> 00:14:24,120
kounye a li nan O nan n divize pa 10,
oswa O nan n divize pa 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Epi pandan ke y nou te pale
teyorikman sou konpleksite

296
00:14:26,940 --> 00:14:30,061
nou respekte konstan, nan reyèl la
mond bagay sa yo aktyèlman gen pwoblèm,

297
00:14:30,061 --> 00:14:30,560
dwa?

298
00:14:30,560 --> 00:14:33,080
Nou aktyèlman ap remake
ki sa rive

299
00:14:33,080 --> 00:14:36,610
nan kouri 10 fwa pi vit,
oswa 1,000 fwa pi vit,

300
00:14:36,610 --> 00:14:41,570
paske nou ap distribye yon sèl lontan
chèn atravè 1,000 chenn pi piti.

301
00:14:41,570 --> 00:14:45,090
Se konsa, chak fwa nou gen nan rechèch
a youn nan moun ki chenn sa nou kapab

302
00:14:45,090 --> 00:14:50,290
inyore 999 chenn yo nou pa pran swen
sou, ak jis rechèch ke yon moun.

303
00:14:50,290 --> 00:14:53,220
>> Ki se sou mwayèn yo
gen 1,000 fwa pi kout.

304
00:14:53,220 --> 00:14:56,460
Se konsa, nou toujou yo sòt de
okipe nan direksyon pou sa a jou mwayèn ka

305
00:14:56,460 --> 00:15:01,610
pou yo te tan konstan, men
sèlman paske nou ap swe

306
00:15:01,610 --> 00:15:03,730
divize pa kèk gwo faktè konstan.

307
00:15:03,730 --> 00:15:05,804
Ann wè ki jan sa a ta ka
aktyèlman gade menm si.

308
00:15:05,804 --> 00:15:08,720
Se konsa, sa a te tab la regle nou te gen
anvan nou te deklare yon tab regle ki

309
00:15:08,720 --> 00:15:10,270
te kapab nan estoke 10 strings.

310
00:15:10,270 --> 00:15:11,728
Nou pa ap ale nan fè sa ankò.

311
00:15:11,728 --> 00:15:13,880
Nou deja konnen nan
limit nan metòd sa.

312
00:15:13,880 --> 00:15:20,170
Koulye a, tab regle nou an k ap pase yo dwe
yon etalaj de 10 nœuds, endikasyon

313
00:15:20,170 --> 00:15:22,120
bay chèf nan lis lye.

314
00:15:22,120 --> 00:15:23,830
>> E yo gen dwa kounye a li nan nil.

315
00:15:23,830 --> 00:15:26,170
Chak youn nan moun ki 10 endikasyon se nil.

316
00:15:26,170 --> 00:15:29,870
Pa gen anyen nan nou an
Hash tab kounye a.

317
00:15:29,870 --> 00:15:32,690
>> Koulye a, kite a kòmanse mete kèk
bagay sa yo nan sa a tab regle.

318
00:15:32,690 --> 00:15:35,440
Li kite yo wè ki jan metòd sa a se
ale nan benefisye nou yon ti kras.

319
00:15:35,440 --> 00:15:36,760
Se pou nou kounye a Hash Joey.

320
00:15:36,760 --> 00:15:40,210
Nou pral pral kouri fisèl la Joey a
yon fonksyon regle ak nou retounen 6.

321
00:15:40,210 --> 00:15:41,200
Oke sa nou fè kounye a?

322
00:15:41,200 --> 00:15:44,090
>> Oke kounye a ap travay ak lis lye,
nou pa ap travay ak ranje.

323
00:15:44,090 --> 00:15:45,881
Lè nou ap travay
ak lis lye nou

324
00:15:45,881 --> 00:15:49,790
konnen nou bezwen kòmanse dynamique
allocation espas ak bilding ti chenn.

325
00:15:49,790 --> 00:15:54,020
Sa a sòt de how-- sa yo se nwayo a
eleman nan bati yon lis lye.

326
00:15:54,020 --> 00:15:57,670
Se konsa nou dynamique
asiyen espas pou Joey,

327
00:15:57,670 --> 00:16:00,390
ak Lè sa a kite a ajoute l 'nan chèn lan.

328
00:16:00,390 --> 00:16:03,170
>> Se konsa, kounye a gade sa nou te fè.

329
00:16:03,170 --> 00:16:06,440
Lè nou Hash Joey nou te resevwa hashcode nan 6.

330
00:16:06,440 --> 00:16:11,790
Koulye a, konsèy la nan etalaj kote 6
lonje dwèt nan tèt la nan yon lis lye,

331
00:16:11,790 --> 00:16:14,900
e yo gen dwa kounye a li nan sèlman nan
eleman nan yon lis lye.

332
00:16:14,900 --> 00:16:18,350
Apre sa, ne la nan ki
lis lye se Joey.

333
00:16:18,350 --> 00:16:22,300
>> Se konsa, si nou bezwen yo gade jiska Joey
apre, nou jis Hash Joey ankò,

334
00:16:22,300 --> 00:16:26,300
nou jwenn 6 ankò paske nou an
fonksyon regle se detèrminist.

335
00:16:26,300 --> 00:16:30,400
Lè sa a, nou kòmanse nan plas tèt la
nan lis la lye pwente

336
00:16:30,400 --> 00:16:33,360
ak li avèk kote etalaj
6, epi nou ka repekte

337
00:16:33,360 --> 00:16:35,650
atravè ki ap eseye jwenn Joey.

338
00:16:35,650 --> 00:16:37,780
Men, si nou bati nou an
Hash tab efektivman,

339
00:16:37,780 --> 00:16:41,790
ak fonksyon regle nou an efektivman
yo distribye done byen,

340
00:16:41,790 --> 00:16:45,770
an mwayèn chak nan sa yo lye
lis nan chak kote etalaj

341
00:16:45,770 --> 00:16:50,110
yo pral 1/10 gwosè a nan si nou
jis te gen li kòm yon sèl gwo

342
00:16:50,110 --> 00:16:51,650
lye lis ak tout bagay nan li.

343
00:16:51,650 --> 00:16:55,670
>> Si nou distribye ke gwo lye
lis atravè 10 lis lye

344
00:16:55,670 --> 00:16:57,760
chak lis pral 1/10 gwosè a.

345
00:16:57,760 --> 00:17:01,432
Epi konsa, 10 fwa pi vit
fè rechèch nan.

346
00:17:01,432 --> 00:17:02,390
Se konsa nou fè sa ankò.

347
00:17:02,390 --> 00:17:04,290
Se pou nou kounye a Hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Li kite yo di Ross, lè nou fè sa
kòd a regle nou jwenn tounen se 2.

349
00:17:07,540 --> 00:17:10,630
Oke kounye a nou dynamique asiyen yon
nouvo ne, nou mete Ross nan ki ne,

350
00:17:10,630 --> 00:17:14,900
epi nou di kounye a kote etalaj
2, olye pou yo lonje dwèt nan nil,

351
00:17:14,900 --> 00:17:18,579
lonje dwèt nan tèt la nan yon lye
lis ki gen sèlman ne se Ross.

352
00:17:18,579 --> 00:17:22,660
Apre sa, nou ka fè sa yon lòt fwa ankò, nou
ka Hash Rachèl epi pou yo jwenn hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malok yon nouvo ne, mete Rachèl nan
ne la, ak di yon kote etalaj

354
00:17:25,490 --> 00:17:27,839
4 kounye a lonje dwèt nan tèt la
nan yon lis lye ki gen

355
00:17:27,839 --> 00:17:31,420
sèlman eleman k ap pase yo Rachèl.

356
00:17:31,420 --> 00:17:33,470
>> OK men ki sa k ap pase si
nou gen yon kolizyon?

357
00:17:33,470 --> 00:17:38,560
Ann wè ki jan nou okipe kolizyon
lè l sèvi avèk metòd la Anchènman ki apa a.

358
00:17:38,560 --> 00:17:39,800
Se pou yo Hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Nou jwenn hashcode nan 6.

360
00:17:41,094 --> 00:17:44,010
Nan egzanp anvan nou an, nou te jis
estoke strings yo nan etalaj la.

361
00:17:44,010 --> 00:17:45,980
Sa a te yon pwoblèm.

362
00:17:45,980 --> 00:17:48,444
>> Nou pa vle batr
Joey, epi nou te deja

363
00:17:48,444 --> 00:17:51,110
wè ke nou ka jwenn kèk clustering
pwoblèm si nou eseye ak etap

364
00:17:51,110 --> 00:17:52,202
nan ak pwofonde.

365
00:17:52,202 --> 00:17:54,660
Men, sa ki si nou jis kalite
trete sa a menm jan an, dwa?

366
00:17:54,660 --> 00:17:57,440
Li nan jis tankou ajoute yon eleman
nan tèt la nan yon lis lye.

367
00:17:57,440 --> 00:18:00,220
Se pou nou jis malok espas pou Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Nou pral di pwen pwochen konsèy Phoebe a
nan tèt la fin vye granmoun nan lis la lye,

369
00:18:04,764 --> 00:18:07,180
ak Lè sa a 6 jis lonje dwèt nan la
nouvo ki an tèt lis la lye.

370
00:18:07,180 --> 00:18:10,150
Epi, koulye a gade, nou te chanje Phoebe a.

371
00:18:10,150 --> 00:18:14,210
Nou kapab kounye a magazen de
eleman ak hashcode 6,

372
00:18:14,210 --> 00:18:17,170
epi nou pa gen okenn pwoblèm.

373
00:18:17,170 --> 00:18:20,147
>> Sa a bèl anpil tout
gen nan Anchènman.

374
00:18:20,147 --> 00:18:21,980
Apre sa, Anchènman se definitivman
metòd la sa a, se

375
00:18:21,980 --> 00:18:27,390
pral fè pi efikas pou ou si
w ap estoke done nan yon tab regle.

376
00:18:27,390 --> 00:18:30,890
Men, sa a konbinezon de
ranje e li bay lis lye

377
00:18:30,890 --> 00:18:36,080
ansanm yo fòme yon tab regle reyèlman
dramatikman amelyore kapasite w

378
00:18:36,080 --> 00:18:40,550
nan magazen gwo kantite done, ak
trè byen vit epi avèk efikasite rechèch

379
00:18:40,550 --> 00:18:41,630
nan ki done.

380
00:18:41,630 --> 00:18:44,150
>> Genyen toujou yon sèl plis
done estrikti yo deyò

381
00:18:44,150 --> 00:18:48,700
ki ta ka menm gen yon ti jan
pi bon an tèm de garanti

382
00:18:48,700 --> 00:18:51,920
ki ensèsyon nou an, sipresyon, ak
gade moute tan sont menm pi vit.

383
00:18:51,920 --> 00:18:55,630
Epitou, n ap wè ke nan yon videyo sou ap eseye.

384
00:18:55,630 --> 00:18:58,930
Mwen se Doug Lloyd, sa a se CS50.

385
00:18:58,930 --> 00:19:00,214