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

2
00:00:00,500 --> 00:00:01,900
[MUSIC nagpe-play]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: sa ngayon ikaw
alam ng maraming tungkol sa array,

5
00:00:09,150 --> 00:00:11,610
at alam mo ng maraming tungkol sa mga listahan ng link.

6
00:00:11,610 --> 00:00:13,650
At hindi namin pag-usapan ang
mga kalamangan at kahinaan, na namin

7
00:00:13,650 --> 00:00:16,620
napag-usapan na ang mga listahan ng link
ay maaaring makakuha ng mas malaki at mas maliit,

8
00:00:16,620 --> 00:00:18,630
ngunit tumagal ng hanggang sila ay mas laki.

9
00:00:18,630 --> 00:00:22,359
Ang mga array ay mas matapat na
gamitin, ngunit ang mga ito ay mahigpit sa mas maraming

10
00:00:22,359 --> 00:00:24,900
bilang kami upang itakda ang laki ng
ang array sa pinakadulo simula

11
00:00:24,900 --> 00:00:26,910
at pagkatapos ay natigil kami sa mga ito.

12
00:00:26,910 --> 00:00:30,470
>> Ngunit iyon, na namin medyo marami
naubos na ang lahat ng aming mga paksa

13
00:00:30,470 --> 00:00:33,040
tungkol sa naka-link na mga listahan at mga array.

14
00:00:33,040 --> 00:00:34,950
O mayroon kami?

15
00:00:34,950 --> 00:00:37,720
Siguro maaari naming gawin ang isang bagay
kahit na mas creative.

16
00:00:37,720 --> 00:00:40,950
At na uri ng mga nagpapautang
ang ideya ng isang hash table.

17
00:00:40,950 --> 00:00:46,680
>> Kaya sa isang hash table kami ay pagpunta sa subukan
pagsamahin ang isang array na may isang naka-link na listahan.

18
00:00:46,680 --> 00:00:49,520
Kami ay pagpunta sa gawin ang mga pakinabang
ng array, tulad ng random access,

19
00:00:49,520 --> 00:00:53,510
kawalan ng kakayahang pumunta lamang sa array
element 4 o array elemento 8

20
00:00:53,510 --> 00:00:55,560
nang hindi na kinakailangang upang umulit sa kabuuan.

21
00:00:55,560 --> 00:00:57,260
Iyan ay medyo mabilis, di ba?

22
00:00:57,260 --> 00:01:00,714
>> Ngunit din namin na magkaroon ng aming data
istraktura ay maaaring sa paglaki at pag-urong.

23
00:01:00,714 --> 00:01:02,630
Hindi natin kailangan, ay hindi kami
gustong maging limitado.

24
00:01:02,630 --> 00:01:04,588
At gusto namin na ma
upang idagdag at alisin ang mga bagay-bagay

25
00:01:04,588 --> 00:01:08,430
tunay madali, na kung isipin mo,
ay napaka-komplikadong sa isang array.

26
00:01:08,430 --> 00:01:11,650
At maaari naming tawagan ang
bagong bagay ng hash table.

27
00:01:11,650 --> 00:01:15,190
>> At kung naipatupad nang tama,
uri ng kami ay pagkuha

28
00:01:15,190 --> 00:01:18,150
ang mga pakinabang ng parehong data
istruktura na nakita mo,

29
00:01:18,150 --> 00:01:19,880
array at mga listahan ng link.

30
00:01:19,880 --> 00:01:23,070
Insertion ay maaaring magsimula sa
malamang papunta theta ng 1.

31
00:01:23,070 --> 00:01:26,207
Theta hindi talaga namin napag-usapan,
ngunit theta ay lamang ng average na mga kaso,

32
00:01:26,207 --> 00:01:27,540
kung ano ang aktwal na pagpunta sa mangyayari.

33
00:01:27,540 --> 00:01:29,680
Hindi ka palaging pagpunta sa
may pinakamasama kaso sitwasyon,

34
00:01:29,680 --> 00:01:32,555
at ikaw ay hindi palaging pagpunta sa may
ang pinakamahusay na kaso sitwasyon, kaya kung ano ang

35
00:01:32,555 --> 00:01:33,900
ang average na sitwasyon?

36
00:01:33,900 --> 00:01:36,500
>> Well isang average insertion
sa isang hash table

37
00:01:36,500 --> 00:01:39,370
maaari simulan upang makakuha ng malapit sa pare-pareho ang panahon.

38
00:01:39,370 --> 00:01:41,570
At pagtanggal ay maaaring makakuha ng
isara sa pare-pareho ng panahon.

39
00:01:41,570 --> 00:01:44,440
At lookup ay maaaring makakuha ng
isara sa pare-pareho ng panahon.

40
00:01:44,440 --> 00:01:48,600
That's-- wala tayong isang data
structure pa na maaaring gawin iyon,

41
00:01:48,600 --> 00:01:51,180
at kaya ito na tunog
tulad ng isang medyo magandang bagay.

42
00:01:51,180 --> 00:01:57,010
Na talagang mitigated namin ang
disadvantages ng bawat-isa.

43
00:01:57,010 --> 00:01:59,160
>> Upang makakuha ng pagganap na ito
i-upgrade ang bagaman, kami ay

44
00:01:59,160 --> 00:02:03,580
kailangan umisip na muli kung paano namin magdagdag ng
data sa istraktura.

45
00:02:03,580 --> 00:02:07,380
Partikular nais naming ang
data ng kanyang sarili upang sabihin sa amin

46
00:02:07,380 --> 00:02:09,725
kung saan ito ay dapat pumunta sa istraktura.

47
00:02:09,725 --> 00:02:12,850
At kung pagkatapos ay kailangan namin upang makita kung ito ay sa
ang istraktura, kung kailangan namin upang mahanap ang mga ito,

48
00:02:12,850 --> 00:02:16,610
gusto naming tingnan ang data
at ma-muli mabisa,

49
00:02:16,610 --> 00:02:18,910
gamit ang data, random access ito.

50
00:02:18,910 --> 00:02:20,700
Sa pamamagitan lamang ng pagtingin sa mga
data na dapat naming magkaroon

51
00:02:20,700 --> 00:02:25,890
isang ideya ng kung saan ang eksaktong hindi namin
pagpunta upang mahanap ito sa hash table.

52
00:02:25,890 --> 00:02:28,770
>> Ngayon ang downside ng isang hash
mesa ay na ang mga ito ay talagang

53
00:02:28,770 --> 00:02:31,770
medyo masama sa pag-order o pag-uuri ng data.

54
00:02:31,770 --> 00:02:34,970
At sa katunayan, kung sinimulan mo
gamitin mag-order o pag-uuri ang mga ito

55
00:02:34,970 --> 00:02:37,990
data nawala mo ang lahat ng
pakinabang sa iyo dati

56
00:02:37,990 --> 00:02:40,710
nagkaroon sa mga tuntunin ng insertion at pagtanggal.

57
00:02:40,710 --> 00:02:44,060
Ang oras ay nagiging mas malapit sa
theta ng n, at hindi na namin nai talaga

58
00:02:44,060 --> 00:02:45,530
regressed sa isang listahan ng mga link.

59
00:02:45,530 --> 00:02:48,850
At kaya gusto lamang naming gamitin ang hash
tables kung hindi namin pag-aalaga tungkol

60
00:02:48,850 --> 00:02:51,490
kung ang data ay pinagsunod-sunod.

61
00:02:51,490 --> 00:02:54,290
Para sa konteksto kung saan
kakailanganin mong gamitin ang mga ito sa CS50

62
00:02:54,290 --> 00:02:58,900
marahil ay hindi mo pag-aalaga
na ang data ay pinagsunod-sunod.

63
00:02:58,900 --> 00:03:03,170
>> Kaya ang isang hash table ay isang kumbinasyon
ng dalawang natatanging mga piraso

64
00:03:03,170 --> 00:03:04,980
na kung saan kami ay pamilyar.

65
00:03:04,980 --> 00:03:07,930
Ang una ay isang function, kung saan
karaniwang namin tumawag sa isang hash.

66
00:03:07,930 --> 00:03:11,760
At na hash ay pagpunta sa
ibalik ang ilang mga hindi-negatibong integer, na

67
00:03:11,760 --> 00:03:14,870
karaniwang namin tumawag sa isang hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Ang ikalawang piraso ay isang array, na kung saan ay
kaya ng pagtatago ng data ng mga uri namin

69
00:03:20,230 --> 00:03:22,190
gustong ilagay sa istraktura ng data.

70
00:03:22,190 --> 00:03:24,310
Susubukan naming i-hold off sa
naka-link na listahan ng elemento para sa ngayon

71
00:03:24,310 --> 00:03:27,810
at simulan lamang sa mga pangunahing kaalaman ng isang
hash talahanayan upang makakuha ng inyong ulo sa paligid nito,

72
00:03:27,810 --> 00:03:30,210
at pagkatapos ay gagamitin namin siguro pumutok
ang iyong isip nang kaunti kapag kami

73
00:03:30,210 --> 00:03:32,920
pagsamahin ang mga array at mga listahan ng mga link na magkasama.

74
00:03:32,920 --> 00:03:35,590
>> Ang pangunahing ideya bagaman
ay tumagal kami ng ilang data.

75
00:03:35,590 --> 00:03:37,860
Nagpapatakbo kami na data sa pamamagitan ng
ang hash.

76
00:03:37,860 --> 00:03:41,980
At sa gayon ang data ay na-proseso
at ito spits isang numero, OK?

77
00:03:41,980 --> 00:03:44,890
At pagkatapos ay may numero na
imbak lamang namin ang mga data

78
00:03:44,890 --> 00:03:48,930
gusto naming upang i-imbak sa
array sa lokasyon na iyon.

79
00:03:48,930 --> 00:03:53,990
Kaya halimbawa kami siguro
ito hash table ng mga string.

80
00:03:53,990 --> 00:03:57,350
Ito ay nakuha ng 10 mga elemento sa loob nito, kaya
maaari naming magkasya 10 string sa loob nito.

81
00:03:57,350 --> 00:03:59,320
>> Ipagpalagay natin na nais nating hash John.

82
00:03:59,320 --> 00:04:02,979
Kaya si Juan ang data na nais namin upang ipasok
sa ito hash table sa tabi-tabi.

83
00:04:02,979 --> 00:04:03,770
Saan mo ilalagay namin dito?

84
00:04:03,770 --> 00:04:05,728
Well karaniwang may isang
array sa ngayon kami ay marahil

85
00:04:05,728 --> 00:04:07,610
ay ilagay ito sa array lokasyon 0.

86
00:04:07,610 --> 00:04:09,960
Ngunit ngayon kami ay ang bagong function hash.

87
00:04:09,960 --> 00:04:13,180
>> At sabihin natin na aming pinatatakbo John
sa pamamagitan na ito hash

88
00:04:13,180 --> 00:04:15,417
at ito ay spits 4.

89
00:04:15,417 --> 00:04:17,500
Well na kung saan hindi namin
pagpunta sa nais na ilagay John.

90
00:04:17,500 --> 00:04:22,050
Gusto naming ilagay Juan sa lokasyon array
4, dahil kung hash namin John again--

91
00:04:22,050 --> 00:04:23,810
sabihin natin mamaya namin
nais na paghahanap at makita

92
00:04:23,810 --> 00:04:26,960
kung umiiral John sa hash
table-- lahat ng kailangan naming gawin

93
00:04:26,960 --> 00:04:30,310
ay tatakbo ito sa pamamagitan ng parehong hash
function, makuha ang numero 4 out,

94
00:04:30,310 --> 00:04:33,929
at ma-makahanap John
kaagad sa aming mga istraktura ng data.

95
00:04:33,929 --> 00:04:34,720
Iyan ay medyo mabuti.

96
00:04:34,720 --> 00:04:36,928
>> Ipagpalagay natin na gawin namin ito ngayon
muli, nais naming hash Paul.

97
00:04:36,928 --> 00:04:39,446
Gusto naming magdagdag ng Paul
sa ito hash table.

98
00:04:39,446 --> 00:04:42,070
Sabihin natin na ang oras na ito tumakbo kami
Paul sa pamamagitan ng hash function,

99
00:04:42,070 --> 00:04:44,600
ang hashcode na nabuo ay 6.

100
00:04:44,600 --> 00:04:47,340
Well ngayon ay maaari naming ilagay ang Paul
sa array lokasyon 6.

101
00:04:47,340 --> 00:04:50,040
At kung kailangan namin upang tumingin up kung
Paul ay nasa ito hash table,

102
00:04:50,040 --> 00:04:53,900
lahat ng kailangan naming gawin ay tumakbo Paul
sa pamamagitan ng hash muli

103
00:04:53,900 --> 00:04:55,830
at kami ay pagpunta upang makakuha ng 6 out muli.

104
00:04:55,830 --> 00:04:57,590
>> At pagkatapos ay tumingin lang namin
sa array lokasyon 6.

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

106
00:04:58,910 --> 00:05:00,160
Kung gayon, siya ay sa hash table.

107
00:05:00,160 --> 00:05:01,875
Ay Paul hindi doon?

108
00:05:01,875 --> 00:05:03,000
Siya ay wala sa hash table.

109
00:05:03,000 --> 00:05:05,720
Ito ay medyo tapat.

110
00:05:05,720 --> 00:05:07,770
>> Ngayon paano mo tukuyin ang isang hash function?

111
00:05:07,770 --> 00:05:11,460
Well may tunay na walang limitasyon sa
bilang ng mga posibleng hash function.

112
00:05:11,460 --> 00:05:14,350
Sa katunayan mayroong isang bilang ng mga tunay,
tunay mabuti iyan sa internet.

113
00:05:14,350 --> 00:05:17,560
Mayroong isang bilang ng mga tunay,
ganap na hindi maayos na iyan sa internet.

114
00:05:17,560 --> 00:05:21,080
Ito ay medyo madali din
sumulat ng isang masamang isa.

115
00:05:21,080 --> 00:05:23,760
>> Kaya kung ano ang gumagawa ng isang magandang
hash, di ba?

116
00:05:23,760 --> 00:05:27,280
Well isang magandang function hash dapat
gamitin lamang ang mga data na na-hash,

117
00:05:27,280 --> 00:05:29,420
at ang lahat ng mga data na na-hash.

118
00:05:29,420 --> 00:05:32,500
Kaya hindi namin nais na gumamit ng anything--
hindi namin isama ang anumang bagay

119
00:05:32,500 --> 00:05:35,560
pa ang iba sa mga data.

120
00:05:35,560 --> 00:05:37,080
At gusto namin na gamitin ang lahat ng mga data.

121
00:05:37,080 --> 00:05:39,830
Hindi namin nais na gumamit lamang ng isang piraso
ng mga ito, gusto naming gamitin ang lahat ng ito.

122
00:05:39,830 --> 00:05:41,710
Isang hash dapat
maging deterministic din.

123
00:05:41,710 --> 00:05:42,550
Ano ang ibig sabihin nito?

124
00:05:42,550 --> 00:05:46,200
Well ito ay nangangahulugan na ang bawat oras na namin
ipasa ang parehong piraso ng data

125
00:05:46,200 --> 00:05:50,040
sa hash kami ay palaging
makakuha ng parehong hashcode out.

126
00:05:50,040 --> 00:05:52,870
Kung pumasa I Juan sa
hash na nakukuha ko mula 4.

127
00:05:52,870 --> 00:05:56,110
Dapat kong magawa na 10,000
beses at lagi makakuha ng 4.

128
00:05:56,110 --> 00:06:00,810
Kaya walang mga random na numero epektibong
maaaring kasangkot sa aming hash tables--

129
00:06:00,810 --> 00:06:02,750
sa ating mga pag-andar hash.

130
00:06:02,750 --> 00:06:05,750
>> Isang hash ay dapat din
pantay ipamahagi ang data.

131
00:06:05,750 --> 00:06:09,700
Kung sa bawat oras na patakbuhin mo ang data sa pamamagitan ng
hash mong makuha ang hashcode 0,

132
00:06:09,700 --> 00:06:11,200
na malamang ay hindi kaya mahusay na, i-right?

133
00:06:11,200 --> 00:06:14,600
Maaring nais na malaki
isang hanay ng mga hash code.

134
00:06:14,600 --> 00:06:17,190
Gayundin bagay ay maaaring kumalat
out sa buong table.

135
00:06:17,190 --> 00:06:23,210
At din ito ay mahusay na kung talagang
katulad na data, tulad ni Juan at Jonathan,

136
00:06:23,210 --> 00:06:26,320
marahil ay magkahiwalay sa timbangin
iba't-ibang lokasyon sa hash table.

137
00:06:26,320 --> 00:06:28,750
Iyon ay isang magandang bentahe.

138
00:06:28,750 --> 00:06:31,250
>> Narito ang isang halimbawa ng isang hash.

139
00:06:31,250 --> 00:06:33,150
Isinulat ko ang isang ito up nang mas maaga.

140
00:06:33,150 --> 00:06:35,047
Ito ay hindi isang partikular na
magandang function hash

141
00:06:35,047 --> 00:06:37,380
para sa mga dahilan na hindi tunay
madala ang pagpunta sa ngayon.

142
00:06:37,380 --> 00:06:41,040
Ngunit huwag mong makita kung ano ang nangyayari sa dito?

143
00:06:41,040 --> 00:06:44,420
Tila tulad ng kami ay deklarasyon ng variable
tinatawag sum at ang setting na ito katumbas ng 0.

144
00:06:44,420 --> 00:06:50,010
At pagkatapos ay tila ako ng paggawa ng isang bagay
kaya hangga't strstr [j] ay hindi katumbas ng

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

146
00:06:52,490 --> 00:06:54,870
Ang ginagawa ko doon?

147
00:06:54,870 --> 00:06:57,440
>> Ito ay karaniwang lamang ng isa pang
paraan ng pagpapatupad [? strl?]

148
00:06:57,440 --> 00:06:59,773
at tiktik kapag na sa iyo
naabot na ang dulo ng string.

149
00:06:59,773 --> 00:07:02,480
Kaya hindi ko kung talagang
kalkulahin ang haba ng string,

150
00:07:02,480 --> 00:07:05,640
Lamang ako ng gamit kapag ako ay pindutin ang
backslash 0 karakter alam ko

151
00:07:05,640 --> 00:07:07,185
Naabot ko na ang dulo ng string.

152
00:07:07,185 --> 00:07:09,560
At pagkatapos ay ako pagpunta sa panatilihin
iterating sa pamamagitan ng na string,

153
00:07:09,560 --> 00:07:15,310
pagdagdag ng strstr [j] sa sum, at pagkatapos ay sa
pagtatapos ng araw upang bumalik sum mod

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

155
00:07:16,200 --> 00:07:18,700
>> Talaga lahat ng hash na ito
function na ito ay ginagawa ng pagdaragdag ng hanggang

156
00:07:18,700 --> 00:07:23,450
lahat ng mga halaga ASCII ng
aking string, at pagkatapos ito ay

157
00:07:23,450 --> 00:07:26,390
bumabalik ilang hashcode
modded pamamagitan HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Ito ay marahil ang laki
ng aking array, di ba?

159
00:07:29,790 --> 00:07:33,160
Hindi ko nais na maging sa pagkuha hash
Mga code kung ang aking array ng laki 10,

160
00:07:33,160 --> 00:07:35,712
Hindi ko nais na maging pagkuha
out hash code 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, hindi ko maaaring ilagay ang mga bagay sa
mga lokasyon ng mga array,

162
00:07:38,690 --> 00:07:39,790
na labag sa batas.

163
00:07:39,790 --> 00:07:42,130
Gusto ko magdusa ng segmentation fault.

164
00:07:42,130 --> 00:07:45,230
>> Ngayon dito ay isa pang mabilis tabi.

165
00:07:45,230 --> 00:07:48,470
Kadalasan ikaw ay marahil hindi pagpunta sa
gusto mong isulat ang iyong sariling mga hash function.

166
00:07:48,470 --> 00:07:50,997
Ito ay talagang isang piraso ng
isang sining, hindi isang science.

167
00:07:50,997 --> 00:07:52,580
At mayroong isang pulutong na napupunta sa mga ito.

168
00:07:52,580 --> 00:07:55,288
Ang internet, tulad ng sinabi ko, ay puno
ng tunay na magandang pag-andar hash,

169
00:07:55,288 --> 00:07:58,470
at dapat mong gamitin ang internet upang
maghanap ng hash function dahil ito ay talagang

170
00:07:58,470 --> 00:08:03,230
lamang ang uri ng isang hindi kailangang
aksaya ng panahon upang lumikha ng iyong sarili.

171
00:08:03,230 --> 00:08:05,490
>> Maaari mong isulat ang mga musmos
para sa mga layunin sa pagsubok.

172
00:08:05,490 --> 00:08:08,323
Ngunit kapag ikaw talaga ay pagpunta sa
simulan hashing data at pag-imbak nito

173
00:08:08,323 --> 00:08:10,780
sa isang hash table ikaw
marahil pagpunta sa gusto

174
00:08:10,780 --> 00:08:14,580
upang gamitin ang ilang mga function na ay binuo
para sa iyo, na umiiral sa internet.

175
00:08:14,580 --> 00:08:17,240
Kapag kayo ay siguraduhin lamang
na banggitin ang iyong mga pinagkukunan.

176
00:08:17,240 --> 00:08:21,740
Walang dahilan upang
mamlahiyo anumang bagay dito.

177
00:08:21,740 --> 00:08:25,370
>> Ang komunidad na computer science ay
tiyak lumalaki, at talagang halaga

178
00:08:25,370 --> 00:08:28,796
open source, at ito ay talagang mahalaga
na banggitin ang iyong mga pinagkukunan sa gayon na ang mga tao

179
00:08:28,796 --> 00:08:30,670
ay maaaring makakuha ng pagpapatungkol para sa
ang mga trabaho na ang mga ito ay

180
00:08:30,670 --> 00:08:32,312
paggawa sa mga benepisyo ng komunidad.

181
00:08:32,312 --> 00:08:34,020
Kaya laging sure--
at hindi lamang para sa hash

182
00:08:34,020 --> 00:08:37,270
pag-andar, ngunit sa pangkalahatan ay kapag ikaw
gamitin ang code mula sa isang panlabas na pinagmulan,

183
00:08:37,270 --> 00:08:38,299
laging banggitin ang iyong source.

184
00:08:38,299 --> 00:08:43,500
Bigyan ng credit sa mga tao na ang
ilan sa mga trabaho kaya hindi mo na kailangang.

185
00:08:43,500 --> 00:08:46,720
>> OK ni muling bisitahin ito upang ipaalam sa
hash talahanayan para sa isang segundo.

186
00:08:46,720 --> 00:08:48,780
Ito ay kung saan namin kaliwa
off pagkatapos naming nakapasok

187
00:08:48,780 --> 00:08:53,300
John at Paul sa ito hash table.

188
00:08:53,300 --> 00:08:55,180
May nakikita ka bang problema dito?

189
00:08:55,180 --> 00:08:58,410
Maaari kang makakita ng dalawang.

190
00:08:58,410 --> 00:09:02,240
Ngunit sa partikular, gawin mo
makikita ito ng mga posibleng problema?

191
00:09:02,240 --> 00:09:06,770
>> Paano kung ako hash Ringo, at ito
lumiliko out na matapos ang pagproseso

192
00:09:06,770 --> 00:09:14,000
ang data na iyon sa pamamagitan ng hash
Ringo nakabuo din ang hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Na mayroon akong data sa
hashcode-- lokasyon array 6.

194
00:09:16,810 --> 00:09:22,000
Kaya ito ay marahil pagpunta sa maging isang bit
ng isang problema para sa akin ngayon, tama?

195
00:09:22,000 --> 00:09:23,060
>> Tinatawag namin itong isang banggaan.

196
00:09:23,060 --> 00:09:26,460
At ang banggaan ay nangyayari kapag ang dalawang
mga piraso ng data tumakbo sa pamamagitan ng parehong hash

197
00:09:26,460 --> 00:09:29,200
function na ani ng parehong hashcode.

198
00:09:29,200 --> 00:09:32,850
Siguro namin gusto pa rin upang makakuha ng parehong mga
mga piraso ng data sa hash table,

199
00:09:32,850 --> 00:09:36,330
kabilang banda ay hindi maaaring tumakbo kami Ringo
nagkataon pamamagitan ng hash.

200
00:09:36,330 --> 00:09:40,870
Siguro namin nais na makakuha ng
Ringo sa na array.

201
00:09:40,870 --> 00:09:46,070
>> Paano namin gawin ito bagaman, kung siya
at Paul parehong ani hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Hindi namin gusto ang patungan Paul,
gusto naming Paul na may masyadong.

203
00:09:49,520 --> 00:09:52,790
Kaya kailangan namin upang makahanap ng isang paraan upang makakuha ng
elemento sa hash table na

204
00:09:52,790 --> 00:09:56,550
pinapanatili pa rin ang aming mabilis na
insertion at mabilis na pagtingin up.

205
00:09:56,550 --> 00:10:01,350
At isang paraan upang harapin ang mga ito ay upang
gawin ang isang bagay na tinatawag na linear probing.

206
00:10:01,350 --> 00:10:04,170
>> Gamit ang pamamaraan na kung kami ay may isang
banggaan, well, ano ang gagawin namin?

207
00:10:04,170 --> 00:10:08,580
Well hindi namin maaaring ilagay sa kanya sa lokasyon array
6, o kahit anong hashcode ay nabuo,

208
00:10:08,580 --> 00:10:10,820
Maglagay ng kanya sa hashcode plus 1 ipaalam.

209
00:10:10,820 --> 00:10:13,670
At kung na full hahayaan
inilagay siya sa hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Ang mga benepisyo ng mga ito na kung siya ay
hindi eksakto kung saan sa tingin namin siya ay,

211
00:10:17,420 --> 00:10:20,850
at kami ay may upang simulan ang paghahanap,
marahil hindi namin ay may upang pumunta masyadong malayo.

212
00:10:20,850 --> 00:10:23,900
Siguro hindi natin kailangang maghanap
lahat ng mga elemento n ng hash table.

213
00:10:23,900 --> 00:10:25,790
Siguro na namin sa paghahanap
isang pares ng mga ito.

214
00:10:25,790 --> 00:10:30,680
>> At kaya kami ay nag-aalaga pa rin patungo sa
na average case pagiging malapit sa 1 vs

215
00:10:30,680 --> 00:10:34,280
malapit sa n, kaya marahil na kakailanganin sa trabaho.

216
00:10:34,280 --> 00:10:38,010
Kaya sabihin makita kung paano ito
maaaring gumana out sa katotohanan.

217
00:10:38,010 --> 00:10:41,460
At makita kung marahil maaari naming makita ipaalam
mga problema na maaaring mangyari dito.

218
00:10:41,460 --> 00:10:42,540
>> Ipagpalagay natin na hash namin Bart.

219
00:10:42,540 --> 00:10:45,581
Kaya ngayon kami ay pagpunta sa magpatakbo ng isang bagong set
ng mga string sa pamamagitan ng hash function,

220
00:10:45,581 --> 00:10:48,460
at tumakbo kami Bart sa pamamagitan ng hash
function, makakakuha tayo ng hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Kumuha kami ng isang tumingin, makikita natin na 6 ay
walang laman, upang maaari naming ilagay Bart doon.

222
00:10:52,100 --> 00:10:55,410
>> Ngayon hash namin Lisa at na
Bumubuo din hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Well ngayon na aming ginagamit ito
linear probing paraan simulan namin sa 6,

224
00:10:58,330 --> 00:10:59,330
nakita namin na 6 ay puno na.

225
00:10:59,330 --> 00:11:00,990
Hindi namin maaaring ilagay Lisa sa 6.

226
00:11:00,990 --> 00:11:02,090
Kaya kung saan tayo pupunta?

227
00:11:02,090 --> 00:11:03,280
Sabihin pumunta sa 7.

228
00:11:03,280 --> 00:11:04,610
7 ng walang laman, kaya na gumagana.

229
00:11:04,610 --> 00:11:06,510
Kaya sabihin maglagay Lisa doon ipaalam.

230
00:11:06,510 --> 00:11:10,200
>> Ngayon hash namin Homer at makuha namin 7.

231
00:11:10,200 --> 00:11:13,380
OK na rin alam namin na 7 ng full
ngayon, kaya hindi namin maaaring ilagay Homer doon.

232
00:11:13,380 --> 00:11:14,850
Kaya sabihin pumunta sa 8.

233
00:11:14,850 --> 00:11:15,664
Available ba 8?

234
00:11:15,664 --> 00:11:18,330
Oo, at malapit sa 7 8, kaya kung
kami ay may upang simulan ang paghahanap hindi namin

235
00:11:18,330 --> 00:11:20,020
hindi pagpunta sa may upang pumunta masyadong malayo.

236
00:11:20,020 --> 00:11:22,860
At ang ilagay Homer sa 8 kaya hayaan.

237
00:11:22,860 --> 00:11:25,151
>> Ngayon hash namin Maggie at
nagbabalik 3, salamat sa diyos

238
00:11:25,151 --> 00:11:26,650
hindi namin magagawang ilagay lamang Maggie doon.

239
00:11:26,650 --> 00:11:29,070
Hindi natin kailangang gawin ang anumang
uri ng probing para sa na.

240
00:11:29,070 --> 00:11:32,000
Ngayon hash namin Marge, at
Nagbabalik din Marge 6.

241
00:11:32,000 --> 00:11:39,560
>> Well 6 ay puno na, 7 ay puno na, 8 ay puno na,
9, ang lahat ng karapatan salamat sa Diyos, 9 ay walang laman.

242
00:11:39,560 --> 00:11:41,600
Maaari ko bang ilagay Marge sa 9.

243
00:11:41,600 --> 00:11:45,280
Ginagamit mo na maaari naming makita na kami ay nagsisimula
na magkaroon ng ganitong problema kung saan ngayon hindi namin

244
00:11:45,280 --> 00:11:48,780
simula upang mabatak bagay uri
ng malayo mula sa kanilang hash code.

245
00:11:48,780 --> 00:11:52,960
At na theta ng 1, na average
kaso ng pagiging pare-pareho ang oras,

246
00:11:52,960 --> 00:11:56,560
ay nagsisimula upang makakuha ng isang maliit more--
nagsisimula na may posibilidad ng kaunti pa

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

248
00:11:58,050 --> 00:12:01,270
Kami ay nagsisimula sa mawala na ang
bentahe ng hash talahanayan.

249
00:12:01,270 --> 00:12:03,902
>> Ang problemang ito na nakita namin lamang
isang bagay na tinatawag clustering.

250
00:12:03,902 --> 00:12:06,360
At kung ano ang talagang masama tungkol
clustering ay na sa sandaling ikaw ay ngayon

251
00:12:06,360 --> 00:12:09,606
may dalawang mga sangkap na bahagi sa pamamagitan ng
gilid ito ay gumagawa ito kahit na mas malamang,

252
00:12:09,606 --> 00:12:11,480
ikaw ay may double ang
pagkakataon, na ikaw ay pagpunta

253
00:12:11,480 --> 00:12:13,516
magkaroon ng isa pang banggaan
may na kumpol,

254
00:12:13,516 --> 00:12:14,890
at ang mga kumpol ay lalaki sa pamamagitan ng isa.

255
00:12:14,890 --> 00:12:19,640
At makikita mo panatilihin lumalago at lumalaki
ang iyong posibilidad ng pagkakaroon ng isang banggaan.

256
00:12:19,640 --> 00:12:24,470
At sa huli ito ay tulad ng masama
bilang hindi pag-uuri sa lahat ng mga data.

257
00:12:24,470 --> 00:12:27,590
>> Ang iba pang mga problema bagaman ay namin
pa rin, at sa ngayon hanggang sa puntong ito,

258
00:12:27,590 --> 00:12:30,336
lang nakaya naming uri ng
sa pag-unawa kung ano ang isang hash table ay,

259
00:12:30,336 --> 00:12:31,960
pa rin namin ang magkaroon lamang ng room para sa 10 mga string.

260
00:12:31,960 --> 00:12:37,030
Kung gusto namin upang magpatuloy sa hash
ang mga mamamayan ng Springfield,

261
00:12:37,030 --> 00:12:38,790
kami ay maaari lamang makakuha ng 10 sa mga ito sa doon.

262
00:12:38,790 --> 00:12:42,619
At kung susubukan at magdagdag ng isang ika-11 o ika-12 namin,
hindi namin ay may isang lugar upang ilagay ang mga ito.

263
00:12:42,619 --> 00:12:45,660
Kami ay maaaring lamang ay umiikot sa paligid sa
bilog sinusubukan upang mahanap ang isang walang laman na lugar,

264
00:12:45,660 --> 00:12:49,000
at kami ay marahil makakuha ng mapagmataas
sa isang walang-katapusang loop.

265
00:12:49,000 --> 00:12:51,810
>> Kaya ito uri ng mga nagpapautang sa ideya
ng isang bagay na tinatawag pagdudugtong.

266
00:12:51,810 --> 00:12:55,790
At ito ay kung saan kami ay pagpunta upang dalhin sa
mga listahan ng naka-link pabalik sa ang larawan.

267
00:12:55,790 --> 00:13:01,300
Paano kung sa halip ng pag-iimbak lamang
ang data mismo sa array,

268
00:13:01,300 --> 00:13:04,471
bawat elemento ng array ng dati
maghawak ng maramihang mga piraso ng data?

269
00:13:04,471 --> 00:13:05,970
Well na ay hindi magkaroon ng kahulugan, tama?

270
00:13:05,970 --> 00:13:09,280
Alam namin na ang isang array ay maaari lamang
hold-- bawat elemento ng isang array

271
00:13:09,280 --> 00:13:12,930
maaari lamang humawak ng isang piraso
ng data ng mga uri ng data.

272
00:13:12,930 --> 00:13:16,750
>> Ngunit paano kung na uri ng data
ay isang listahan ng mga link, di ba?

273
00:13:16,750 --> 00:13:19,830
Kaya kung ano kung ang bawat
element ng array ay

274
00:13:19,830 --> 00:13:22,790
isang pointer sa ulo ng isang listahan ng mga link?

275
00:13:22,790 --> 00:13:24,680
At pagkatapos ay maaari kaming bumuo ng
mga listahan ng link

276
00:13:24,680 --> 00:13:27,120
at maging ang mga ito nagkataon,
dahil pinapayagan listahan ng link

277
00:13:27,120 --> 00:13:32,090
sa amin upang maging at pag-urong ng maraming higit pa
flexibly kaysa sa isang array ay.

278
00:13:32,090 --> 00:13:34,210
Kaya kung ano kung kami ay gamitin ngayon,
naming pagkilos na ito, i-right?

279
00:13:34,210 --> 00:13:37,760
Simulan namin na palaguin ang mga kadena
out ng mga lokasyon na array.

280
00:13:37,760 --> 00:13:40,740
>> Ngayon ay maaari naming magkasya sa isang walang hanggan
halaga ng data, o hindi walang katapusan,

281
00:13:40,740 --> 00:13:44,170
isang di-makatwirang halaga ng
data, sa aming hash table

282
00:13:44,170 --> 00:13:47,760
nang hindi kailanman tumatakbo sa
ang problema ng banggaan.

283
00:13:47,760 --> 00:13:50,740
Na inalis rin namin
clustering pamamagitan ng paggawa nito.

284
00:13:50,740 --> 00:13:54,380
At well alam namin na kapag ipasok namin
sa isang listahan ng mga link, kung ang pagpapabalik sa iyo

285
00:13:54,380 --> 00:13:57,779
mula sa aming mga video sa listahan ng link, isa-isa
naka-link na mga listahan at mga doble-link na listahan,

286
00:13:57,779 --> 00:13:59,070
ito ay isang patuloy na operasyon ng panahon.

287
00:13:59,070 --> 00:14:00,710
Lang kaming nagdadagdag sa harap.

288
00:14:00,710 --> 00:14:04,400
>> At para sa hitsura up, well alam natin
na tumingin up sa isang listahan ng mga link

289
00:14:04,400 --> 00:14:05,785
maaaring maging isang problema, di ba?

290
00:14:05,785 --> 00:14:07,910
Mayroon kaming upang maghanap sa pamamagitan ng
ito mula sa umpisa hanggang katapusan.

291
00:14:07,910 --> 00:14:10,460
Walang random
access sa isang naka-link na listahan.

292
00:14:10,460 --> 00:14:15,610
Ngunit kung sa halip ng pagkakaroon ng isa na naka-link
list kung saan ang isang lookup ay O ng n,

293
00:14:15,610 --> 00:14:19,590
kami ngayon ay mayroon ng 10 mga listahan na naka-link,
o 1,000 mga listahan na naka-link,

294
00:14:19,590 --> 00:14:24,120
ngayon ito ay O ng n hinati sa 10,
o O ng n hinahati sa pamamagitan ng 1,000.

295
00:14:24,120 --> 00:14:26,940
>> At habang kami ay pakikipag-usap
theoretically tungkol kumplikado

296
00:14:26,940 --> 00:14:30,061
babalewalain natin constants, sa tunay na
mundo ng mga bagay na talagang mahalaga,

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

298
00:14:30,560 --> 00:14:33,080
Kami ay talagang mapansin
na nangyari ito

299
00:14:33,080 --> 00:14:36,610
upang magpatakbo ng 10 beses na mas mabilis,
o 1,000 beses na mas mabilis,

300
00:14:36,610 --> 00:14:41,570
dahil kami ay namamahagi ng isang mahabang
chain sa buong 1,000 mas maliliit na kadena.

301
00:14:41,570 --> 00:14:45,090
At kaya sa bawat oras na namin sa paghahanap
sa pamamagitan ng isa sa mga chains ng aming makakaya

302
00:14:45,090 --> 00:14:50,290
huwag pansinin ang 999 chains hindi namin pakialam
tungkol sa, at hanapin lang ang isa.

303
00:14:50,290 --> 00:14:53,220
>> Alin sa average na
1,000 beses na mas maikli.

304
00:14:53,220 --> 00:14:56,460
At gayon pa rin kami uri ng
tending patungo ito average case

305
00:14:56,460 --> 00:15:01,610
ng pagiging pare-pareho ang oras, ngunit
lamang dahil tayo ay pagdaragdag

306
00:15:01,610 --> 00:15:03,730
naghahati sa pamamagitan ng ilang mga napakalaking constant factor.

307
00:15:03,730 --> 00:15:05,804
Tayo'y makita kung paano maaaring ito Hayaan
aktwal na hitsura kahit na.

308
00:15:05,804 --> 00:15:08,720
Kaya ito ay ang talahanayan hash namin ay
bago namin ipinahayag ng isang hash table na

309
00:15:08,720 --> 00:15:10,270
ay kaya ng pagtatago ng 10 string.

310
00:15:10,270 --> 00:15:11,728
Hindi namin pagpunta sa gawin na anymore.

311
00:15:11,728 --> 00:15:13,880
Alam na namin ang
limitasyon ng pamamaraan na iyon.

312
00:15:13,880 --> 00:15:20,170
Ngayon ang aming hash table ay magiging
isang array ng 10 nodes, mga payo

313
00:15:20,170 --> 00:15:22,120
sa mga ulo ng mga naka-link na mga listahan.

314
00:15:22,120 --> 00:15:23,830
>> At ngayon ito ay null.

315
00:15:23,830 --> 00:15:26,170
Ang bawat isa sa mga 10 mga payo ay null.

316
00:15:26,170 --> 00:15:29,870
Walang wala sa aming
hash talahanayan ngayon.

317
00:15:29,870 --> 00:15:32,690
>> Ngayon sabihin simulan upang ilagay ang ilang ipaalam
mga bagay na ito sa hash table.

318
00:15:32,690 --> 00:15:35,440
At makita kung paano ang paraan na ito ay ipaalam
pagpunta upang makinabang sa amin nang kaunti.

319
00:15:35,440 --> 00:15:36,760
Ngayon sumira ni Joey Hayaan.

320
00:15:36,760 --> 00:15:40,210
Susubukan naming tatakbo ang string Joey pamamagitan
isang hash at kami ay bumalik 6.

321
00:15:40,210 --> 00:15:41,200
Well kung ano ang gagawin namin ngayon?

322
00:15:41,200 --> 00:15:44,090
>> Well ngayon ay nagtatrabaho sa naka-link na mga listahan,
hindi namin ay nagtatrabaho sa array.

323
00:15:44,090 --> 00:15:45,881
At kapag kami ay nagtatrabaho
may mga listahan ng link namin

324
00:15:45,881 --> 00:15:49,790
Alam na kailangan namin upang simulan ang magilas
paglaan ng space at mga gusali ng kadena.

325
00:15:49,790 --> 00:15:54,020
Iyan ay ang uri ng mga how-- iyon ay ang mga core
mga elemento ng pagbuo ng isang listahan ng mga link.

326
00:15:54,020 --> 00:15:57,670
Kaya sabihin magilas
maglaan ng espasyo para Joey,

327
00:15:57,670 --> 00:16:00,390
at pagkatapos ay sabihin magdagdag ng kanya sa chain.

328
00:16:00,390 --> 00:16:03,170
>> Kaya tingnan mo ngayon kung ano ang aming nagawa.

329
00:16:03,170 --> 00:16:06,440
Kapag hash namin Joey namin nakuha ang hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Ngayon ang pointer sa array lokasyon 6
puntos sa ulo ng isang listahan ng mga link,

331
00:16:11,790 --> 00:16:14,900
at ngayon ito ay ang tanging
elemento ng isang listahan ng mga link.

332
00:16:14,900 --> 00:16:18,350
At ang mga node sa na
listahan ng mga link ay Joey.

333
00:16:18,350 --> 00:16:22,300
>> Kaya kung kailangan namin upang tumingin up Joey
mamaya, hash namin lamang Joey muli,

334
00:16:22,300 --> 00:16:26,300
makakakuha tayo ng 6 muli dahil ang aming
hash ay deterministic.

335
00:16:26,300 --> 00:16:30,400
At pagkatapos ay simulan namin sa ulo
mga listahan ng mga link tulis

336
00:16:30,400 --> 00:16:33,360
sa pamamagitan ng lokasyon array
6, at maaari naming umulit

337
00:16:33,360 --> 00:16:35,650
kabuuan na sinusubukan mong hanapin Joey.

338
00:16:35,650 --> 00:16:37,780
At kung bumuo kami ng aming
hash talahanayan mabisa,

339
00:16:37,780 --> 00:16:41,790
at ang aming hash epektibong
upang ipamahagi na rin ang data,

340
00:16:41,790 --> 00:16:45,770
sa average na bawat isa sa mga naka-link
mga listahan sa bawat lokasyon array

341
00:16:45,770 --> 00:16:50,110
ay 1/10 ang laki ng kung tayo
Nagkaroon lamang ito bilang isang solong malaking

342
00:16:50,110 --> 00:16:51,650
listahan ng mga link sa lahat ng bagay sa loob nito.

343
00:16:51,650 --> 00:16:55,670
>> Kung ipamahagi namin na malaking naka-link
list sa buong 10 mga listahan na naka-link

344
00:16:55,670 --> 00:16:57,760
bawat listahan ay 1/10 ang laki.

345
00:16:57,760 --> 00:17:01,432
At kaya 10 beses na mas mabilis
upang maghanap sa pamamagitan ng.

346
00:17:01,432 --> 00:17:02,390
Kaya sabihin gawin ito muli.

347
00:17:02,390 --> 00:17:04,290
Ngayon sumira ni Ross Hayaan.

348
00:17:04,290 --> 00:17:07,540
>> At sabihin natin Ross, kapag ginagawa namin na
ang code hash makuha namin pabalik ay 2.

349
00:17:07,540 --> 00:17:10,630
Well ngayon dynamic allocate kami ng isang
bagong node, inilalagay namin Ross sa na node,

350
00:17:10,630 --> 00:17:14,900
at sinasabi namin ngayon lokasyon array
2, sa halip na tumuturo sa null,

351
00:17:14,900 --> 00:17:18,579
puntos sa ulo ng isang naka-link
list na ang tanging node ay Ross.

352
00:17:18,579 --> 00:17:22,660
At maaari naming gawin ito ng isa pang beses, kami ay
Maaari hash Rachel at makakuha hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc isang bagong node, ilagay Rachel in
buko, at sabihin ang isang lokasyon array

354
00:17:25,490 --> 00:17:27,839
4 ngayon puntos sa ulo
ng isang listahan ng mga link na

355
00:17:27,839 --> 00:17:31,420
mangyayari lamang ang sangkap na Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK ngunit kung ano ang mangyayari kung
kami ay may isang banggaan?

357
00:17:33,470 --> 00:17:38,560
Tayo'y makita kung paano namin pinangangasiwaan ang mga banggaan Ipaalam
gamit ang hiwalay na paraan chaining.

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

359
00:17:39,800 --> 00:17:41,094
Makuha namin ang hashcode 6.

360
00:17:41,094 --> 00:17:44,010
Sa aming nakaraang halimbawa kami ay lamang
pag-iimbak ng mga string sa array.

361
00:17:44,010 --> 00:17:45,980
Ito ay isang problema.

362
00:17:45,980 --> 00:17:48,444
>> Hindi namin nais na gumulpi
Joey, at kami Na nai

363
00:17:48,444 --> 00:17:51,110
makikita na maaari naming makakuha ng ilang clustering
problema kung susubukan namin at hakbang

364
00:17:51,110 --> 00:17:52,202
sa pamamagitan at sa probe.

365
00:17:52,202 --> 00:17:54,660
Ngunit paano kung namin lamang uri ng
gamutin ito sa parehong paraan, di ba?

366
00:17:54,660 --> 00:17:57,440
Ito ay tulad ng pagdagdag ng isang sangkap
sa ulo ng isang naka-link na listahan.

367
00:17:57,440 --> 00:18:00,220
Sabihin lang malloc espasyo para sa Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Susubukan naming sabihin sa susunod na pointer puntos Phoebe
sa lumang ulo ng naka-link na listahan,

369
00:18:04,764 --> 00:18:07,180
at pagkatapos lamang ng 6 na puntos sa mga
bagong ulo ng naka-link na listahan.

370
00:18:07,180 --> 00:18:10,150
At ngayon, tumingin, binago namin Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Maaari naming ngayon tindahan ng dalawang
elemento na may hashcode 6,

372
00:18:14,210 --> 00:18:17,170
at hindi namin ay may anumang problema.

373
00:18:17,170 --> 00:18:20,147
>> Iyan ay medyo marami ang lahat ng
doon ay upang chaining.

374
00:18:20,147 --> 00:18:21,980
At pagdudugtong ay tiyak
ang paraan na

375
00:18:21,980 --> 00:18:27,390
magiging pinaka-epektibo para sa iyo kung
ikaw ay pagtatago ng data sa isang hash table.

376
00:18:27,390 --> 00:18:30,890
Ngunit ang kumbinasyon ng mga
array at mga listahan ng link

377
00:18:30,890 --> 00:18:36,080
magkasama upang bumuo ng hash table talagang
kapansin-pansing mapabuti ang iyong kakayahan

378
00:18:36,080 --> 00:18:40,550
upang mag-imbak ng malaking halaga ng data, at
masyadong mabilis at mahusay sa paghahanap

379
00:18:40,550 --> 00:18:41,630
sa pamamagitan ng na data.

380
00:18:41,630 --> 00:18:44,150
>> Mayroong isa pang pa rin
istraktura ng data out there

381
00:18:44,150 --> 00:18:48,700
na maaaring kahit na maging isang bit
mas mahusay sa mga tuntunin ng guaranteeing

382
00:18:48,700 --> 00:18:51,920
na ang aming insertion, pagtanggal, at
maghanap ng mga oras ay mas mabilis pa.

383
00:18:51,920 --> 00:18:55,630
At kami na makita na sa isang video sa pagsusubok.

384
00:18:55,630 --> 00:18:58,930
Ako Doug Lloyd, ito ay CS50.

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