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

2
00:00:00,500 --> 00:00:01,900
[Muzikos grojimo]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Iki šiol jūs
žinoti apie masyvų daug,

5
00:00:09,150 --> 00:00:11,610
ir žinote apie susijusių sąrašus daug.

6
00:00:11,610 --> 00:00:13,650
Ir mes aptarti
privalumus ir trūkumus, mes

7
00:00:13,650 --> 00:00:16,620
aptarta, kad susijęs sąrašus
gali gauti daugiau ir mažesnių,

8
00:00:16,620 --> 00:00:18,630
tačiau jie užima daugiau dydį.

9
00:00:18,630 --> 00:00:22,359
Masyvai yra daug paprasta
naudoti, bet jie ribojanti kiek

10
00:00:22,359 --> 00:00:24,900
kaip mes turime nustatyti dydį
tuo pat pradžios masyvo

11
00:00:24,900 --> 00:00:26,910
ir tada mes pakimba su juo.

12
00:00:26,910 --> 00:00:30,470
>> Bet tai, mes gana daug
išnaudotos visos mūsų pranešimus

13
00:00:30,470 --> 00:00:33,040
apie susijusių sąrašų ir matricos.

14
00:00:33,040 --> 00:00:34,950
Arba mes?

15
00:00:34,950 --> 00:00:37,720
Gal mes galime padaryti kažką
dar kūrybingi.

16
00:00:37,720 --> 00:00:40,950
Ir kad skolina Rūšiuoti
iš maišos lentelės idėja.

17
00:00:40,950 --> 00:00:46,680
>> Taigi maišos lentelę mes ketiname pabandyti
sujungti masyvą su susietą sąrašą.

18
00:00:46,680 --> 00:00:49,520
Mes ketiname imtis privalumus
masyvo, pavyzdžiui, laisvą prieigą,

19
00:00:49,520 --> 00:00:53,510
kad galėtų tiesiog eikite į masyvą
elementas 4 arba masyvo elementas 8

20
00:00:53,510 --> 00:00:55,560
nereikia kartoti visoje.

21
00:00:55,560 --> 00:00:57,260
Tai gana greitas, tiesa?

22
00:00:57,260 --> 00:01:00,714
>> Tačiau mes taip pat norime, kad mūsų duomenis
struktūra galėtų augti ir trauktis.

23
00:01:00,714 --> 00:01:02,630
Mums nereikia, mes do not
nori būti apribota.

24
00:01:02,630 --> 00:01:04,588
Ir mes norime, kad būtų galima
pridėti ir pašalinti dalykus

25
00:01:04,588 --> 00:01:08,430
labai lengvai, o jei prisimenate,
yra labai kompleksas su masyvo.

26
00:01:08,430 --> 00:01:11,650
Ir mes galime tai vadiname
naujas dalykas maišos lentelė.

27
00:01:11,650 --> 00:01:15,190
>> Ir jei teisingai įgyvendinami,
mes tarsi atsižvelgiant

28
00:01:15,190 --> 00:01:18,150
abiejų duomenų privalumai
struktūros jūs jau matė,

29
00:01:18,150 --> 00:01:19,880
matricas ir susiję sąrašus.

30
00:01:19,880 --> 00:01:23,070
Įterpimas gali pradėti
linkę link teta 1.

31
00:01:23,070 --> 00:01:26,207
Teta mes tikrai ne aptarti,
bet teta yra tik vidutinis atvejis,

32
00:01:26,207 --> 00:01:27,540
kas iš tikrųjų nutiks.

33
00:01:27,540 --> 00:01:29,680
Jūs neprisijungęs visada bus
turi blogiausią scenarijų,

34
00:01:29,680 --> 00:01:32,555
ir jūs ne visada turėsi
Geriausiu atveju, tai kas

35
00:01:32,555 --> 00:01:33,900
vidutinis scenarijus?

36
00:01:33,900 --> 00:01:36,500
>> Na vidutinis įterpimo
į maišos lentelė

37
00:01:36,500 --> 00:01:39,370
gali pradėti priartėti prie pastovaus laiko.

38
00:01:39,370 --> 00:01:41,570
Ir išbraukta galite gauti
uždaryti iki pastovaus laiko.

39
00:01:41,570 --> 00:01:44,440
Ir peržvalgos galite gauti
uždaryti iki pastovaus laiko.

40
00:01:44,440 --> 00:01:48,600
That's-- neturime duomenų
struktūra, kad dar galite tai padaryti,

41
00:01:48,600 --> 00:01:51,180
ir todėl tai jau skamba
kaip gana didelis dalykas.

42
00:01:51,180 --> 00:01:57,010
Mes tikrai sušvelnintas
trūkumai kiekvienas savo.

43
00:01:57,010 --> 00:01:59,160
>> Norėdami gauti šią veiklą
atnaujinti, nors mes

44
00:01:59,160 --> 00:02:03,580
reikia permąstyti, kaip mes pridėti
duomenų struktūrai.

45
00:02:03,580 --> 00:02:07,380
Tiksliau mes norime, kad
Patys duomenys papasakoti

46
00:02:07,380 --> 00:02:09,725
kur ji turėtų eiti struktūrą.

47
00:02:09,725 --> 00:02:12,850
Ir jei mes tada reikia pamatyti, jei ji yra
struktūrą, jei mes turime jį rasti,

48
00:02:12,850 --> 00:02:16,610
mes norime pažvelgti į duomenų
vėl ir būtų galima veiksmingai,

49
00:02:16,610 --> 00:02:18,910
naudojant duomenis, atsitiktinai jį pasiekti.

50
00:02:18,910 --> 00:02:20,700
Tiesiog pažvelgti į
duomenys turėtume

51
00:02:20,700 --> 00:02:25,890
apie tai, kur tiksliai mes idėja
ketina jį rasti maišos lentelę.

52
00:02:25,890 --> 00:02:28,770
>> Dabar iš maišos neigiama
Lentelėje yra ta, kad jie tikrai

53
00:02:28,770 --> 00:02:31,770
gana neblogai užsisakyti ar rūšiavimo duomenis.

54
00:02:31,770 --> 00:02:34,970
Ir iš tiesų, jei jūs pradėsite
naudoti juos užsisakyti ar rūšiuoti

55
00:02:34,970 --> 00:02:37,990
duomenys jūs prarasite visus iš
privalumai anksčiau

56
00:02:37,990 --> 00:02:40,710
turėjo požiūriu įterpimo ir ištrynimo.

57
00:02:40,710 --> 00:02:44,060
Laikas tampa artimesnis
teta n, ir mes iš esmės

58
00:02:44,060 --> 00:02:45,530
regresavo į susietą sąrašą.

59
00:02:45,530 --> 00:02:48,850
Ir taip mes tik norime naudoti maišos
stalai jei mes nerūpi

60
00:02:48,850 --> 00:02:51,490
ar Duomenys išrikiuoti.

61
00:02:51,490 --> 00:02:54,290
Dėl nuo konteksto, kuriame
jūs juos naudoti CS50

62
00:02:54,290 --> 00:02:58,900
tikriausiai nerūpi
kad Duomenys išrikiuoti.

63
00:02:58,900 --> 00:03:03,170
>> Taigi maišos lentelė derinys
iš dviejų skirtingų vienetų

64
00:03:03,170 --> 00:03:04,980
su kuriais mes pažįstami.

65
00:03:04,980 --> 00:03:07,930
Pirmasis yra funkcija, kuri
mes paprastai vadiname maišos funkciją.

66
00:03:07,930 --> 00:03:11,760
Ir maišos funkcija ketina
grįžti šiek tiek ne neigiamas sveikasis skaičius, kuris

67
00:03:11,760 --> 00:03:14,870
mes paprastai vadiname hashCode, gerai?

68
00:03:14,870 --> 00:03:20,230
Antrasis gabalas yra masyvo, kuris yra
gali saugoti duomenis tipo mes

69
00:03:20,230 --> 00:03:22,190
norite patalpinti į duomenų struktūrą.

70
00:03:22,190 --> 00:03:24,310
Mes laikykite ant
susiję sąrašą elementą dabar

71
00:03:24,310 --> 00:03:27,810
ir tiesiog pradėti su vienu pagrindai
maišos lentelė gauti savo galvą aplink jį,

72
00:03:27,810 --> 00:03:30,210
ir tada mes gal pūsti
jūsų protas šiek tiek, kai mes

73
00:03:30,210 --> 00:03:32,920
sujungti masyvus ir susieti sąrašus kartu.

74
00:03:32,920 --> 00:03:35,590
>> Pagrindinė idėja, nors
yra mes kai kuriuos duomenis.

75
00:03:35,590 --> 00:03:37,860
Mes vykdome tą duomenis per
maišos funkcija.

76
00:03:37,860 --> 00:03:41,980
Ir taip duomenys apdorojami
ir jis išspjauna numerį, gerai?

77
00:03:41,980 --> 00:03:44,890
Ir tada su šio skaičiaus
mes tiesiog laikyti duomenis

78
00:03:44,890 --> 00:03:48,930
norime Laikyti
masyvo toje vietoje.

79
00:03:48,930 --> 00:03:53,990
Taigi, pavyzdžiui mes turime gal
tai maišos lentelės eilučių.

80
00:03:53,990 --> 00:03:57,350
Jis gavo 10 elementų, taigi
mes gali tilpti 10 eilutes į jį.

81
00:03:57,350 --> 00:03:59,320
>> Tarkime, mes norime maišos Joną.

82
00:03:59,320 --> 00:04:02,979
Taigi Jono kaip duomenų norime įterpti
į šią maišos lentelė kažkur.

83
00:04:02,979 --> 00:04:03,770
Kur mes jį?

84
00:04:03,770 --> 00:04:05,728
Na paprastai su
masyvas šiol mes tikriausiai

85
00:04:05,728 --> 00:04:07,610
būtų įdėti jį į masyvą vietoje 0.

86
00:04:07,610 --> 00:04:09,960
Bet dabar mes turime šį naują maišos funkciją.

87
00:04:09,960 --> 00:04:13,180
>> Ir tarkim, kad mes paleisti Joną
per šį maišos funkcija

88
00:04:13,180 --> 00:04:15,417
ir jis išspjauna 4.

89
00:04:15,417 --> 00:04:17,500
Na tai kur mes
ketinate norite įdėti Joną.

90
00:04:17,500 --> 00:04:22,050
Mes norime įdėti Jonui masyvo vietoje
4, nes jei mes maišos Joną again--

91
00:04:22,050 --> 00:04:23,810
tarkim vėliau mes
norite ieškoti ir pamatyti

92
00:04:23,810 --> 00:04:26,960
jeigu Jonas egzistuoja šiame maišos
table-- visi mes turime daryti

93
00:04:26,960 --> 00:04:30,310
yra paleisti per tą patį maišos
funkcija, gauti skaičius 4 iš,

94
00:04:30,310 --> 00:04:33,929
ir gebėti rasti Joną
iš karto mūsų duomenų struktūros.

95
00:04:33,929 --> 00:04:34,720
Tai gana gerai.

96
00:04:34,720 --> 00:04:36,928
>> Tarkime, dabar mes tai padaryti
vėl norime maišos Pauliui.

97
00:04:36,928 --> 00:04:39,446
Mes norime pridėti Paulių
į šį maišos lentelėje.

98
00:04:39,446 --> 00:04:42,070
Tarkime, kad šį kartą mes paleisti
Paulius per maišos funkcija,

99
00:04:42,070 --> 00:04:44,600
hashCode kuri yra generuojama yra 6.

100
00:04:44,600 --> 00:04:47,340
Na, dabar mes galime įdėti Paulių
masyve vietoje 6 d.

101
00:04:47,340 --> 00:04:50,040
Ir jei mes turime ieškoti, ar
Paulius šiame maišos lentelė,

102
00:04:50,040 --> 00:04:53,900
viskas, ką reikia padaryti, tai paleisti Paulius
per maišos funkcija vėl

103
00:04:53,900 --> 00:04:55,830
ir mes ketiname gauti 6 iš naujo.

104
00:04:55,830 --> 00:04:57,590
>> Ir tada mes tiesiog ieškoti
ne masyvo vietoje 6 d.

105
00:04:57,590 --> 00:04:58,910
Ar Paulius ten?

106
00:04:58,910 --> 00:05:00,160
Jei taip, jis į maišos lentelę.

107
00:05:00,160 --> 00:05:01,875
Ar Paulius ne ten?

108
00:05:01,875 --> 00:05:03,000
Jis ne maišos lentelę.

109
00:05:03,000 --> 00:05:05,720
Tai gana paprasta.

110
00:05:05,720 --> 00:05:07,770
>> Dabar, kaip jūs nustatyti maišos funkcija?

111
00:05:07,770 --> 00:05:11,460
Na ten tikrai ne riba
Galimų maišos funkcijų.

112
00:05:11,460 --> 00:05:14,350
Tiesą sakant, ten yra numeris tikrai,
tikrai gerų internete.

113
00:05:14,350 --> 00:05:17,560
Yra numerių tikrai,
tikrai blogų internete.

114
00:05:17,560 --> 00:05:21,080
Tai taip pat gana lengva
rašyti blogą vieną.

115
00:05:21,080 --> 00:05:23,760
>> Taigi, kas sudaro geras
maišos funkcija, tiesa?

116
00:05:23,760 --> 00:05:27,280
Na geras maišos funkciją, turi
naudoti tik duomenys yra sumaišomas,

117
00:05:27,280 --> 00:05:29,420
ir visi duomenys bus sumaišomas.

118
00:05:29,420 --> 00:05:32,500
Taigi mes nenorime naudoti anything--
mes neturime įtraukti nieko

119
00:05:32,500 --> 00:05:35,560
kitur, išskyrus duomenų.

120
00:05:35,560 --> 00:05:37,080
Ir mes nori naudoti visus duomenis.

121
00:05:37,080 --> 00:05:39,830
Mes nenorime, tiesiog naudokite gabalas
jo, mes nori naudoti visa tai.

122
00:05:39,830 --> 00:05:41,710
Maišos funkciją, turi
taip pat deterministinis.

123
00:05:41,710 --> 00:05:42,550
Ką tai reiškia?

124
00:05:42,550 --> 00:05:46,200
Na, tai reiškia, kad kiekvieną kartą mes
perduoti tą patį kūrinį duomenų

125
00:05:46,200 --> 00:05:50,040
į maišos funkcija visada
gauti tą patį hashCode iš.

126
00:05:50,040 --> 00:05:52,870
Jei aš praeiti Joną į
maišos funkcija man išeiti 4.

127
00:05:52,870 --> 00:05:56,110
Būčiau gali padaryti, kad 10000
kartų ir aš visada gausite 4.

128
00:05:56,110 --> 00:06:00,810
Taigi nėra atsitiktiniai skaičiai efektyviai
gali būti įtraukti į mūsų maišos tables--

129
00:06:00,810 --> 00:06:02,750
mūsų maišos funkcijų.

130
00:06:02,750 --> 00:06:05,750
>> Maišos funkcija taip pat turėtų
tolygiai paskirsto duomenis.

131
00:06:05,750 --> 00:06:09,700
Jei kiekvieną kartą paleidus duomenis per
maišos funkcija gausite hashCode 0,

132
00:06:09,700 --> 00:06:11,200
tai tikriausiai ne toks didelis, tiesa?

133
00:06:11,200 --> 00:06:14,600
Jūs tikriausiai norite didelis
iš maišos kodai asortimentas.

134
00:06:14,600 --> 00:06:17,190
Taip pat dalykai gali būti paskirstytas
iš visoje lentelėje.

135
00:06:17,190 --> 00:06:23,210
Taip pat būtų puiku, jei tikrai
panašūs duomenys, pavyzdžiui, Jono ir Jehonatano

136
00:06:23,210 --> 00:06:26,320
gal buvo išplitę pasverti
skirtingose ​​vietose maišos lentelė.

137
00:06:26,320 --> 00:06:28,750
Tai būtų gražus privalumas.

138
00:06:28,750 --> 00:06:31,250
>> Štai maišos funkcija pavyzdys.

139
00:06:31,250 --> 00:06:33,150
Parašiau tai vienas anksčiau.

140
00:06:33,150 --> 00:06:35,047
Tai nėra itin
geras maišos funkcija

141
00:06:35,047 --> 00:06:37,380
dėl priežasčių, kurios tikrai ne
padengia vyksta į dabar.

142
00:06:37,380 --> 00:06:41,040
Bet tu matai, kas vyksta čia?

143
00:06:41,040 --> 00:06:44,420
Atrodo, kad mes paskelbti kintamąjį
vadinamas suma ir ją nustatyti lygi 0.

144
00:06:44,420 --> 00:06:50,010
Ir tada, matyt, aš darau kažką
tol, kol strstr [j] nėra lygus

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

146
00:06:52,490 --> 00:06:54,870
Ką aš darau čia?

147
00:06:54,870 --> 00:06:57,440
>> Tai iš esmės yra tik dar vienas
įgyvendinimo būdas [? strl?]

148
00:06:57,440 --> 00:06:59,773
ir aptikti, kai jūs
pasiekė stygos galą.

149
00:06:59,773 --> 00:07:02,480
Taigi aš neturiu, kad iš tikrųjų
apskaičiuoti ilgis eilutę,

150
00:07:02,480 --> 00:07:05,640
Aš tik naudojant, kai aš paspauskite
Backslash 0 charakteris aš žinau

151
00:07:05,640 --> 00:07:07,185
Aš pasiekė eilutę pabaigą.

152
00:07:07,185 --> 00:07:09,560
Ir tada aš ruošiuosi laikyti
Iteracja per tą eilutę,

153
00:07:09,560 --> 00:07:15,310
pridėti strstr [J] Apibendrinant, tada ne
pabaigos dienos ketina grįžti sumą mod

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

155
00:07:16,200 --> 00:07:18,700
>> Iš esmės visa tai maišos
funkcija darote, yra sudėjus

156
00:07:18,700 --> 00:07:23,450
visi ASCII verčių
mano eilutė, o tada tai

157
00:07:23,450 --> 00:07:26,390
grįžti šiek tiek hashCode
modded iki HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Tai tikriausiai dydis
mano masyvas, tiesa?

159
00:07:29,790 --> 00:07:33,160
Aš nenoriu būti gauti maišos
kodai, jei mano masyvas dydžio 10

160
00:07:33,160 --> 00:07:35,712
Aš nenoriu, kad būtų gauti
iš maišos kodai 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, aš negaliu įdėti daiktus į
tie masyvo vietos,

162
00:07:38,690 --> 00:07:39,790
kad būtų neteisėtas.

163
00:07:39,790 --> 00:07:42,130
Norėčiau patirti segmentavimo kaltės.

164
00:07:42,130 --> 00:07:45,230
>> Dabar čia yra dar vienas greitai panaikinti.

165
00:07:45,230 --> 00:07:48,470
Paprastai jūs tikriausiai nesiruošia
noriu rašyti savo maišos funkcijas.

166
00:07:48,470 --> 00:07:50,997
Tai iš tikrųjų yra šiek tiek
menas, o ne mokslas.

167
00:07:50,997 --> 00:07:52,580
Ir ten daug, kad eina į juos.

168
00:07:52,580 --> 00:07:55,288
Internetas, kaip sakiau, yra pilnas
tikrai gerų maišos funkcijų,

169
00:07:55,288 --> 00:07:58,470
ir jūs turėtumėte naudoti prie interneto
rasti maišos funkcijos, nes tai tikrai

170
00:07:58,470 --> 00:08:03,230
tiesiog rūšies nereikalingas
laiko švaistymas sukurti savo.

171
00:08:03,230 --> 00:08:05,490
>> Jūs galite rašyti paprastus tuos
bandymų tikslais.

172
00:08:05,490 --> 00:08:08,323
Bet kai jūs iš tikrųjų ketiname
pradėti maišos duomenis ir saugoti

173
00:08:08,323 --> 00:08:10,780
į maišos lentelė esate
tikriausiai nori

174
00:08:10,780 --> 00:08:14,580
naudoti tam funkciją, kuri buvo sukauptos
už jus, kad egzistuoja internete.

175
00:08:14,580 --> 00:08:17,240
Jei tiesiog įsitikinkite,
paminėti savo šaltinius.

176
00:08:17,240 --> 00:08:21,740
Nėra jokios priežasties, kad
plagijuoti nieko čia.

177
00:08:21,740 --> 00:08:25,370
>> Kompiuteris mokslo bendruomenė
tikrai auga, ir tikrai vertybes

178
00:08:25,370 --> 00:08:28,796
atviro kodo, ir tai tikrai svarbu
paminėti savo šaltinius, kad žmonės

179
00:08:28,796 --> 00:08:30,670
galite gauti priskyrimo
darbas, kurį jie

180
00:08:30,670 --> 00:08:32,312
daro, kad bendruomenės labui.

181
00:08:32,312 --> 00:08:34,020
Taigi visada bus sure--
ir ne tik maišos

182
00:08:34,020 --> 00:08:37,270
funkcijas, tačiau paprastai, jei jus
naudoti kodą iš išorinio šaltinio,

183
00:08:37,270 --> 00:08:38,299
visada nurodo savo šaltinį.

184
00:08:38,299 --> 00:08:43,500
Duoti kreditą asmeniui, kuris padarė
kai kurių darbų, todėl jūs neturite.

185
00:08:43,500 --> 00:08:46,720
>> Gerai, kad galime peržiūrėti šį
maišos lentelė sekundę.

186
00:08:46,720 --> 00:08:48,780
Tai kur mes palikome
išjungti, kai mes įdėta

187
00:08:48,780 --> 00:08:53,300
Jonas ir Paulius į šį maišos lentelė.

188
00:08:53,300 --> 00:08:55,180
Ar matote problema čia?

189
00:08:55,180 --> 00:08:58,410
Jūs galite pamatyti du.

190
00:08:58,410 --> 00:09:02,240
Bet visų pirma, tai jums
pamatyti šį galimą problemą?

191
00:09:02,240 --> 00:09:06,770
>> Ką daryti, jei aš maišos Ringo, ir ji
Pasirodo, kad po apdorojimo

192
00:09:06,770 --> 00:09:14,000
kad duomenys per maišos funkcija
Ringo pat generuoja hashCode 6.

193
00:09:14,000 --> 00:09:16,810
Aš jau turiu duomenis
hashcode-- masyvo vietą 6.

194
00:09:16,810 --> 00:09:22,000
Taigi, tai tikriausiai bus šiek tiek
iš man problema dabar, tiesa?

195
00:09:22,000 --> 00:09:23,060
>> Mes tai vadiname susidūrimas.

196
00:09:23,060 --> 00:09:26,460
Ir susidūrimas įvyksta, kai dvi
duomenų dalis, eina per tą patį maišos

197
00:09:26,460 --> 00:09:29,200
funkcija duoda tą patį hashCode.

198
00:09:29,200 --> 00:09:32,850
Matyt mes vis dar norime gauti tiek
vienetų duomenis į maišos lentelė,

199
00:09:32,850 --> 00:09:36,330
kitaip nebūtų veikia Ringo
savavališkai per maišos funkcija.

200
00:09:36,330 --> 00:09:40,870
Mes turbūt norite gauti
Ringo į tą masyvą.

201
00:09:40,870 --> 00:09:46,070
>> Kaip mes tai darome, nors, jei jis
Paulius ir derlius hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Mes nenorime, kad perrašyti Paulių
norime Paulius būti ten pat.

203
00:09:49,520 --> 00:09:52,790
Taigi mums reikia rasti būdą, kaip gauti
elementus į maišos lentelę,

204
00:09:52,790 --> 00:09:56,550
vis dar išsaugo mūsų Quick
įterpimo ir greitai ieškoti.

205
00:09:56,550 --> 00:10:01,350
Ir vienas būdas kovoti su juo yra
padaryti kažką vadinama linijinis zondavimo.

206
00:10:01,350 --> 00:10:04,170
>> Naudojant šį metodą, jei mes turime
Avarija, gerai, ką mes galime padaryti?

207
00:10:04,170 --> 00:10:08,580
Na mes negalime įdėti jį į masyvą vietoje
6, ar kas hashCode buvo sukurtas,

208
00:10:08,580 --> 00:10:10,820
tegul įdėti jį ne hashCode plius 1 d.

209
00:10:10,820 --> 00:10:13,670
Ir jei tai visiškai tegul
įdėti jį į hashCode pridėjus 2.

210
00:10:13,670 --> 00:10:17,420
Šio būties naudos, jei jis
ne ten, kur mes manome jis yra,

211
00:10:17,420 --> 00:10:20,850
ir mes turime pradėti ieškoti,
gal mes neturime eiti per toli.

212
00:10:20,850 --> 00:10:23,900
Gal mes neturime ieškoti
visi n elementai maišos lentelė.

213
00:10:23,900 --> 00:10:25,790
Gal mes turime ieškoti
iš jų pora.

214
00:10:25,790 --> 00:10:30,680
>> Ir taip mes vis dar linksta link
kad vidutinis atvejis yra artimas 1 vs

215
00:10:30,680 --> 00:10:34,280
Uždaryti n, tai gal, kad bus dirbti.

216
00:10:34,280 --> 00:10:38,010
Taigi pažiūrėkime, kaip tai
gali dirbti iš tikrųjų.

217
00:10:38,010 --> 00:10:41,460
Ir tegul pamatyti, jei mes galime aptikti gal
problema, kuri gali atsirasti čia.

218
00:10:41,460 --> 00:10:42,540
>> Tarkime, mes maišos Bart.

219
00:10:42,540 --> 00:10:45,581
Taigi dabar mes ketiname paleisti naują rinkinį
eilučių per maišos funkcija,

220
00:10:45,581 --> 00:10:48,460
ir mes paleisti Bart per maišos
funkcija, gauname hashCode 6.

221
00:10:48,460 --> 00:10:52,100
Mes pažvelgsime matome 6 yra
tuščia, todėl mes galime įdėti Bart ten.

222
00:10:52,100 --> 00:10:55,410
>> Dabar mes maišos Lisa ir kad
taip pat sukuria hashCode 6.

223
00:10:55,410 --> 00:10:58,330
Na, dabar, kad mes naudojame šią
linijinis zondavimo metodą mes pradedame 6,

224
00:10:58,330 --> 00:10:59,330
matome, kad 6 yra pilna.

225
00:10:59,330 --> 00:11:00,990
Mes negalime įdėti Lisa 6.

226
00:11:00,990 --> 00:11:02,090
Taigi, kur mes einame?

227
00:11:02,090 --> 00:11:03,280
Vykime į 7.

228
00:11:03,280 --> 00:11:04,610
7 tuščia, kad veikia.

229
00:11:04,610 --> 00:11:06,510
Taigi leiskite įdėti Lisa ten.

230
00:11:06,510 --> 00:11:10,200
>> Dabar mes maišos Homeras ir gauname 7.

231
00:11:10,200 --> 00:11:13,380
Gerai gerai žinome, kad 7 Full
dabar, todėl mes negalime įdėti Homer ten.

232
00:11:13,380 --> 00:11:14,850
Taigi eikime į 8.

233
00:11:14,850 --> 00:11:15,664
Ar 8 prieinama?

234
00:11:15,664 --> 00:11:18,330
Taip, ir 8 glaudus 7, tad jei
mes turime pradėti ieškoti mes

235
00:11:18,330 --> 00:11:20,020
nesiruošia eiti per toli.

236
00:11:20,020 --> 00:11:22,860
Ir todėl galime įdėti Homer ne 8.

237
00:11:22,860 --> 00:11:25,151
>> Dabar mes maišos Maggie ir
grąžina 3, ačiū Dievui,

238
00:11:25,151 --> 00:11:26,650
mes galime tiesiog įdėti Maggie ten.

239
00:11:26,650 --> 00:11:29,070
Neturime daryti bet
rūšiuoti zondavimo už tai.

240
00:11:29,070 --> 00:11:32,000
Dabar mes maišos Marge ir
Marge pat grįžta 6 d.

241
00:11:32,000 --> 00:11:39,560
>> Na 6 yra pilna, 7 pilna, 8 yra pilna,
9, viskas gerai, ačiū Dievui, 9 yra tuščias.

242
00:11:39,560 --> 00:11:41,600
Aš galiu įdėti Marge, 9.

243
00:11:41,600 --> 00:11:45,280
Jau matome, kad mes pradedant
turėti šią problemą, kur dabar mes

244
00:11:45,280 --> 00:11:48,780
pradedant ruožas dalykų natūra
iš toli nuo savo maišos kodų.

245
00:11:48,780 --> 00:11:52,960
Ir kad iš 1 teta, kad vidutinis
atvejis yra pastovus laikas,

246
00:11:52,960 --> 00:11:56,560
pradeda gauti šiek tiek more--
pradedant linkę šiek tiek daugiau

247
00:11:56,560 --> 00:11:58,050
link teta n.

248
00:11:58,050 --> 00:12:01,270
Mes pradedame prarasti, kad
privalumas maišos lentelėmis.

249
00:12:01,270 --> 00:12:03,902
>> Ši problema, kad mes tik pamačiau
yra kažkas vadinamas grupavimas.

250
00:12:03,902 --> 00:12:06,360
Ir kas tikrai blogai apie
grupavimo, kad kai jums dabar

251
00:12:06,360 --> 00:12:09,606
turi du elementus, kurie yra vienas šalia
pusėje ji tampa dar labiau tikėtina,

252
00:12:09,606 --> 00:12:11,480
turite du kartus
tikimybė, kad jūs ketinate

253
00:12:11,480 --> 00:12:13,516
turėti kitą susidūrimo
su tuo klasterį,

254
00:12:13,516 --> 00:12:14,890
o klasteris augs vienas.

255
00:12:14,890 --> 00:12:19,640
Ir jūs nuolat auga ir auga
Jūsų tikimybė turėti susidūrimo.

256
00:12:19,640 --> 00:12:24,470
Ir galiausiai, tai lygiai taip pat blogai
nes ne rūšiavimas duomenis ne visiems.

257
00:12:24,470 --> 00:12:27,590
>> Kita problema, nors tai mes
vis tiek, ir iki šiol iki šio taško,

258
00:12:27,590 --> 00:12:30,336
mes ką tik buvo tarsi
suprasti, kas maišos lentelė,

259
00:12:30,336 --> 00:12:31,960
mes vis dar turime tik kambarį už 10 stygos.

260
00:12:31,960 --> 00:12:37,030
Jei norime ir toliau maišos
Springfield piliečiai,

261
00:12:37,030 --> 00:12:38,790
mes galime iš jų 10 tik gauti ten.

262
00:12:38,790 --> 00:12:42,619
Ir jei mes stengiamės ir pridėkite 11-ąją ar 12,
mes neturime vietą įdėti juos.

263
00:12:42,619 --> 00:12:45,660
Mes tiesiog negalėjo būti verpimo aplink
apskritimai bando rasti tuščią vietą,

264
00:12:45,660 --> 00:12:49,000
ir mes gal įstrigti
begalinis ciklas.

265
00:12:49,000 --> 00:12:51,810
>> Taigi šis skolina idėja rūšiuoti
kažką vadinama Grupavimo.

266
00:12:51,810 --> 00:12:55,790
Ir tai, kai mes ketiname duoti
susiję sąrašai atgal į nuotrauką.

267
00:12:55,790 --> 00:13:01,300
Ką daryti, jei vietoj laikyti tik
patys duomenys masyve,

268
00:13:01,300 --> 00:13:04,471
kiekvienas masyvo elementas galėtų
palaikykite keletą vienetų Duomenų?

269
00:13:04,471 --> 00:13:05,970
Gerai, kad nėra prasmės, tiesa?

270
00:13:05,970 --> 00:13:09,280
Mes žinome, kad masyvas gali tik
hold-- kiekvieną masyvo elementą

271
00:13:09,280 --> 00:13:12,930
gali turėti tik vieną gabalas
Duomenų tos duomenų tipą.

272
00:13:12,930 --> 00:13:16,750
>> Bet kas, jei tai duomenų tipas
yra susijusi sąrašas, tiesa?

273
00:13:16,750 --> 00:13:19,830
Taigi ką daryti, jei kas
elementas masyve buvo

274
00:13:19,830 --> 00:13:22,790
rodyklė į objektą, susietą sąrašą galvos?

275
00:13:22,790 --> 00:13:24,680
Ir tada mes galime sukurti
susijusius sąrašai

276
00:13:24,680 --> 00:13:27,120
ir augti juos savavališkai,
nes susiję sąrašai leidžia

277
00:13:27,120 --> 00:13:32,090
mums augti ir trauktis daug daugiau
lanksčiai nei masyvas daro.

278
00:13:32,090 --> 00:13:34,210
Taigi ką daryti, jei mes dabar naudoja,
mes sverto tai, tiesa?

279
00:13:34,210 --> 00:13:37,760
Mes pradeda augti šias grandines
iš šių matricų vietose.

280
00:13:37,760 --> 00:13:40,740
>> Dabar mes galime tilpti begalinė
duomenų kiekis, ar ne begalinis,

281
00:13:40,740 --> 00:13:44,170
savavališkai dydis
duomenys, į mūsų maišos lentelė

282
00:13:44,170 --> 00:13:47,760
be galimybės kada nors veikia į
susikirtimo problema.

283
00:13:47,760 --> 00:13:50,740
Mes taip pat eliminuojami
grupavimas pagal tai daryti.

284
00:13:50,740 --> 00:13:54,380
Ir gerai žinome, kad, kai mes įterpti
į susietą sąrašą, jei jūs prisimenate

285
00:13:54,380 --> 00:13:57,779
iš mūsų vaizdo susijusius sąrašus, pavieniui
susiję sąrašai ir dvigubai susiję sąrašus,

286
00:13:57,779 --> 00:13:59,070
tai pastovus laikas operacija.

287
00:13:59,070 --> 00:14:00,710
Užtenka tik pridedant į priekį.

288
00:14:00,710 --> 00:14:04,400
>> Ir ieškoti, gerai mes žinome
kad ieškoti susietoje sąrašą

289
00:14:04,400 --> 00:14:05,785
gali būti problema, tiesa?

290
00:14:05,785 --> 00:14:07,910
Turime ieškoti
jis nuo pradžios iki pabaigos.

291
00:14:07,910 --> 00:14:10,460
Nėra atsitiktinių
prieiga susietą sąrašą.

292
00:14:10,460 --> 00:14:15,610
Bet jei užuot vienas susijęs
sąrašas, kur peržvalgos būtų O n,

293
00:14:15,610 --> 00:14:19,590
dabar mes turime 10, susijusius sąrašus,
arba 1,000 susiję sąrašai,

294
00:14:19,590 --> 00:14:24,120
dabar tai O n, padalytą iš 10,
arba O n, padalytą iš 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Ir nors mes kalbame
Teoriškai apie sudėtingumo

296
00:14:26,940 --> 00:14:30,061
mes nepaisyti konstantas, nekilnojamojo
Pasaulio šie dalykai iš tikrųjų nesvarbu,

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

298
00:14:30,560 --> 00:14:33,080
Mes iš tikrųjų pastebėsite
kad tai atsitiks

299
00:14:33,080 --> 00:14:36,610
paleisti 10 kartų greičiau,
arba 1000 kartų greičiau,

300
00:14:36,610 --> 00:14:41,570
nes mes platinti vienas ilgas
grandinės visoje 1000 mažesnių grandines.

301
00:14:41,570 --> 00:14:45,090
Ir taip kiekvieną kartą mes turime ieškoti
per vieną iš šių grandines mes gali

302
00:14:45,090 --> 00:14:50,290
ignoruoti 999 grandines Mums nerūpi
apie, ir tiesiog ieškoti, kad vienas.

303
00:14:50,290 --> 00:14:53,220
>> Kuris yra vidutiniškai
būti 1000 kartų trumpesnis.

304
00:14:53,220 --> 00:14:56,460
Ir taip, mes vis dar yra tarsi
linksta į šį vidutinis atveju

305
00:14:56,460 --> 00:15:01,610
buvimo pastovų laiką, bet
tik todėl, kad mes sverto

306
00:15:01,610 --> 00:15:03,730
dalijant iš kai didžiulis pastoviu daugikliu.

307
00:15:03,730 --> 00:15:05,804
Pažiūrėkime, kaip tai gali
realiai atrodo nors.

308
00:15:05,804 --> 00:15:08,720
Taigi tai buvo maišos lentelė mes turėjome
kol mes paskelbė maišos lentelę,

309
00:15:08,720 --> 00:15:10,270
buvo galima saugoti 10 eilutes.

310
00:15:10,270 --> 00:15:11,728
Mes neketiname daryti, kad nebėra.

311
00:15:11,728 --> 00:15:13,880
Mes jau žinome,
apribojimai šio metodo.

312
00:15:13,880 --> 00:15:20,170
Dabar mūsų maišos lentelės ketina būti
kaip 10 mazgų, rodyklės masyvo

313
00:15:20,170 --> 00:15:22,120
vadovams, susijusių sąrašus.

314
00:15:22,120 --> 00:15:23,830
>> Ir dabar jis niekinis.

315
00:15:23,830 --> 00:15:26,170
Kiekviena iš šių 10 patarimų yra niekinis.

316
00:15:26,170 --> 00:15:29,870
Nėra nieko mūsų šalyje
maišos lentelė dabar.

317
00:15:29,870 --> 00:15:32,690
>> Dabar pradėkime įdėti šiek tiek
dalykų, į šį maišos lentelė.

318
00:15:32,690 --> 00:15:35,440
Ir pažiūrėkime, kaip šis metodas yra
ketina pasinaudoti mums truputį.

319
00:15:35,440 --> 00:15:36,760
Leiskite dabar maišos Joey.

320
00:15:36,760 --> 00:15:40,210
Mes bus paleisti eilutę Joey per
maišos funkcija ir mes grįžtame 6 d.

321
00:15:40,210 --> 00:15:41,200
Na ką mes darome dabar?

322
00:15:41,200 --> 00:15:44,090
>> Na, dabar dirba su susijusių sąrašus,
mes ne dirbti su matricomis.

323
00:15:44,090 --> 00:15:45,881
Ir kai mes dirbame
su susijusių sąrašus mes

324
00:15:45,881 --> 00:15:49,790
žinome, mes turime pradėti dinamiškai
patalpų skyrimo ir statybos grandines.

325
00:15:49,790 --> 00:15:54,020
Tai tarsi how-- tai yra pagrindinis
elementai kuriant susietą sąrašą.

326
00:15:54,020 --> 00:15:57,670
Taigi leiskite dinamiškai
skirti vietos Joey,

327
00:15:57,670 --> 00:16:00,390
ir tada tegul pridėti jį prie grandinės.

328
00:16:00,390 --> 00:16:03,170
>> Taigi dabar pažiūrėkite, ką mes padarėme.

329
00:16:03,170 --> 00:16:06,440
Kai mes maišos Joey mes turime hashCode 6.

330
00:16:06,440 --> 00:16:11,790
Dabar ne masyvo vietoje 6 žymeklis
atkreipia į susietą sąrašą galvos,

331
00:16:11,790 --> 00:16:14,900
ir dabar tai tik
elementas susijęs sąrašą.

332
00:16:14,900 --> 00:16:18,350
Ir tuo, kad mazgas
susiję sąrašas Joey.

333
00:16:18,350 --> 00:16:22,300
>> Taigi, jei mes turime ieškoti Joey
vėliau, mes tiesiog maišos Joey vėl,

334
00:16:22,300 --> 00:16:26,300
mes gauname 6 vėl, nes mūsų
maišos funkcija yra deterministinis.

335
00:16:26,300 --> 00:16:30,400
Ir tada mes pradėti galvos
iš susietų sąrašą pažymėti

336
00:16:30,400 --> 00:16:33,360
kaip iki masyvo vietoje
6, ir mes galime pakartoti

337
00:16:33,360 --> 00:16:35,650
visoje, kad bando rasti Joey.

338
00:16:35,650 --> 00:16:37,780
Ir jei mes sukurti mūsų
maišos lentelė efektyviai,

339
00:16:37,780 --> 00:16:41,790
ir mūsų maišos funkcija efektyviai
platinti duomenis gerai,

340
00:16:41,790 --> 00:16:45,770
vidutiniškai kiekvienas iš tuos, kurie susiję
sąrašus kiekvienam masyvo vietoje

341
00:16:45,770 --> 00:16:50,110
bus 1/10 IF dydis mums
tiesiog turėjo ją kaip vieną didžiulis

342
00:16:50,110 --> 00:16:51,650
susiję sąrašas su viskuo jame.

343
00:16:51,650 --> 00:16:55,670
>> Jei mes platinti, kad didžiulis susijęs
Sąrašas visoje 10 susijusių sąrašus

344
00:16:55,670 --> 00:16:57,760
kiekviena sąrašas bus 1/10 dydis.

345
00:16:57,760 --> 00:17:01,432
Ir taip 10 kartų greitesnis
ieškoti per.

346
00:17:01,432 --> 00:17:02,390
Taigi leiskite tai padaryti dar kartą.

347
00:17:02,390 --> 00:17:04,290
Leiskite dabar maišos Ross.

348
00:17:04,290 --> 00:17:07,540
>> Ir tarkim Ross, kai mes darome, kad
maišos kodą gauname atgal yra 2.

349
00:17:07,540 --> 00:17:10,630
Na, dabar mes dinamiškai skirdavo
Naujas mazgas, mes įdėti Ross toje mazgas,

350
00:17:10,630 --> 00:17:14,900
ir sakome dabar masyvo vietą
2, vietoj to, nukreipta į nuliui,

351
00:17:14,900 --> 00:17:18,579
atkreipia dėmesį į susieto galvos
sąrašas, kurios tik mazgas yra Ross.

352
00:17:18,579 --> 00:17:22,660
Ir mes galime tai padaryti dar vieną kartą, mes
gali maišos Rachelę ir gauti hashCode 4.

353
00:17:22,660 --> 00:17:25,490
malloc naują mazgas, įdėti į Rachelę
mazgas ir pasakyti masyvo vietą

354
00:17:25,490 --> 00:17:27,839
4 dabar atkreipia į galvą
Susietos sąrašą, kurio

355
00:17:27,839 --> 00:17:31,420
tik elementas atsitinka būti Rachelė.

356
00:17:31,420 --> 00:17:33,470
>> Gerai, bet kas atsitiks, jei
turime susidūrimo?

357
00:17:33,470 --> 00:17:38,560
Pažiūrėkime, kaip mes tvarkome susidūrimų
naudojant atskirą Grupavimo metodas.

358
00:17:38,560 --> 00:17:39,800
Leiskite maišos Phoebe.

359
00:17:39,800 --> 00:17:41,094
Mes gauti hashCode 6.

360
00:17:41,094 --> 00:17:44,010
Mūsų ankstesniame pavyzdyje mes buvome tik
saugoti masyve eilutes.

361
00:17:44,010 --> 00:17:45,980
Tai buvo problema.

362
00:17:45,980 --> 00:17:48,444
>> Mes nenorime, kad Clobber
Joey, ir mes jau ve

363
00:17:48,444 --> 00:17:51,110
matyti, kad mes galime gauti tam tikrą grupavimą
problemų, jei mes pabandyti ir žingsnis

364
00:17:51,110 --> 00:17:52,202
per ir zondas.

365
00:17:52,202 --> 00:17:54,660
Bet kas, jei mes tiesiog rūšies
gydyti tai tas pats būdas, tiesa?

366
00:17:54,660 --> 00:17:57,440
Tai kaip pridėti elementą
į susietojo sąrašo galvą.

367
00:17:57,440 --> 00:18:00,220
Tegul tik malloc erdvę Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Mes pasakyti Phoebe naujos žymeklį taškų
prie senosios galvos susietą sąrašą

369
00:18:04,764 --> 00:18:07,180
ir tada 6 tik atkreipia dėmesį į
Naujasis vadovas susietą sąrašą.

370
00:18:07,180 --> 00:18:10,150
Ir dabar atrodo, mes pakeitėme Phoebe vietą.

371
00:18:10,150 --> 00:18:14,210
Dabar mes galime laikyti du
elementai su hashCode 6

372
00:18:14,210 --> 00:18:17,170
ir mes neturime jokių problemų.

373
00:18:17,170 --> 00:18:20,147
>> Štai beveik visi
ten yra susiejami.

374
00:18:20,147 --> 00:18:21,980
Ir susiejami yra tikrai
metodas tai

375
00:18:21,980 --> 00:18:27,390
bus efektyviausias, jei
Jūs saugoti duomenis maišos lentelė.

376
00:18:27,390 --> 00:18:30,890
Tačiau šis derinys
matricas ir susiję sąrašai

377
00:18:30,890 --> 00:18:36,080
kartu, siekiant sudaryti maišos lentelę tikrai
žymiai pagerina savo gebėjimą

378
00:18:36,080 --> 00:18:40,550
saugoti didelius kiekius duomenų, ir
labai greitai ir efektyviai ieškoti

379
00:18:40,550 --> 00:18:41,630
per tą duomenis.

380
00:18:41,630 --> 00:18:44,150
>> Yra dar viena daugiau
duomenų struktūra ten

381
00:18:44,150 --> 00:18:48,700
kad gali būti net šiek tiek
geriau kalbant apie garantuojant

382
00:18:48,700 --> 00:18:51,920
kad mūsų įterpimo, išbraukta, ir
ieškoti laikai yra net greičiau.

383
00:18:51,920 --> 00:18:55,630
Ir mes pamatysime, kad dėl bandymų vaizdo įrašą.

384
00:18:55,630 --> 00:18:58,930
Aš Doug Lloyd, tai CS50.

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