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

2
00:00:00,500 --> 00:00:01,900
[Predvaja glasba]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Do sedaj ste
vedo veliko o nizi,

5
00:00:09,150 --> 00:00:11,610
in veste veliko o povezanih seznamih.

6
00:00:11,610 --> 00:00:13,650
In smo razpravljali
prednosti in slabosti, ki smo jih

7
00:00:13,650 --> 00:00:16,620
razpravljali, da povezana sezname
lahko dobite večji in manjši,

8
00:00:16,620 --> 00:00:18,630
vendar pa lahko zasedejo več velikosti.

9
00:00:18,630 --> 00:00:22,359
Polja so veliko bolj enostavne za
uporabo, ampak oni so omejevalni toliko

10
00:00:22,359 --> 00:00:24,900
saj moramo določiti velikost
array na samem začetku

11
00:00:24,900 --> 00:00:26,910
in potem smo obtičali z njim.

12
00:00:26,910 --> 00:00:30,470
>> Ampak to je, ki smo jih precej
izčrpane vse naše teme

13
00:00:30,470 --> 00:00:33,040
o povezanih seznamih in nizi.

14
00:00:33,040 --> 00:00:34,950
Ali imamo?

15
00:00:34,950 --> 00:00:37,720
Mogoče lahko naredimo nekaj
še bolj ustvarjalni.

16
00:00:37,720 --> 00:00:40,950
In to nekako daje
ideja o hash tabele.

17
00:00:40,950 --> 00:00:46,680
>> Torej v hash tabele bomo poskušali
združiti niz s povezani seznam.

18
00:00:46,680 --> 00:00:49,520
Bomo vzeli prednosti
matrike, kot bralno,

19
00:00:49,520 --> 00:00:53,510
da lahko samo pojdi na paleto
element 4 ali matrika element 8

20
00:00:53,510 --> 00:00:55,560
ne da bi čez Ponovil.

21
00:00:55,560 --> 00:00:57,260
To je zelo hitro, kajne?

22
00:00:57,260 --> 00:01:00,714
>> Vendar pa smo tudi želeli, da imajo naše podatke
struktura lahko rastejo in psihiater.

23
00:01:00,714 --> 00:01:02,630
Mi ne potrebujemo, ne bomo
želijo biti omejeni.

24
00:01:02,630 --> 00:01:04,588
In želimo, da bi lahko
dodati in odstraniti stvari

25
00:01:04,588 --> 00:01:08,430
zelo enostavno, ki bodo, če se spomnite,
je zelo zapleten s paleto.

26
00:01:08,430 --> 00:01:11,650
In lahko rečemo to
nova stvar hash tabele.

27
00:01:11,650 --> 00:01:15,190
>> In če se izvaja pravilno,
smo nekako ob

28
00:01:15,190 --> 00:01:18,150
prednosti obeh podatkov
strukture, ki ste jih že videli,

29
00:01:18,150 --> 00:01:19,880
nizi in povezani seznam.

30
00:01:19,880 --> 00:01:23,070
Vstavljanje lahko začnete
nagibajo k theta od 1.

31
00:01:23,070 --> 00:01:26,207
Theta smo res ne razpravlja,
vendar theta je le povprečna primeru

32
00:01:26,207 --> 00:01:27,540
kaj se dejansko dogaja, da se zgodi.

33
00:01:27,540 --> 00:01:29,680
Vi ne vedno dogaja, da
imajo najslabši možni scenarij,

34
00:01:29,680 --> 00:01:32,555
in ne boš vedno dogaja, da imajo
najboljši scenarij, kaj je

35
00:01:32,555 --> 00:01:33,900
povprečna scenarij?

36
00:01:33,900 --> 00:01:36,500
>> Dobro povprečno vstavljanje
v hash tabelo

37
00:01:36,500 --> 00:01:39,370
Lahko začnete priti blizu stalnim časom.

38
00:01:39,370 --> 00:01:41,570
In izbris lahko dobite
zapreti do konstantne časa.

39
00:01:41,570 --> 00:01:44,440
In lookup lahko dobite
zapreti do konstantne časa.

40
00:01:44,440 --> 00:01:48,600
That's-- ne bomo imeli podatkov
struktura še, da lahko to storite,

41
00:01:48,600 --> 00:01:51,180
in tako to že sliši
kot zelo velika stvar.

42
00:01:51,180 --> 00:01:57,010
Smo v resnici ublažilo
slabosti vsaka sama.

43
00:01:57,010 --> 00:01:59,160
>> Da bi dobili ta zmogljivost
nadgradnjo pa smo

44
00:01:59,160 --> 00:02:03,580
je treba premisliti, kako bomo dodali
Podatki v strukturi.

45
00:02:03,580 --> 00:02:07,380
Posebej želimo,
Sam podatek, da nam pove

46
00:02:07,380 --> 00:02:09,725
kjer naj gre v strukturi.

47
00:02:09,725 --> 00:02:12,850
In če bomo potem morali videti, če je to v
struktura, če bomo potrebovali, da ga najdejo,

48
00:02:12,850 --> 00:02:16,610
želimo gledati podatkov
znova in biti sposoben učinkovito,

49
00:02:16,610 --> 00:02:18,910
uporabo podatkov, naključno dostop do nje.

50
00:02:18,910 --> 00:02:20,700
Samo jih je videti na
Podatki bi morali imeti

51
00:02:20,700 --> 00:02:25,890
ideja o tem, kje točno smo
dogaja, da ga najdejo v hash tabele.

52
00:02:25,890 --> 00:02:28,770
>> Zdaj je negativna zgoščene
Miza je, da si res

53
00:02:28,770 --> 00:02:31,770
Precej slabo naročanju ali razvrščanje podatkov.

54
00:02:31,770 --> 00:02:34,970
In v resnici, če začnete
jih uporabiti, da odredijo ali vrsta

55
00:02:34,970 --> 00:02:37,990
Podatki, ki ste izgubili vse
prej ste prednosti

56
00:02:37,990 --> 00:02:40,710
imel v smislu vstavljanja in brisanja.

57
00:02:40,710 --> 00:02:44,060
Čas postane bližje
theta n, in smo v bistvu

58
00:02:44,060 --> 00:02:45,530
nazadovala v povezanem seznamu.

59
00:02:45,530 --> 00:02:48,850
In tako smo le želeli uporabiti hash
mize, če ne skrbijo

60
00:02:48,850 --> 00:02:51,490
ali se podatki razporejene.

61
00:02:51,490 --> 00:02:54,290
Za kontekst, v katerem
jih boste uporabili v CS50

62
00:02:54,290 --> 00:02:58,900
ti verjetno ne skrbi
da se podatki razporejene.

63
00:02:58,900 --> 00:03:03,170
>> Torej hash tabela je kombinacija
iz dveh ločenih delov

64
00:03:03,170 --> 00:03:04,980
s katerimi smo seznanjeni.

65
00:03:04,980 --> 00:03:07,930
Prva je funkcija, ki
smo običajno imenujemo funkcijo razpršitve.

66
00:03:07,930 --> 00:03:11,760
In to funkcijo razpršitve se dogaja, da
vrne neko nenegativno celo število, ki je

67
00:03:11,760 --> 00:03:14,870
smo ponavadi klic hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
Drugi del je matrika, ki je
sposoben shranjevanja podatkov o vrsti mi

69
00:03:20,230 --> 00:03:22,190
želijo postaviti v strukturo podatkov.

70
00:03:22,190 --> 00:03:24,310
Bomo držite off na
povezani seznam element za zdaj

71
00:03:24,310 --> 00:03:27,810
in šele začeti z osnovami
hash tabele, da bi dobili svojo glavo okoli njega,

72
00:03:27,810 --> 00:03:30,210
in potem bomo morda razstrelil
tvoj um malo, ko smo

73
00:03:30,210 --> 00:03:32,920
združujejo nize in sezname povezavo skupaj.

74
00:03:32,920 --> 00:03:35,590
>> Osnovna ideja je, čeprav
je vzamemo nekaj podatkov.

75
00:03:35,590 --> 00:03:37,860
Vodimo te podatke prek
funkcija hash.

76
00:03:37,860 --> 00:03:41,980
In tako se podatki obdelujejo
in ga izpljune številko, OK?

77
00:03:41,980 --> 00:03:44,890
In potem s to številko
smo pravkar shranjevanje podatkov

78
00:03:44,890 --> 00:03:48,930
želimo shraniti v
Niz na tej lokaciji.

79
00:03:48,930 --> 00:03:53,990
Tako na primer imamo morda
to hash tabela nizov.

80
00:03:53,990 --> 00:03:57,350
Ima 10 elementov v njej, tako da
bomo lahko fit 10 strune v njem.

81
00:03:57,350 --> 00:03:59,320
>> Recimo, da želimo, da hash John.

82
00:03:59,320 --> 00:04:02,979
Torej Janeza kot podatkih želimo vstaviti
v ta hash tabelo nekje.

83
00:04:02,979 --> 00:04:03,770
Kje smo ga dal?

84
00:04:03,770 --> 00:04:05,728
No, po navadi s
Niz doslej smo verjetno

85
00:04:05,728 --> 00:04:07,610
bi ga dal v matrično mestu 0.

86
00:04:07,610 --> 00:04:09,960
Toda zdaj imamo to novo funkcijo razpršitve.

87
00:04:09,960 --> 00:04:13,180
>> In recimo, da tečemo po Janezu
skozi to funkcijo razpršitve

88
00:04:13,180 --> 00:04:15,417
in to je izpljune 4.

89
00:04:15,417 --> 00:04:17,500
No, to je, če smo
dogaja, da želijo dati John.

90
00:04:17,500 --> 00:04:22,050
Želimo postaviti John v matriki lokacijo
4, ker če smo izbrskali John again--

91
00:04:22,050 --> 00:04:23,810
recimo kasneje smo
želite iskati in videti

92
00:04:23,810 --> 00:04:26,960
če John obstaja v tem hash
table-- vse moramo storiti

93
00:04:26,960 --> 00:04:30,310
se jo vodijo skozi isti hash
Funkcija, dobili številko 4,

94
00:04:30,310 --> 00:04:33,929
in biti sposobni najti Johna
takoj v našo strukturo podatkov.

95
00:04:33,929 --> 00:04:34,720
To je zelo dobro.

96
00:04:34,720 --> 00:04:36,928
>> Recimo, da imamo sedaj to storiti
še enkrat, želimo hash Paul.

97
00:04:36,928 --> 00:04:39,446
Želimo, da dodate Paul
v ta hash tabelo.

98
00:04:39,446 --> 00:04:42,070
Recimo, da smo tokrat teči
Paul skozi funkcije razpršitve,

99
00:04:42,070 --> 00:04:44,600
hashcode da se ustvari je 6.

100
00:04:44,600 --> 00:04:47,340
No, zdaj bomo lahko dal Pavlu
na lokaciji matrike 6.

101
00:04:47,340 --> 00:04:50,040
In če moramo pogledati, ali
Paul je v tem hash tabeli

102
00:04:50,040 --> 00:04:53,900
vse, kar morate storiti je, teči Paul
s pomočjo funkcije razpršitve spet

103
00:04:53,900 --> 00:04:55,830
in bomo dobili 6 spet ven.

104
00:04:55,830 --> 00:04:57,590
>> In potem smo samo pogled
na matrično lokaciji 6.

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

106
00:04:58,910 --> 00:05:00,160
Če je tako, da je v hash tabele.

107
00:05:00,160 --> 00:05:01,875
Paul ni tam?

108
00:05:01,875 --> 00:05:03,000
On ni v hash tabele.

109
00:05:03,000 --> 00:05:05,720
To je precej preprosta.

110
00:05:05,720 --> 00:05:07,770
>> Zdaj kako definirate funkcijo razpršitve?

111
00:05:07,770 --> 00:05:11,460
No, tam je res ni omejitev na
število možnih funkcij hash.

112
00:05:11,460 --> 00:05:14,350
V bistvu je število res,
res dobri na internetu.

113
00:05:14,350 --> 00:05:17,560
Obstaja nekaj res,
res slabe na internetu.

114
00:05:17,560 --> 00:05:21,080
Prav tako je zelo enostavno
napisati slabega.

115
00:05:21,080 --> 00:05:23,760
>> Torej, kaj naredi gor dober
hash funkcijo, kajne?

116
00:05:23,760 --> 00:05:27,280
No dobra funkcija hash smeli
uporabljajte samo so zgoščene podatke,

117
00:05:27,280 --> 00:05:29,420
in vse podatke, ki zgoščen.

118
00:05:29,420 --> 00:05:32,500
Torej ne želimo uporabiti anything--
ne vključujejo ničesar

119
00:05:32,500 --> 00:05:35,560
drug razen podatkov.

120
00:05:35,560 --> 00:05:37,080
In želimo uporabiti vse podatke.

121
00:05:37,080 --> 00:05:39,830
Nočemo, da samo uporabite kos
od tega, želimo uporabiti vse.

122
00:05:39,830 --> 00:05:41,710
Funkcija hash smeli
tudi deterministična.

123
00:05:41,710 --> 00:05:42,550
Kaj to pomeni?

124
00:05:42,550 --> 00:05:46,200
No, to pomeni, da vsakič, ko smo
opraviti natančno isto podatek

125
00:05:46,200 --> 00:05:50,040
v funkcijo razpršitve smo vedno
dobil isto hashcode ven.

126
00:05:50,040 --> 00:05:52,870
Če sem mimo Johna Into The
hash funkcija pridem ven 4.

127
00:05:52,870 --> 00:05:56,110
Moral bi biti sposoben narediti, da je 10.000
krat in bom vedno dobili 4.

128
00:05:56,110 --> 00:06:00,810
Torej ni naključnih števil učinkovito
lahko sodelujejo v našem hash tables--

129
00:06:00,810 --> 00:06:02,750
v naših hash funkcij.

130
00:06:02,750 --> 00:06:05,750
>> Funkcija hash naj bi tudi
enakomerno porazdeli podatke.

131
00:06:05,750 --> 00:06:09,700
Če vsakič, ko zaženete podatkov prek
hash funkcija dobiš hashcode 0,

132
00:06:09,700 --> 00:06:11,200
da je to verjetno ni tako veliko, kajne?

133
00:06:11,200 --> 00:06:14,600
Boste verjetno želeli, da velik
vrsta hash kode.

134
00:06:14,600 --> 00:06:17,190
Prav tako se stvari lahko širijo
v celotnem tabeli.

135
00:06:17,190 --> 00:06:23,210
In prav bi bilo super, če res
podobne podatke, kot so John in Jonatanom,

136
00:06:23,210 --> 00:06:26,320
Mogoče so bili razporejeni za tehtanje
različne lokacije v hash tabele.

137
00:06:26,320 --> 00:06:28,750
To bi bilo lepo prednost.

138
00:06:28,750 --> 00:06:31,250
>> Tukaj je primer funkcije razpršitve.

139
00:06:31,250 --> 00:06:33,150
Sem napisal tole gor prej.

140
00:06:33,150 --> 00:06:35,047
To ni posebej
dobra funkcija razpršitve

141
00:06:35,047 --> 00:06:37,380
iz razlogov, ki v resnici ne
nosi dogaja v tem trenutku.

142
00:06:37,380 --> 00:06:41,040
Ampak vidite, kaj se dogaja tukaj?

143
00:06:41,040 --> 00:06:44,420
Zdi se, kot da smo razglasitvi spremenljivko
imenovano vsoto in jo nastavite enaka 0.

144
00:06:44,420 --> 00:06:50,010
In potem očitno delam nekaj
dokler strstr [j] ni enako

145
00:06:50,010 --> 00:06:52,490
da poševnica nazaj 0.

146
00:06:52,490 --> 00:06:54,870
Kaj počnem tukaj?

147
00:06:54,870 --> 00:06:57,440
>> To je v bistvu samo še en
način izvajanja [? STRL?]

148
00:06:57,440 --> 00:06:59,773
in odkrivanje, ko ste
prišli do konca niza.

149
00:06:59,773 --> 00:07:02,480
Torej, jaz ne bi bilo treba dejansko
izračunati dolžino niza,

150
00:07:02,480 --> 00:07:05,640
Jaz sem samo s pomočjo, ko sem udaril
poševnica nazaj 0 značaj vem

151
00:07:05,640 --> 00:07:07,185
Sem dosegel konec niza.

152
00:07:07,185 --> 00:07:09,560
In potem grem naprej
ponavljanjem skozi ta niz,

153
00:07:09,560 --> 00:07:15,310
dodajanje strstr [J], da povzamem, in nato na
konec dneva bomo vrnili znesek mod

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

155
00:07:16,200 --> 00:07:18,700
>> V bistvu vse to hash
funkcija počne se sešteva

156
00:07:18,700 --> 00:07:23,450
vse vrednosti ASCII
moj niz, nato pa je

157
00:07:23,450 --> 00:07:26,390
vračanje nekaj hashcode
modded jih HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Verjetno je velikost
moje array, kajne?

159
00:07:29,790 --> 00:07:33,160
Nočem, da bi dobili hash
Kode če moj array je velikosti 10,

160
00:07:33,160 --> 00:07:35,712
Ne želim, da bi dobili
od hash kode 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, ne morem postaviti stvari v
tiste lokacije matrike,

162
00:07:38,690 --> 00:07:39,790
da bi bilo nezakonito.

163
00:07:39,790 --> 00:07:42,130
Sem trpel napako segmentacije.

164
00:07:42,130 --> 00:07:45,230
>> Zdaj tukaj je še en hiter stran.

165
00:07:45,230 --> 00:07:48,470
Na splošno ste verjetno ne bo
želite napisati svoje hash funkcije.

166
00:07:48,470 --> 00:07:50,997
Dejansko je malo
umetnost, ne znanost.

167
00:07:50,997 --> 00:07:52,580
In tam je veliko, da gre v njih.

168
00:07:52,580 --> 00:07:55,288
Internet, kot sem rekel, je polno
zares dobrih hash funkcije,

169
00:07:55,288 --> 00:07:58,470
in morate uporabljati internet, da bi
našli hash funkcije, ker to je res

170
00:07:58,470 --> 00:08:03,230
le nekako nepotrebno
zapravljanje časa, da ustvarite svojo.

171
00:08:03,230 --> 00:08:05,490
>> Lahko napišete preproste tiste
za testiranje.

172
00:08:05,490 --> 00:08:08,323
Toda, ko ste dejansko se dogaja, da
začetek razpršitev podatkov in shranjevanje

173
00:08:08,323 --> 00:08:10,780
v hash tabelo ste ga
Verjetno boš želel

174
00:08:10,780 --> 00:08:14,580
Za uporabo nekatere funkcije, ki je ustvarjen
za vas, da obstaja na internetu.

175
00:08:14,580 --> 00:08:17,240
Če vam samo se prepričajte,
citirati svoje vire.

176
00:08:17,240 --> 00:08:21,740
Ni razloga, da bi
plagiarize ničesar tukaj.

177
00:08:21,740 --> 00:08:25,370
>> Računalnik znanstvena skupnost je
definitivno raste, in res vrednote

178
00:08:25,370 --> 00:08:28,796
open source, in to je res pomembno
citirati svoje vire, da se ljudje

179
00:08:28,796 --> 00:08:30,670
lahko dobite pripis za
delo, da oni

180
00:08:30,670 --> 00:08:32,312
delaš v korist skupnosti.

181
00:08:32,312 --> 00:08:34,020
Torej vedno sure--
in ne samo za hash

182
00:08:34,020 --> 00:08:37,270
funkcije, ampak na splošno, ko vas
uporabo kode iz zunanjega vira,

183
00:08:37,270 --> 00:08:38,299
Vedno navajajo svoj vir.

184
00:08:38,299 --> 00:08:43,500
Dati kredit, da osebe, ki je
nekaj dela, tako da ne bi bilo treba.

185
00:08:43,500 --> 00:08:46,720
>> OK, tako da je ponovno to
hash tabela za sekundo.

186
00:08:46,720 --> 00:08:48,780
To je, kjer se nam z leve
off ko smo vstavi

187
00:08:48,780 --> 00:08:53,300
John in Paul v tem hash tabelo.

188
00:08:53,300 --> 00:08:55,180
Ali vidiš problem tukaj?

189
00:08:55,180 --> 00:08:58,410
Morda boste videli dva.

190
00:08:58,410 --> 00:09:02,240
Ampak predvsem, kajne
glej to možno težavo?

191
00:09:02,240 --> 00:09:06,770
>> Kaj pa, če sem hash Ringo, in
Izkazalo se je, da je po predelavi

192
00:09:06,770 --> 00:09:14,000
da so podatki prek funkcije razpršitve
Ringo ustvarila tudi hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Sem že dobil podatke na
hashcode-- lokacija matrika 6.

194
00:09:16,810 --> 00:09:22,000
Tako da je verjetno, da bo malo
problem zame, kajne?

195
00:09:22,000 --> 00:09:23,060
>> Pravimo to trčenje.

196
00:09:23,060 --> 00:09:26,460
In pride do trčenja, ko dva
deli podatkov teče skozi isti hash

197
00:09:26,460 --> 00:09:29,200
Funkcija dobimo enako hashcode.

198
00:09:29,200 --> 00:09:32,850
Verjetno bomo še vedno želijo, da bi dobili tako
koščki podatkov v hash tabele,

199
00:09:32,850 --> 00:09:36,330
drugače mi ne bi bilo tekmovanje v teku Ringo
poljubno skozi funkcije razpršitve.

200
00:09:36,330 --> 00:09:40,870
Bomo verjetno želeli, da bi dobili
Ringo v tem polju.

201
00:09:40,870 --> 00:09:46,070
>> Kako to storiti, čeprav, če je
in Paul sta donos hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Mi ne želite prepisati Pavla,
želimo Paul biti tam.

203
00:09:49,520 --> 00:09:52,790
Zato moramo najti način, da bi dobili
elementi v hash tabele, ki

204
00:09:52,790 --> 00:09:56,550
še vedno ohranja Naš hiter
vstavljanje in hiter pogled navzgor.

205
00:09:56,550 --> 00:10:01,350
In eden od načinov za spopadanje s tem je, da
storiti nekaj, kar ti linearni sondiranje.

206
00:10:01,350 --> 00:10:04,170
>> Z uporabo te metode, če imamo
trčenje, no, kaj naj naredimo?

207
00:10:04,170 --> 00:10:08,580
No, ne moremo ga dal v matriki lokacijo
6, ali karkoli hashcode je bil ustvarjen,

208
00:10:08,580 --> 00:10:10,820
dajmo mu ga na hashcode plus 1.

209
00:10:10,820 --> 00:10:13,670
In če je to v celoti Oglejmo
ga dal v hashcode plus 2.

210
00:10:13,670 --> 00:10:17,420
Korist od tega bitja, če je on
ne točno tam, kjer mislimo, da je,

211
00:10:17,420 --> 00:10:20,850
in moramo začeti iskati,
Mogoče mi ne bi bilo treba iti predaleč.

212
00:10:20,850 --> 00:10:23,900
Morda ne bi bilo treba iskati
vseh n elementi hash tabele.

213
00:10:23,900 --> 00:10:25,790
Morda bomo morali iskati
Nekaj ​​od njih.

214
00:10:25,790 --> 00:10:30,680
>> In tako smo še vedno težijo k
da v povprečju velja, da so blizu 1 vs

215
00:10:30,680 --> 00:10:34,280
blizu do n, tako da morda, da bo delovalo.

216
00:10:34,280 --> 00:10:38,010
Torej, da vidimo, kako to
lahko izšlo v resnici.

217
00:10:38,010 --> 00:10:41,460
In poglejmo, če morda lahko zazna
problem, da lahko pride do tu.

218
00:10:41,460 --> 00:10:42,540
>> Recimo, da smo izbrskali Bart.

219
00:10:42,540 --> 00:10:45,581
Torej, zdaj gremo teči nov niz
nizov s pomočjo funkcije razpršitve,

220
00:10:45,581 --> 00:10:48,460
in tečemo Bart skozi hash
Funkcija, smo dobili hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Mi si oglejte, vidimo 6 je
prazna, tako da bomo lahko dal Bart tam.

222
00:10:52,100 --> 00:10:55,410
>> Zdaj smo hash Liso in da
Prav tako ustvarja hashcode 6.

223
00:10:55,410 --> 00:10:58,330
No sedaj, da smo s pomočjo tega
Linearni sondiranje metodo začnemo na 6,

224
00:10:58,330 --> 00:10:59,330
vidimo, da je 6 polni.

225
00:10:59,330 --> 00:11:00,990
Ne moremo dati Liso v 6.

226
00:11:00,990 --> 00:11:02,090
Torej, kam gremo?

227
00:11:02,090 --> 00:11:03,280
Pojdimo do 7.

228
00:11:03,280 --> 00:11:04,610
7 je prazna, tako da deluje.

229
00:11:04,610 --> 00:11:06,510
Torej, kaj je dal Lisa tam.

230
00:11:06,510 --> 00:11:10,200
>> Zdaj smo hash Homerja in smo dobili 7.

231
00:11:10,200 --> 00:11:13,380
OK, dobro vemo, da je 7 je poln
zdaj, zato ne moremo dati Homer tam.

232
00:11:13,380 --> 00:11:14,850
Torej, pojdimo do 8.

233
00:11:14,850 --> 00:11:15,664
8 na voljo?

234
00:11:15,664 --> 00:11:18,330
Ja, in 8 je blizu 7, tako da, če
moramo začeti iskati smo

235
00:11:18,330 --> 00:11:20,020
ne bo treba iti predaleč.

236
00:11:20,020 --> 00:11:22,860
In tako da je dal Homer ob 8.

237
00:11:22,860 --> 00:11:25,151
>> Zdaj smo hash Maggie in
vrne 3, hvala bogu

238
00:11:25,151 --> 00:11:26,650
smo sposobni samo dal Maggie tam.

239
00:11:26,650 --> 00:11:29,070
Mi ne bi bilo treba storiti vse
nekako sondiranje za to.

240
00:11:29,070 --> 00:11:32,000
Zdaj smo hash Marge, in
Marge tudi vrne 6.

241
00:11:32,000 --> 00:11:39,560
>> No 6 polna, 7 je poln, 8 je polna,
9, v redu hvala bogu, 9 je prazna.

242
00:11:39,560 --> 00:11:41,600
Jaz lahko postavite Marge ob 9.

243
00:11:41,600 --> 00:11:45,280
Že vidimo, da začenjamo
da ima ta problem, kjer smo zdaj

244
00:11:45,280 --> 00:11:48,780
začenja se raztezajo stvari nekako
od daleč od svojih hash kode.

245
00:11:48,780 --> 00:11:52,960
In da theta po 1, da je povprečna
V primeru da je konstantna čas,

246
00:11:52,960 --> 00:11:56,560
se začenja, da bi dobili malo more--
začenja ponavadi malo bolj

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

248
00:11:58,050 --> 00:12:01,270
Mi smo začeli izgubljati da
Prednost hash tabel.

249
00:12:01,270 --> 00:12:03,902
>> Ta problem, ki smo ga pravkar videli
je nekaj, kar se imenuje grozdenje.

250
00:12:03,902 --> 00:12:06,360
In kaj je res slabo o
grozdenje je, da ko vas zdaj

251
00:12:06,360 --> 00:12:09,606
ima dva elementa, ki so drug ob
drugo pa je še bolj verjetno,

252
00:12:09,606 --> 00:12:11,480
imate dvakrat več
priložnost, da greste

253
00:12:11,480 --> 00:12:13,516
da imajo še eno trčenje
s tem grozdu,

254
00:12:13,516 --> 00:12:14,890
in grozd bo rasla po enega.

255
00:12:14,890 --> 00:12:19,640
In si bomo še naprej raste in raste
vaša verjetnost ob trčenju.

256
00:12:19,640 --> 00:12:24,470
In na koncu, da je ravno tako slabo
saj ni sortiranje podatkov na vseh.

257
00:12:24,470 --> 00:12:27,590
>> Druga težava, čeprav je, da smo
pri miru in doslej do te točke,

258
00:12:27,590 --> 00:12:30,336
pravkar smo bili nekako
razumevanje, kaj je hash tabela,

259
00:12:30,336 --> 00:12:31,960
imamo še vedno le prostor za 10 nizov.

260
00:12:31,960 --> 00:12:37,030
Če želimo, da še naprej hash
državljani Springfield,

261
00:12:37,030 --> 00:12:38,790
bomo lahko dobili le 10 od njih tam.

262
00:12:38,790 --> 00:12:42,619
In če bomo poskušali dodati 11. ali 12.,
nimamo mesto da bi jih dal.

263
00:12:42,619 --> 00:12:45,660
Lahko bi se samo vrti okoli v
krogi poskušajo najti prazno mesto,

264
00:12:45,660 --> 00:12:49,000
in smo dobili morda zaljubljen
v neskončni zanki.

265
00:12:49,000 --> 00:12:51,810
>> Tako da je ta vrsta primerna za idejo
nečesa imenovano veriženje.

266
00:12:51,810 --> 00:12:55,790
In to je, kam gremo, da bi
povezani seznami nazaj v sliko.

267
00:12:55,790 --> 00:13:01,300
Kaj če bi namesto shranjevanja samo
Sam podatek v matriki,

268
00:13:01,300 --> 00:13:04,471
vsak element matrike lahko
držite več kosov podatkov?

269
00:13:04,471 --> 00:13:05,970
No, da nima smisla, kajne?

270
00:13:05,970 --> 00:13:09,280
Vemo, da lahko le niz
hold-- vsak element matrike

271
00:13:09,280 --> 00:13:12,930
lahko ima samo en kos
podatkov te vrste podatkov.

272
00:13:12,930 --> 00:13:16,750
>> Toda kaj, če ta vrsta podatkov
je povezani seznam, kajne?

273
00:13:16,750 --> 00:13:19,830
Pa kaj, če vsak
element matrike je

274
00:13:19,830 --> 00:13:22,790
kazalec na čelu povezani seznam?

275
00:13:22,790 --> 00:13:24,680
In potem lahko gradimo
ti povezani seznami

276
00:13:24,680 --> 00:13:27,120
in jim rastejo poljubno,
ker povezani seznami omogočajo

277
00:13:27,120 --> 00:13:32,090
nas, da raste in psihiater veliko več
fleksibilno kot array počne.

278
00:13:32,090 --> 00:13:34,210
Pa kaj, če smo zdaj uporabljajo,
smo vzvod to, kajne?

279
00:13:34,210 --> 00:13:37,760
Začetek smo gojili te verige
od teh nizov lokacijah.

280
00:13:37,760 --> 00:13:40,740
>> Sedaj lahko fit neskončno
količina podatkov, ali ni neskončna,

281
00:13:40,740 --> 00:13:44,170
poljubna količina
podatkov, v našem hash tabelo

282
00:13:44,170 --> 00:13:47,760
ne da bi kdaj teče v
problem trka.

283
00:13:47,760 --> 00:13:50,740
Prav tako smo jih odpraviti
grozdenje s tem.

284
00:13:50,740 --> 00:13:54,380
In dobro vemo, da ko smo vstavite
v povezani seznam, če se spomnite

285
00:13:54,380 --> 00:13:57,779
iz naše video na povezanih seznamov, posamezno
povezani seznami in dvojno povezani seznam,

286
00:13:57,779 --> 00:13:59,070
to je konstantna operacija čas.

287
00:13:59,070 --> 00:14:00,710
Mi smo samo tako, da je spredaj.

288
00:14:00,710 --> 00:14:04,400
>> In poglej gor, dobro vemo,
da pogledate v povezanem seznamu

289
00:14:04,400 --> 00:14:05,785
je lahko problem, kajne?

290
00:14:05,785 --> 00:14:07,910
Moramo iskati prek
je od začetka do konca.

291
00:14:07,910 --> 00:14:10,460
Ni naključno
dostop v povezanem seznamu.

292
00:14:10,460 --> 00:14:15,610
Toda, če namesto da eno povezano
seznam, kjer bi bilo iskanje O n,

293
00:14:15,610 --> 00:14:19,590
imamo zdaj 10 povezanih seznamov,
ali 1.000 povezani seznami,

294
00:14:19,590 --> 00:14:24,120
zdaj je O n deljeno z 10,
ali O n, deljeno s 1.000.

295
00:14:24,120 --> 00:14:26,940
>> In medtem, ko smo govorili
teoretično o kompleksnosti

296
00:14:26,940 --> 00:14:30,061
odmislimo konstante, v realnem
svet te stvari dejansko pomembno,

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

298
00:14:30,560 --> 00:14:33,080
Pravzaprav bomo opazili
da se to zgodi

299
00:14:33,080 --> 00:14:36,610
teči 10-krat hitreje,
ali 1.000-krat hitreje,

300
00:14:36,610 --> 00:14:41,570
ker smo distribucijo eno dolgo
veriga poda 1.000 manjših verig.

301
00:14:41,570 --> 00:14:45,090
In tako vsakič, ko imamo za iskanje
skozi eno od teh verig moremo

302
00:14:45,090 --> 00:14:50,290
prezreti 999 verig nam ni mar
o, in samo iskanje, da je eden.

303
00:14:50,290 --> 00:14:53,220
>> Ki je v povprečju
1.000-krat krajši.

304
00:14:53,220 --> 00:14:56,460
In tako smo še nekako
težijo k temu povprečnega primera

305
00:14:56,460 --> 00:15:01,610
, da so stalno časa, vendar
samo zato, ker smo vplivno

306
00:15:01,610 --> 00:15:03,730
delimo z neko ogromno konstantnim faktorjem.

307
00:15:03,730 --> 00:15:05,804
Poglejmo, kako bi to lahko
dejansko videti, čeprav.

308
00:15:05,804 --> 00:15:08,720
Torej je bil to hash tabelo smo imeli
preden smo razglasili za razpršene tabele, ki

309
00:15:08,720 --> 00:15:10,270
je lahko shrani 10 nizov.

310
00:15:10,270 --> 00:15:11,728
Ne bomo storiti več.

311
00:15:11,728 --> 00:15:13,880
Smo že vedeli
omejitve te metode.

312
00:15:13,880 --> 00:15:20,170
Sedaj naš hash tabele, se dogaja, da
niz 10 vozlišč, kazalci

313
00:15:20,170 --> 00:15:22,120
vodjem povezanih seznamov.

314
00:15:22,120 --> 00:15:23,830
>> In zdaj je ničen.

315
00:15:23,830 --> 00:15:26,170
Vsak od teh 10 kazalcev, je nična.

316
00:15:26,170 --> 00:15:29,870
Nič ni v naši
hash tabelo zdaj.

317
00:15:29,870 --> 00:15:32,690
>> Zdaj pa začnimo postaviti nekatere
Stvari v tej hash tabele.

318
00:15:32,690 --> 00:15:35,440
In poglejmo, kako se je ta metoda
dogaja, da nam koristijo malo.

319
00:15:35,440 --> 00:15:36,760
Poglejmo zdaj hash Joey.

320
00:15:36,760 --> 00:15:40,210
Bomo bo potekal niz Joey skozi
funkcija razpršitve in vrnemo 6.

321
00:15:40,210 --> 00:15:41,200
No, kaj pa zdaj?

322
00:15:41,200 --> 00:15:44,090
>> No, zdaj delajo s povezanimi seznamov,
ne bomo delo z nizi.

323
00:15:44,090 --> 00:15:45,881
In ko delamo
s povezanimi seznamov smo

324
00:15:45,881 --> 00:15:49,790
vedeti moramo, da dinamično začeti
dodeljevanja prostora in gradnjo verige.

325
00:15:49,790 --> 00:15:54,020
To je nekako how-- ti so jedro
elementi izgradnjo povezani seznam.

326
00:15:54,020 --> 00:15:57,670
Torej Dovolite dinamično
dodeliti prostor za Joeya,

327
00:15:57,670 --> 00:16:00,390
nato pa dodajte ga v verige.

328
00:16:00,390 --> 00:16:03,170
>> Torej, zdaj poglej, kaj smo naredili.

329
00:16:03,170 --> 00:16:06,440
Ko smo hash Joey imamo hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Zdaj se kazalec na matrično lokaciji 6
opozarja na glavo povezanega seznama

331
00:16:11,790 --> 00:16:14,900
in zdaj je edina
element povezani seznam.

332
00:16:14,900 --> 00:16:18,350
In s tem, da vozlišče
povezani seznam je Joey.

333
00:16:18,350 --> 00:16:22,300
>> Torej, če bomo morali pogledati Joey
kasneje, smo samo hash Joey spet,

334
00:16:22,300 --> 00:16:26,300
smo dobili 6 spet, ker je naša
hash funkcija je deterministično.

335
00:16:26,300 --> 00:16:30,400
In potem začnemo na čelu
od povezanega seznama opozoril

336
00:16:30,400 --> 00:16:33,360
jih matrike lokacijo
6, in bomo lahko Ponovil

337
00:16:33,360 --> 00:16:35,650
čez, da poskuša najti Joey.

338
00:16:35,650 --> 00:16:37,780
In če bomo gradili
učinkovito hash tabelo,

339
00:16:37,780 --> 00:16:41,790
in naša hash funkcija učinkovito
za distribucijo podatkov dobro,

340
00:16:41,790 --> 00:16:45,770
v povprečju vsak od tiste, povezane
Seznami na vsakem diod lokacijo

341
00:16:45,770 --> 00:16:50,110
bo 1/10 velikost, če smo
Pravkar ga je imel kot en sam ogromen

342
00:16:50,110 --> 00:16:51,650
povezani seznam z vsem v njem.

343
00:16:51,650 --> 00:16:55,670
>> Če bomo razdelili, da je velik povezan
seznam čez 10 povezanih seznamov

344
00:16:55,670 --> 00:16:57,760
vsak seznam bo 1/10 velikost.

345
00:16:57,760 --> 00:17:01,432
In s tem 10-krat hitreje
iskanje skozi.

346
00:17:01,432 --> 00:17:02,390
Torej, kaj je to storiti še enkrat.

347
00:17:02,390 --> 00:17:04,290
Poglejmo zdaj hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> In recimo, Ross, ko to naredimo
hash code bomo dobili nazaj, je 2.

349
00:17:07,540 --> 00:17:10,630
No, zdaj smo dinamično dodeli
novo vozlišče, smo se Ross v tem vozlišču,

350
00:17:10,630 --> 00:17:14,900
in smo rekli, zdaj matrika lokacijo
2, namesto da kaže na ničlo,

351
00:17:14,900 --> 00:17:18,579
opozarja na čelu povezani
Seznam katerega edino vozlišče je Ross.

352
00:17:18,579 --> 00:17:22,660
In bomo lahko to storijo še enkrat, mi
lahko hash Rachel in dobili hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc novo vozlišče, dal Rachel v
vozlišče, in pravijo lokacijo niz

354
00:17:25,490 --> 00:17:27,839
4 zdaj opozarja na glavi
iz povezanega seznama S

355
00:17:27,839 --> 00:17:31,420
Edini element, se zgodi, da bo Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, ampak kaj se zgodi, če
imamo trčenje?

357
00:17:33,470 --> 00:17:38,560
Pa poglejmo, kako ravnamo trčenja
z ločeno metodo veriženja.

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

359
00:17:39,800 --> 00:17:41,094
Smo dobili hashcode 6.

360
00:17:41,094 --> 00:17:44,010
V prejšnjem primeru smo pravkar
shranjevanje strune v array.

361
00:17:44,010 --> 00:17:45,980
To je problem.

362
00:17:45,980 --> 00:17:48,444
>> Nočemo, da clobber
Joey, in smo jih že

363
00:17:48,444 --> 00:17:51,110
razvidno, da bomo lahko dobili nekaj gruč
težave, če bomo poskušali in korak

364
00:17:51,110 --> 00:17:52,202
skozi in sonda.

365
00:17:52,202 --> 00:17:54,660
Toda kaj, če smo le nekako
zdravljenje je to na enak način, kajne?

366
00:17:54,660 --> 00:17:57,440
To je tako kot dodaja element
z glavo povezanega seznama.

367
00:17:57,440 --> 00:18:00,220
Naj samo malloc prostor za Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Bomo rekli naslednji kazalec točk Phoebe je
s starim glavo povezanem seznamu

369
00:18:04,764 --> 00:18:07,180
in nato na 6 samo opozarja na
Novi vodja povezanega seznama.

370
00:18:07,180 --> 00:18:10,150
In zdaj poglej, smo spremenili Phoebe v.

371
00:18:10,150 --> 00:18:14,210
Sedaj lahko shranite dve
elementi z hashcode 6,

372
00:18:14,210 --> 00:18:17,170
in nimamo nobenih težav.

373
00:18:17,170 --> 00:18:20,147
>> To je zal veliko vse
tam je veriženje.

374
00:18:20,147 --> 00:18:21,980
In veriženje je definitivno
metoda, ki je

375
00:18:21,980 --> 00:18:27,390
dogaja, da je najbolj učinkovita za vas, če
ste shranjevanje podatkov v hash tabele.

376
00:18:27,390 --> 00:18:30,890
Toda ta kombinacija
nizi in povezani seznami

377
00:18:30,890 --> 00:18:36,080
skupaj tvorita razpršene tabele res
dramatično izboljša vašo sposobnost

378
00:18:36,080 --> 00:18:40,550
za shranjevanje velike količine podatkov, in
zelo hitro in učinkovito iskanje

379
00:18:40,550 --> 00:18:41,630
preko teh podatkov.

380
00:18:41,630 --> 00:18:44,150
>> Tam je še ena več
podatkovna struktura tam

381
00:18:44,150 --> 00:18:48,700
da je morda celo malce
bolje v smislu zagotavljanja

382
00:18:48,700 --> 00:18:51,920
da je naša vstavljanje, brisanje in
poglej gor časi so še hitreje.

383
00:18:51,920 --> 00:18:55,630
In bomo videli, da je v video na poskusih.

384
00:18:55,630 --> 00:18:58,930
Sem Doug Lloyd, to je CS50.

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