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

2
00:00:00,500 --> 00:00:01,900
[Music kucheza]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD N Kwa sasa wewe
kujua mengi kuhusu arrays,

5
00:00:09,150 --> 00:00:11,610
na unajua mengi kuhusu orodha zinazoungwa.

6
00:00:11,610 --> 00:00:13,650
Na tumekuwa kujadili
faida na hasara, tumekuwa

7
00:00:13,650 --> 00:00:16,620
kujadiliwa kwamba wanaohusishwa orodha
wanaweza kupata kubwa na ndogo,

8
00:00:16,620 --> 00:00:18,630
lakini wao kuchukua zaidi ukubwa.

9
00:00:18,630 --> 00:00:22,359
Arrays ni zaidi ya moja kwa moja kwa
kutumia, lakini wao ni restriktiva katika kiasi

10
00:00:22,359 --> 00:00:24,900
kama tuna kuweka ukubwa wa
safu mwanzoni kabisa

11
00:00:24,900 --> 00:00:26,910
na kisha sisi ni kukwama kwa hayo.

12
00:00:26,910 --> 00:00:30,470
>> Lakini hiyo ni, tumekuwa pretty much
nimechoka yote ya mada yetu

13
00:00:30,470 --> 00:00:33,040
kuhusu orodha wanaohusishwa na arrays.

14
00:00:33,040 --> 00:00:34,950
Au kuwa na sisi?

15
00:00:34,950 --> 00:00:37,720
Labda tunaweza kufanya kitu
hata zaidi ya ubunifu.

16
00:00:37,720 --> 00:00:40,950
Na kwamba aina ya lends
wazo la meza hash.

17
00:00:40,950 --> 00:00:46,680
>> Hivyo katika meza hash tunakwenda kujaribu
kuchanganya safu na orodha wanaohusishwa.

18
00:00:46,680 --> 00:00:49,520
Sisi ni kwenda kuchukua faida
wa safu, kama random kupata,

19
00:00:49,520 --> 00:00:53,510
kuwa na uwezo wa tu kwenda safu
kipengele 4 au safu kipengele 8

20
00:00:53,510 --> 00:00:55,560
bila ya kuwa na iterate hela.

21
00:00:55,560 --> 00:00:57,260
Hiyo ni pretty kufunga, sawa?

22
00:00:57,260 --> 00:01:00,714
>> Lakini pia wanataka kuwa na takwimu zetu
muundo wa kuwa na uwezo wa kukua na kuogopa.

23
00:01:00,714 --> 00:01:02,630
Hatuna haja, hatufanyi
wanataka kuwa vikwazo.

24
00:01:02,630 --> 00:01:04,588
Na tunataka kuwa na uwezo
kuongeza na kuondoa mambo

25
00:01:04,588 --> 00:01:08,430
kwa urahisi sana, ambayo kama unakumbuka,
ni ngumu sana kwa safu.

26
00:01:08,430 --> 00:01:11,650
Na tunaweza kuwaita hii
jambo jipya meza hash.

27
00:01:11,650 --> 00:01:15,190
>> Na kama kutekelezwa kwa usahihi,
sisi ni aina ya kuchukua

28
00:01:15,190 --> 00:01:18,150
faida ya data zote mbili
miundo umefanya tayari kuona,

29
00:01:18,150 --> 00:01:19,880
arrays na orodha wanaohusishwa.

30
00:01:19,880 --> 00:01:23,070
Kuingizwa unaweza kuanza
huwa kuelekea theta ya 1.

31
00:01:23,070 --> 00:01:26,207
Theta sisi si kweli kujadiliwa,
lakini theta ni tu kesi wastani,

32
00:01:26,207 --> 00:01:27,540
nini hasa kitatokea.

33
00:01:27,540 --> 00:01:29,680
Wewe si daima kwenda
na mazingira ya kesi mbaya,

34
00:01:29,680 --> 00:01:32,555
na wewe si daima kwenda na
bora kesi, hivyo nini

35
00:01:32,555 --> 00:01:33,900
wastani mazingira?

36
00:01:33,900 --> 00:01:36,500
>> Naam kuingizwa wastani
ndani ya meza hash

37
00:01:36,500 --> 00:01:39,370
Unaweza kuanza kupata karibu na wakati mara kwa mara.

38
00:01:39,370 --> 00:01:41,570
Na kufutwa wanaweza kupata
karibu na wakati mara kwa mara.

39
00:01:41,570 --> 00:01:44,440
Na chaguo-wanaweza kupata
karibu na wakati mara kwa mara.

40
00:01:44,440 --> 00:01:48,600
That's-- hatuna data
muundo bado kwamba anaweza kufanya hivyo,

41
00:01:48,600 --> 00:01:51,180
na hivyo hii tayari sauti
kama jambo pretty kubwa.

42
00:01:51,180 --> 00:01:57,010
Tumekuwa kweli umepunguza
hasara ya kila juu yake mwenyewe.

43
00:01:57,010 --> 00:01:59,160
>> Kupata utendaji huu
kuboresha ingawa, sisi

44
00:01:59,160 --> 00:02:03,580
haja ya kufikiri upya jinsi sisi kuongeza
data katika muundo.

45
00:02:03,580 --> 00:02:07,380
Hasa tunataka
na takwimu yenyewe kutuambia

46
00:02:07,380 --> 00:02:09,725
ambapo ni lazima kwenda katika muundo.

47
00:02:09,725 --> 00:02:12,850
Na kama sisi basi haja ya kuona kama ni katika
muundo, ikiwa tunahitaji kupata hiyo,

48
00:02:12,850 --> 00:02:16,610
tunataka kuangalia data
tena na kuwa na uwezo wa ufanisi,

49
00:02:16,610 --> 00:02:18,910
kutumia takwimu, nasibu kupata huduma hiyo.

50
00:02:18,910 --> 00:02:20,700
Tu kwa kuangalia
data tunapaswa kuwa

51
00:02:20,700 --> 00:02:25,890
wazo la ambapo hasa tuko
kwenda kupata hiyo katika meza hash.

52
00:02:25,890 --> 00:02:28,770
>> Sasa upande wa chini ya hash
meza ni kwamba wao ni kweli

53
00:02:28,770 --> 00:02:31,770
pretty mbaya wakati kuagiza au kuchagua data.

54
00:02:31,770 --> 00:02:34,970
Na kwa kweli, kama kuanza
kuzitumia ili au aina

55
00:02:34,970 --> 00:02:37,990
data kupoteza wote wa
faida wewe hapo awali

56
00:02:37,990 --> 00:02:40,710
alikuwa katika suala la kuingizwa na kufutwa.

57
00:02:40,710 --> 00:02:44,060
Wakati inakuwa karibu na
theta ya n, na tumekuwa kimsingi

58
00:02:44,060 --> 00:02:45,530
inasimulia katika orodha wanaohusishwa.

59
00:02:45,530 --> 00:02:48,850
Na hivyo sisi tu wanataka kutumia hash
meza kama sisi hawajali kuhusu

60
00:02:48,850 --> 00:02:51,490
iwapo data ni Iliyopangwa.

61
00:02:51,490 --> 00:02:54,290
Kwa mazingira ambayo
utasikia matumizi yao katika CS50

62
00:02:54,290 --> 00:02:58,900
pengine hawana huduma
kwamba data ni Iliyopangwa.

63
00:02:58,900 --> 00:03:03,170
>> Hivyo meza hash ni mchanganyiko
ya vipande viwili tofauti

64
00:03:03,170 --> 00:03:04,980
ambayo sisi ni ukoo.

65
00:03:04,980 --> 00:03:07,930
Kwanza ni kazi, ambayo
sisi kwa kawaida kuwaita heshi.

66
00:03:07,930 --> 00:03:11,760
Na kwamba heshi ni kwenda
kurudi baadhi integer zisizo hasi, ambayo

67
00:03:11,760 --> 00:03:14,870
sisi kwa kawaida kuwaita Msimboreli, sawa?

68
00:03:14,870 --> 00:03:20,230
Kipande cha pili ni safu, ambayo ni
uwezo wa kuhifadhi data ya aina sisi

69
00:03:20,230 --> 00:03:22,190
unataka mahali katika muundo data.

70
00:03:22,190 --> 00:03:24,310
Tutaweza kushikilia mbali juu ya
wanaohusishwa orodha kipengele kwa sasa

71
00:03:24,310 --> 00:03:27,810
na tu kuanza na misingi ya
hash meza ya kupata kichwa yako karibu yake,

72
00:03:27,810 --> 00:03:30,210
na kisha tutaweza labda pigo
akili yako wakati kidogo sisi

73
00:03:30,210 --> 00:03:32,920
kuchanganya arrays na orodha kiungo pamoja.

74
00:03:32,920 --> 00:03:35,590
>> Wazo msingi ingawa
ni sisi kuchukua baadhi ya data.

75
00:03:35,590 --> 00:03:37,860
Sisi kuendesha kwamba data kwa njia ya
heshi.

76
00:03:37,860 --> 00:03:41,980
Na hivyo data ni kusindika
na mtemi idadi, sawa?

77
00:03:41,980 --> 00:03:44,890
Na kisha kwa idadi hiyo
sisi tu kuhifadhi data

78
00:03:44,890 --> 00:03:48,930
tunataka kuhifadhi katika
safu katika eneo hilo.

79
00:03:48,930 --> 00:03:53,990
Hivyo kwa mfano tuna labda
huu meza hash ya masharti.

80
00:03:53,990 --> 00:03:57,350
Ni got mambo 10 ndani yake, hivyo
tunaweza fit 10 masharti ndani yake.

81
00:03:57,350 --> 00:03:59,320
>> Hebu sema tunataka hash Yohana.

82
00:03:59,320 --> 00:04:02,979
Hivyo John kama data tunataka Insert
ndani ya hii meza hash mahali fulani.

83
00:04:02,979 --> 00:04:03,770
Wapi sisi kuiweka?

84
00:04:03,770 --> 00:04:05,728
Naam kawaida kwa
safu hadi sasa sisi pengine

85
00:04:05,728 --> 00:04:07,610
ingekuwa kuiweka katika safu eneo 0.

86
00:04:07,610 --> 00:04:09,960
Lakini sasa tuna hii mpya heshi.

87
00:04:09,960 --> 00:04:13,180
>> Na hebu kusema kwamba sisi kukimbia John
kwa njia hii kazi hash

88
00:04:13,180 --> 00:04:15,417
na ni mtemi 4.

89
00:04:15,417 --> 00:04:17,500
Naam hapo ndipo tuko
atataka kuweka Yohana.

90
00:04:17,500 --> 00:04:22,050
Tunataka kuweka John katika safu eneo
4, kwa sababu kama sisi hash John again--

91
00:04:22,050 --> 00:04:23,810
hebu sema baadaye sisi
unataka kutafuta na kuona

92
00:04:23,810 --> 00:04:26,960
kama John ipo katika hash hii
table-- zote tunahitaji kufanya

93
00:04:26,960 --> 00:04:30,310
ni kukimbia kwa njia hash sawa
kazi, kupata namba 4 nje,

94
00:04:30,310 --> 00:04:33,929
na kuwa na uwezo wa kupata John
mara moja katika mfumo wetu wa data.

95
00:04:33,929 --> 00:04:34,720
Hiyo ni nzuri sana.

96
00:04:34,720 --> 00:04:36,928
>> Hebu sema sisi sasa kufanya hivyo
tena, tunataka hash Paulo.

97
00:04:36,928 --> 00:04:39,446
Tunataka kuongeza Paul
ndani ya hii meza hash.

98
00:04:39,446 --> 00:04:42,070
Hebu kusema kwamba wakati huu sisi kukimbia
Paul kupitia heshi,

99
00:04:42,070 --> 00:04:44,600
Msimboreli kwamba ni yanayotokana ni 6.

100
00:04:44,600 --> 00:04:47,340
Naam sasa tunaweza kuweka Paul
katika safu eneo 6.

101
00:04:47,340 --> 00:04:50,040
Na kama sisi haja ya kuangalia up kama
Paulo yuko huu meza hash,

102
00:04:50,040 --> 00:04:53,900
wote tunahitaji kufanya ni kukimbia Paul
kupitia heshi tena

103
00:04:53,900 --> 00:04:55,830
na sisi ni kwenda kupata 6 nje tena.

104
00:04:55,830 --> 00:04:57,590
>> Na kisha sisi tu kuangalia
katika safu eneo 6.

105
00:04:57,590 --> 00:04:58,910
Je, Paulo huko?

106
00:04:58,910 --> 00:05:00,160
Kama ni hivyo, yeye ni katika meza hash.

107
00:05:00,160 --> 00:05:01,875
Je, Paulo si huko?

108
00:05:01,875 --> 00:05:03,000
Yeye si katika meza hash.

109
00:05:03,000 --> 00:05:05,720
Ni pretty moja kwa moja.

110
00:05:05,720 --> 00:05:07,770
>> Sasa ni jinsi gani unaweza kufafanua heshi?

111
00:05:07,770 --> 00:05:11,460
Naam kuna kweli hakuna kikomo kwa
idadi ya kutokea kazi hash.

112
00:05:11,460 --> 00:05:14,350
Kwa kweli kuna idadi ya kweli,
ndio mzuri kwenye mtandao.

113
00:05:14,350 --> 00:05:17,560
Kuna idadi ya kweli,
ndio mbaya kweli kweli kwenye mtandao.

114
00:05:17,560 --> 00:05:21,080
Ni pia rahisi sana
kuandika moja mbaya.

115
00:05:21,080 --> 00:05:23,760
>> Basi nini hufanya up nzuri
kazi hash, sawa?

116
00:05:23,760 --> 00:05:27,280
Naam nzuri heshi lazima
kutumia tu data kuwa heshi,

117
00:05:27,280 --> 00:05:29,420
na wote wa data kuwa heshi.

118
00:05:29,420 --> 00:05:32,500
Hivyo hatutaki kutumia kitu,
hatuna kuingiza chochote

119
00:05:32,500 --> 00:05:35,560
kingine chochote zaidi data.

120
00:05:35,560 --> 00:05:37,080
Na tunataka kutumia yote ya data.

121
00:05:37,080 --> 00:05:39,830
Hatutaki kutumia tu kipande
yake, tunataka kutumia yote.

122
00:05:39,830 --> 00:05:41,710
Kazi hash lazima
pia kuwa deterministic.

123
00:05:41,710 --> 00:05:42,550
Hiyo ina maana gani?

124
00:05:42,550 --> 00:05:46,200
Vizuri maana yake ni kwamba kila wakati sisi
kupita halisi kipande kimoja cha data

125
00:05:46,200 --> 00:05:50,040
ndani ya heshi sisi daima
kupata Msimboreli huo nje.

126
00:05:50,040 --> 00:05:52,870
Kama mimi kupita John katika
kazi hash mimi kupata nje 4.

127
00:05:52,870 --> 00:05:56,110
Mimi lazima kuwa na uwezo wa kufanya hivyo 10,000
Mimi na nyakati daima utasikia kupata 4.

128
00:05:56,110 --> 00:06:00,810
Hivyo hakuna idadi random ufanisi
inaweza kushiriki katika hash yetu tables--

129
00:06:00,810 --> 00:06:02,750
katika kazi yetu hash.

130
00:06:02,750 --> 00:06:05,750
>> Kazi hash lazima pia
enhetligt kusambaza data.

131
00:06:05,750 --> 00:06:09,700
Kama kila wakati wewe kukimbia data kupitia
kazi hash kupata Msimboreli 0,

132
00:06:09,700 --> 00:06:11,200
kwamba pengine si kubwa sana, sawa?

133
00:06:11,200 --> 00:06:14,600
Pengine wanataka kubwa
mbalimbali ya namba hash.

134
00:06:14,600 --> 00:06:17,190
Pia mambo inaweza kuenea
nje katika meza.

135
00:06:17,190 --> 00:06:23,210
Na pia itakuwa kubwa kama kweli
data kama hizo, kama John na Jonathan,

136
00:06:23,210 --> 00:06:26,320
labda walikuwa kuenea nje kupima
maeneo mbalimbali katika meza hash.

137
00:06:26,320 --> 00:06:28,750
Hiyo itakuwa faida nzuri.

138
00:06:28,750 --> 00:06:31,250
>> Hapa ni mfano wa heshi.

139
00:06:31,250 --> 00:06:33,150
Niliandika hii moja up mapema.

140
00:06:33,150 --> 00:06:35,047
Ni si hasa
nzuri heshi

141
00:06:35,047 --> 00:06:37,380
kwa sababu ya kuwa si kweli
kubeba kwenda katika hivi sasa.

142
00:06:37,380 --> 00:06:41,040
Lakini unaona nini kinaendelea hapa?

143
00:06:41,040 --> 00:06:44,420
Inaonekana kama sisi ni kutangaza variable
kuitwa jumla na kuiandaa sawa na 0.

144
00:06:44,420 --> 00:06:50,010
Na kisha inaonekana mimi nina kufanya kitu
hivyo muda mrefu kama strstr [j] si sawa

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

146
00:06:52,490 --> 00:06:54,870
Je, Mimi kufanya huko?

147
00:06:54,870 --> 00:06:57,440
>> Hii ni kimsingi tu mwingine
njia za utekelezaji [? strl?]

148
00:06:57,440 --> 00:06:59,773
na kuchunguza wakati wewe wameweza
kufikiwa mwisho wa kamba.

149
00:06:59,773 --> 00:07:02,480
Hivyo sina kwa kweli
mahesabu ya urefu wa kamba,

150
00:07:02,480 --> 00:07:05,640
Mimi tu kutumia wakati mimi kugonga
backslash 0 tabia Najua

151
00:07:05,640 --> 00:07:07,185
Nimekuwa kufikiwa mwisho wa kamba.

152
00:07:07,185 --> 00:07:09,560
Na kisha mimi nina kwenda kuweka
iterating kupitia kamba kwamba,

153
00:07:09,560 --> 00:07:15,310
kuongeza strstr [j] kwa jumla, na kisha saa
mwisho wa siku kwenda na kurudi kiasi mod

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

155
00:07:16,200 --> 00:07:18,700
>> Kimsingi hash hii yote
kazi ni kufanya ni kuongeza up

156
00:07:18,700 --> 00:07:23,450
wote wa maadili ASCII ya
kamba yangu, na kisha ni

157
00:07:23,450 --> 00:07:26,390
kurudi baadhi Msimboreli
modded na HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Pengine ni ukubwa
wa safu yangu, sawa?

159
00:07:29,790 --> 00:07:33,160
Sitaki kuwa kupata hash
codes ikiwa safu yangu ni ya kawaida 10,

160
00:07:33,160 --> 00:07:35,712
Sitaki kuwa kupata
codes nje hash 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, siwezi kuweka mambo katika
maeneo hayo ya safu,

162
00:07:38,690 --> 00:07:39,790
hiyo inaweza kuwa kinyume cha sheria.

163
00:07:39,790 --> 00:07:42,130
Ningependa kuteseka segmentation kosa.

164
00:07:42,130 --> 00:07:45,230
>> Sasa hapa ni mwingine haraka kando.

165
00:07:45,230 --> 00:07:48,470
Kwa ujumla pengine wewe si kwenda
unataka kuandika yako kazi hash mwenyewe.

166
00:07:48,470 --> 00:07:50,997
Ni kweli kidogo ya
sanaa, si sayansi.

167
00:07:50,997 --> 00:07:52,580
Na kuna mengi kwamba huenda katika yao.

168
00:07:52,580 --> 00:07:55,288
Biashara, kama nilivyosema, ni kamili
ya kazi nzuri kwa kweli hash,

169
00:07:55,288 --> 00:07:58,470
na unapaswa kutumia biashara kwa
kupata kazi hash kwa sababu ni kweli

170
00:07:58,470 --> 00:08:03,230
aina tu ya lazima
kupoteza muda wa kujenga yako mwenyewe.

171
00:08:03,230 --> 00:08:05,490
>> Unaweza kuandika ndio rahisi
kwa madhumuni ya kupima.

172
00:08:05,490 --> 00:08:08,323
Lakini wakati wewe kweli ni kwenda
kuanza hashing data na hifadhi hiyo

173
00:08:08,323 --> 00:08:10,780
ndani ya hash meza uko
pengine atataka

174
00:08:10,780 --> 00:08:14,580
kutumia baadhi ya kazi kwamba ilitokana
kwa ajili yenu, ambayo ipo kwenye mtandao.

175
00:08:14,580 --> 00:08:17,240
Kama huna tu kuwa na uhakika
wanaelezea vyanzo yako.

176
00:08:17,240 --> 00:08:21,740
Hakuna sababu kwa
plagiarize chochote hapa.

177
00:08:21,740 --> 00:08:25,370
>> Jumuiya ya sayansi ya kompyuta ni
dhahiri kuongezeka, na kwa kweli maadili

178
00:08:25,370 --> 00:08:28,796
wazi chanzo, na kwa kweli ni muhimu
wanaelezea vyanzo yako ili watu

179
00:08:28,796 --> 00:08:30,670
wanaweza kupata maelezo kwa
kazi kwamba wao ni

180
00:08:30,670 --> 00:08:32,312
kufanya kwa manufaa ya jamii.

181
00:08:32,312 --> 00:08:34,020
Hivyo daima kuwa sure--
na si tu kwa ajili hash

182
00:08:34,020 --> 00:08:37,270
kazi, lakini kwa ujumla wakati
kutumia kanuni kutoka chanzo nje,

183
00:08:37,270 --> 00:08:38,299
Daima wanaelezea chanzo wako.

184
00:08:38,299 --> 00:08:43,500
Kutoa mikopo kwa mtu ambaye alifanya
baadhi ya kazi hivyo huna kwa.

185
00:08:43,500 --> 00:08:46,720
>> OK hivyo hebu kupitia upya hii
hash meza kwa ajili ya pili.

186
00:08:46,720 --> 00:08:48,780
Hii ni pale ambapo sisi kushoto
mbali baada ya sisi kuingizwa

187
00:08:48,780 --> 00:08:53,300
Yohana na Paulo katika hii meza hash.

188
00:08:53,300 --> 00:08:55,180
Je, unaweza kuona tatizo hapa?

189
00:08:55,180 --> 00:08:58,410
Unaweza kuona mbili.

190
00:08:58,410 --> 00:09:02,240
Lakini hasa, je,
kuona tatizo hii inawezekana?

191
00:09:02,240 --> 00:09:06,770
>> Nini kama mimi hash Ringo, na
zinageuka kuwa baada ya usindikaji

192
00:09:06,770 --> 00:09:14,000
kwamba data kwa njia ya heshi
Ringo pia yanayotokana Msimboreli 6.

193
00:09:14,000 --> 00:09:16,810
Nimekuwa tayari got data kwenye
hashcode-- safu eneo 6.

194
00:09:16,810 --> 00:09:22,000
Hivyo ni pengine ni kwenda kuwa kidogo
tatizo kwa ajili yangu sasa, sawa?

195
00:09:22,000 --> 00:09:23,060
>> Tunatoa wito huu mgongano.

196
00:09:23,060 --> 00:09:26,460
Na mgongano hutokea wakati watu wawili
vipande vya data kukimbia kwa njia ya hash sawa

197
00:09:26,460 --> 00:09:29,200
kazi mavuno Msimboreli huo.

198
00:09:29,200 --> 00:09:32,850
Takribani sisi bado wanataka kupata wawili
vipande vya data katika meza hash,

199
00:09:32,850 --> 00:09:36,330
vinginevyo sisi bila kuwa mbio Ringo
kiholela kupitia heshi.

200
00:09:36,330 --> 00:09:40,870
Sisi labda wanataka kupata
Ringo ndani ya kwamba safu.

201
00:09:40,870 --> 00:09:46,070
>> Je, sisi kufanya hivyo ingawa, kama yeye
na Paulo wote wawili mavuno Msimboreli 6?

202
00:09:46,070 --> 00:09:49,520
Hatutaki overwrite Paulo,
tunataka Paulo kuwa huko pia.

203
00:09:49,520 --> 00:09:52,790
Kwa hiyo, tunahitaji kutafuta njia ya kupata
mambo katika meza hash kwamba

204
00:09:52,790 --> 00:09:56,550
bado kulinda haraka yetu
kuingizwa na haraka kuangalia juu.

205
00:09:56,550 --> 00:10:01,350
Na njia moja ya kukabiliana nayo ni
kufanya kitu kinachoitwa linear uchunguzi.

206
00:10:01,350 --> 00:10:04,170
>> Kutumia njia hii kama tuna
mgongano, vizuri, tunafanya nini?

207
00:10:04,170 --> 00:10:08,580
Naam hatuwezi kumtia safu eneo
6, au chochote Msimboreli ilitokana,

208
00:10:08,580 --> 00:10:10,820
hebu kuweka naye katika Msimboreli pamoja na 1.

209
00:10:10,820 --> 00:10:13,670
Na kama hiyo full hebu
kumtia Msimboreli pamoja na 2.

210
00:10:13,670 --> 00:10:17,420
Faida ya kiumbe hiki kama yeye ni
si hasa ambapo tunafikiri yeye ni,

211
00:10:17,420 --> 00:10:20,850
na tuna kuanza kutafuta,
labda hatuna kwenda mbali mno.

212
00:10:20,850 --> 00:10:23,900
Labda hatuna kutafuta
mambo yote n ya meza hash.

213
00:10:23,900 --> 00:10:25,790
Labda tuna kutafuta
wanandoa wao.

214
00:10:25,790 --> 00:10:30,680
>> Na hivyo bado tuko kwenye kuchunga
kwamba wastani kesi kuwa karibu na 1 vs

215
00:10:30,680 --> 00:10:34,280
karibu na n, hivyo labda kwamba kutakuwa na kazi.

216
00:10:34,280 --> 00:10:38,010
Basi hebu angalia jinsi hii
inaweza kufanya kazi nje katika hali halisi.

217
00:10:38,010 --> 00:10:41,460
Na hebu angalia kama labda sisi inaweza kuchunguza
Tatizo ambayo inaweza kutokea hapa.

218
00:10:41,460 --> 00:10:42,540
>> Hebu sema sisi hash Bart.

219
00:10:42,540 --> 00:10:45,581
Hivyo sasa sisi ni kwenda kukimbia kuweka mpya
ya masharti kupitia heshi,

220
00:10:45,581 --> 00:10:48,460
na sisi kukimbia Bart kupitia hash
kazi, sisi kupata Msimboreli 6.

221
00:10:48,460 --> 00:10:52,100
Sisi kuangalia, tunaona 6 ni
tupu, ili tuweze kuweka Bart huko.

222
00:10:52,100 --> 00:10:55,410
>> Sasa sisi hash Lisa na kwamba
pia inazalisha Msimboreli 6.

223
00:10:55,410 --> 00:10:58,330
Naam sasa kwamba sisi ni kutumia hii
linear uchunguzi mbinu sisi kuanza saa 6,

224
00:10:58,330 --> 00:10:59,330
tunaona kwamba 6 ni kamili.

225
00:10:59,330 --> 00:11:00,990
Hatuwezi kuweka Lisa katika 6.

226
00:11:00,990 --> 00:11:02,090
Hivyo wapi sisi kwenda?

227
00:11:02,090 --> 00:11:03,280
Hebu kwenda 7.

228
00:11:03,280 --> 00:11:04,610
7 ya tupu, hivyo kwamba kazi.

229
00:11:04,610 --> 00:11:06,510
Basi hebu kuweka Lisa huko.

230
00:11:06,510 --> 00:11:10,200
>> Sasa sisi hash Homer na sisi kupata 7.

231
00:11:10,200 --> 00:11:13,380
OK vizuri tunajua kwamba 7 kamili
sasa, hivyo hatuwezi kuweka Homer huko.

232
00:11:13,380 --> 00:11:14,850
Basi hebu kwenda hadi 8.

233
00:11:14,850 --> 00:11:15,664
Ni 8 inapatikana?

234
00:11:15,664 --> 00:11:18,330
Yeah, na 8 ya karibu na 7, hivyo kama
tuna kuanza kutafuta tuko

235
00:11:18,330 --> 00:11:20,020
si kwenda na kwenda mbali sana.

236
00:11:20,020 --> 00:11:22,860
Na hivyo hebu kuweka Homer saa 8.

237
00:11:22,860 --> 00:11:25,151
>> Sasa sisi hash Maggie na
anarudi 3, kuwashukuru wema

238
00:11:25,151 --> 00:11:26,650
sisi ni uwezo wa kuweka tu Maggie huko.

239
00:11:26,650 --> 00:11:29,070
Hatuna kufanya lolote
aina ya uchunguzi kwa ajili hiyo.

240
00:11:29,070 --> 00:11:32,000
Sasa sisi hash Marge, na
Marge pia anarudi 6.

241
00:11:32,000 --> 00:11:39,560
>> Naam 6 ni kamili, 7 ni kamili, 8 ni kamili,
9, wote wanafunzi wa haki kumshukuru Mungu, 9 ni tupu.

242
00:11:39,560 --> 00:11:41,600
Siwezi kuweka Marge saa 9.

243
00:11:41,600 --> 00:11:45,280
Tayari tunaweza kuona kwamba sisi ni mapya
kuwa na tatizo hili ambapo sasa tuko

244
00:11:45,280 --> 00:11:48,780
kuanzia kwa kunyoosha mambo aina
ya mbali mbali na namba zao hash.

245
00:11:48,780 --> 00:11:52,960
Na kwamba theta ya 1, kwamba wastani
kesi ya kuwa wakati mara kwa mara,

246
00:11:52,960 --> 00:11:56,560
ni mapya ya kupata more-- kidogo
kuanzia huwa kidogo zaidi

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

248
00:11:58,050 --> 00:12:01,270
Sisi ni mapya ya kupoteza kwamba
faida ya meza hash.

249
00:12:01,270 --> 00:12:03,902
>> Tatizo hili kwamba sisi tu kuona
ni kitu kinachoitwa kuunganisha.

250
00:12:03,902 --> 00:12:06,360
Na nini ni mbaya kuhusu
kuunganisha ni kwamba mara sasa

251
00:12:06,360 --> 00:12:09,606
na mambo mawili ambayo ni bega kwa
upande inafanya kuwa hata zaidi,

252
00:12:09,606 --> 00:12:11,480
una mara mbili
nafasi, kwamba wewe ni kwenda

253
00:12:11,480 --> 00:12:13,516
kuwa na mgongano mwingine
na kwamba nguzo,

254
00:12:13,516 --> 00:12:14,890
na nguzo kukua kwa moja.

255
00:12:14,890 --> 00:12:19,640
Na wewe utakuwa kuendelea kukua na kuongezeka
uwezekano yako ya kuwa na mgongano.

256
00:12:19,640 --> 00:12:24,470
Na hatimaye ni tu kama mbaya
kama si kuchagua data wakati wote.

257
00:12:24,470 --> 00:12:27,590
>> Tatizo jingine ingawa ni sisi
bado, na hadi sasa hadi hatua hii,

258
00:12:27,590 --> 00:12:30,336
sisi been tu aina ya
kuelewa nini meza hash ni,

259
00:12:30,336 --> 00:12:31,960
sisi bado tu na chumba kwa 10 masharti.

260
00:12:31,960 --> 00:12:37,030
Kama tunataka kuendelea hash
wananchi wa Springfield,

261
00:12:37,030 --> 00:12:38,790
tunaweza tu kupata 10 kati yao huko.

262
00:12:38,790 --> 00:12:42,619
Na kama sisi kujaribu na kuongeza ya 11 au 12,
hatuna mahali pa kuziweka.

263
00:12:42,619 --> 00:12:45,660
Tunaweza tu kuwa inazunguka kuzunguka katika
duru kujaribu kupata doa tupu,

264
00:12:45,660 --> 00:12:49,000
na sisi labda kukwama
katika kitanzi usio.

265
00:12:49,000 --> 00:12:51,810
>> Hivyo aina hii ya lends kwa wazo
ya kitu kinachoitwa chaining.

266
00:12:51,810 --> 00:12:55,790
Na hii ni wapi tunakwenda kuleta
orodha wanaohusishwa nyuma katika picha.

267
00:12:55,790 --> 00:13:01,300
Nini kama badala ya kuhifadhi tu
data yenyewe katika safu,

268
00:13:01,300 --> 00:13:04,471
kila kipengele cha safu naweza
kushikilia vipande mbalimbali ya data?

269
00:13:04,471 --> 00:13:05,970
Vizuri kwamba haina mantiki, sawa?

270
00:13:05,970 --> 00:13:09,280
Tunajua kwamba safu Unaweza tu
hold-- kila kipengele cha safu

271
00:13:09,280 --> 00:13:12,930
inaweza tu kushikilia kipande kimoja
wa takwimu za aina hiyo data.

272
00:13:12,930 --> 00:13:16,750
>> Lakini nini kama aina hiyo data
ni orodha wanaohusishwa, sawa?

273
00:13:16,750 --> 00:13:19,830
Basi nini kama kila
kipengele cha safu alikuwa

274
00:13:19,830 --> 00:13:22,790
pointer kichwa cha orodha wanaohusishwa?

275
00:13:22,790 --> 00:13:24,680
Na kisha tunaweza kujenga
orodha ya wale wanaohusishwa

276
00:13:24,680 --> 00:13:27,120
na kukua yao kiholela,
kwa sababu orodha wanaohusishwa kuruhusu

277
00:13:27,120 --> 00:13:32,090
sisi kukua na kuogopa mengi zaidi
smidigt kuliko safu gani.

278
00:13:32,090 --> 00:13:34,210
Basi nini kama sisi sasa kutumia,
sisi kujiinua hii, sawa?

279
00:13:34,210 --> 00:13:37,760
Sisi kuanza kukua hii minyororo
nje ya maeneo haya safu.

280
00:13:37,760 --> 00:13:40,740
>> Sasa tunaweza fit usio
kiasi cha data, au si usio na mipaka,

281
00:13:40,740 --> 00:13:44,170
Kiasi holela wa
data, ndani ya hash yetu meza

282
00:13:44,170 --> 00:13:47,760
bila hata kukimbia ndani
tatizo la mgongano.

283
00:13:47,760 --> 00:13:50,740
Tumekuwa pia kuondolewa
kuunganisha kwa kufanya hivyo.

284
00:13:50,740 --> 00:13:54,380
Na vizuri tunajua kwamba wakati sisi kuingiza
ndani ya orodha wanaohusishwa, kama unakumbuka

285
00:13:54,380 --> 00:13:57,779
kutoka sehemu yetu juu ya orodha wanaohusishwa, mmoja-
orodha wanaohusishwa na orodha doubly wanaohusishwa,

286
00:13:57,779 --> 00:13:59,070
ni mara kwa mara wakati wa operesheni.

287
00:13:59,070 --> 00:14:00,710
Sisi ni kuongeza tu na mbele.

288
00:14:00,710 --> 00:14:04,400
>> Na kwa ajili ya kuangalia juu, vizuri tunajua
ili kuangalia juu katika orodha wanaohusishwa

289
00:14:04,400 --> 00:14:05,785
inaweza kuwa tatizo, sawa?

290
00:14:05,785 --> 00:14:07,910
Tuna kutafuta njia
kuanzia mwanzo hadi mwisho.

291
00:14:07,910 --> 00:14:10,460
Hakuna random
upatikanaji katika orodha wanaohusishwa.

292
00:14:10,460 --> 00:14:15,610
Lakini kama badala ya kuwa moja wanaohusishwa
orodha ambapo chaguo-itakuwa O ya n,

293
00:14:15,610 --> 00:14:19,590
sasa tuna orodha 10 wanaohusishwa,
au orodha 1,000 wanaohusishwa,

294
00:14:19,590 --> 00:14:24,120
sasa ni O ya n kugawanywa na 10,
au O ya n kugawanywa na 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Na wakati sisi walikuwa wanazungumza
kinadharia kuhusu utata

296
00:14:26,940 --> 00:14:30,061
sisi kupuuza constants, katika halisi
dunia hayo kwa kweli suala hilo,

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

298
00:14:30,560 --> 00:14:33,080
Sisi kwa kweli utakuwa taarifa
kwamba hii hutokea

299
00:14:33,080 --> 00:14:36,610
kuendesha mara 10 kwa kasi,
au mara 1,000 kwa kasi,

300
00:14:36,610 --> 00:14:41,570
kwa sababu sisi ni kusambaza moja kwa muda mrefu
mlolongo hela minyororo 1,000 ndogo.

301
00:14:41,570 --> 00:14:45,090
Na hivyo kila wakati tuna kutafuta
kwa njia ya moja ya minyororo wale tunaweza

302
00:14:45,090 --> 00:14:50,290
kupuuza 999 minyororo sisi hawajali
kuhusu, na tu kutafuta kwamba mtu.

303
00:14:50,290 --> 00:14:53,220
>> Ambayo ni juu ya wastani kwa
kuwa mara 1,000 mfupi.

304
00:14:53,220 --> 00:14:56,460
Na hivyo sisi bado ni aina ya
kuelekea kesi hii wastani kuchunga

305
00:14:56,460 --> 00:15:01,610
ya kuwa wakati mara kwa mara, lakini
tu kwa sababu sisi ni leveraging

306
00:15:01,610 --> 00:15:03,730
kugawa na baadhi ya mara kwa mara sababu kubwa.

307
00:15:03,730 --> 00:15:05,804
Hebu angalia jinsi hii huenda
kweli kuangalia ingawa.

308
00:15:05,804 --> 00:15:08,720
Hivyo hii ilikuwa hash meza tulikuwa
kabla ya sisi alitangaza meza hash kwamba

309
00:15:08,720 --> 00:15:10,270
alikuwa na uwezo wa kuhifadhi 10 masharti.

310
00:15:10,270 --> 00:15:11,728
Sisi siyo kwenda kufanya hivyo tena.

311
00:15:11,728 --> 00:15:13,880
Sisi tayari kujua
mapungufu ya njia hiyo.

312
00:15:13,880 --> 00:15:20,170
Sasa hash yetu meza kwenda kuwa
safu ya 10 nodes, kuyatumia

313
00:15:20,170 --> 00:15:22,120
na wakuu wa orodha wanaohusishwa.

314
00:15:22,120 --> 00:15:23,830
>> Na hivi sasa ni null.

315
00:15:23,830 --> 00:15:26,170
Kila mmoja wa wale kuyatumia 10 ni batili.

316
00:15:26,170 --> 00:15:29,870
Kuna kitu katika yetu
hash meza hivi sasa.

317
00:15:29,870 --> 00:15:32,690
>> Sasa hebu kuanza kuweka baadhi
mambo ndani ya hii meza hash.

318
00:15:32,690 --> 00:15:35,440
Na hebu angalia jinsi njia hii ni
kwenda kufaidika sisi kidogo.

319
00:15:35,440 --> 00:15:36,760
Hebu sasa hash Joey.

320
00:15:36,760 --> 00:15:40,210
Tutaweza kukimbia kamba Joey kupitia
heshi na sisi kurudi 6.

321
00:15:40,210 --> 00:15:41,200
Vizuri tunafanya nini sasa?

322
00:15:41,200 --> 00:15:44,090
>> Naam sasa kufanya kazi na orodha wanaohusishwa,
sisi siyo kufanya kazi na arrays.

323
00:15:44,090 --> 00:15:45,881
Na wakati sisi ni kufanya kazi
na orodha wanaohusishwa sisi

324
00:15:45,881 --> 00:15:49,790
kujua tunahitaji kuanza dynamically
kugawa nafasi na kujenga minyororo.

325
00:15:49,790 --> 00:15:54,020
Hiyo ni aina ya how-- wale ni msingi
mambo ya kujenga orodha wanaohusishwa.

326
00:15:54,020 --> 00:15:57,670
Basi hebu dynamically
kutenga nafasi kwa Joey,

327
00:15:57,670 --> 00:16:00,390
na kisha hebu kuongeza naye kwa mlolongo.

328
00:16:00,390 --> 00:16:03,170
>> Hivyo sasa kuangalia kile ambacho tumefanya.

329
00:16:03,170 --> 00:16:06,440
Wakati sisi hash Joey tulipata Msimboreli 6.

330
00:16:06,440 --> 00:16:11,790
Sasa pointer katika safu eneo 6
anazungumzia mkuu wa orodha wanaohusishwa,

331
00:16:11,790 --> 00:16:14,900
na sasa hivi ni tu
kipengele cha orodha wanaohusishwa.

332
00:16:14,900 --> 00:16:18,350
Na node kwa kuwa
orodha wanaohusishwa ni Joey.

333
00:16:18,350 --> 00:16:22,300
>> Hivyo kama sisi haja ya kuangalia juu Joey
baadaye, sisi tu hash Joey tena,

334
00:16:22,300 --> 00:16:26,300
tunapata 6 tena kwa sababu yetu
kazi hash ni deterministic.

335
00:16:26,300 --> 00:16:30,400
Na kisha sisi kuanza saa kichwa
ya orodha wanaohusishwa alisema

336
00:16:30,400 --> 00:16:33,360
kwa safu na eneo
6, na tunaweza iterate

337
00:16:33,360 --> 00:16:35,650
hela kwamba kujaribu kupata Joey.

338
00:16:35,650 --> 00:16:37,780
Na kama sisi kujenga wetu
hash meza kwa ufanisi,

339
00:16:37,780 --> 00:16:41,790
na kazi yetu hash ufanisi
kusambaza data vizuri,

340
00:16:41,790 --> 00:16:45,770
kwa wastani kila moja ya hizo wanaohusishwa
orodha katika kila safu eneo

341
00:16:45,770 --> 00:16:50,110
itakuwa 10/1 ukubwa wa kama sisi
tu alikuwa ni kama moja kubwa

342
00:16:50,110 --> 00:16:51,650
wanaohusishwa orodha kwa kila kitu ndani yake.

343
00:16:51,650 --> 00:16:55,670
>> Kama sisi kusambaza kwamba mkubwa wanaohusishwa
orodha hela orodha wanaohusishwa 10

344
00:16:55,670 --> 00:16:57,760
kila orodha itakuwa 10/1 Mkono.

345
00:16:57,760 --> 00:17:01,432
Na hivyo mara 10 wepesi
kutafuta njia.

346
00:17:01,432 --> 00:17:02,390
Basi hebu kufanya hivyo tena.

347
00:17:02,390 --> 00:17:04,290
Hebu sasa hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Na hebu sema Ross, wakati sisi kufanya hivyo
hash kificho sisi kupata nyuma ni 2.

349
00:17:07,540 --> 00:17:10,630
Naam sasa sisi dynamically kutenga
nodi mpya, sisi kuweka Ross katika nodi kwamba,

350
00:17:10,630 --> 00:17:14,900
na tunasema sasa safu eneo
2, badala ya akizungumzia null,

351
00:17:14,900 --> 00:17:18,579
anazungumzia mkuu wa wanaohusishwa
orodha ambao nodi tu ni Ross.

352
00:17:18,579 --> 00:17:22,660
Na tunaweza kufanya wakati huu moja zaidi, sisi
Unaweza hash Rachel na kupata Msimboreli 4.

353
00:17:22,660 --> 00:17:25,490
malloc nodi mpya, kuweka Rachel katika
nodi, na kusema safu eneo

354
00:17:25,490 --> 00:17:27,839
4 sasa anazungumzia kichwa
ya orodha wanaohusishwa ambao

355
00:17:27,839 --> 00:17:31,420
kipengele tu hutokea kwa kuwa Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK lakini kile kinachotokea kama
tuna mgongano?

357
00:17:33,470 --> 00:17:38,560
Hebu angalia jinsi sisi kushughulikia migongano
kutumia tofauti chaining mbinu.

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

359
00:17:39,800 --> 00:17:41,094
Sisi kupata Msimboreli 6.

360
00:17:41,094 --> 00:17:44,010
Katika mfano wetu uliopita sisi walikuwa tu
kuhifadhi masharti katika safu.

361
00:17:44,010 --> 00:17:45,980
Hii ilikuwa ni tatizo.

362
00:17:45,980 --> 00:17:48,444
>> Hatutaki kwa clobber
Joey, na tumekuwa tayari

363
00:17:48,444 --> 00:17:51,110
kuonekana kuwa tunaweza kupata baadhi ya kuunganisha
matatizo kama sisi kujaribu na hatua

364
00:17:51,110 --> 00:17:52,202
kupitia na kuchunguza.

365
00:17:52,202 --> 00:17:54,660
Lakini nini kama sisi tu aina ya
kutibu hii njia ile ile, sawa?

366
00:17:54,660 --> 00:17:57,440
Ni kama tu kuongeza kipengele
na mkuu wa orodha wanaohusishwa.

367
00:17:57,440 --> 00:18:00,220
Hebu tu malloc nafasi kwa Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Tutaweza kusema ijayo pointi Phoebe pointer
kwa kichwa wa zamani wa orodha wanaohusishwa,

369
00:18:04,764 --> 00:18:07,180
na kisha tu 6 anazungumzia
mkuu mpya wa orodha wanaohusishwa.

370
00:18:07,180 --> 00:18:10,150
Na sasa tuangalie, tumekuwa iliyopita Phoebe katika.

371
00:18:10,150 --> 00:18:14,210
Sisi sasa wanaweza kuhifadhi wawili
vipengele na Msimboreli 6,

372
00:18:14,210 --> 00:18:17,170
na hatuna matatizo yoyote.

373
00:18:17,170 --> 00:18:20,147
>> Hiyo ni pretty much wote
hapo ni chaining.

374
00:18:20,147 --> 00:18:21,980
Na chaining ni dhahiri
Njia hiyo ni

375
00:18:21,980 --> 00:18:27,390
kwenda kuwa bora zaidi kwa wewe kama
wewe ni hifadhi ya data katika meza hash.

376
00:18:27,390 --> 00:18:30,890
Lakini hii mchanganyiko wa
arrays na orodha wanaohusishwa

377
00:18:30,890 --> 00:18:36,080
pamoja na kuunda meza hash kweli
kasi inaboresha uwezo wako

378
00:18:36,080 --> 00:18:40,550
kuhifadhi kiasi kikubwa cha data, na
haraka sana na kwa ufanisi kutafuta

379
00:18:40,550 --> 00:18:41,630
kupitia data hizo.

380
00:18:41,630 --> 00:18:44,150
>> Bado kuna moja zaidi
data ya muundo huko nje

381
00:18:44,150 --> 00:18:48,700
kwamba anaweza hata kuwa kidogo
bora katika suala la kuhakikisha

382
00:18:48,700 --> 00:18:51,920
kwamba kuingizwa yetu, kufutwa, na
kuangalia juu mara ni hata kwa kasi.

383
00:18:51,920 --> 00:18:55,630
Na tutaweza kuona kwamba katika video juu ya anajaribu.

384
00:18:55,630 --> 00:18:58,930
Mimi nina Doug Lloyd, hii ni CS50.

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