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

2
00:00:00,500 --> 00:00:01,900
[Musika jotzen]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: orain By duzu
Array buruz asko jakin,

5
00:00:09,150 --> 00:00:11,610
eta lotutako zerrendak buruz asko ezagutzen duzu.

6
00:00:11,610 --> 00:00:13,650
Eta eztabaidatzeko dugu
abantailak eta desabantailak, dugu

7
00:00:13,650 --> 00:00:16,620
zerrendak lotuta dagoela eztabaidatu
handiagoa eta txikiagoa lor daiteke,

8
00:00:16,620 --> 00:00:18,630
baina hartu zuten tamainako gehiago.

9
00:00:18,630 --> 00:00:22,359
Arrayak askoz gehiago zuzenean daude
erabili, baina murriztailea ari dira bezainbeste batean

10
00:00:22,359 --> 00:00:24,900
tamaina ezartzeko dugun bezala
hasieran oso array

11
00:00:24,900 --> 00:00:26,910
eta orduan ari gara bertan gelditzen da.

12
00:00:26,910 --> 00:00:30,470
>> Hori, ordea, nahiko askoz dugu
Gure gaien guztiak agortu

13
00:00:30,470 --> 00:00:33,040
zerrendak lotuta array buruz.

14
00:00:33,040 --> 00:00:34,950
Edo behar dugu?

15
00:00:34,950 --> 00:00:37,720
Agian zerbait egin dezakegu
are gehiago sortzaile.

16
00:00:37,720 --> 00:00:40,950
Eta erabaki moduko hori
Hash taula baten ideia.

17
00:00:40,950 --> 00:00:46,680
>> Beraz, hash taula bat ere ari gara saiatzen joan
array bat konbinatu lotuta zerrenda batekin.

18
00:00:46,680 --> 00:00:49,520
Abantaila hartu goaz
Array, ausazko sarbidea bezala,

19
00:00:49,520 --> 00:00:53,510
ahal izateko besterik joan array nahi izateagatik
elementu 4 edo array elementu 8

20
00:00:53,510 --> 00:00:55,560
zehar batetik bestera joateko beharrik gabe.

21
00:00:55,560 --> 00:00:57,260
Hori nahiko azkarra, ezta?

22
00:00:57,260 --> 00:01:00,714
>> Baina, era berean, gure datu eduki nahi dugu
egitura izango hazten eta txikitu gai.

23
00:01:00,714 --> 00:01:02,630
Ez dugu behar, ez dugu
mugatuta egon nahi.

24
00:01:02,630 --> 00:01:04,588
Eta gai izan nahi dugu
gehitzeko eta gauzak kendu

25
00:01:04,588 --> 00:01:08,430
Oso erraz, zein gogoratzen baduzu,
oso konplexua sorta batekin da.

26
00:01:08,430 --> 00:01:11,650
Eta hau esan genezake
hash taula bat gauza berria.

27
00:01:11,650 --> 00:01:15,190
>> Eta behar bezala eginez gero,
sort gara hartzen dugu

28
00:01:15,190 --> 00:01:18,150
bai datuak abantailak
Dagoeneko ikusi duzu egiturak,

29
00:01:18,150 --> 00:01:19,880
array eta zerrendak lotutako.

30
00:01:19,880 --> 00:01:23,070
Txertatze has daiteke
1 theta norabidean joera.

31
00:01:23,070 --> 00:01:26,207
Theta ez dute benetan aztertu ditugu,
baina theta batez beste kasu besterik ez da,

32
00:01:26,207 --> 00:01:27,540
zer benetan gertatuko.

33
00:01:27,540 --> 00:01:29,680
Oraindik ez duzu beti joan
kasu okerrena izan,

34
00:01:29,680 --> 00:01:32,555
eta ez zaren beti behar joan
kasurik onenean, beraz, zer da

35
00:01:32,555 --> 00:01:33,900
Bidaiarien batez besteko eszenatoki?

36
00:01:33,900 --> 00:01:36,500
>> Beno bataz-sartzeak bat
hash taula batean

37
00:01:36,500 --> 00:01:39,370
etengabeko denbora hurbiltzeko has daiteke.

38
00:01:39,370 --> 00:01:41,570
Eta ezabatzeko lor daiteke
etengabeko denbora itxi.

39
00:01:41,570 --> 00:01:44,440
Eta bilatu lor daiteke
etengabeko denbora itxi.

40
00:01:44,440 --> 00:01:48,600
That ez dugu datu bat izan
egitura oraindik hori egin daiteke,

41
00:01:48,600 --> 00:01:51,180
eta, beraz, honek dagoeneko soinuak
gauza nahiko handi bat bezala.

42
00:01:51,180 --> 00:01:57,010
Nik benetan arindu dugu
bakoitzaren desabantailak bere kabuz.

43
00:01:57,010 --> 00:01:59,160
>> Performance hau lortzeko
berritzea arren, ez dugu

44
00:01:59,160 --> 00:02:03,580
birpentsatzeko nola dugu gehitzeko behar den
egitura sartu datuak.

45
00:02:03,580 --> 00:02:07,380
Hain zuzen ere nahi dugu
Datu bera kontatzen digu,

46
00:02:07,380 --> 00:02:09,725
non behar egitura ere joan da.

47
00:02:09,725 --> 00:02:12,850
Eta bada, ondoren, behar dugun da, ikusteko
egitura, hura aurkitu behar badugu,

48
00:02:12,850 --> 00:02:16,610
Datuak begiratu nahi dugu
behin eta egin ahal izango dute, modu eraginkorrean,

49
00:02:16,610 --> 00:02:18,910
datuak erabiliz, ausaz sar ezazu.

50
00:02:18,910 --> 00:02:20,700
Just begira
Datu izan behar dugu

51
00:02:20,700 --> 00:02:25,890
non zehatz-mehatz ari garen ideia bat
aurkitu hash taula doa.

52
00:02:25,890 --> 00:02:28,770
>> Orain egiaztapen bat arazotxo
mahai benetan ari dira

53
00:02:28,770 --> 00:02:31,770
nahiko txarra ordenatzen edo datuen arabera ordenatzeko at.

54
00:02:31,770 --> 00:02:34,970
Eta hain zuzen ere, hasiko baduzu
horiek erabili ahal izateko, edo horrelako

55
00:02:34,970 --> 00:02:37,990
galtzen duzu datu guztiak
abantailak aurretik zuk

56
00:02:37,990 --> 00:02:40,710
eta ezabaketa dagokionez izan.

57
00:02:40,710 --> 00:02:44,060
Denbora bihurtzen gertuago
theta n, eta guk dut funtsean

58
00:02:44,060 --> 00:02:45,530
Lotuta zerrenda atzera.

59
00:02:45,530 --> 00:02:48,850
Eta horrela bakarrik hash erabili nahi dugu
mahaiak ez badugu zaintzeko

60
00:02:48,850 --> 00:02:51,490
Datu ordenatuko da ala ez.

61
00:02:51,490 --> 00:02:54,290
Testuinguruan bertan
Horiek erabili ahal izango duzu CS50

62
00:02:54,290 --> 00:02:58,900
Ziurrenik ez duzu axola
Datu hori horrela antolatu.

63
00:02:58,900 --> 00:03:03,170
>> Beraz, hash taula bat konbinazioa da
bi pieza desberdin baten

64
00:03:03,170 --> 00:03:04,980
bertan ezagutzen ari gara.

65
00:03:04,980 --> 00:03:07,930
Lehenengo eta behin, funtzio bat da, eta horrek
Ohi hash funtzio bat deitu dugu.

66
00:03:07,930 --> 00:03:11,760
Eta hash funtzio hori joan
itzuli zenbaki oso ez negatiboa batzuk, eta horrek

67
00:03:11,760 --> 00:03:14,870
Ohi hashcode deritzogu, OK?

68
00:03:14,870 --> 00:03:20,230
Bigarren pieza sorta bat, eta hori da
mota dugun du datuak gordetzeko gai

69
00:03:20,230 --> 00:03:22,190
Datuen egitura sartu jarri nahi.

70
00:03:22,190 --> 00:03:24,310
Eutsi off egingo dugu buruzko
Zerrenda elementu lotuta oraingoz

71
00:03:24,310 --> 00:03:27,810
eta besterik baten oinarriak hasteko
Hash taula zure burua lortzeko bere inguruan,

72
00:03:27,810 --> 00:03:30,210
eta orduan, agian egingo dugu putz
zure burua pixka bat dugunean

73
00:03:30,210 --> 00:03:32,920
matrizeak eta link zerrendak konbinatu batera.

74
00:03:32,920 --> 00:03:35,590
>> Oinarrizko ideia arren
datu batzuk hartu ditugu.

75
00:03:35,590 --> 00:03:37,860
Datu hori zehar ibiltzen gara
hash funtzioa.

76
00:03:37,860 --> 00:03:41,980
Eta beraz, datuak prozesatu
eta zenbaki bat spits, OK?

77
00:03:41,980 --> 00:03:44,890
Eta gero, zenbaki horrekin
datuak gordetzeko besterik ez dugu

78
00:03:44,890 --> 00:03:48,930
to the gorde nahi dugu
kokapena hartan array.

79
00:03:48,930 --> 00:03:53,990
Beraz, adibidez, agian ez dugu
hash kateen mahai honetan.

80
00:03:53,990 --> 00:03:57,350
Honez bertan 10 elementu lortu, beraz,
10 kateak doi dezakegu bertan.

81
00:03:57,350 --> 00:03:59,320
>> Demagun John hash nahi dugu.

82
00:03:59,320 --> 00:04:02,979
Beraz, John txertatu nahi ditugu, datu gisa
Hash taula hau nonbait sartu.

83
00:04:02,979 --> 00:04:03,770
Nora jarri dugu?

84
00:04:03,770 --> 00:04:05,728
Beno, normalean batekin
array orain arte seguruenik dugu

85
00:04:05,728 --> 00:04:07,610
jartzen array kokapena 0 da.

86
00:04:07,610 --> 00:04:09,960
Baina orain hash funtzio berri hau dugu.

87
00:04:09,960 --> 00:04:13,180
>> Eta demagun John run garela
hash funtzio honen bidez

88
00:04:13,180 --> 00:04:15,417
eta nik tu egiten du 4.

89
00:04:15,417 --> 00:04:17,500
Beno, hortxe gaude
John jarri nahi du.

90
00:04:17,500 --> 00:04:22,050
John jarri array kokapena Nahi dugu
4, John hash bagenu, berriro delako

91
00:04:22,050 --> 00:04:23,810
demagun geroago dugu
bilatu eta ikusi nahi

92
00:04:23,810 --> 00:04:26,960
John hash hau badago
mahaian egin behar dugun guztia

93
00:04:26,960 --> 00:04:30,310
da hash bera zehar ibiltzen da
funtzioa, lortu zenbakia 4 out,

94
00:04:30,310 --> 00:04:33,929
eta gai izango John aurkitu
Berehala gure datu-egitura.

95
00:04:33,929 --> 00:04:34,720
Hori nahiko ona.

96
00:04:34,720 --> 00:04:36,928
>> Demagun orain egiten dugun honetan
Berriro, Paul hash nahi dugu.

97
00:04:36,928 --> 00:04:39,446
Paul gehitu nahi dugu
hash taula batean.

98
00:04:39,446 --> 00:04:42,070
Demagun exekutatu dugu denbora honetan
Paul hash funtzio bidez,

99
00:04:42,070 --> 00:04:44,600
bat sortzen da, hashcode 6 da.

100
00:04:44,600 --> 00:04:47,340
Beno, orain, Paul jarri ahal izango dugu
Array kokapena 6 ere.

101
00:04:47,340 --> 00:04:50,040
Eta ala bilatuko behar badugu
Paul hash taula hau da,

102
00:04:50,040 --> 00:04:53,900
Egin behar dugun guztia da exekutatu Paul
hash funtzioa bidez berriro

103
00:04:53,900 --> 00:04:55,830
eta 6 ateratzeko berriro joan ginen.

104
00:04:55,830 --> 00:04:57,590
>> Eta gero, begiratu besterik ez dugu
array kokapena 6 etan.

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

106
00:04:58,910 --> 00:05:00,160
Hala bada, da hash taula zuen.

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

108
00:05:01,875 --> 00:05:03,000
Bera ez da hash taula.

109
00:05:03,000 --> 00:05:05,720
Nahiko erraza da.

110
00:05:05,720 --> 00:05:07,770
>> Orain, nola ez, hash funtzio bat definitzen duzu?

111
00:05:07,770 --> 00:05:11,460
Beno, ez da benetan ez du mugarik
Posible hash funtzio kopurua.

112
00:05:11,460 --> 00:05:14,350
Izan ere, zenbaki bat da, benetan,
Interneten benetan onak.

113
00:05:14,350 --> 00:05:17,560
Badira zenbaki bat da benetan,
Interneten benetan txarra ere bai.

114
00:05:17,560 --> 00:05:21,080
Gainera, nahiko erraza da
txarra bat idazteko.

115
00:05:21,080 --> 00:05:23,760
>> Beraz, zerk ona
hash funtzioa, ezta?

116
00:05:23,760 --> 00:05:27,280
Beno hash funtzioa ona egin beharko lukete
bakarrik ari hash- datuak erabili,

117
00:05:27,280 --> 00:05:29,420
eta ari hash- datu guztiak.

118
00:05:29,420 --> 00:05:32,500
Beraz, ez dugu nahi ezerk baino erabili
Ez dugu ezer erantsiko

119
00:05:32,500 --> 00:05:35,560
Bestela datuak baino beste.

120
00:05:35,560 --> 00:05:37,080
Eta datu guztiak erabili nahi dugu.

121
00:05:37,080 --> 00:05:39,830
Ez dugu nahi pieza bat bakarrik erabili
hura, hura guztia erabili nahi dugu.

122
00:05:39,830 --> 00:05:41,710
Hash funtzioa beharko lukete A
halaber determinista izan.

123
00:05:41,710 --> 00:05:42,550
Zer esan nahi du horrek?

124
00:05:42,550 --> 00:05:46,200
Beno, esan nahi du, aldi bakoitzean dugu
zehatza datuak pieza bera pasatzen

125
00:05:46,200 --> 00:05:50,040
Hash funtzioa dugu beti
the hashcode bera lortu.

126
00:05:50,040 --> 00:05:52,870
Pasatzen dut John bada sartu
hash funtzioa ateratzeko I 4.

127
00:05:52,870 --> 00:05:56,110
Horretarako gai izan behar dut 10.000
aldiz eta ez dut beti lortu 4.

128
00:05:56,110 --> 00:06:00,810
Beraz ausazko zenbakiak ez eraginkortasunez
den gure hash inplikatutako daiteke tables--

129
00:06:00,810 --> 00:06:02,750
gure hash funtzioak.

130
00:06:02,750 --> 00:06:05,750
>> Hash funtzioa behar ere
uniformeki datuak banatu.

131
00:06:05,750 --> 00:06:09,700
Bidez datuak exekutatzen duzunetan bada
hash funtzioa hashcode 0 eta lortuko duzu,

132
00:06:09,700 --> 00:06:11,200
Hori ez da, seguruenik, hain handia da, ezta?

133
00:06:11,200 --> 00:06:14,600
Ziurrenik dezakezu big nahi
hash kodeak sorta bat.

134
00:06:14,600 --> 00:06:17,190
Era berean, gauzak zabaldu ahal izango da
mahai zehar egindako.

135
00:06:17,190 --> 00:06:23,210
Eta, gainera, handia izango litzateke benetan bada
antzeko datuak, John eta Jonathan bezala,

136
00:06:23,210 --> 00:06:26,320
Agian zabaldu ziren pisatzen
Hash taula leku desberdinetan.

137
00:06:26,320 --> 00:06:28,750
Hori polita abantaila bat izango litzateke.

138
00:06:28,750 --> 00:06:31,250
>> Hemen hash funtzio bat adibide bat.

139
00:06:31,250 --> 00:06:33,150
Inork idatzitakoa up lehenago dut.

140
00:06:33,150 --> 00:06:35,047
Ez da bereziki bat
hash funtzioa ona

141
00:06:35,047 --> 00:06:37,380
benetan ez duten arrazoiak direla-eta
bear oraintxe sartu.

142
00:06:37,380 --> 00:06:41,040
Baina zer gertatzen da hemen ikusten duzu?

143
00:06:41,040 --> 00:06:44,420
Aldagai bat deklaratzen dugun bezala ari dela dirudi
batuketa eta 0 berdina ezarriz deitzen.

144
00:06:44,420 --> 00:06:50,010
Eta gero, itxuraz zerbait egiten ari naiz
hain luze strstr [j] ez da berdin

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

146
00:06:52,490 --> 00:06:54,870
Zer ari naiz hor?

147
00:06:54,870 --> 00:06:57,440
>> Hau da, funtsean, besterik gabe, beste
gauzatzeko [modu? Strl?]

148
00:06:57,440 --> 00:06:59,773
eta detektatzeko denean duzun
kate amaiera iritsi.

149
00:06:59,773 --> 00:07:02,480
Beraz, ez daukat benetan
luzera kalkulatzeko katea,

150
00:07:02,480 --> 00:07:05,640
Besterik ez denean hit I naiz erabiliz
backslash 0 pertsonaia dakit

151
00:07:05,640 --> 00:07:07,185
Katea amaieran Iritsi dut.

152
00:07:07,185 --> 00:07:09,560
Eta ondoren, naiz mantentzeko joan
kate horretan zehar errepikatzean,

153
00:07:09,560 --> 00:07:15,310
, laburbildu strstr [j] gehituz eta ondoren hartu du
Egunaren amaieran batura mod itzuli egingo da

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

155
00:07:16,200 --> 00:07:18,700
>> Funtsean hash hau guztia
funtzioa egiten ari dena gehituz

156
00:07:18,700 --> 00:07:23,450
ASCII balioak guztia
Nire katea, eta, ondoren,

157
00:07:23,450 --> 00:07:26,390
hashcode batzuk itzuli
HASH_MAX arabera modded.

158
00:07:26,390 --> 00:07:29,790
Seguruenik tamainaren
nire array, ezta?

159
00:07:29,790 --> 00:07:33,160
Ez dut nahi den hash lortzean
kode nire array tamaina 10 da, bada,

160
00:07:33,160 --> 00:07:35,712
Ez dut lortzean izan nahi
out hash 12 kodeak 11,

161
00:07:35,712 --> 00:07:38,690
13 Ezin dut jarri gauzak sartu
Array kokapenak horiek,

162
00:07:38,690 --> 00:07:39,790
hori legez kanpokoa izango litzateke.

163
00:07:39,790 --> 00:07:42,130
Segmentazio errua jasango nuke.

164
00:07:42,130 --> 00:07:45,230
>> Orain hemen beste bat da, azkar alde batera utzita.

165
00:07:45,230 --> 00:07:48,470
Oro har, seguruenik ari zaren ez da joan
Zeure hash funtzioak idatzi nahi.

166
00:07:48,470 --> 00:07:50,997
Benetan da apur bat
arte, ez da zientzia.

167
00:07:50,997 --> 00:07:52,580
Eta ez dagoela horiek sartzen da asko.

168
00:07:52,580 --> 00:07:55,288
Interneten, esan bezala, beteta dago
hash funtzio benetan ona,

169
00:07:55,288 --> 00:07:58,470
eta internet erabili behar duzu
hash funtzio aurkitu da benetan delako

170
00:07:58,470 --> 00:08:03,230
Mota besterik ez beharrezkoa
Denbora hondakin propioak sortzeko.

171
00:08:03,230 --> 00:08:05,490
>> Simple direnak idatzi ditzakezu
probetarako.

172
00:08:05,490 --> 00:08:08,323
Baina duzunean benetan joan
hasteko datuak osatzerakoan eta gordetzeko

173
00:08:08,323 --> 00:08:10,780
hash taula bat bazara sartu
ziurrenik nahi joan

174
00:08:10,780 --> 00:08:14,580
Sortu funtzio batzuk erabili
Zuretzat, Interneten existitzen.

175
00:08:14,580 --> 00:08:17,240
Zuk ez ziur egon bada
Zure iturriak aipatu beharrik.

176
00:08:17,240 --> 00:08:21,740
Ez da, arrazoirik ez
plagiarize ezer hemen.

177
00:08:21,740 --> 00:08:25,370
>> Informatikako komunitatea da
, balioak betiko hazten eta benetan

178
00:08:25,370 --> 00:08:28,796
kode irekia, eta benetan garrantzitsua da
Zure iturriak aipatu, jendeak

179
00:08:28,796 --> 00:08:30,670
eskuduntza lor daiteke
lana ari dira

180
00:08:30,670 --> 00:08:32,312
Komunitatearen onurarako egiten.

181
00:08:32,312 --> 00:08:34,020
Beraz, beti egon sure--
eta ez bakarrik hash egiteko

182
00:08:34,020 --> 00:08:37,270
funtzioak, baina, oro har duzunean
kodea erabili kanpoko iturri batetik,

183
00:08:37,270 --> 00:08:38,299
Beti aipatu zure iturburu.

184
00:08:38,299 --> 00:08:43,500
Eman kreditu pertsonaren egin nahi
lan batzuk, beraz, ez duzu behar.

185
00:08:43,500 --> 00:08:46,720
>> OK beraz Dezagun berriro honetan
bigarren bat mahai hash.

186
00:08:46,720 --> 00:08:48,780
Hau da, non utzi dugun
off dugu txertatuko ondoren

187
00:08:48,780 --> 00:08:53,300
John eta Paul hash taula batean.

188
00:08:53,300 --> 00:08:55,180
Ez da arazo bat ikusten duzu hemen?

189
00:08:55,180 --> 00:08:58,410
Baliteke bi ikusiko duzu.

190
00:08:58,410 --> 00:09:02,240
Baina batez ere, ez duzu
ikusi posible arazo hau?

191
00:09:02,240 --> 00:09:06,770
>> Zer hash dut Ringo bada, eta hura
bihurtzen duten prozesatu ondoren

192
00:09:06,770 --> 00:09:14,000
Datu hori hash funtzio bidez
Ringo halaber hashcode 6 sortzen.

193
00:09:14,000 --> 00:09:16,810
Nik dagoeneko lortu datuak
hashcode-- array kokapena 6.

194
00:09:16,810 --> 00:09:22,000
Beraz, ziurrenik, pixka bat izango da
niretzat arazo bat, ezta?

195
00:09:22,000 --> 00:09:23,060
>> Hau deitu dugu talka bat.

196
00:09:23,060 --> 00:09:26,460
Eta talka gertatzen denean bi
datu zati hash bera zehar ibiltzen

197
00:09:26,460 --> 00:09:29,200
Funtzio amore hashcode bera.

198
00:09:29,200 --> 00:09:32,850
Ustezko oraindik bi lortu nahi dugu
datu zati hash taula sartu,

199
00:09:32,850 --> 00:09:36,330
bestela ez genuke Ringo exekutatzen
arbitrarioki hash funtzio bidez.

200
00:09:36,330 --> 00:09:40,870
Zentzuzkoa lortu nahi dugu,
Array horretan sartu Ringo.

201
00:09:40,870 --> 00:09:46,070
>> Nola egiten dugu ordea, bada zuen
eta Paul bai etekin hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Ez dugu Paul gainidatzi nahi,
Paul han ere izan nahi dugu.

203
00:09:49,520 --> 00:09:52,790
Beraz, modu bat aurkitu lortu behar dugu
hash taula sartu elementu hori

204
00:09:52,790 --> 00:09:56,550
oraindik gure azkar kontserbak
sartzeak, azkar itxura eman.

205
00:09:56,550 --> 00:10:01,350
Eta horri aurre egiteko modu bat da
lineala deitzen kraterrak zerbait egin.

206
00:10:01,350 --> 00:10:04,170
>> Metodo hau erabiliz bat badaukagu
Talka, bai, zer egiten dugu?

207
00:10:04,170 --> 00:10:08,580
Beno, ezin dugu jarri zion array kokapenean
6, edo dena hashcode sortu da,

208
00:10:08,580 --> 00:10:10,820
dezagun jarri zion hashcode plus 1ean.

209
00:10:10,820 --> 00:10:13,670
Eta hori da, bada utzi beteta en
jarri zion hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Izate hau onerako egin baldin badu
Ez zehazki non dagoen uste dugu,

211
00:10:17,420 --> 00:10:20,850
eta bilatzen hasi beharko dugu,
Agian ez dugu urrunegi joan.

212
00:10:20,850 --> 00:10:23,900
Agian ez dugu bilatu
n hash taula elementu guztiak.

213
00:10:23,900 --> 00:10:25,790
Agian bilatu behar dugu
Horietako pare bat.

214
00:10:25,790 --> 00:10:30,680
>> Eta beraz, bidean oraindik dugun joera ari
bataz Kasu horretan hurbil vs izateaz 1

215
00:10:30,680 --> 00:10:34,280
n hurbil, beraz, agian lan egingo.

216
00:10:34,280 --> 00:10:38,010
Beraz, ikus dezagun nola hau
egindako lan baliteke errealitatean.

217
00:10:38,010 --> 00:10:41,460
Eta ikus dezagun agian detektatu ahal badugu
Hemen gerta zitekeen arazoa.

218
00:10:41,460 --> 00:10:42,540
>> Demagun Bart hash ditugu.

219
00:10:42,540 --> 00:10:45,581
Beraz, orain ari gara multzo berri bat exekutatu joan
hash funtzioa bidez kateak,

220
00:10:45,581 --> 00:10:48,460
eta Bart exekutatu dugu hash bidez
funtzioa, hashcode 6 lortuko dugu.

221
00:10:48,460 --> 00:10:52,100
Begirada bat hartu dugu, ikusiko dugu 6 da
hutsik, beraz, jarri ahal izango dugu Bart dago.

222
00:10:52,100 --> 00:10:55,410
>> Orain Lisa eta Hash dugu
halaber hashcode 6 sortzen.

223
00:10:55,410 --> 00:10:58,330
Beno, orain dela hau erabiltzen ari gara
artesiak lineala hasten 6 dugun metodoa,

224
00:10:58,330 --> 00:10:59,330
ikusten dugun 6 betea.

225
00:10:59,330 --> 00:11:00,990
Ezin dugu jarri Lisa 6 ere.

226
00:11:00,990 --> 00:11:02,090
Beraz, nora goaz?

227
00:11:02,090 --> 00:11:03,280
Goazen 7ra en.

228
00:11:03,280 --> 00:11:04,610
7 hutsik, beraz, lan egiten duen.

229
00:11:04,610 --> 00:11:06,510
Hargatik jarri Lisa dago.

230
00:11:06,510 --> 00:11:10,200
>> Orain Homer hash dugu eta lortuko dugu 7.

231
00:11:10,200 --> 00:11:13,380
OK ondo ezagutzen dugun 7 osoko dagoela
orain, beraz, ezin dugu jarri Homer dago.

232
00:11:13,380 --> 00:11:14,850
Beraz, goazen 8 en.

233
00:11:14,850 --> 00:11:15,664
Eskuragarri dagoen 8?

234
00:11:15,664 --> 00:11:18,330
Bai, 8 7 hurbil, beraz, eta bada
bilatzen ari gara hasteko aukera izango dugu

235
00:11:18,330 --> 00:11:20,020
ez oso urrun joan nahi izan du.

236
00:11:20,020 --> 00:11:22,860
Eta, beraz dezagun jarri Homer 8etan.

237
00:11:22,860 --> 00:11:25,151
>> Orain hash ditugu Maggie eta
3 itzultzen, eskerrak

238
00:11:25,151 --> 00:11:26,650
besterik jarri Maggie ez gai gara.

239
00:11:26,650 --> 00:11:29,070
Guk ez dugu izan inolako egin
Sort duten probak.

240
00:11:29,070 --> 00:11:32,000
Orain hash ditugu Marge, eta
Marge halaber 6 itzultzen.

241
00:11:32,000 --> 00:11:39,560
>> Beno 6 beteta dago, 7 beteta dago, 8 beteta dago,
9, guztiak eskuineko Jainkoari eskerrak, 9 hutsik dago.

242
00:11:39,560 --> 00:11:41,600
Jarri ahal izango dut Marge 9etan.

243
00:11:41,600 --> 00:11:45,280
Dagoeneko ikusi ahal dugu hasten ari gara
Arazo hau non orain gaude dute

244
00:11:45,280 --> 00:11:48,780
Gauza mota luzatzeko hasita
far euren hash kodeak urrun.

245
00:11:48,780 --> 00:11:52,960
Eta 1 theta dela, batez besteko hori
etengabeko denbora izatearen kasuan,

246
00:11:52,960 --> 00:11:56,560
more-- pixka bat lortzeko hasi
apur bat gehiago joera hasita

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

248
00:11:58,050 --> 00:12:01,270
Ari dela galtzen hasita gaude
hash taulak abantaila.

249
00:12:01,270 --> 00:12:03,902
>> Arazo hau ikusi besterik ez dugu
clustering izeneko zerbait da.

250
00:12:03,902 --> 00:12:06,360
Eta zer da benetan txarra
clustering da zuk behin orain

251
00:12:06,360 --> 00:12:09,606
Bi elementu hori albo dira by dute
alde egiten du, are gehiago egongo da,

252
00:12:09,606 --> 00:12:11,480
bikoitza egin behar duzu
aukera, hori gertatzen ari zarela

253
00:12:11,480 --> 00:12:13,516
Talka beste bat izan
kluster horrekin,

254
00:12:13,516 --> 00:12:14,890
eta kluster egingo banan hazten.

255
00:12:14,890 --> 00:12:19,640
Eta gero eta gehiago hazten mantentzeko duzu
Zure talka bat izateko arriskua.

256
00:12:19,640 --> 00:12:24,470
Eta, azkenean, ez da bezain txarra
ez bezala Datuak guztiak ordenatzeko.

257
00:12:24,470 --> 00:12:27,590
>> Beste arazoa guk da
oraindik, eta orain arte, puntu honetan,

258
00:12:27,590 --> 00:12:30,336
besterik ez dugu izan da sort
hash taula bat zer den ulertzeko,

259
00:12:30,336 --> 00:12:31,960
dugu oraindik 10 kateak gela bakarra izan.

260
00:12:31,960 --> 00:12:37,030
Hash jarraitu nahi badugu
Springfield herritarrek,

261
00:12:37,030 --> 00:12:38,790
Horietako 10 bakarrik gaitezke hor.

262
00:12:38,790 --> 00:12:42,619
Eta saiatu gara eta 11an edo 12an gehitzeko,
ez dugu leku bat jartzea dute.

263
00:12:42,619 --> 00:12:45,660
Besterik ezin izango spinning dugu inguruan
zirkuluak leku hutsik aurkitu nahian,

264
00:12:45,660 --> 00:12:49,000
eta, agian get itsasten dugu
begizta infinitua.

265
00:12:49,000 --> 00:12:51,810
>> Beraz, ideia erabaki moduko honetan
Zerbait izeneko kateatzea.

266
00:12:51,810 --> 00:12:55,790
Eta hau da, non ari gara ekartzea joan
zerrendak lotutako argazki sartu atzera.

267
00:12:55,790 --> 00:13:01,300
Ordez zer bada besterik gordetzeko
datu bera array,

268
00:13:01,300 --> 00:13:04,471
array elementu guztietan Could
eutsi datu zati bat baino gehiago?

269
00:13:04,471 --> 00:13:05,970
Beno, ez du zentzurik, ezta?

270
00:13:05,970 --> 00:13:09,280
Badakigu array soilik
array baten elementu bakoitzaren hold--

271
00:13:09,280 --> 00:13:12,930
Pieza bat egon daiteke
Datu mota horretako datuen.

272
00:13:12,930 --> 00:13:16,750
>> Baina zer gertatzen da datu-mota hori
lotutako zerrenda bat da, ezta?

273
00:13:16,750 --> 00:13:19,830
Beraz, zer da bada
array elementu izan zen

274
00:13:19,830 --> 00:13:22,790
lotuta zerrenda burua erakuslea?

275
00:13:22,790 --> 00:13:24,680
Eta gero, ezin dugu eraiki
lotutako zerrendak horiek

276
00:13:24,680 --> 00:13:27,120
eta hazten horiek arbitrarioki,
delako lotuta zerrendak baimendu

277
00:13:27,120 --> 00:13:32,090
gurekin hazten eta txikitu askoz gehiago
malgutasunez array bat baino ez.

278
00:13:32,090 --> 00:13:34,210
Beraz, orain zer erabili badugu,
honek onura dugu, ezta?

279
00:13:34,210 --> 00:13:37,760
Kate horiek hazten hasten dugu
array kokaleku horietan egindako.

280
00:13:37,760 --> 00:13:40,740
>> Orain amaigabe bat doi dezakegu
datu zenbatekoa, edo ez da infinitua,

281
00:13:40,740 --> 00:13:44,170
kopuru arbitrario bat
datuak, gure hash taula sartu

282
00:13:44,170 --> 00:13:47,760
inoiz sartu exekutatzen gabe
Talka arazoa.

283
00:13:47,760 --> 00:13:50,740
Ere kendu dugu
hau eginez clustering.

284
00:13:50,740 --> 00:13:54,380
Eta ondo ezagutzen dugun noiz sartu dugu
Lotuta zerrenda, gogoratzen baduzu

285
00:13:54,380 --> 00:13:57,779
Gure zerrendak lotuta buruzko bideo-tik, banaka
lotutako zerrendak eta bi aldiz lotuta zerrendak,

286
00:13:57,779 --> 00:13:59,070
denbora etengabeko eragiketa bat da.

287
00:13:59,070 --> 00:14:00,710
Ari gara aurrealdean gehituz.

288
00:14:00,710 --> 00:14:04,400
>> Eta begirada bat ireki, ondo jakin nahi dugu
itxura eman lotuta zerrenda batean

289
00:14:04,400 --> 00:14:05,785
arazo bat izan daiteke, ezta?

290
00:14:05,785 --> 00:14:07,910
Bidez bilatu behar dugu
hasieratik amaierara da.

291
00:14:07,910 --> 00:14:10,460
Ez da, ausazko ez
lotuta zerrenda batean sartzeko aukera.

292
00:14:10,460 --> 00:14:15,610
Baina horren ordez, bada bat izatearen lotuta
Zerrenda non bilatu a n O izango litzateke,

293
00:14:15,610 --> 00:14:19,590
orain dugu 10 lotuta zerrendak,
edo 1.000 lotuta zerrendak,

294
00:14:19,590 --> 00:14:24,120
Orain bat, O n 10 arabera banatzen da,
edo n O 1.000 arabera banatuta.

295
00:14:24,120 --> 00:14:26,940
>> Eta hitz egiten genuen bitartean
teorikoki konplexutasuna buruz

296
00:14:26,940 --> 00:14:30,061
konstanteak iezaiozu dugu, erreala
Mundu gauza horiek benetan axola,

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

298
00:14:30,560 --> 00:14:33,080
Benetan dugu nabarituko
Hori gertatzen dela

299
00:14:33,080 --> 00:14:36,610
10 aldiz azkarragoa,
edo 1.000 aldiz azkarrago,

300
00:14:36,610 --> 00:14:41,570
Oraindik inork luze banatzeko dugulako
1.000 kateak txikiagoa zehar katean.

301
00:14:41,570 --> 00:14:45,090
Eta beraz, aldi bakoitzean bilatu
ahal dugun kateak horietakoa bidez

302
00:14:45,090 --> 00:14:50,290
999 kateak ez dugu axola ez ikusi
buruz, eta besterik ez bilatu bat dela.

303
00:14:50,290 --> 00:14:53,220
>> Zein batez beste da
1.000 aldiz laburragoa izan.

304
00:14:53,220 --> 00:14:56,460
Eta, beraz, oraindik ez gara Sort
bataz Kasu honetan doazen

305
00:14:56,460 --> 00:15:01,610
etengabeko denbora izatea, baina
aprobetxatuz dugun bakarra delako

306
00:15:01,610 --> 00:15:03,730
Etengabeko faktore handi batzuk zatituz.

307
00:15:03,730 --> 00:15:05,804
Ikus nola liteke dezagun
Egia esan, nahiz eta itxura.

308
00:15:05,804 --> 00:15:08,720
Beraz, hau izan zen taula hash izan genuen
hash taula bat deklaratu dugu aurretik

309
00:15:08,720 --> 00:15:10,270
10 kateak gordetzeko gai izan zen.

310
00:15:10,270 --> 00:15:11,728
Ez dugu hori gehiago egin behar.

311
00:15:11,728 --> 00:15:13,880
Dagoeneko badakigu
Metodo horren mugak.

312
00:15:13,880 --> 00:15:20,170
Orain gure hash taula da hori izango da
10 nodo, erakusle bat array

313
00:15:20,170 --> 00:15:22,120
zerrendak lotuta buruak.

314
00:15:22,120 --> 00:15:23,830
>> Eta oraintxe nulua da.

315
00:15:23,830 --> 00:15:26,170
Bakoitzak 10 erakusleak horietako bat da nulua.

316
00:15:26,170 --> 00:15:29,870
Ez dago ezer gure in
Hash taula oraintxe.

317
00:15:29,870 --> 00:15:32,690
>> Orain dezagun hasteko batzuk jarri
hash taula batean gauzak.

318
00:15:32,690 --> 00:15:35,440
Eta ikus dezagun metodo hau nola da
guri mesede pixka bat doa.

319
00:15:35,440 --> 00:15:36,760
Let hash en orain Joey.

320
00:15:36,760 --> 00:15:40,210
Egingo dugu Joey kate bidez exekutatu egingo
hash funtzio bat eta gu itzuli 6.

321
00:15:40,210 --> 00:15:41,200
Beno, zer egingo dugu orain?

322
00:15:41,200 --> 00:15:44,090
>> Beno, orain zerrendak lotutako lan egitea,
ez gara hilarak lanean.

323
00:15:44,090 --> 00:15:45,881
Eta lanean ari gara
zerrendak lotuta dugu

324
00:15:45,881 --> 00:15:49,790
Badakizu dinamikoki hasi behar dugu
espazio eta eraikin kateak esleitzean.

325
00:15:49,790 --> 00:15:54,020
Hori da Ordena how-- horiek dira muina
lotutako zerrenda bat eraikitzeko elementu.

326
00:15:54,020 --> 00:15:57,670
Hargatik dinamikoki
esleitu espazioa Joey egiteko,

327
00:15:57,670 --> 00:16:00,390
eta, ondoren, dezagun gehitu zion kateari.

328
00:16:00,390 --> 00:16:03,170
>> Beraz, orain zer egin dugu begiratu.

329
00:16:03,170 --> 00:16:06,440
When Joey hash ditugu hashcode 6 lortu dugu.

330
00:16:06,440 --> 00:16:11,790
Orain array kokapena 6 erakuslea
lotutako zerrenda baten buru puntu,

331
00:16:11,790 --> 00:16:14,900
eta oraintxe bakarrik da
lotuta zerrenda elementua.

332
00:16:14,900 --> 00:16:18,350
Eta hori nodoarentzat
Zerrenda lotuta Joey da.

333
00:16:18,350 --> 00:16:22,300
>> Beraz Joey begiratu behar badugu
geroago, hash dugu besterik Joey berriro,

334
00:16:22,300 --> 00:16:26,300
lortuko dugu 6 berriro gure duelako
hash funtzioa determinista da.

335
00:16:26,300 --> 00:16:30,400
Eta orduan hasten buru izaten dugu
lotuta zerrendaren adierazi

336
00:16:30,400 --> 00:16:33,360
array kokapena ek
6, eta batetik bestera joateko aukera izango dugu

337
00:16:33,360 --> 00:16:35,650
Hori Joey bilatzen saiatzen zeharkatuz.

338
00:16:35,650 --> 00:16:37,780
Eta guk eraikiko balitz, gure
Hash taula eraginkorrean,

339
00:16:37,780 --> 00:16:41,790
eta gure hash funtzioa eraginkortasunez
Datu ondo banatzeko,

340
00:16:41,790 --> 00:16:45,770
batez beste horietako bakoitzean lotuta
array kokapena guztietan zerrendak

341
00:16:45,770 --> 00:16:50,110
1/10 izango bada tamainaren dugu
besterik handi bakar bat bezala izan da

342
00:16:50,110 --> 00:16:51,650
lotuta bertan dena batera zerrenda.

343
00:16:51,650 --> 00:16:55,670
>> Lotuta dagoela handi banatu badiogu
10 lotuta zerrendak zeharkatuz zerrenda

344
00:16:55,670 --> 00:16:57,760
Zerrenda bakoitzak 1/10 tamaina izango da.

345
00:16:57,760 --> 00:17:01,432
Eta horrela, 10 aldiz azkarrago
bilatu bidez.

346
00:17:01,432 --> 00:17:02,390
Beraz Berriro egin dezagun.

347
00:17:02,390 --> 00:17:04,290
Let hash en orain Ross.

348
00:17:04,290 --> 00:17:07,540
>> Eta demagun Ross, noiz egiten dugun
hash-kodea itzultzen garen 2 da.

349
00:17:07,540 --> 00:17:10,630
Beno, orain dinamikoki esleitu a dugu
nodo berria, Ross jarri dugu nodo horretan,

350
00:17:10,630 --> 00:17:14,900
eta orain esaten dugu array kokapena
2, ordez null seinalatuz,

351
00:17:14,900 --> 00:17:18,579
a lotuta buru seinalatzen
Zerrenda zeinen nodo bakarra Ross da.

352
00:17:18,579 --> 00:17:22,660
Eta denbora gehiago bat hau egin ahal izango dugu, ez dugu
Rachel hash dezakegu eta hashcode 4.

353
00:17:22,660 --> 00:17:25,490
Nodo berria malloc, jarri Rachel hasi
nodoa, eta array kokapena batek esaten

354
00:17:25,490 --> 00:17:27,839
4 orain buruan seinalatzen
lotutako zerrenda bat zeinen

355
00:17:27,839 --> 00:17:31,420
elementu bakarra gertatzen Rachel izan.

356
00:17:31,420 --> 00:17:33,470
>> Ados, baina bada zer gertatzen den
Talka izan dugu?

357
00:17:33,470 --> 00:17:38,560
Ikus dezagun talkak nola kudeatu dugu utzi
aparteko kateatzea metodoa erabiliz.

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

359
00:17:39,800 --> 00:17:41,094
Hashcode 6 lortuko dugu.

360
00:17:41,094 --> 00:17:44,010
Gure aurreko Adibidez besterik ginen
Array en kateak gordetzeko.

361
00:17:44,010 --> 00:17:45,980
Hau arazo bat izan zen.

362
00:17:45,980 --> 00:17:48,444
>> Guk ez dugu nahi gainean idazteko nahi
Joey, eta dagoeneko dugu

363
00:17:48,444 --> 00:17:51,110
Ikusten duten clustering batzuk eskuratu ahal izango dugu
arazoak saiatzen bagara eta urrats

364
00:17:51,110 --> 00:17:52,202
bidez eta zunda.

365
00:17:52,202 --> 00:17:54,660
Baina ez dugu zer bada mota besterik
hau tratatzeko modu berean, ezta?

366
00:17:54,660 --> 00:17:57,440
Besterik ez da elementu bat gehitzen bezalakoa da
lotutako zerrenda baten buru izateko.

367
00:17:57,440 --> 00:18:00,220
Let Phoebe dagoen espazio besterik malloc.

368
00:18:00,220 --> 00:18:04,764
>> Esan dugu Phoebe hurrengo erakuslea puntu
lotuta zerrendaren burua zaharrari,

369
00:18:04,764 --> 00:18:07,180
eta ondoren, 6 puntu
Zerrenda lotuta buru berria.

370
00:18:07,180 --> 00:18:10,150
Eta orain, begira, aldatu dugu Phoebe ere.

371
00:18:10,150 --> 00:18:14,210
Orain dugu bi gorde ahal izateko
hashcode 6 elementu,

372
00:18:14,210 --> 00:18:17,170
eta ez dugu inolako arazorik izan.

373
00:18:17,170 --> 00:18:20,147
>> Hori nahiko askoz guztiak
ez kateatzea da.

374
00:18:20,147 --> 00:18:21,980
Eta kateatzea da betiko
hori da metodoaren

375
00:18:21,980 --> 00:18:27,390
gehien baduzu eraginkorra izango da
datuak gordetzeko duzu hash taula batean.

376
00:18:27,390 --> 00:18:30,890
Baina konbinazio honetan
array eta zerrendak lotutako

377
00:18:30,890 --> 00:18:36,080
elkarrekin hash taula bat osatzeko benetan
nabarmen gaitasuna hobetzen

378
00:18:36,080 --> 00:18:40,550
datu kantitate handiak gordetzeko, eta
Oso azkar eta modu eraginkorrean bilatu

379
00:18:40,550 --> 00:18:41,630
Datu hori bidez.

380
00:18:41,630 --> 00:18:44,150
>> Ez da oraindik bat gehiago
Datuen egitura daude

381
00:18:44,150 --> 00:18:48,700
Hori izan liteke, nahiz eta pixka bat izan
bermatzean hobeto

382
00:18:48,700 --> 00:18:51,920
gure txertatzeko, ezabatzeko, eta
itxura eman aldiz are azkarrago.

383
00:18:51,920 --> 00:18:55,630
Eta hori ikusiko dugu saiatzen bideo batetan.

384
00:18:55,630 --> 00:18:58,930
Naiz Doug Lloyd, hau CS50 da.

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