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

2
00:00:00,500 --> 00:00:01,900
[MUZIKO Ludante]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: De nun vi
scias multon pri arrays,

5
00:00:09,150 --> 00:00:11,610
kaj vi scias tre pri ligitaj listoj.

6
00:00:11,610 --> 00:00:13,650
Havas ni diskuti la
avantaĝoj kaj contras, ni

7
00:00:13,650 --> 00:00:16,620
diskutis ke ligitaj listoj
povas pligrandiĝi kaj pli malgranda,

8
00:00:16,620 --> 00:00:18,630
sed levu pli grandeco.

9
00:00:18,630 --> 00:00:22,359
Tabeloj estas multe pli simpla al
uzi, sed ili estas limiga dum

10
00:00:22,359 --> 00:00:24,900
kiel ni devas agordi la grandecon de
la tabelo ĉe la komenco

11
00:00:24,900 --> 00:00:26,910
kaj poste ni gluata kun ĝi.

12
00:00:26,910 --> 00:00:30,470
>> Sed tio, ni preskaux
elĉerpita ĉiuj niaj temoj

13
00:00:30,470 --> 00:00:33,040
pri ligitaj listoj kaj tabeloj.

14
00:00:33,040 --> 00:00:34,950
Aŭ ni havas?

15
00:00:34,950 --> 00:00:37,720
Eble ni povas fari ion
eĉ pli krea.

16
00:00:37,720 --> 00:00:40,950
Kaj tiaj pruntedonas
la ideo de hash tablo.

17
00:00:40,950 --> 00:00:46,680
>> Do en hash tablo ni tuj provos
kombini tabelo kun ligillisto.

18
00:00:46,680 --> 00:00:49,520
Ni tuj prenos la avantaĝojn
de la tabelo, kiel hazarda aliro,

19
00:00:49,520 --> 00:00:53,510
povi ĝuste iri al tabelo
elemento 4 aŭ tabelo elemento 8

20
00:00:53,510 --> 00:00:55,560
sen devi persisti trans.

21
00:00:55,560 --> 00:00:57,260
Tio estas sufiĉe rapida, dekstra?

22
00:00:57,260 --> 00:01:00,714
>> Sed ni ankaŭ deziras havi niajn datumojn
strukturo povi kreski kaj ŝrumpi.

23
00:01:00,714 --> 00:01:02,630
Ni ne bezonas, ni ne
volas esti restriktita.

24
00:01:02,630 --> 00:01:04,588
Kaj ni volas povi
aldoni kaj forigi aferojn

25
00:01:04,588 --> 00:01:08,430
tre facile, kaj se vi memoras,
estas tre kompleksa kun tabelo.

26
00:01:08,430 --> 00:01:11,650
Kaj ni povas nomi ĉi
nova afero hash tablo.

27
00:01:11,650 --> 00:01:15,190
>> Kaj se implementado korekte,
ni ia prenante

28
00:01:15,190 --> 00:01:18,150
la avantaĝojn de ambaŭ datumoj
strukturoj vi jam vidis,

29
00:01:18,150 --> 00:01:19,880
arrays kaj ligitaj listoj.

30
00:01:19,880 --> 00:01:23,070
Inserción povas komenci
inklinas al theta de 1.

31
00:01:23,070 --> 00:01:26,207
Theta ni ne vere diskutis,
sed theta estas simple la ordinara kazo,

32
00:01:26,207 --> 00:01:27,540
kio efektive okazos.

33
00:01:27,540 --> 00:01:29,680
Vi ne ĉiam tuj
havi la plej malbona kazo scenaro,

34
00:01:29,680 --> 00:01:32,555
kaj vi ne ĉiam tuj devas
la plej bona kazo scenaro, do kio estas

35
00:01:32,555 --> 00:01:33,900
la averaĝa scenaro?

36
00:01:33,900 --> 00:01:36,500
>> Nu mezumo inserción
en hash tablo

37
00:01:36,500 --> 00:01:39,370
povas komenci alproksimigi al konstanta tempo.

38
00:01:39,370 --> 00:01:41,570
Kaj forigoj povas akiri
fermi al konstanta tempo.

39
00:01:41,570 --> 00:01:44,440
Kaj lookup povas akiri
fermi al konstanta tempo.

40
00:01:44,440 --> 00:01:48,600
That's-- ni ne havas datumojn
strukturo tamen kiu povas tion fari,

41
00:01:48,600 --> 00:01:51,180
kaj tiel ĉi jam sonas
kiel bela granda afero.

42
00:01:51,180 --> 00:01:57,010
Ni vere mildigis la
malavantaĝoj de ĉiu en lia propra.

43
00:01:57,010 --> 00:01:59,160
>> Por ricevi ĉi agado
ĝisdatigi kvankam ni

44
00:01:59,160 --> 00:02:03,580
bezonas rekonsideri kiel ni aldonu
datumojn en la strukturo.

45
00:02:03,580 --> 00:02:07,380
Specife ni deziras la
datumoj al diri nin

46
00:02:07,380 --> 00:02:09,725
kie devus iri en la strukturo.

47
00:02:09,725 --> 00:02:12,850
Kaj se ni tiam devas vidi se ĝi estas en
la strukturon, se ni devas trovi ĝin,

48
00:02:12,850 --> 00:02:16,610
Ni volas rigardi la datumoj
denove kaj povos efike,

49
00:02:16,610 --> 00:02:18,910
uzante la datumoj, hazarde aliras.

50
00:02:18,910 --> 00:02:20,700
Nur rigardante la
datumojn ni devus havi

51
00:02:20,700 --> 00:02:25,890
ideon de kie ekzakte ni estas
tuj trovi gxin en la hash tablo.

52
00:02:25,890 --> 00:02:28,770
>> Nun la malavantaĝo de hash
tablo estas ke ili estas vere

53
00:02:28,770 --> 00:02:31,770
sufiĉe malbone ĉe ordigante aŭ ordigado de datumoj.

54
00:02:31,770 --> 00:02:34,970
Kaj fakte, se vi komencas
uzi ilin ordigi aŭ varo

55
00:02:34,970 --> 00:02:37,990
datumoj vi perdas ĉiuj la
avantaĝojn vi antaŭe

56
00:02:37,990 --> 00:02:40,710
devis en terminoj de inserción kaj forigo.

57
00:02:40,710 --> 00:02:44,060
La tempo iĝas pli proksime al
theta de n, kaj ni esence

58
00:02:44,060 --> 00:02:45,530
regresis en ligillisto.

59
00:02:45,530 --> 00:02:48,850
Kaj tiel ni nur volas uzi hash
tabloj se ni ne zorgas pri

60
00:02:48,850 --> 00:02:51,490
ĉu datumoj estas ordo.

61
00:02:51,490 --> 00:02:54,290
Por la kunteksto en kiu
vi uzos ilin en CS50

62
00:02:54,290 --> 00:02:58,900
vi probable ne zorgas
ke la datumoj estas ordigitaj.

63
00:02:58,900 --> 00:03:03,170
>> Do hash tablo estas kombinaĵo
el du distingaj pecoj

64
00:03:03,170 --> 00:03:04,980
kun kiu ni estas konataj.

65
00:03:04,980 --> 00:03:07,930
La unua estas funkcio, kiun
ni kutime nomas hash funkcio.

66
00:03:07,930 --> 00:03:11,760
Kaj ke hash funkcio tuj
reveni iu ne-negativa entjero, kiu

67
00:03:11,760 --> 00:03:14,870
ni kutime nomas hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
La dua peco estas tabelo, kiu estas
kapablaj de stoki datumojn de la tipo ni

69
00:03:20,230 --> 00:03:22,190
volas meti en la datumstrukturo.

70
00:03:22,190 --> 00:03:24,310
Ni teni ekstere sur la
ligillisto elementon nuntempe

71
00:03:24,310 --> 00:03:27,810
kaj komencu kun la fundamentojn de
hash tablo akiri vian kapon ĉirkaŭe,

72
00:03:27,810 --> 00:03:30,210
kaj tiam ni eble blovi
via menso iomete kiam ni

73
00:03:30,210 --> 00:03:32,920
kombini arrays kaj karmo listojn kune.

74
00:03:32,920 --> 00:03:35,590
>> La baza ideo kvankam
Estas ni preni iujn datumojn.

75
00:03:35,590 --> 00:03:37,860
Ni kuras tra kiuj datumoj
la hash funkcio.

76
00:03:37,860 --> 00:03:41,980
Kaj tial la datumoj procesas
kaj ĝi kraĉas el kelkaj, OK?

77
00:03:41,980 --> 00:03:44,890
Kaj tiam kun tiu nombro
ni nur stoki la datumojn

78
00:03:44,890 --> 00:03:48,930
ni volas konservi en la
tabelo ĉe tiu loko.

79
00:03:48,930 --> 00:03:53,990
Do por ekzemplo havas eble
tiu hash tablo de kordoj.

80
00:03:53,990 --> 00:03:57,350
Oni alvenis 10 elementoj en ĝi, do
ni povas persvadi 10 kordoj en ĝi.

81
00:03:57,350 --> 00:03:59,320
>> Supozu ke ni volas hash Johano.

82
00:03:59,320 --> 00:04:02,979
Do Johanon la datumoj ni volas enmeti
en tiu hash tablo ie.

83
00:04:02,979 --> 00:04:03,770
Kie ni metis ĝin?

84
00:04:03,770 --> 00:04:05,728
Nu tipe kun
tabelo ĝis nun ni probable

85
00:04:05,728 --> 00:04:07,610
metus ĝin en tabelo ĉelo 0.

86
00:04:07,610 --> 00:04:09,960
Sed nun ni havas tiun novan hash funkcio.

87
00:04:09,960 --> 00:04:13,180
>> Kaj ni diras, ke ni kuras Johano
tra ĉi hash funkcio

88
00:04:13,180 --> 00:04:15,417
kaj ĝin kraĉas el 4.

89
00:04:15,417 --> 00:04:17,500
Nu tio estas kie ni estas
tuj volas Johanon.

90
00:04:17,500 --> 00:04:22,050
Ni volas meti John vicojn location
4, ĉar se ni hash John again--

91
00:04:22,050 --> 00:04:23,810
diru poste ni
volas serĉi kaj vidi

92
00:04:23,810 --> 00:04:26,960
se John ekzistas en tiu hash
table-- ĉiuj ni devas fari

93
00:04:26,960 --> 00:04:30,310
kuras tra la sama hash
funkcion, la numeron 4 el,

94
00:04:30,310 --> 00:04:33,929
kaj povos trovi Johano
tuj en nia datumstrukturo.

95
00:04:33,929 --> 00:04:34,720
Tio estas sufiĉe bona.

96
00:04:34,720 --> 00:04:36,928
>> Supozu ke ni nun faras tiun
denove, ni volas hash Paul.

97
00:04:36,928 --> 00:04:39,446
Ni volas aldoni Paul
en tiu hash tablo.

98
00:04:39,446 --> 00:04:42,070
Diru ke ĉi tiu tempo ni kuras
Paŭlo tra la krada funkcio,

99
00:04:42,070 --> 00:04:44,600
la hashcode kiu generas estas 6.

100
00:04:44,600 --> 00:04:47,340
Nu nun ni povas meti Paul
en la tabelo situon 6.

101
00:04:47,340 --> 00:04:50,040
Kaj se ni bezonas serĉi ĉu
Paul estas en ĉi hash tablo,

102
00:04:50,040 --> 00:04:53,900
ĉiuj ni devas fari estas kuri Paul
tra la krada funkcio denove

103
00:04:53,900 --> 00:04:55,830
kaj ni tuj ricevas 6 reeliri.

104
00:04:55,830 --> 00:04:57,590
>> Kaj tiam ni simple rigardi
ĉe tabelo situon 6.

105
00:04:57,590 --> 00:04:58,910
Paul tie?

106
00:04:58,910 --> 00:05:00,160
Se jes, li estas en la hash tablo.

107
00:05:00,160 --> 00:05:01,875
Paul ne?

108
00:05:01,875 --> 00:05:03,000
Li ne estas en la hash tablo.

109
00:05:03,000 --> 00:05:05,720
Ĝi estas bela simpla.

110
00:05:05,720 --> 00:05:07,770
>> Nun kiel vi difinas hash funkcio?

111
00:05:07,770 --> 00:05:11,460
Bone tie estas vere nenia limo al la
nombro de eblaj kradaj funkcioj.

112
00:05:11,460 --> 00:05:14,350
Fakte ekzistas kelkaj vere,
vere bona sur la interreto.

113
00:05:14,350 --> 00:05:17,560
Ekzistas kelkaj vere,
vere malbonaj sur la interreto.

114
00:05:17,560 --> 00:05:21,080
Estas ankaŭ sufiĉe facila
skribi malbongusta.

115
00:05:21,080 --> 00:05:23,760
>> Do kio konsistigas bonan
hash funkcio, ĉu ne?

116
00:05:23,760 --> 00:05:27,280
Nu bona hash funkcio devus
uzi nur la datumoj estanta hashed,

117
00:05:27,280 --> 00:05:29,420
kaj ĉiujn la datumoj estanta hashed.

118
00:05:29,420 --> 00:05:32,500
Do ni ne volas uzi ion ajn
ni ne korpigi ion

119
00:05:32,500 --> 00:05:35,560
alia krom la datumoj.

120
00:05:35,560 --> 00:05:37,080
Kaj ni volas uzi ĉiujn de la datumo.

121
00:05:37,080 --> 00:05:39,830
Ni ne volas simple uzi peco
de ĝi, ni volas uzi ĉiujn de ĝi.

122
00:05:39,830 --> 00:05:41,710
Hash funkcio devus
ankaŭ determinisma.

123
00:05:41,710 --> 00:05:42,550
Kion tio signifas?

124
00:05:42,550 --> 00:05:46,200
Nu signifas ke ĉiufoje ni
pasi la ĝusta sama peco de datumoj

125
00:05:46,200 --> 00:05:50,040
en la hash funkcio ni ĉiam
atingi la saman hashcode eksteren.

126
00:05:50,040 --> 00:05:52,870
Se mi pasas Johanon en la
hash funkcio mi liberiĝos el 4.

127
00:05:52,870 --> 00:05:56,110
Mi devus povi fari ke 10,000
fojojn kaj mi ĉiam ricevas 4.

128
00:05:56,110 --> 00:06:00,810
Do neniu hazardaj nombroj efike
povas esti implikitaj en nia hash tables--

129
00:06:00,810 --> 00:06:02,750
en nia kradaj funkcioj.

130
00:06:02,750 --> 00:06:05,750
>> Hash funkcio devus ankaŭ
unuforme distribui datumojn.

131
00:06:05,750 --> 00:06:09,700
Se ĉiufoje kiam vi kuros datumoj tra la
hash funkcio vi ricevas la hashcode 0,

132
00:06:09,700 --> 00:06:11,200
ke estas probable ne tiom granda, ĉu ne?

133
00:06:11,200 --> 00:06:14,600
Vi probable volas grandaj
gamon de hash kodojn.

134
00:06:14,600 --> 00:06:17,190
Ankaŭ aĵoj povas disvastigi
el ĉie en la tablo.

135
00:06:17,190 --> 00:06:23,210
Kaj ankaŭ ĝi estus granda se vere
similajn datumojn, kiel John kaj Jonatan,

136
00:06:23,210 --> 00:06:26,320
eble estis etendantaj levar
malsamaj lokoj en la hash tablo.

137
00:06:26,320 --> 00:06:28,750
Tio estus bela avantaĝon.

138
00:06:28,750 --> 00:06:31,250
>> Jen ekzemplo de hash funkcio.

139
00:06:31,250 --> 00:06:33,150
Mi skribis ĉi unu supren antaŭe.

140
00:06:33,150 --> 00:06:35,047
Ĝi ne estas aparte
bona hash funkcio

141
00:06:35,047 --> 00:06:37,380
por kialoj kiuj ne vere
elporti internigi nun.

142
00:06:37,380 --> 00:06:41,040
Sed ĉu vi vidas kio okazas ĉi tie?

143
00:06:41,040 --> 00:06:44,420
Ŝajnas kiel ni deklari variablon
nomata sumo kaj fiksante ĝin egala al 0.

144
00:06:44,420 --> 00:06:50,010
Kaj tiam ŝajne mi faras ion
tiel longe kiel strstr [j] estas ne egala

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

146
00:06:52,490 --> 00:06:54,870
Kion mi faris?

147
00:06:54,870 --> 00:06:57,440
>> Tiu estas esence nur alia
formo de apliko [? strl?]

148
00:06:57,440 --> 00:06:59,773
kaj detektante kiam vi havas
atingis la finon de la ŝnuro.

149
00:06:59,773 --> 00:07:02,480
Do mi ne devas reale
kalkuli la longecon de la kordo,

150
00:07:02,480 --> 00:07:05,640
Mi nur uzas kiam mi batis la
backslash 0 karaktero Mi scias

151
00:07:05,640 --> 00:07:07,185
Mi jam atingis la finon de la ŝnuro.

152
00:07:07,185 --> 00:07:09,560
Kaj tiam mi tuj konservi
ripetanta tra tiu ŝnuro,

153
00:07:09,560 --> 00:07:15,310
aldonante strstr [j] al sumo, kaj tiam ĉe la
fino de la tago tuj revenos sumo mod

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

155
00:07:16,200 --> 00:07:18,700
>> Esence ĉiuj ĉi hash
funkcio faras estas adicio

156
00:07:18,700 --> 00:07:23,450
ĉiuj ASCII valoroj de
mian ŝnuron, kaj tiam estas

157
00:07:23,450 --> 00:07:26,390
reveninte iuj hashcode
modded per HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Estas probable la grandeco
de mia tabelo, dekstra?

159
00:07:29,790 --> 00:07:33,160
Mi ne volas esti akiranta hash
kodoj se miaj tabelo estas de amplekso 10,

160
00:07:33,160 --> 00:07:35,712
Mi ne volas esti akiranta
eksteren hash kodoj 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, mi ne povas meti aferojn en
tiuj lokoj de la tabelo,

162
00:07:38,690 --> 00:07:39,790
ke estus kontraŭleĝa.

163
00:07:39,790 --> 00:07:42,130
Mi suferas segmentación kulpo.

164
00:07:42,130 --> 00:07:45,230
>> Nun tie estas alia rapida flanken.

165
00:07:45,230 --> 00:07:48,470
Ĝenerale vi probable ne tuj
volas skribi viajn proprajn kradaj funkcioj.

166
00:07:48,470 --> 00:07:50,997
Estas efektive iom de
arto, ne scienco.

167
00:07:50,997 --> 00:07:52,580
Kaj ekzistas multe kiu iras tra ili.

168
00:07:52,580 --> 00:07:55,288
La interreto, kiel mi diris, estas kompleta
de vere bona kradaj funkcioj,

169
00:07:55,288 --> 00:07:58,470
kaj vi devus uzi la interreton
trovi kradaj funkcioj ĉar estas vere

170
00:07:58,470 --> 00:08:03,230
nur speco de nenecesa
tempoperdo krei vian propran.

171
00:08:03,230 --> 00:08:05,490
>> Vi povas skribi simplaj
por testado.

172
00:08:05,490 --> 00:08:08,323
Sed kiam vi vere intencas
komenci hashing datumoj kaj stokante ĝin

173
00:08:08,323 --> 00:08:10,780
en hash tablo vi estas
probable tuj volas

174
00:08:10,780 --> 00:08:14,580
uzi iu funkcio kiu generis
por vi, ke ekzistas sur la interreto.

175
00:08:14,580 --> 00:08:17,240
Se vi ĵus certi
por citi viajn fontojn.

176
00:08:17,240 --> 00:08:21,740
Ekzistas neniu kialo por
plagiar nenio ĉi tie.

177
00:08:21,740 --> 00:08:25,370
>> La komputiko komunumo estas
sendube kreskas, kaj vere valoroj

178
00:08:25,370 --> 00:08:28,796
malfermita, kaj ĝi estas vere grava
por citi viajn fontojn por ke homoj

179
00:08:28,796 --> 00:08:30,670
povas akiri atribuu
laboro, kiun ili estas

180
00:08:30,670 --> 00:08:32,312
faras al la profito de la komunumo.

181
00:08:32,312 --> 00:08:34,020
Do ĉiam sure--
kaj ne nur por hash

182
00:08:34,020 --> 00:08:37,270
funkcioj, sed ĝenerale kiam vi
uzi kodon de ekstera fonto,

183
00:08:37,270 --> 00:08:38,299
ĉiam citas vian fonton.

184
00:08:38,299 --> 00:08:43,500
Doni krediton al la persono kiu faris
iuj de la laboro do vi ne devas.

185
00:08:43,500 --> 00:08:46,720
>> OK do ni reviziti ĉi
hash tablo por dua.

186
00:08:46,720 --> 00:08:48,780
Tie estas kie ni maldekstre
for post ni insertita

187
00:08:48,780 --> 00:08:53,300
John kaj Paul en tiu hash tablo.

188
00:08:53,300 --> 00:08:55,180
Ĉu vi vidas problemon tie?

189
00:08:55,180 --> 00:08:58,410
Vi povus vidi du.

190
00:08:58,410 --> 00:09:02,240
Sed precipe, ĉu vi
vidu tiun eblan problemon?

191
00:09:02,240 --> 00:09:06,770
>> Kio se mi hash Ringo, kaj ĝi
Rezultas ke post prilaborado

192
00:09:06,770 --> 00:09:14,000
ke datumoj tra la krada funkcio
Ringo ankaŭ generis la hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Mi jam akiris datumojn ĉe
hashcode-- tabelo situon 6.

194
00:09:16,810 --> 00:09:22,000
Do ĝi estas probable tuj estos iom
de problemo por mi nun, ĉu ne?

195
00:09:22,000 --> 00:09:23,060
>> Ni nomas tiun kolizion.

196
00:09:23,060 --> 00:09:26,460
Kaj la kolizio okazas kiam du
datumerojn kuri tra la sama hash

197
00:09:26,460 --> 00:09:29,200
funkcio cedas la samaj hashcode.

198
00:09:29,200 --> 00:09:32,850
Supozeble ni ankoraŭ volas akiri ambaŭ
datumerojn en la hash tablo,

199
00:09:32,850 --> 00:09:36,330
alie ni ne estus kuranta Ringo
arbitre tra la krada funkcio.

200
00:09:36,330 --> 00:09:40,870
Ni supozeble volas ricevi
Ringo en tiun tabelo.

201
00:09:40,870 --> 00:09:46,070
>> Kiel ni faru ĝin kvankam, se li
kaj Paul ambaŭ rendimento hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Ni ne volas anstataŭigi Paul,
ni volas Paul esti tie ankaŭ.

203
00:09:49,520 --> 00:09:52,790
Do ni devas trovi manieron ricevi
elementoj en la hash tablo ke

204
00:09:52,790 --> 00:09:56,550
ankoraŭ konservas nian rapida
inserción kaj rapidan rigardon supren.

205
00:09:56,550 --> 00:10:01,350
Kaj unu maniero trakti ĝin estas
fari iu nomita lineara tuŝoprobado.

206
00:10:01,350 --> 00:10:04,170
>> Uzante tiun metodon, se ni havas
kolizio, nu, kion ni faru?

207
00:10:04,170 --> 00:10:08,580
Bone ni ne povas meti lin en tabelo location
6, aŭ kion ajn hashcode estis generita,

208
00:10:08,580 --> 00:10:10,820
ni metis lin ĉe hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
Kaj se tio estas plena let estas
metis lin en hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
La profito de tiu estaĵo se li estas
ne ĝuste kie ni kredas ke li estas,

211
00:10:17,420 --> 00:10:20,850
kaj ni devos ekserĉi,
eble ni ne devas iri tro ege.

212
00:10:20,850 --> 00:10:23,900
Eble ni ne devas serĉi
ĉiuj n elementoj de la hash tablo.

213
00:10:23,900 --> 00:10:25,790
Eble ni devas serĉi
paro de ili.

214
00:10:25,790 --> 00:10:30,680
>> Kaj tial ni ankoraŭ strebanta al
ke mezumo kazo estanta proksime al 1 vs

215
00:10:30,680 --> 00:10:34,280
proksime al n, do eble tio devos labori.

216
00:10:34,280 --> 00:10:38,010
Do ni vidu kiel ĉi
povus eliri en realo.

217
00:10:38,010 --> 00:10:41,460
Kaj ni vidu, se eble ni povas detekti
la problemo kiu povus okazi tie.

218
00:10:41,460 --> 00:10:42,540
>> Supozu ke ni hash Bart.

219
00:10:42,540 --> 00:10:45,581
Do nun ni tuj kuri nova aro
de kordoj tra la krada funkcio,

220
00:10:45,581 --> 00:10:48,460
kaj ni kuras Bart tra la hash
funkcio, ni preni hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Ni rigardu, ni vidas 6 estas
malplena, do ni povas meti Bart tie.

222
00:10:52,100 --> 00:10:55,410
>> Nun ni hash Lisa kaj ke
ankaŭ generas hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Nu nun ke ni uzas tiun
lineara tuŝoprobado metodo ni starti je 6,

224
00:10:58,330 --> 00:10:59,330
ni vidas ke 6 estas plena.

225
00:10:59,330 --> 00:11:00,990
Ni ne povas meti Lisa en 6.

226
00:11:00,990 --> 00:11:02,090
Do kie ni iras?

227
00:11:02,090 --> 00:11:03,280
Ni iru al 7.

228
00:11:03,280 --> 00:11:04,610
7 La malplena, por ke funkcias.

229
00:11:04,610 --> 00:11:06,510
Do ni metu Lisa tie.

230
00:11:06,510 --> 00:11:10,200
>> Nun ni hash Homer kaj ni preni 7.

231
00:11:10,200 --> 00:11:13,380
OK bone ni scias ke 7 plenas
nun, tial ni ne povas meti Homero tie.

232
00:11:13,380 --> 00:11:14,850
Do ni iru al 8.

233
00:11:14,850 --> 00:11:15,664
Estas 8 havebla?

234
00:11:15,664 --> 00:11:18,330
Jes, kaj 8 proksimaj al 7, do se
ni devos ekserĉi ni estas

235
00:11:18,330 --> 00:11:20,020
ne tuj devas iri tro ege.

236
00:11:20,020 --> 00:11:22,860
Kaj do ni metis Homero ĉe 8.

237
00:11:22,860 --> 00:11:25,151
>> Nun ni hash Maggie kaj
Revenas 3, dank'al Dio

238
00:11:25,151 --> 00:11:26,650
ni povas nur meti Maggie tie.

239
00:11:26,650 --> 00:11:29,070
Ni ne devas fari ajnan
ia tuŝoprobado por tio.

240
00:11:29,070 --> 00:11:32,000
Nun ni hash Marge, kaj
Marge ankaŭ revenas 6.

241
00:11:32,000 --> 00:11:39,560
>> Nu 6 estas plena, 7 estas plena, 8 estas plena,
9, tute certe dankas Dion, 9 estas malplena.

242
00:11:39,560 --> 00:11:41,600
Mi povas meti Marge ĉe 9.

243
00:11:41,600 --> 00:11:45,280
Jam ni povas vidi ke ni startanta
havi tiun problemon kie nun ni estas

244
00:11:45,280 --> 00:11:48,780
komencante por streĉi aferoj speco
de fore de ilia hash kodojn.

245
00:11:48,780 --> 00:11:52,960
Kaj ke theta de 1, ke mezumo
kazo de esti konstanta tempo,

246
00:11:52,960 --> 00:11:56,560
estas komencanta akiri malgrandan more--
komencantaj emas iom pli

247
00:11:56,560 --> 00:11:58,050
al theta de n.

248
00:11:58,050 --> 00:12:01,270
Ni komencas perdi tiun
avantaĝon de hash tabloj.

249
00:12:01,270 --> 00:12:03,902
>> Tiu problemo kiun ni ĵus vidis
Estas io nomita clustering.

250
00:12:03,902 --> 00:12:06,360
Kaj kio estas vere malbona pri
clustering estas ke unufoje vi nun

251
00:12:06,360 --> 00:12:09,606
havas du elementojn kiuj flank
bandola faras ankoraŭ pli verŝajna,

252
00:12:09,606 --> 00:12:11,480
vi havas duoblan
hazardo, ke vi tuj

253
00:12:11,480 --> 00:12:13,516
havi alian kolizion
kun tiu areto,

254
00:12:13,516 --> 00:12:14,890
kaj la areto kreskos post unu.

255
00:12:14,890 --> 00:12:19,640
Kaj Vi pli kaj kreskanta
via verŝajneco de havado de kolizio.

256
00:12:19,640 --> 00:12:24,470
Kaj fine ĝi estas egale malbona
kiel ne ordigado la datumoj ajn.

257
00:12:24,470 --> 00:12:27,590
>> La alia problemo tamen estas ni
ankoraŭ, kaj ĝis nun ĝis tiu punkto,

258
00:12:27,590 --> 00:12:30,336
ni ĵus estis ia
komprenante kio hash tablo estas,

259
00:12:30,336 --> 00:12:31,960
ni ankoraŭ nur havas spacon por 10 kordoj.

260
00:12:31,960 --> 00:12:37,030
Se ni volas ri hash
la civitanoj de Springfield,

261
00:12:37,030 --> 00:12:38,790
ni povas nur akiri 10 el ili en tie.

262
00:12:38,790 --> 00:12:42,619
Kaj se ni provu kaj aldoni 11a aŭ 12a,
ni ne havas lokon por meti ilin.

263
00:12:42,619 --> 00:12:45,660
Ni povus simple esti turnadanta ĉirkaŭ en
rondoj provanta trovi malplenan lokon,

264
00:12:45,660 --> 00:12:49,000
kaj ni eble akiri senmoviĝita
en senfina buklo.

265
00:12:49,000 --> 00:12:51,810
>> Do tiu speco de pruntedonas al la ideo
de iu nomita ĉenante.

266
00:12:51,810 --> 00:12:55,790
Kaj tio estas kie ni estas iranta alporti
ligitaj listoj reen en la bildon.

267
00:12:55,790 --> 00:13:01,300
Kio se anstataŭ stoki nur
la datumoj en la tabelo,

268
00:13:01,300 --> 00:13:04,471
ĉiu ero de la tabelo povis
teni multnombraj pecoj de datumoj?

269
00:13:04,471 --> 00:13:05,970
Nu tio ne havas sencon, ĉu ne?

270
00:13:05,970 --> 00:13:09,280
Ni scias ke tabelo povas nur
hold-- ĉiu elemento de tabelo

271
00:13:09,280 --> 00:13:12,930
povas nur teni unu peco
de datumoj de tiu datumtipo.

272
00:13:12,930 --> 00:13:16,750
>> Sed kio se tiu datumtipo
estas ligillisto, dekstra?

273
00:13:16,750 --> 00:13:19,830
Do kio se ĉiu
elemento de la tabelo estis

274
00:13:19,830 --> 00:13:22,790
sagon al la kapo de ligitaj listo?

275
00:13:22,790 --> 00:13:24,680
Kaj tiam ni povus konstrui
tiuj ligitaj lertaj

276
00:13:24,680 --> 00:13:27,120
kaj kreski ilin arbitre,
ĉar ligitaj listoj permesi

277
00:13:27,120 --> 00:13:32,090
nin kreski kaj ŝrumpi multe pli
flekse ol tabelo faras.

278
00:13:32,090 --> 00:13:34,210
Do kio se ni nun uzas,
ni ekspluati tion, ĉu ne?

279
00:13:34,210 --> 00:13:37,760
Ni komencas kreski tiuj ĉenoj
el tiuj tabelo lokoj.

280
00:13:37,760 --> 00:13:40,740
>> Nun ni povas persvadi malfinia
kvanto de datumoj, aŭ ne senfina,

281
00:13:40,740 --> 00:13:44,170
arbitran kvanton de
datumoj, en nia hash tablo

282
00:13:44,170 --> 00:13:47,760
sen iam alkuri
la problemo de kolizio.

283
00:13:47,760 --> 00:13:50,740
Ni ankaŭ eliminita
clustering farante tion.

284
00:13:50,740 --> 00:13:54,380
Kaj bone ni scias ke kiam ni enŝovu
en ligillisto, se vi memoras

285
00:13:54,380 --> 00:13:57,779
de nia vídeo en ligitaj listoj, unuope
ligitaj listoj kaj duoble ligitaj listoj,

286
00:13:57,779 --> 00:13:59,070
ĝi estas konstanta tempo operacio.

287
00:13:59,070 --> 00:14:00,710
Ni simple aldonante al la fronto.

288
00:14:00,710 --> 00:14:04,400
>> Kaj por rigardon supren, bone ni scias
aspektantaj supren en ligillisto

289
00:14:04,400 --> 00:14:05,785
povas esti problemo, ĉu ne?

290
00:14:05,785 --> 00:14:07,910
Ni devas traserĉi
ĝin de komenco al fino.

291
00:14:07,910 --> 00:14:10,460
Mankas hazarda
aliro en ligillisto.

292
00:14:10,460 --> 00:14:15,610
Sed se anstataŭ havi kunligita
lerta kie lookup estus O de n,

293
00:14:15,610 --> 00:14:19,590
Ni nun havas 10 ligitaj listoj,
aŭ 1,000 ligitaj listoj,

294
00:14:19,590 --> 00:14:24,120
nun ĝi estas ho de n dividita per 10,
aŭ O de n dividita per 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Kaj dum ni parolis
teorie pri komplekseco

296
00:14:26,940 --> 00:14:30,061
ni ignoru konstantoj, en la reala
mondo tion vere gravas,

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

298
00:14:30,560 --> 00:14:33,080
Ni efektive rimarkos
ke tio okazas

299
00:14:33,080 --> 00:14:36,610
kuri 10 fojoj pli rapida,
aŭ 1.000 fojoj pli rapida,

300
00:14:36,610 --> 00:14:41,570
ĉar ni distribui longa
ĉeno trans 1.000 malgrandaj ĉenoj.

301
00:14:41,570 --> 00:14:45,090
Kaj tiel ĉiu tempo ni devas serĉi
tra unu el tiuj ĉenoj eblan

302
00:14:45,090 --> 00:14:50,290
ignori la 999 ĉenojn ni ne zorgas
pri, kaj nur serĉu tiu.

303
00:14:50,290 --> 00:14:53,220
>> Kiu estas averaĝe al
esti 1,000 fojojn pli mallonga.

304
00:14:53,220 --> 00:14:56,460
Kaj tial ni ankoraŭ estas ia
emanta al ĉi mezumo kazo

305
00:14:56,460 --> 00:15:01,610
esti konstanta tempo, sed
nur ĉar ni laŭtigas

306
00:15:01,610 --> 00:15:03,730
dividante de iu grandega konstanta faktoro.

307
00:15:03,730 --> 00:15:05,804
Ni vidu kiom tio eble
vere aspektas tamen.

308
00:15:05,804 --> 00:15:08,720
Do tio estis la hash tablo ni havis
antaŭ ni deklaris hash tablo ke

309
00:15:08,720 --> 00:15:10,270
Estis kapabla de stoki 10 kordoj.

310
00:15:10,270 --> 00:15:11,728
Ni ne faros tion plu.

311
00:15:11,728 --> 00:15:13,880
Ni jam konas la
limigoj de tiu metodo.

312
00:15:13,880 --> 00:15:20,170
Nun nia hash tablo tuj estos
tabelo de 10 nodoj, punteros

313
00:15:20,170 --> 00:15:22,120
al kapoj de ligitaj listoj.

314
00:15:22,120 --> 00:15:23,830
>> Kaj ĝuste nun ĝi estas nula.

315
00:15:23,830 --> 00:15:26,170
Ĉiu el tiuj 10 punteros estas nula.

316
00:15:26,170 --> 00:15:29,870
Nenio en nia
hash tablo nun.

317
00:15:29,870 --> 00:15:32,690
>> Nun ni komencu meti iun
aferojn en tiu hash tablo.

318
00:15:32,690 --> 00:15:35,440
Kaj ni vidu kiel ĉi tiu metodo estas
iranta profitigi nin iomete.

319
00:15:35,440 --> 00:15:36,760
Ni nun hash Joey.

320
00:15:36,760 --> 00:15:40,210
Ni kuros la kordo Joey tra
hash funkcio kaj ni revenos 6.

321
00:15:40,210 --> 00:15:41,200
Nu kion ni faru nun?

322
00:15:41,200 --> 00:15:44,090
>> Nu nun laboras kun ligitaj listoj,
ni ne laboras per tabeloj.

323
00:15:44,090 --> 00:15:45,881
Kaj kiam ni laboras
kun ligitaj listoj ni

324
00:15:45,881 --> 00:15:49,790
scias ni bezonas komenci dinamike
asignante spaco kaj konstrumaterialoj ĉenoj.

325
00:15:49,790 --> 00:15:54,020
Tio estas speco de how-- tiuj estas la kerno
elementoj de konstruado ligillisto.

326
00:15:54,020 --> 00:15:57,670
Do ni dinamike
rezervu spacon por Joey,

327
00:15:57,670 --> 00:16:00,390
kaj tiam ni aldonu lin al la ĉeno.

328
00:16:00,390 --> 00:16:03,170
>> Do nun rigardas kion ni faris.

329
00:16:03,170 --> 00:16:06,440
Kiam ni hash Joey ni akiris la hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Nun la montrilo ĉe tabelo situon 6
notas al la kapo de ligillisto,

331
00:16:11,790 --> 00:16:14,900
kaj ĝuste nun ĝi estas la sola
elemento de ligitaj listo.

332
00:16:14,900 --> 00:16:18,350
Kaj la nodo en tiu
ligillisto estas Joey.

333
00:16:18,350 --> 00:16:22,300
>> Do se ni bezonas serĉi Joey
poste, ni nur hash Joey denove,

334
00:16:22,300 --> 00:16:26,300
ni ricevas 6 denove ĉar nia
krada funkcio estas determinisma.

335
00:16:26,300 --> 00:16:30,400
Kaj tiam ni komencu ĉe la kapo
de la ligillisto atentigis

336
00:16:30,400 --> 00:16:33,360
al per tabelo location
6, kaj ni povas persisti

337
00:16:33,360 --> 00:16:35,650
trans tiu provanta trovi Joey.

338
00:16:35,650 --> 00:16:37,780
Kaj se ni konstruas nian
hash tablo efike,

339
00:16:37,780 --> 00:16:41,790
kaj nia hash funkcio efike
distribui datumoj bone,

340
00:16:41,790 --> 00:16:45,770
averaĝe ĉiu de tiuj ligitaj
listoj ĉe ĉiu tabelo location

341
00:16:45,770 --> 00:16:50,110
Estos 1/10 la grandeco de se ni
nur havis ĝin kiel ununura grandega

342
00:16:50,110 --> 00:16:51,650
ligillisto kun ĉio en ĝi.

343
00:16:51,650 --> 00:16:55,670
>> Se ni disdoni ke grandega ligitaj
lerta trans 10 ligitaj listoj

344
00:16:55,670 --> 00:16:57,760
ĉiu listo estos 1/10 la grandeco.

345
00:16:57,760 --> 00:17:01,432
Kaj tiel 10 fojoj pli rapida
serĉi tra.

346
00:17:01,432 --> 00:17:02,390
Do ni faru ĉi denove.

347
00:17:02,390 --> 00:17:04,290
Ni nun hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Kaj diru Ross, kiam ni faru tion
la hash kodo ni reiros estas 2.

349
00:17:07,540 --> 00:17:10,630
Nu nun ni dinamike rezervu
nova nodo, ni metis Ross en tiu nodo,

350
00:17:10,630 --> 00:17:14,900
kaj ni diras nun tabelo location
2, anstataŭ montrante al nula,

351
00:17:14,900 --> 00:17:18,579
notas al la kapo de ligitaj
lerta kies nura nodo estas Ross.

352
00:17:18,579 --> 00:17:22,660
Kaj ni povas fari tion pli tempo, ni
povas hash Rahxel kaj akiri hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc nova nodo, metu Rahxel en
la nodo, kaj diri tabelo location

354
00:17:25,490 --> 00:17:27,839
4 nun notas al la kapo
de ligillisto kies

355
00:17:27,839 --> 00:17:31,420
nur elemento hazarde estas Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK sed kio okazas se
ni havas kolizion?

357
00:17:33,470 --> 00:17:38,560
Ni vidu kiel ni pritrakti koliziojn
uzante la apartaj ĉeni metodo.

358
00:17:38,560 --> 00:17:39,800
Ni hash Phoebe.

359
00:17:39,800 --> 00:17:41,094
Ni akiros la hashcode 6.

360
00:17:41,094 --> 00:17:44,010
En nia antaŭa ekzemplo ni estis ĵus
stokante kordoj en la tabelo.

361
00:17:44,010 --> 00:17:45,980
Tiu estis problemo.

362
00:17:45,980 --> 00:17:48,444
>> Ni ne volas clobber
Joey, kaj ni jam

363
00:17:48,444 --> 00:17:51,110
vidis ke ni povas akiri iom clustering
problemoj se ni provas kaj paŝo

364
00:17:51,110 --> 00:17:52,202
tra kaj sondas.

365
00:17:52,202 --> 00:17:54,660
Sed kio se ni nur speco de
trakti tiun sammaniere, dekstra?

366
00:17:54,660 --> 00:17:57,440
Estas nur kiel aldoni elementon
al la kapo de ligitaj listo.

367
00:17:57,440 --> 00:18:00,220
Ni simple malloc spaco por Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Ni diru Phoebe venonta puntero punktoj
al la malnova kapo de la ligillisto,

369
00:18:04,764 --> 00:18:07,180
kaj tiam 6 nur notas al la
nova estro de la ligitaj listo.

370
00:18:07,180 --> 00:18:10,150
Kaj nun rigardu, ni ŝanĝis Phoebe en.

371
00:18:10,150 --> 00:18:14,210
Ni povas nun enteni du
elementoj kun hashcode 6

372
00:18:14,210 --> 00:18:17,170
kaj ni ne havas problemojn.

373
00:18:17,170 --> 00:18:20,147
>> Tio estas sufiĉe multe ĉiuj
oni devas sinsekvon.

374
00:18:20,147 --> 00:18:21,980
Kaj ĉeni estas sendube
la metodo tio

375
00:18:21,980 --> 00:18:27,390
tuj estos plej efika por vi se
vi amasigas datumojn en hash tablo.

376
00:18:27,390 --> 00:18:30,890
Sed tiu kombino de
arrays kaj ligitaj listoj

377
00:18:30,890 --> 00:18:36,080
kune formi hash tablo vere
draste plibonigas vian kapablon

378
00:18:36,080 --> 00:18:40,550
stoki grandajn kvantojn de datumoj, kaj
tre rapide kaj efike serĉi

379
00:18:40,550 --> 00:18:41,630
tra tiu datumo.

380
00:18:41,630 --> 00:18:44,150
>> Ekzistas ankoraŭ unu pli
datumstrukturo tie

381
00:18:44,150 --> 00:18:48,700
kiuj povus eĉ esti iom
bona en terminoj de garantiado

382
00:18:48,700 --> 00:18:51,920
ke nia inserción, forigo, kaj
rigardi supren tempoj estas ankoraŭ pli rapida.

383
00:18:51,920 --> 00:18:55,630
Kaj ni vidos ke en video sur provoj.

384
00:18:55,630 --> 00:18:58,930
Mi Doug Lloyd, tiu estas CS50.

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