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

2
00:00:00,500 --> 00:00:01,900
[Muusika mängib]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Nüüdseks olete
teavad palju massiivid,

5
00:00:09,150 --> 00:00:11,610
ja sa tead palju ahelloendid.

6
00:00:11,610 --> 00:00:13,650
Ja me oleme arutada
plusse ja miinuseid, me oleme

7
00:00:13,650 --> 00:00:16,620
arutati, et ahelloendid
saavad suuremad ja väiksemad,

8
00:00:16,620 --> 00:00:18,630
kuid nad võtavad rohkem suurust.

9
00:00:18,630 --> 00:00:22,359
Massiivid on palju lihtne
kasutada, kuid nad piiravad nii palju

10
00:00:22,359 --> 00:00:24,900
kui me peame seadma suurus
massiivi alguses

11
00:00:24,900 --> 00:00:26,910
ja siis me ummikus see.

12
00:00:26,910 --> 00:00:30,470
>> Aga see, me oleme päris palju
ammendanud kõik meie teemasid

13
00:00:30,470 --> 00:00:33,040
umbes ahelloendid ja massiivid.

14
00:00:33,040 --> 00:00:34,950
Või on meil?

15
00:00:34,950 --> 00:00:37,720
Võib-olla me saame teha midagi
isegi loovamaks.

16
00:00:37,720 --> 00:00:40,950
Ja seda sorti laenab
idee hash tabelit.

17
00:00:40,950 --> 00:00:46,680
>> Nii et hash tabelit me ei kavatse proovida
ühendada massiivi ahelloend.

18
00:00:46,680 --> 00:00:49,520
Me läheme eelised
massiivi, nagu muutmälu,

19
00:00:49,520 --> 00:00:53,510
on võimalik lihtsalt minema massiivi
element 4 või massiivi element 8

20
00:00:53,510 --> 00:00:55,560
ilma et korrata üle.

21
00:00:55,560 --> 00:00:57,260
See on päris kiire, eks?

22
00:00:57,260 --> 00:01:00,714
>> Aga tahame ka meie andmeid
struktuuri saaks kasvada ja kahaneb.

23
00:01:00,714 --> 00:01:02,630
Meil ei ole vaja, me ei
tahan olla piiratud.

24
00:01:02,630 --> 00:01:04,588
Ja me tahame, et oleks võimalik
lisada ja eemaldada asju

25
00:01:04,588 --> 00:01:08,430
väga lihtne, mis siis, kui te mäletate,
on väga keeruline massiivi.

26
00:01:08,430 --> 00:01:11,650
Ja me nimetame seda
uus asi räsi tabelis.

27
00:01:11,650 --> 00:01:15,190
>> Ja kui rakendatakse õigesti,
me mingi võttes

28
00:01:15,190 --> 00:01:18,150
eeliseid nii andmete
struktuuride olete juba näinud,

29
00:01:18,150 --> 00:01:19,880
massiivid ja ahelloendid.

30
00:01:19,880 --> 00:01:23,070
Sisestamine võib hakata
kalduvust teeta 1.

31
00:01:23,070 --> 00:01:26,207
Theta me ei ole tõesti arutatud,
kuid teeta on lihtsalt keskmisest juhul,

32
00:01:26,207 --> 00:01:27,540
mis tegelikult juhtub.

33
00:01:27,540 --> 00:01:29,680
Sa ei ole alati läheb
on halvimal juhul,

34
00:01:29,680 --> 00:01:32,555
ja sa ei ole alati saab olema
Parimal juhul, siis millised

35
00:01:32,555 --> 00:01:33,900
keskmine stsenaarium?

36
00:01:33,900 --> 00:01:36,500
>> Noh keskmiselt sisestamise
arvesse hash tabelis

37
00:01:36,500 --> 00:01:39,370
saab hakkama saada lähedal konstantset aega.

38
00:01:39,370 --> 00:01:41,570
Ja kustutamist saad
sulgeda pidevalt aega.

39
00:01:41,570 --> 00:01:44,440
Ja lookup saab
sulgeda pidevalt aega.

40
00:01:44,440 --> 00:01:48,600
On-- me ei ole andmebaasi
struktuuri veel, et ei saa seda teha,

41
00:01:48,600 --> 00:01:51,180
ja nii see juba kõlab
nagu päris suur asi.

42
00:01:51,180 --> 00:01:57,010
Me oleme tõesti kergendanud
puudused iga oma.

43
00:01:57,010 --> 00:01:59,160
>> Et saada selle etenduse
uuendada küll, me

44
00:01:59,160 --> 00:02:03,580
vaja mõelda, kuidas me lisada
andmed selle struktuuri.

45
00:02:03,580 --> 00:02:07,380
Nimelt tahame
andmed ise meile öelda

46
00:02:07,380 --> 00:02:09,725
kus see peaks minema struktuuri.

47
00:02:09,725 --> 00:02:12,850
Ja kui me siis peame nägema, kui see on
struktuuri, kui meil on vaja üles leida,

48
00:02:12,850 --> 00:02:16,610
tahame vaadata andmeid
uuesti ja suutma tõhusalt,

49
00:02:16,610 --> 00:02:18,910
Andmete kasutamisel juhuslikult ligi.

50
00:02:18,910 --> 00:02:20,700
Lihtsalt vaadates
andmed meil peaks olema

51
00:02:20,700 --> 00:02:25,890
idee, kus täpselt me ​​oleme
leiame seda hash tabelit.

52
00:02:25,890 --> 00:02:28,770
>> Nüüd negatiivsed räsi
Tabelis on see, et nad on tõesti

53
00:02:28,770 --> 00:02:31,770
päris halb tellimise või sorteerimine andmeid.

54
00:02:31,770 --> 00:02:34,970
Ja tegelikult, kui hakkate
kasutada neid tellida või järjesta

55
00:02:34,970 --> 00:02:37,990
andmed sa kaotad kõik
eeliseid, mida varem

56
00:02:37,990 --> 00:02:40,710
oli nii sisestamise ja kustutamise.

57
00:02:40,710 --> 00:02:44,060
Kell saab lähemale
teeta n, ja me oleme põhiliselt

58
00:02:44,060 --> 00:02:45,530
taandarenenud arvesse ahelloend.

59
00:02:45,530 --> 00:02:48,850
Ja nii me ainult tahame kasutada hash
tabelid, kui me ei hooli

60
00:02:48,850 --> 00:02:51,490
kas andmed on järjestatud.

61
00:02:51,490 --> 00:02:54,290
Selles kontekstis, kus
saate neid kasutada CS50

62
00:02:54,290 --> 00:02:58,900
siis ilmselt ei hooli
et andmed järjestatud.

63
00:02:58,900 --> 00:03:03,170
>> Nii hash tabelis on kombinatsioon
kahest erinevast tükki

64
00:03:03,170 --> 00:03:04,980
kellega me oleme tuttavad.

65
00:03:04,980 --> 00:03:07,930
Esimene on funktsioon, mis
me tavaliselt nimetame hash funktsiooni.

66
00:03:07,930 --> 00:03:11,760
Ja et hash funktsiooni saab
tagasi mõned mittenegatiivne täisarv, mis

67
00:03:11,760 --> 00:03:14,870
me tavaliselt nimetame räsikood, OK?

68
00:03:14,870 --> 00:03:20,230
Teine tükk on massiiv, mis on
võimeline talletama andmeid tüübi me

69
00:03:20,230 --> 00:03:22,190
tahad pane andmestruktuur.

70
00:03:22,190 --> 00:03:24,310
Me hoidke off
ahelloendid element nüüd

71
00:03:24,310 --> 00:03:27,810
ja lihtsalt alustada põhitõdesid
hash tabelit, et su pea ümber,

72
00:03:27,810 --> 00:03:30,210
ja siis me võibolla puhuda
meelt natuke, kui me

73
00:03:30,210 --> 00:03:32,920
ühendada massiivid ja link nimekirjad koos.

74
00:03:32,920 --> 00:03:35,590
>> Põhiidee kuigi
on meil võtta mõned andmed.

75
00:03:35,590 --> 00:03:37,860
Juhime et andmete abil
hash funktsiooni.

76
00:03:37,860 --> 00:03:41,980
Ja nii andmeid töödeldakse
ja see sülitab välja mitmeid, OK?

77
00:03:41,980 --> 00:03:44,890
Ja seejärel, et number
me lihtsalt salvestada andmeid

78
00:03:44,890 --> 00:03:48,930
Me tahame hoida ka
massiivi selles asukohas.

79
00:03:48,930 --> 00:03:53,990
Nii näiteks on meil võibolla
see hash tabelit stringid.

80
00:03:53,990 --> 00:03:57,350
See ju 10 elementi, seega
meil mahub 10 stringid ta.

81
00:03:57,350 --> 00:03:59,320
>> Oletame, et me tahame hash John.

82
00:03:59,320 --> 00:04:02,979
Nii Johannes andmeid me tahame lisada
sellesse hash tabelis kusagil.

83
00:04:02,979 --> 00:04:03,770
Kust me seda?

84
00:04:03,770 --> 00:04:05,728
Noh tavaliselt koos
massiivi nii kaugele me ilmselt

85
00:04:05,728 --> 00:04:07,610
paneks ta massiivi 0.

86
00:04:07,610 --> 00:04:09,960
Aga nüüd on meil see uus hash funktsiooni.

87
00:04:09,960 --> 00:04:13,180
>> Ja ütleme, et võtame John
läbi selle hash funktsiooni

88
00:04:13,180 --> 00:04:15,417
ja see sülitab välja 4.

89
00:04:15,417 --> 00:04:17,500
Noh, et kus me oleme
läheb taha panna John.

90
00:04:17,500 --> 00:04:22,050
Tahame panna John massiivi asukohta
4, sest kui me hash John again--

91
00:04:22,050 --> 00:04:23,810
oletame hiljem me
soovite otsida ja vaadata

92
00:04:23,810 --> 00:04:26,960
Kui John esineb selles hash
table-- kõik me peame tegema

93
00:04:26,960 --> 00:04:30,310
juhib ta läbi sama räsi
funktsioon, saada number 4 välja,

94
00:04:30,310 --> 00:04:33,929
ja suutma leida John
kohe meie andmestruktuur.

95
00:04:33,929 --> 00:04:34,720
See on päris hea.

96
00:04:34,720 --> 00:04:36,928
>> Oletame, et me nüüd teeme seda
jälle, me tahame hash Paul.

97
00:04:36,928 --> 00:04:39,446
Me tahame, et lisada Paul
sellesse hash tabelit.

98
00:04:39,446 --> 00:04:42,070
Oletame, et seekord võtame
Paul läbi hash funktsiooni,

99
00:04:42,070 --> 00:04:44,600
räsikood edastatakse, mis on loodud on 6.

100
00:04:44,600 --> 00:04:47,340
Noh nüüd saab panna Paul
massiivi asukoha 6.

101
00:04:47,340 --> 00:04:50,040
Ja kui meil on vaja otsida, kas
Paul on selles hash tabelit,

102
00:04:50,040 --> 00:04:53,900
kõik me peame tegema, on käivitada Paul
läbi hash funktsiooni uuesti

103
00:04:53,900 --> 00:04:55,830
ja me ei kavatse saada 6 jälle.

104
00:04:55,830 --> 00:04:57,590
>> Ja siis me lihtsalt vaadata
kell massiivi asukoha 6.

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

106
00:04:58,910 --> 00:05:00,160
Kui jah, ta on hash tabelit.

107
00:05:00,160 --> 00:05:01,875
Kas Paul ole olemas?

108
00:05:01,875 --> 00:05:03,000
Ta ei räsi tabelis.

109
00:05:03,000 --> 00:05:05,720
See on üsna lihtne.

110
00:05:05,720 --> 00:05:07,770
>> Nüüd, kuidas sa määratleda hash funktsiooni?

111
00:05:07,770 --> 00:05:11,460
Noh seal on tõesti mingeid piiranguid
arvu võimalik räsifunktsioone.

112
00:05:11,460 --> 00:05:14,350
Tegelikult seal on mitmeid tõesti,
tõesti head internetis.

113
00:05:14,350 --> 00:05:17,560
Seal on mitmeid tõesti,
tõesti halvad internetis.

114
00:05:17,560 --> 00:05:21,080
See on ka üsna lihtne
kirjutada halb.

115
00:05:21,080 --> 00:05:23,760
>> Nii teebki up hea
hash funktsiooni, eks?

116
00:05:23,760 --> 00:05:27,280
Noh hea hash funktsiooni peaksid
kasutada ainult andmed on räsitud,

117
00:05:27,280 --> 00:05:29,420
ja kõik andmed ohtu räsitud.

118
00:05:29,420 --> 00:05:32,500
Nii et me ei taha kasutada anything--
meil ei sisalda midagi

119
00:05:32,500 --> 00:05:35,560
muud peale andmeid.

120
00:05:35,560 --> 00:05:37,080
Ja me tahame kasutada kõiki andmeid.

121
00:05:37,080 --> 00:05:39,830
Me ei taha lihtsalt kasutada tükk
sellest, tahame kasutada kõik.

122
00:05:39,830 --> 00:05:41,710
Hash funktsioon peab
Samuti on determineeritud.

123
00:05:41,710 --> 00:05:42,550
Mida see tähendab?

124
00:05:42,550 --> 00:05:46,200
Aga see tähendab, et iga kord, kui me
edasi täpselt sama tükk andmed

125
00:05:46,200 --> 00:05:50,040
arvesse hash funktsiooni me alati
saada sama räsikood välja.

126
00:05:50,040 --> 00:05:52,870
Kui ma edasi John sisse
hash funktsiooni ma saan välja 4.

127
00:05:52,870 --> 00:05:56,110
Ma peaks olema võimalik teha, et 10000
korda ja ma alati 4.

128
00:05:56,110 --> 00:06:00,810
Nii ei juhuslike arvude tõhusalt
võib olla seotud meie hash tables--

129
00:06:00,810 --> 00:06:02,750
Meie räsifunktsioone.

130
00:06:02,750 --> 00:06:05,750
>> Hash funktsioon peaks ka
ühtlaselt jaotada andmed.

131
00:06:05,750 --> 00:06:09,700
Kui iga kord, kui käivitad kaudu andmeid
hash funktsiooni saad räsikood 0,

132
00:06:09,700 --> 00:06:11,200
et ilmselt ei ole nii suur, eks?

133
00:06:11,200 --> 00:06:14,600
Sa ilmselt tahad suured
vahemikus räsikoodid.

134
00:06:14,600 --> 00:06:17,190
Samuti asju võib levida
välja kogu tabel.

135
00:06:17,190 --> 00:06:23,210
Ja ka see oleks tore, kui tõesti
samasugune, nagu John ja Jonathan,

136
00:06:23,210 --> 00:06:26,320
võibolla olid laiali lööma
erinevates kohtades hash tabelit.

137
00:06:26,320 --> 00:06:28,750
See oleks kena ära.

138
00:06:28,750 --> 00:06:31,250
>> Siin on näide hash funktsiooni.

139
00:06:31,250 --> 00:06:33,150
Kirjutasin selle ühe kuni varem.

140
00:06:33,150 --> 00:06:35,047
See ei ole eriti
hea hash funktsiooni

141
00:06:35,047 --> 00:06:37,380
põhjustel, mis ei ole tegelikult
kandma laskumist kohe.

142
00:06:37,380 --> 00:06:41,040
Aga sa vaata, mis siin toimub?

143
00:06:41,040 --> 00:06:44,420
Tundub nagu me kuulutab muutuja
nimetatakse summa, ning kehtestatakse võrdne 0.

144
00:06:44,420 --> 00:06:50,010
Ja siis ilmselt teen midagi
nii kaua kui strstr [j] ei ole võrdne

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

146
00:06:52,490 --> 00:06:54,870
Mida ma teen seal?

147
00:06:54,870 --> 00:06:57,440
>> See on põhimõtteliselt lihtsalt üks
rakendusaktiga [? strl?]

148
00:06:57,440 --> 00:06:59,773
ja avastada, kui olete
jõudis lõpuks string.

149
00:06:59,773 --> 00:07:02,480
Nii et ma ei pea tegelikult
arvutada stringi pikkusena,

150
00:07:02,480 --> 00:07:05,640
Ma lihtsalt kasutades, kui ma tabanud
kurakriips 0 iseloomu Tean

151
00:07:05,640 --> 00:07:07,185
Olen jõudnud lõpuks string.

152
00:07:07,185 --> 00:07:09,560
Ja siis ma lähen hoida
iterating läbi, et string,

153
00:07:09,560 --> 00:07:15,310
Lisades strstr [j] Kokkuvõttes, ja siis on
Päeva lõpuks läheb tagasi summa mod

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

155
00:07:16,200 --> 00:07:18,700
>> Põhimõtteliselt kõik selle räsi
funktsioon teeb lisab kuni

156
00:07:18,700 --> 00:07:23,450
kõik ASCII väärtused
minu string, ja siis on see

157
00:07:23,450 --> 00:07:26,390
tagasi mõned räsikood
modida poolt HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
See on ilmselt suurus
minu rida, eks?

159
00:07:29,790 --> 00:07:33,160
Ma ei taha saada hash
koodid, kui minu rida on suurus 10,

160
00:07:33,160 --> 00:07:35,712
Ma ei taha olla saada
välja räsikoodid 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, ma ei saa panna asjad
need kohad massiivi,

162
00:07:38,690 --> 00:07:39,790
mis oleks ebaseaduslik.

163
00:07:39,790 --> 00:07:42,130
Ma kannatavad killustatust süü.

164
00:07:42,130 --> 00:07:45,230
>> Nüüd siin on teise kiire kõrvale.

165
00:07:45,230 --> 00:07:48,470
Üldiselt sa ilmselt ei kavatse
tahan kirjutada oma räsifunktsioone.

166
00:07:48,470 --> 00:07:50,997
See on tegelikult natuke
kunst, mitte teadus.

167
00:07:50,997 --> 00:07:52,580
Ja seal on palju, mis läheb neile.

168
00:07:52,580 --> 00:07:55,288
Internet, nagu ma ütlesin, on täis
tõesti hea räsifunktsioone,

169
00:07:55,288 --> 00:07:58,470
ja sa peaksid kasutama internetti
leida räsifunktsioone sest see on tõesti

170
00:07:58,470 --> 00:08:03,230
lihtsalt selline ebavajalik
ajaraiskamine luua oma.

171
00:08:03,230 --> 00:08:05,490
>> Võite kirjutada lihtsaid
testimise eesmärgil.

172
00:08:05,490 --> 00:08:08,323
Aga kui sa tegelikult ei kavatse
alustada hashing andmed ja säilitamist

173
00:08:08,323 --> 00:08:10,780
arvesse hash tabelit sa oled
ilmselt läheb taha

174
00:08:10,780 --> 00:08:14,580
kasutada mõnda funktsiooni, mis oli loodud
teile, et on olemas internet.

175
00:08:14,580 --> 00:08:17,240
Kui sa just kindlasti
tsiteerida oma allikaid.

176
00:08:17,240 --> 00:08:21,740
Ei ole mingit põhjust, et
Plagioida siin midagi.

177
00:08:21,740 --> 00:08:25,370
>> Computer Science kogukond
kindlasti kasvab, ja tõesti väärtused

178
00:08:25,370 --> 00:08:28,796
avatud lähtekoodiga, ja see on tõesti oluline
tsiteerida oma allikatest, et inimesed

179
00:08:28,796 --> 00:08:30,670
saab omistamisega eest
töö, et nad

180
00:08:30,670 --> 00:08:32,312
teeme selle hüvena.

181
00:08:32,312 --> 00:08:34,020
Nii alati sure--
ja mitte ainult hash

182
00:08:34,020 --> 00:08:37,270
funktsioone, kuid üldiselt kui
kasuta koodi väljaspool allikas,

183
00:08:37,270 --> 00:08:38,299
alati tuua oma allikas.

184
00:08:38,299 --> 00:08:43,500
Anna krediidi isik, kes tegi
mõned tööd, et sa ei pea.

185
00:08:43,500 --> 00:08:46,720
>> OK, nii olgem vaadata seda
hash tabelis teiseks.

186
00:08:46,720 --> 00:08:48,780
See on koht, kus me lahkusime
välja pärast me sisestatud

187
00:08:48,780 --> 00:08:53,300
John ja Paul sellesse hash tabelit.

188
00:08:53,300 --> 00:08:55,180
Kas te näete siin probleemi?

189
00:08:55,180 --> 00:08:58,410
Sa võid näha kaks.

190
00:08:58,410 --> 00:09:02,240
Aga eelkõige, kas sa
vaata seda võimalikku probleemi?

191
00:09:02,240 --> 00:09:06,770
>> Mis siis, kui ma hash Ringo, ja see
Selgub, et pärast töötlemist

192
00:09:06,770 --> 00:09:14,000
et andmed läbi hash funktsiooni
Ringo ka genereerinud räsikood 6.

193
00:09:14,000 --> 00:09:16,810
Olen juba saanud andmeid
hashcode-- massiivi asukoha 6.

194
00:09:16,810 --> 00:09:22,000
Nii et see on ilmselt saab olema natuke
probleem minu jaoks praegu, eks?

195
00:09:22,000 --> 00:09:23,060
>> Me nimetame seda kokkupõrget.

196
00:09:23,060 --> 00:09:26,460
Ja kokkupõrge toimub siis, kui kaks
tükki andmeid läbib sama räsi

197
00:09:26,460 --> 00:09:29,200
funktsiooni saada sama räsikood.

198
00:09:29,200 --> 00:09:32,850
Arvatavasti me ikka tahad nii
tükki andmeid hash tabelit,

199
00:09:32,850 --> 00:09:36,330
muidu ei saa töötab Ringo
suvaliselt läbi hash funktsiooni.

200
00:09:36,330 --> 00:09:40,870
Me ilmselt tahad saada
Ringo arvesse, et massiivi.

201
00:09:40,870 --> 00:09:46,070
>> Kuidas me seda teeme küll, kui ta
ja Paul nii tulu- räsikood 6?

202
00:09:46,070 --> 00:09:49,520
Me ei taha kirjutada Paul,
tahame Paul olla ka seal.

203
00:09:49,520 --> 00:09:52,790
Seega peame leidma viisi, kuidas saada
elemendid hash tabelit, et

204
00:09:52,790 --> 00:09:56,550
ikka säilitab oma kiire
sisestamise ja pilgu üles.

205
00:09:56,550 --> 00:10:01,350
Ja üks viis lahendada see on
teha midagi, mida nimetatakse lineaarselt katsetamine.

206
00:10:01,350 --> 00:10:04,170
>> Seda meetodit kasutades, kui meil on
Kokkupõrke, noh, mida me teeme?

207
00:10:04,170 --> 00:10:08,580
Noh me ei saa teda massiivi asukohta
6, või mis iganes räsikood tekkinud,

208
00:10:08,580 --> 00:10:10,820
paneme teda räsikood pluss 1.

209
00:10:10,820 --> 00:10:13,670
Ja kui see täis olgem
pani ta räsikood pluss 2.

210
00:10:13,670 --> 00:10:17,420
Kasu on see olevus, kui ta on
ei täpselt, kus me arvan, et ta on,

211
00:10:17,420 --> 00:10:20,850
ja me peame hakkama otsima,
võibolla me ei pea minema liiga kaugele.

212
00:10:20,850 --> 00:10:23,900
Võib-olla me ei pea otsima
kõik n elemendid hash tabelit.

213
00:10:23,900 --> 00:10:25,790
Võib-olla on meil otsida
paar neist.

214
00:10:25,790 --> 00:10:30,680
>> Ja nii me ikka kipub suunas
et keskmine juhul on peaaegu 1 vs

215
00:10:30,680 --> 00:10:34,280
lähedal n, et äkki, et teen tööd.

216
00:10:34,280 --> 00:10:38,010
Vaatame, kuidas see
võiks töötada välja tegelikkus.

217
00:10:38,010 --> 00:10:41,460
Ja vaatame, kui äkki saame tuvastada
probleemi, mis võib esineda siin.

218
00:10:41,460 --> 00:10:42,540
>> Oletame, et meil hash Bart.

219
00:10:42,540 --> 00:10:45,581
Nüüd me läheme sõitma uued
stringid läbi hash funktsiooni,

220
00:10:45,581 --> 00:10:48,460
ja võtame Bart läbi hash
funktsiooni, saame räsikood 6.

221
00:10:48,460 --> 00:10:52,100
Me vaatleme, siis näeme 6
tühi, nii et me ei pane Bart seal.

222
00:10:52,100 --> 00:10:55,410
>> Nüüd hash Lisa ja et
Samuti tekitab räsikood 6.

223
00:10:55,410 --> 00:10:58,330
Noh nüüd, et me kasutame seda
lineaarne katsetamine meetod hakkame kell 6,

224
00:10:58,330 --> 00:10:59,330
näeme, et 6 on täis.

225
00:10:59,330 --> 00:11:00,990
Me ei saa panna Lisa 6.

226
00:11:00,990 --> 00:11:02,090
Nii et kui me läheme?

227
00:11:02,090 --> 00:11:03,280
Lähme 7.

228
00:11:03,280 --> 00:11:04,610
7 on tühi, nii et töötab.

229
00:11:04,610 --> 00:11:06,510
Nii paneme Lisa olemas.

230
00:11:06,510 --> 00:11:10,200
>> Nüüd hash Homer ja saame 7.

231
00:11:10,200 --> 00:11:13,380
OK hästi teame, et 7 täielikku
nüüd, et me ei saa Homer seal.

232
00:11:13,380 --> 00:11:14,850
Nii lähme 8.

233
00:11:14,850 --> 00:11:15,664
Kas 8 kättesaadav?

234
00:11:15,664 --> 00:11:18,330
Jah, ja 8 on ligi 7, nii et kui
meil hakkab otsima me oleme

235
00:11:18,330 --> 00:11:20,020
ei kavatse lasta minna liiga kaugele.

236
00:11:20,020 --> 00:11:22,860
Ja nii paneme Homer kell 8.

237
00:11:22,860 --> 00:11:25,151
>> Nüüd hash Maggie ja
tagasi 3, jumal tänatud

238
00:11:25,151 --> 00:11:26,650
me saame lihtsalt panna Maggie seal.

239
00:11:26,650 --> 00:11:29,070
Me ei pea tegema muud
omamoodi katsetamine selle eest.

240
00:11:29,070 --> 00:11:32,000
Nüüd hash Marge ja
Marge ka tagasi 6.

241
00:11:32,000 --> 00:11:39,560
>> Noh 6 on täis, 7 on täis, 8 on täis,
9, kõik õige jumal tänatud, 9 on tühi.

242
00:11:39,560 --> 00:11:41,600
Ma ei pane Marge kell 9.

243
00:11:41,600 --> 00:11:45,280
Juba on näha, et me oleme hakanud
on see probleem, kus nüüd oleme

244
00:11:45,280 --> 00:11:48,780
alates venitada asju omamoodi
on kaugel oma räsikoodid.

245
00:11:48,780 --> 00:11:52,960
Ja et teeta 1, et keskmine
Kui on pidev aega,

246
00:11:52,960 --> 00:11:56,560
hakkab natuke more--
hakanud kipuvad veidi rohkem

247
00:11:56,560 --> 00:11:58,050
suunas teeta n.

248
00:11:58,050 --> 00:12:01,270
Me küsime kaota
ära hash tabeleid.

249
00:12:01,270 --> 00:12:03,902
>> See probleem, et me lihtsalt nägin
on midagi, mida nimetatakse loomist.

250
00:12:03,902 --> 00:12:06,360
Ja mis on tõesti halb umbes
rühmitamise on, et kui sa nüüd

251
00:12:06,360 --> 00:12:09,606
on kaks elementi, mis asuvad üksteise
küljele see muudab veelgi tõenäolisem,

252
00:12:09,606 --> 00:12:11,480
Teil on kaks korda
võimalus, et sa lähed

253
00:12:11,480 --> 00:12:13,516
on teine ​​kokkupõrge
selle klastri,

254
00:12:13,516 --> 00:12:14,890
ja klastri kasvab üks.

255
00:12:14,890 --> 00:12:19,640
Ja sa hoida kasvab ja kasvab
Sinu esinemise tõenäosus kokkupõrke.

256
00:12:19,640 --> 00:12:24,470
Ja lõpuks, see on lihtsalt nii halb
mitte andmete sorteerimist üldse.

257
00:12:24,470 --> 00:12:27,590
>> Teine probleem, kuigi on meil
ikka, ja seni kuni see punkt,

258
00:12:27,590 --> 00:12:30,336
oleme lihtsalt omamoodi
mõista, mida hash tabelis on

259
00:12:30,336 --> 00:12:31,960
me alles on ruumi 10 stringe.

260
00:12:31,960 --> 00:12:37,030
Kui me tahame jätkata hash
kodanike Springfield,

261
00:12:37,030 --> 00:12:38,790
meil on võimalik ainult saada neist 10 on.

262
00:12:38,790 --> 00:12:42,619
Ja kui me püüame lisada 11. või 12.,
meil ei ole koht, kus neid ellu.

263
00:12:42,619 --> 00:12:45,660
Me võiksime lihtsalt ketramine ringi
ringid, püüdes leida tühja koha,

264
00:12:45,660 --> 00:12:49,000
ja me äkki jänni
lõputu silmuse.

265
00:12:49,000 --> 00:12:51,810
>> Nii selline laenab idee
on midagi, mida nimetatakse aheldamine.

266
00:12:51,810 --> 00:12:55,790
Ja see on koht, kus me ei kavatse tuua
ahelloendid tagasi pildil.

267
00:12:55,790 --> 00:13:01,300
Mis siis, kui selle asemel ladustamiseks lihtsalt
andmed ise massiivi,

268
00:13:01,300 --> 00:13:04,471
iga element massiivi võiks
hoidke mitu tükki andmeid?

269
00:13:04,471 --> 00:13:05,970
Noh, et ei ole mõtet, eks?

270
00:13:05,970 --> 00:13:09,280
Me teame, et massiivi saab ainult
hold-- iga massiivi elemendile

271
00:13:09,280 --> 00:13:12,930
saab omada ainult üks tükk
andmete, et andmete tüübi.

272
00:13:12,930 --> 00:13:16,750
>> Aga mis siis, kui andmetüüp
on seotud nimekirja, eks?

273
00:13:16,750 --> 00:13:19,830
Mis siis, kui iga
massiivi element oli

274
00:13:19,830 --> 00:13:22,790
kursor juht ahelloend?

275
00:13:22,790 --> 00:13:24,680
Ja siis me võiks ehitada
need ahelloendid

276
00:13:24,680 --> 00:13:27,120
ja kasvatada neid meelevaldselt,
sest ahelloendid võimaldavad

277
00:13:27,120 --> 00:13:32,090
meil kasvada ja kahaneb palju
paindlikumalt kui massiivi teeb.

278
00:13:32,090 --> 00:13:34,210
Mis siis, kui me nüüd kasutada,
meil võimendada seda, eks?

279
00:13:34,210 --> 00:13:37,760
Meil hakkavad kasvama need ketid
välja need massiivi kohtades.

280
00:13:37,760 --> 00:13:40,740
>> Nüüd mahub lõpmatu
andmemaht või mitte lõpmatu,

281
00:13:40,740 --> 00:13:44,170
suvalise summa
andmed, meie hash tabelis

282
00:13:44,170 --> 00:13:47,760
pole kunagi suubuvad
probleemi kokkupõrget.

283
00:13:47,760 --> 00:13:50,740
Samuti oleme kõrvaldanud
klastrite seda teed.

284
00:13:50,740 --> 00:13:54,380
Ja ka me teame, et kui me sisestada
arvesse ahelloend, kui te mäletate

285
00:13:54,380 --> 00:13:57,779
meie video ahelloendid, üksikult
ahelloendid ja kahekordselt ahelloendid,

286
00:13:57,779 --> 00:13:59,070
see on pidev aega tööd.

287
00:13:59,070 --> 00:14:00,710
Me lihtsalt lisades ees.

288
00:14:00,710 --> 00:14:04,400
>> Ja vaadake üles ja me ei tea,
et otsida üles ahelloend

289
00:14:04,400 --> 00:14:05,785
võib olla probleem, eks?

290
00:14:05,785 --> 00:14:07,910
Meil on otsida
see algusest lõpuni.

291
00:14:07,910 --> 00:14:10,460
Pole juhuslik
juurdepääsu ahelloend.

292
00:14:10,460 --> 00:14:15,610
Aga kui selle asemel üks on seotud
nimekirja, kus lookup oleks O n,

293
00:14:15,610 --> 00:14:19,590
nüüd on meil 10 ahelloendid,
või 1000 ahelloendid,

294
00:14:19,590 --> 00:14:24,120
nüüd on O n jagatud 10,
või O n jagatud 1000.

295
00:14:24,120 --> 00:14:26,940
>> Ja kuigi me rääkisime
teoreetiliselt umbes keerukus

296
00:14:26,940 --> 00:14:30,061
me eirata konstandid, reaalses
maailma need asjad tegelikult oluline,

297
00:14:30,061 --> 00:14:30,560
õige?

298
00:14:30,560 --> 00:14:33,080
Me tegelikult ei märka
et see juhtub

299
00:14:33,080 --> 00:14:36,610
joosta 10 korda kiiremini,
või 1000 korda kiiremini,

300
00:14:36,610 --> 00:14:41,570
sest me jaotavad üks pikk
kett üle 1000 väiksemate ketid.

301
00:14:41,570 --> 00:14:45,090
Ja nii iga kord on meil otsida
läbi üks neist kettidest saame

302
00:14:45,090 --> 00:14:50,290
ignoreerida 999 ketid me ei hooli
umbes, ja lihtsalt otsida, et üks.

303
00:14:50,290 --> 00:14:53,220
>> Milline on keskmiselt
olla 1000 korda lühem.

304
00:14:53,220 --> 00:14:56,460
Ja nii me ikka oleme omamoodi
kalduvad selles suunas keskmiselt juhul

305
00:14:56,460 --> 00:15:01,610
olla pidev aega, kuid
ainult sellepärast, et meil on võimendades

306
00:15:01,610 --> 00:15:03,730
jagades mõned suured konstandiks.

307
00:15:03,730 --> 00:15:05,804
Vaatame, kuidas see võib
tegelikult vaatama küll.

308
00:15:05,804 --> 00:15:08,720
Nii et see oli hash tabelis pidime
enne julistimme hash tabelit, et

309
00:15:08,720 --> 00:15:10,270
oli võimalik säilitada 10 stringe.

310
00:15:10,270 --> 00:15:11,728
Me ei kavatse seda teha enam.

311
00:15:11,728 --> 00:15:13,880
Me juba teame
piiranguid, mis meetodil.

312
00:15:13,880 --> 00:15:20,170
Nüüd on meie hash tabelit saab olema
massiivi 10 sõlmed, viiteid

313
00:15:20,170 --> 00:15:22,120
juhtidele ahelloendid.

314
00:15:22,120 --> 00:15:23,830
>> Ja praegu on null.

315
00:15:23,830 --> 00:15:26,170
Iga üks neist 10 suunanäitajaks on null.

316
00:15:26,170 --> 00:15:29,870
Pole midagi meie
hash tabelit kohe.

317
00:15:29,870 --> 00:15:32,690
>> Nüüd alustame panna mõned
asju sellesse hash tabelit.

318
00:15:32,690 --> 00:15:35,440
Vaatame, kuidas see meetod on
läheb meile kasu natuke.

319
00:15:35,440 --> 00:15:36,760
Olgem nüüd hash Joey.

320
00:15:36,760 --> 00:15:40,210
Me kestab string Joey läbi
räsi funktsioon ja me tagasi 6.

321
00:15:40,210 --> 00:15:41,200
Noh, mis me nüüd teeme?

322
00:15:41,200 --> 00:15:44,090
>> Noh nüüd töötavad ahelloendid,
me ei tööta massiivid.

323
00:15:44,090 --> 00:15:45,881
Ja kui me töötame
lingitud nimekirjad me

324
00:15:45,881 --> 00:15:49,790
tea me peame hakkama dünaamiliselt
eraldada ruumi ja hoone ketid.

325
00:15:49,790 --> 00:15:54,020
See on omamoodi how-- need on peamised
elemendid hoone ahelloend.

326
00:15:54,020 --> 00:15:57,670
Nii saab dünaamiliselt
eraldada ruumi Joey,

327
00:15:57,670 --> 00:16:00,390
ja siis lisame teda ketti.

328
00:16:00,390 --> 00:16:03,170
>> Nüüd vaatame, mida me oleme teinud.

329
00:16:03,170 --> 00:16:06,440
Kui me hash Joey saime räsikood 6.

330
00:16:06,440 --> 00:16:11,790
Nüüd osuti massiivi asukoha 6
osutab juht ahelloend,

331
00:16:11,790 --> 00:16:14,900
ja just nüüd on see ainus
element ahelloend.

332
00:16:14,900 --> 00:16:18,350
Ja sõlme, et
ahelloendid on Joey.

333
00:16:18,350 --> 00:16:22,300
>> Nii et kui meil on vaja üles otsima Joey
hiljem, me lihtsalt hash Joey uuesti,

334
00:16:22,300 --> 00:16:26,300
saame 6 jälle, sest meie
hash funktsiooni on determineeritud.

335
00:16:26,300 --> 00:16:30,400
Ja siis hakkame eesotsas
on seotud nimekirja märkis

336
00:16:30,400 --> 00:16:33,360
poolt massiivi asukohta
6, ja me võime kinnitada,

337
00:16:33,360 --> 00:16:35,650
üle, mis üritab leida Joey.

338
00:16:35,650 --> 00:16:37,780
Ja kui me ehitame meie
hash tabelis tõhusalt,

339
00:16:37,780 --> 00:16:41,790
ja meie hash funktsiooni efektiivselt
levitada andmeid ka,

340
00:16:41,790 --> 00:16:45,770
keskmiselt iga neist seotud
nimekirjad iga massiivi asukohta

341
00:16:45,770 --> 00:16:50,110
saab 1/10 suurust kui me
oli just see ühe suure

342
00:16:50,110 --> 00:16:51,650
ahelloendid kõike seda.

343
00:16:51,650 --> 00:16:55,670
>> Kui me jagada, et tohutu seotud
nimekirja üle 10 ahelloendid

344
00:16:55,670 --> 00:16:57,760
Iga nimekirjas on 1/10 suurust.

345
00:16:57,760 --> 00:17:01,432
Ja nii 10 korda kiiremini
otsida.

346
00:17:01,432 --> 00:17:02,390
Nii teeme seda jälle.

347
00:17:02,390 --> 00:17:04,290
Olgem nüüd hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Ja oletame, et Ross, kui me seda teeme
hash kood saame tagasi on 2.

349
00:17:07,540 --> 00:17:10,630
Noh nüüd me dünaamiliselt eraldada
uus sõlm, paneme Ross, et sõlm,

350
00:17:10,630 --> 00:17:14,900
ja ütleme nüüd massiivi asukohta
2 asemel juhtides tühjaks,

351
00:17:14,900 --> 00:17:18,579
osutab juht seotud
nimekirja, kelle ainus sõlm on Ross.

352
00:17:18,579 --> 00:17:22,660
Ja me saame seda teha veel üks kord, siis
võib hash Rachel ja saada räsikood 4.

353
00:17:22,660 --> 00:17:25,490
malloc uus sõlm, pane Rachel
sõlme, ja öelda massiivi asukohta

354
00:17:25,490 --> 00:17:27,839
4 nüüd juhib pea
on seotud nimekirja, kelle

355
00:17:27,839 --> 00:17:31,420
ainult element juhtub olema Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, aga mis juhtub siis, kui
meil kokkupõrge?

357
00:17:33,470 --> 00:17:38,560
Vaatame, kuidas me käsitleme kokkupõrked
kasutades eraldi ühendamine meetod.

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

359
00:17:39,800 --> 00:17:41,094
Saame räsikood 6.

360
00:17:41,094 --> 00:17:44,010
Meie eelmises näites me olime lihtsalt
ladustamiseks stringid massiivi.

361
00:17:44,010 --> 00:17:45,980
See ilmnes probleem.

362
00:17:45,980 --> 00:17:48,444
>> Me ei taha Tellida
Joey, ja me oleme juba

363
00:17:48,444 --> 00:17:51,110
näha, et saame mõne klastrite
probleeme, kui püüame ja samm

364
00:17:51,110 --> 00:17:52,202
läbi ja põhja.

365
00:17:52,202 --> 00:17:54,660
Aga mis siis, kui me lihtsalt selline
käsitleda seda samamoodi, eks?

366
00:17:54,660 --> 00:17:57,440
See on nagu lisades element
to juht ahelloend.

367
00:17:57,440 --> 00:18:00,220
Lihtsalt malloc ruumi Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Me ütleme Phoebe järgmise pointer punktid
vana juht seotud nimekirja,

369
00:18:04,764 --> 00:18:07,180
ja siis 6 lihtsalt viitab
uue juhi seotud nimekirja.

370
00:18:07,180 --> 00:18:10,150
Ja nüüd vaatame, oleme muutnud Phoebe.

371
00:18:10,150 --> 00:18:14,210
Nüüd on võimalik salvestada kaks
elemente räsikood 6,

372
00:18:14,210 --> 00:18:17,170
ja meil ei ole mingeid probleeme.

373
00:18:17,170 --> 00:18:20,147
>> See on päris palju kõik
seal on ühendamine.

374
00:18:20,147 --> 00:18:21,980
Ja ühendamine on kindlasti
meetod, mis on

375
00:18:21,980 --> 00:18:27,390
saab olema kõige efektiivsem Sulle, kui
te andmete salvestamiseks räsi tabelis.

376
00:18:27,390 --> 00:18:30,890
Aga see kombinatsioon
massiivid ja ahelloendid

377
00:18:30,890 --> 00:18:36,080
kokku, moodustamaks hash tabelit tegelikult
dramaatiliselt parandab teie võimet

378
00:18:36,080 --> 00:18:40,550
talletada suurel hulgal andmeid ja
väga kiiresti ja tõhusalt otsida

379
00:18:40,550 --> 00:18:41,630
läbi, et andmeid.

380
00:18:41,630 --> 00:18:44,150
>> Seal on veel üks
andmestruktuur seal

381
00:18:44,150 --> 00:18:48,700
et võib-olla isegi natuke
parem nii tagamisel

382
00:18:48,700 --> 00:18:51,920
et meie lisamise, kustutamise ja
otsida ajad on veelgi kiirem.

383
00:18:51,920 --> 00:18:55,630
Ja me näeme, et video proovib.

384
00:18:55,630 --> 00:18:58,930
Ma olen Doug Lloyd, see on CS50.

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