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

2
00:00:00,500 --> 00:00:01,900
[Glazbom]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Do sada ste
znam puno o polja,

5
00:00:09,150 --> 00:00:11,610
i znate puno o povezanim popisima.

6
00:00:11,610 --> 00:00:13,650
A mi smo razgovarali o
prednosti i mane, da smo

7
00:00:13,650 --> 00:00:16,620
objašnjeno da povezane liste
može dobiti veći i manji,

8
00:00:16,620 --> 00:00:18,630
ali oni zauzimaju više veličina.

9
00:00:18,630 --> 00:00:22,359
Nizovi su mnogo više neposredan
koristiti, ali oni su restriktivni u koliko

10
00:00:22,359 --> 00:00:24,900
kao što smo postaviti veličinu
Niz na samom početku

11
00:00:24,900 --> 00:00:26,910
a onda smo zapeli s njim.

12
00:00:26,910 --> 00:00:30,470
>> Ali to je, mi smo prilično mnogo
iscrpljene sve naše teme

13
00:00:30,470 --> 00:00:33,040
o povezanim popisima i polja.

14
00:00:33,040 --> 00:00:34,950
Ili smo?

15
00:00:34,950 --> 00:00:37,720
Možda možemo nešto učiniti
još kreativniji.

16
00:00:37,720 --> 00:00:40,950
I to vrsta posuđuje
ideja hash tablici.

17
00:00:40,950 --> 00:00:46,680
>> Tako je u hash tablici ćemo pokušati
kombinirati niz s popisa povezane.

18
00:00:46,680 --> 00:00:49,520
Idemo uzeti prednosti
od polja, kao što slučajnim pristupom,

19
00:00:49,520 --> 00:00:53,510
biti u mogućnosti samo ići niz
Element 4 ili niz elementa 8

20
00:00:53,510 --> 00:00:55,560
bez ponoviti preko.

21
00:00:55,560 --> 00:00:57,260
To je prilično brzo, zar ne?

22
00:00:57,260 --> 00:01:00,714
>> Ali, mi također žele imati svoje podatke
Struktura moći rasti i smanjivati.

23
00:01:00,714 --> 00:01:02,630
Mi ne trebamo, mi ne
želim biti ograničen.

24
00:01:02,630 --> 00:01:04,588
A mi želimo biti u mogućnosti
dodati i ukloniti stvari

25
00:01:04,588 --> 00:01:08,430
vrlo jednostavno, što ako se sjetiti,
vrlo je složen s nizom.

26
00:01:08,430 --> 00:01:11,650
I možemo zvati
Nova stvar hash tablicu.

27
00:01:11,650 --> 00:01:15,190
>> A ako se provodi ispravno,
Mi smo vrsta uzimanja

28
00:01:15,190 --> 00:01:18,150
Prednosti i podatke
Strukture koje ste već vidjeli,

29
00:01:18,150 --> 00:01:19,880
polja i povezane liste.

30
00:01:19,880 --> 00:01:23,070
Ubacivanje može početi
skloni theta od 1.

31
00:01:23,070 --> 00:01:26,207
Theta nismo stvarno razgovarali,
ali teta je samo prosječan slučaj,

32
00:01:26,207 --> 00:01:27,540
što se zapravo će se dogoditi.

33
00:01:27,540 --> 00:01:29,680
Nećeš uvijek će
imaju najgori mogući scenarij,

34
00:01:29,680 --> 00:01:32,555
i niste uvijek će imati
najboljem slučaju, tako što je

35
00:01:32,555 --> 00:01:33,900
prosječan scenarij?

36
00:01:33,900 --> 00:01:36,500
>> Pa u prosjeku za umetanje
u hash tablici

37
00:01:36,500 --> 00:01:39,370
možete početi da se u neposrednoj blizini konstantnom vremenu.

38
00:01:39,370 --> 00:01:41,570
I brisanje može dobiti
zatvoriti stalnom vrijeme.

39
00:01:41,570 --> 00:01:44,440
I pretraživanje može dobiti
zatvoriti stalnom vrijeme.

40
00:01:44,440 --> 00:01:48,600
That's-- mi nemamo podatke
Struktura gostiju koji može učiniti,

41
00:01:48,600 --> 00:01:51,180
i tako to već zvuči
kao prilično velika stvar.

42
00:01:51,180 --> 00:01:57,010
Mi stvarno sam ublažila
nedostaci svaki na svoju vlastitu.

43
00:01:57,010 --> 00:01:59,160
>> Da biste dobili ovaj nastup
nadograditi ipak, mi

44
00:01:59,160 --> 00:02:03,580
potrebno promisliti kako ćemo dodati
podataka u strukturi.

45
00:02:03,580 --> 00:02:07,380
Naime želimo
Sama podaci nam reći

46
00:02:07,380 --> 00:02:09,725
gdje je trebao ići u strukturi.

47
00:02:09,725 --> 00:02:12,850
I ako onda treba vidjeti je li to u
struktura, ako moramo pronaći,

48
00:02:12,850 --> 00:02:16,610
želimo pogledajte podataka
opet moći učinkovito,

49
00:02:16,610 --> 00:02:18,910
korištenja podataka, slučajno mu pristupiti.

50
00:02:18,910 --> 00:02:20,700
Samo gledanjem na
Podaci bi trebali imati

51
00:02:20,700 --> 00:02:25,890
ideja gdje točno smo
će ga pronaći u hash tablici.

52
00:02:25,890 --> 00:02:28,770
>> Sada je downside skraćenog
stol je da su oni zapravo

53
00:02:28,770 --> 00:02:31,770
prilično loše na naređivanje ili sortiranja podataka.

54
00:02:31,770 --> 00:02:34,970
A u stvari, ako počnete
koristiti ih naručiti ili sortiranje

55
00:02:34,970 --> 00:02:37,990
Podaci izgubite sve od
Prednosti ste prethodno

56
00:02:37,990 --> 00:02:40,710
imao u pogledu umetanja i brisanja.

57
00:02:40,710 --> 00:02:44,060
Vrijeme postaje bliži
theta n, a mi smo zapravo

58
00:02:44,060 --> 00:02:45,530
regresiju u popisu povezane.

59
00:02:45,530 --> 00:02:48,850
I tako smo se samo želite koristiti hash
tablice, ako mi ne stalo

60
00:02:48,850 --> 00:02:51,490
je li se podaci razvrstani.

61
00:02:51,490 --> 00:02:54,290
Za kontekst u kojem
ćete ih koristiti u CS50

62
00:02:54,290 --> 00:02:58,900
vjerojatno ne briga
da se podaci razvrstani.

63
00:02:58,900 --> 00:03:03,170
>> Tako hash tablica kombinacija
dva različita komada

64
00:03:03,170 --> 00:03:04,980
s kojima smo upoznati.

65
00:03:04,980 --> 00:03:07,930
Prva je funkcija, koje
mi obično nazivamo hash funkcije.

66
00:03:07,930 --> 00:03:11,760
I to hash funkcija će
vratiti neke ne-negativni cijeli broj, koji

67
00:03:11,760 --> 00:03:14,870
mi obično nazivamo Hash broj, u redu?

68
00:03:14,870 --> 00:03:20,230
Drugi dio je niz, što je
sposoban za pohranu podataka tipa mi

69
00:03:20,230 --> 00:03:22,190
žele staviti u strukturu podataka.

70
00:03:22,190 --> 00:03:24,310
Mi ćemo odlagati na
povezani s popisa elementa za sada

71
00:03:24,310 --> 00:03:27,810
i samo početi s Osnove
hash tablicu dobiti svoju glavu oko njega,

72
00:03:27,810 --> 00:03:30,210
a onda ćemo možda odsvirati
vaš um malo kad smo

73
00:03:30,210 --> 00:03:32,920
kombinirati polja i link popise zajedno.

74
00:03:32,920 --> 00:03:35,590
>> Osnovna ideja ipak
je uzmemo neke podatke.

75
00:03:35,590 --> 00:03:37,860
Mi smo mali da podatke putem
hash funkcija.

76
00:03:37,860 --> 00:03:41,980
I tako se podaci obrađuju
i to ispljune broj, u redu?

77
00:03:41,980 --> 00:03:44,890
A onda s tim brojem
samo mi pohranu podataka

78
00:03:44,890 --> 00:03:48,930
želimo pohraniti u
niz na tom mjestu.

79
00:03:48,930 --> 00:03:53,990
Tako na primjer, imamo možda
hash tablica žice.

80
00:03:53,990 --> 00:03:57,350
To je dobio 10 elemenata u njemu, tako da
možemo stati 10 žice u njemu.

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

82
00:03:59,320 --> 00:04:02,979
Dakle, Ivana kao podatke želimo umetnuti
u ovom hash tablicu negdje.

83
00:04:02,979 --> 00:04:03,770
Gdje ćemo ga staviti?

84
00:04:03,770 --> 00:04:05,728
Pa obično Sa
Niz dosad vjerojatno

85
00:04:05,728 --> 00:04:07,610
će ga staviti u polja položaj 0.

86
00:04:07,610 --> 00:04:09,960
No, sada imamo ovu novu funkciju hash.

87
00:04:09,960 --> 00:04:13,180
>> I recimo da smo pokrenuti Ivan
kroz ovaj hash funkcije

88
00:04:13,180 --> 00:04:15,417
i to ispljune 4.

89
00:04:15,417 --> 00:04:17,500
Pa to je gdje smo
će htjeti staviti Johna.

90
00:04:17,500 --> 00:04:22,050
Želimo staviti Ivanu u array mjestu
4, jer ako smo razmotrili Ivan again--

91
00:04:22,050 --> 00:04:23,810
recimo kasnije smo
želite pretraživati ​​i vidjeti

92
00:04:23,810 --> 00:04:26,960
ako je John postoji u ovom hash
table-- sve što trebate učiniti

93
00:04:26,960 --> 00:04:30,310
je trčanje kroz isti hash
funkcija, dobiti broj 4 out,

94
00:04:30,310 --> 00:04:33,929
i biti u mogućnosti pronaći Ivanu
Odmah u našem strukture podataka.

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

96
00:04:34,720 --> 00:04:36,928
>> Recimo mi sada to
opet, želimo hash Pavla.

97
00:04:36,928 --> 00:04:39,446
Želimo dodati Pavla
u ovom hash tablicu.

98
00:04:39,446 --> 00:04:42,070
Recimo da je ovaj put smo pokrenuti
Pavao kroz hash funkcija,

99
00:04:42,070 --> 00:04:44,600
Hash koji se generira 6.

100
00:04:44,600 --> 00:04:47,340
Pa sad možemo staviti Pavla
u polja lokaciji 6.

101
00:04:47,340 --> 00:04:50,040
A ako moramo pogledati je li
Pavao je u ovoj hash tablicu,

102
00:04:50,040 --> 00:04:53,900
sve što trebate učiniti je pokrenuti Pavao
kroz hash funkcije ponovno

103
00:04:53,900 --> 00:04:55,830
a mi ćemo dobiti 6 opet.

104
00:04:55,830 --> 00:04:57,590
>> A onda smo samo pogledajte
na polja lokaciji 6.

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

106
00:04:58,910 --> 00:05:00,160
Ako je tako, on je u hash tablici.

107
00:05:00,160 --> 00:05:01,875
Je Pavao ne postoji?

108
00:05:01,875 --> 00:05:03,000
On nije u hash tablici.

109
00:05:03,000 --> 00:05:05,720
To je prilično jednostavan.

110
00:05:05,720 --> 00:05:07,770
>> Sad kako ti definirati hash funkcije?

111
00:05:07,770 --> 00:05:11,460
Pa da stvarno nema ograničenja na
Broj mogućih hash funkcija.

112
00:05:11,460 --> 00:05:14,350
U stvari postoji nekoliko stvarno,
stvarno dobre one na internetu.

113
00:05:14,350 --> 00:05:17,560
Postoji nekoliko jako,
stvarno loši na internetu.

114
00:05:17,560 --> 00:05:21,080
To je također prilično jednostavan
napisati lošu jedan.

115
00:05:21,080 --> 00:05:23,760
>> Dakle, ono što čini dobar
hash funkcija, zar ne?

116
00:05:23,760 --> 00:05:27,280
Pa dobro funkcija raspršivanja trebao
koristiti samo podatke koji se raspršen,

117
00:05:27,280 --> 00:05:29,420
i sve podatke koji se raspršen.

118
00:05:29,420 --> 00:05:32,500
Dakle, mi ne želimo koristiti anything--
ne sadrže ništa

119
00:05:32,500 --> 00:05:35,560
drugo osim podataka.

120
00:05:35,560 --> 00:05:37,080
I želimo iskoristiti sve podatke.

121
00:05:37,080 --> 00:05:39,830
Mi ne želimo samo koristiti komad
nje, želimo iskoristiti sve to.

122
00:05:39,830 --> 00:05:41,710
Hash funkcija trebala
također biti deterministička.

123
00:05:41,710 --> 00:05:42,550
Što to znači?

124
00:05:42,550 --> 00:05:46,200
Pa to znači da svaki put smo
prolaze isti komad podataka

125
00:05:46,200 --> 00:05:50,040
u hash funkcije uvijek
dobiti isti Hash broj van.

126
00:05:50,040 --> 00:05:52,870
Ako prođem Ivan Into the
hash funkcija izađem 4.

127
00:05:52,870 --> 00:05:56,110
Ja bi trebao biti u mogućnosti to učiniti 10.000
puta i uvijek ću 4.

128
00:05:56,110 --> 00:06:00,810
Tako da nema slučajnih brojeva učinkovito
mogu biti uključeni u našoj hash tables--

129
00:06:00,810 --> 00:06:02,750
u našim hash funkcija.

130
00:06:02,750 --> 00:06:05,750
>> Hash funkcija također trebao
ravnomjerno distribuirati podatke.

131
00:06:05,750 --> 00:06:09,700
Ako svaki put kada pokrenete podatke preko
hash funkcija ste dobili Hash broj 0,

132
00:06:09,700 --> 00:06:11,200
to vjerojatno nije tako velika, zar ne?

133
00:06:11,200 --> 00:06:14,600
Vi vjerojatno želite veliki
raspon hash kodova.

134
00:06:14,600 --> 00:06:17,190
Također se stvari mogu širiti
po cijeloj tablici.

135
00:06:17,190 --> 00:06:23,210
I to bi bilo sjajno, ako stvarno
slični podaci, kao što su Ivana i Jonatana,

136
00:06:23,210 --> 00:06:26,320
možda su se proširile na vaganje
različita mjesta u hash tablici.

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

138
00:06:28,750 --> 00:06:31,250
>> Evo primjer hash funkcije.

139
00:06:31,250 --> 00:06:33,150
Napisao sam ovo gore ranije.

140
00:06:33,150 --> 00:06:35,047
To nije osobito
dobro funkcioniraju mljeveno meso

141
00:06:35,047 --> 00:06:37,380
iz razloga koji ne stvarno
nose ide u upravo sada.

142
00:06:37,380 --> 00:06:41,040
Ali vidiš što se ovdje događa?

143
00:06:41,040 --> 00:06:44,420
Čini se kao da smo progla varijablu
zove suma i postavljanje ga jednaka 0.

144
00:06:44,420 --> 00:06:50,010
A onda je očito da radim nešto
tako dugo dok strstr [j] nije jednak

145
00:06:50,010 --> 00:06:52,490
za kose crtice 0.

146
00:06:52,490 --> 00:06:54,870
Što ja radim ovdje?

147
00:06:54,870 --> 00:06:57,440
>> To je u osnovi samo još jedan
način provedbe [? strl?]

148
00:06:57,440 --> 00:06:59,773
i otkrivanje kada ste
stigao kraj niza.

149
00:06:59,773 --> 00:07:02,480
Dakle, nemam zapravo
izračunati duljinu niza,

150
00:07:02,480 --> 00:07:05,640
Ja sam samo pomoću kada sam pogodio
backslash 0 karakter znam

151
00:07:05,640 --> 00:07:07,185
Ja sam stigao do kraja niza.

152
00:07:07,185 --> 00:07:09,560
A onda ću zadržati
iterating kroz taj niz,

153
00:07:09,560 --> 00:07:15,310
dodajući strstr [J] da zaključimo, a zatim na
kraj dana će se vratiti zbroj mod

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

155
00:07:16,200 --> 00:07:18,700
>> Uglavnom sve je to mljeveno meso
Funkcija radi se zbroje

156
00:07:18,700 --> 00:07:23,450
sve ASCII vrijednosti
moj string, a zatim je

157
00:07:23,450 --> 00:07:26,390
povratka neke Hash broj
modded by HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
To je vjerojatno veličina
moje polje, zar ne?

159
00:07:29,790 --> 00:07:33,160
Ne želim biti uzimajući hašiš
Kodovi ako mi niz je veličine 10,

160
00:07:33,160 --> 00:07:35,712
Ne želim biti sve
van hash oznake 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, ne mogu staviti stvari u
one lokacije polja,

162
00:07:38,690 --> 00:07:39,790
to bi bilo protuzakonito.

163
00:07:39,790 --> 00:07:42,130
Ja bih pate grešku segmentiranja.

164
00:07:42,130 --> 00:07:45,230
>> Sada ovdje je još jedan brz stranu.

165
00:07:45,230 --> 00:07:48,470
Općenito vjerojatno nećeš
želite napisati svoje hash funkcije.

166
00:07:48,470 --> 00:07:50,997
To je zapravo malo
umjetnost, a ne znanost.

167
00:07:50,997 --> 00:07:52,580
I tu je mnogo toga što ide u njih.

168
00:07:52,580 --> 00:07:55,288
Internet, kao što sam rekao, puna
stvarno dobar hash funkcija,

169
00:07:55,288 --> 00:07:58,470
i trebali koristiti internet za
naći hash funkcija, jer to je stvarno

170
00:07:58,470 --> 00:08:03,230
samo vrsta nepotreban
gubljenje vremena za napraviti svoj vlastiti.

171
00:08:03,230 --> 00:08:05,490
>> Možete napisati jednostavne one
za svrhe testiranja.

172
00:08:05,490 --> 00:08:08,323
Ali kada su zapravo ide
početi raspršivanja podataka i spremanje

173
00:08:08,323 --> 00:08:10,780
u hash tablici koju
Vjerojatno će htjeti

174
00:08:10,780 --> 00:08:14,580
koristiti neke funkcije koje je generirana
za vas, koji postoji na internetu.

175
00:08:14,580 --> 00:08:17,240
Ako samo nemojte biti sigurni
citirati svoje izvore.

176
00:08:17,240 --> 00:08:21,740
Nema razloga da se
plagirati ništa ovdje.

177
00:08:21,740 --> 00:08:25,370
>> Računalo znanost zajednica
definitivno raste, a realno vrijednosti

178
00:08:25,370 --> 00:08:28,796
open source, i to je stvarno važno
navesti svoje izvore, tako da ljudi

179
00:08:28,796 --> 00:08:30,670
mogu dobiti atribucije za
rad koji oni

180
00:08:30,670 --> 00:08:32,312
radi na dobrobit zajednice.

181
00:08:32,312 --> 00:08:34,020
Dakle, uvijek biti sure--
a ne samo za mljeveno meso

182
00:08:34,020 --> 00:08:37,270
funkcije, ali općenito kad vas
koristiti kod iz vanjskog izvora,

183
00:08:37,270 --> 00:08:38,299
uvijek navode svoj izvor.

184
00:08:38,299 --> 00:08:43,500
Dati kredit osobi koja je učinio
Neki od posla, tako da ne morate.

185
00:08:43,500 --> 00:08:46,720
>> U redu, tako ćemo ponovno ovu
hash tablicu na sekundu.

186
00:08:46,720 --> 00:08:48,780
To je mjesto gdje smo ostavili
off nakon što umetnuta

187
00:08:48,780 --> 00:08:53,300
Ivan i Pavao u ovom hash tablicu.

188
00:08:53,300 --> 00:08:55,180
Vidite li problem ovdje?

189
00:08:55,180 --> 00:08:58,410
Možda ćete vidjeti dva.

190
00:08:58,410 --> 00:09:02,240
No posebno, zar ne
pogledajte ovaj mogući problem?

191
00:09:02,240 --> 00:09:06,770
>> Što ako hash Ringo, i to
Ispada da je nakon obrade

192
00:09:06,770 --> 00:09:14,000
te podatke kroz hash funkcije
Ringo također generirao Hash broj 6.

193
00:09:14,000 --> 00:09:16,810
Već sam dobio podatke
hashcode-- niz lokacija 6.

194
00:09:16,810 --> 00:09:22,000
Pa vjerojatno će biti malo
problem za mene, zar ne?

195
00:09:22,000 --> 00:09:23,060
>> Mi to nazivamo sudara.

196
00:09:23,060 --> 00:09:26,460
A sudara nastaje kada dva
komadići podataka izvoditi kroz isti hash

197
00:09:26,460 --> 00:09:29,200
Funkcija dati istu Hash broj.

198
00:09:29,200 --> 00:09:32,850
Vjerojatno još uvijek žele dobiti i
komadići podataka u hash tablici,

199
00:09:32,850 --> 00:09:36,330
inače ne bismo se prikazivati ​​Ringo
samovoljno kroz hash funkcije.

200
00:09:36,330 --> 00:09:40,870
Mi vjerojatno želite dobiti
Ringo u taj niz.

201
00:09:40,870 --> 00:09:46,070
>> Kako ćemo to učiniti, iako, ako on
i Paul i prinos Hash broj 6?

202
00:09:46,070 --> 00:09:49,520
Mi ne želite prebrisati Pavla,
želimo Pavao biti tamo.

203
00:09:49,520 --> 00:09:52,790
Dakle, moramo naći način da se
elemente u hash tablici koja

204
00:09:52,790 --> 00:09:56,550
još uvijek čuva našeg brzog
umetanje i brzi pogled gore.

205
00:09:56,550 --> 00:10:01,350
A jedan od načina da se nositi s time je
učiniti nešto što se zove linearni sondiranja.

206
00:10:01,350 --> 00:10:04,170
>> Koristeći ovu metodu, ako imamo
sudara, dobro, što nam je činiti?

207
00:10:04,170 --> 00:10:08,580
Pa ne možemo ga staviti u array mjestu
6, ili što god Hash broj je generiran,

208
00:10:08,580 --> 00:10:10,820
neka ga stavi na Hash broj plus 1.

209
00:10:10,820 --> 00:10:13,670
A ako je to pun neka je
stavite ga u Hash broj plus 2.

210
00:10:13,670 --> 00:10:17,420
Korist od ovog bića je li
Ne točno gdje mi mislimo da je,

211
00:10:17,420 --> 00:10:20,850
a mi moramo početi tražiti,
Možda ne moramo ići predaleko.

212
00:10:20,850 --> 00:10:23,900
Možda nemamo za pretraživanje
sve n elementi hash tablici.

213
00:10:23,900 --> 00:10:25,790
Možda ćemo morati tražiti
par njih.

214
00:10:25,790 --> 00:10:30,680
>> I tako smo još uvijek teži ka
da prosječni slučaj bude blizu 1 vs

215
00:10:30,680 --> 00:10:34,280
u neposrednoj blizini n, pa možda da će raditi.

216
00:10:34,280 --> 00:10:38,010
Tako ćemo vidjeti kako se to
možda rade u stvarnosti.

217
00:10:38,010 --> 00:10:41,460
I neka je vidjeti ako možda možemo otkriti
problem koji se može dogoditi ovdje.

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

219
00:10:42,540 --> 00:10:45,581
Dakle, sada ćemo pokrenuti novi set
žice kroz hash funkcija,

220
00:10:45,581 --> 00:10:48,460
i mi pokrenuti Bart kroz hash
funkcija, dobili smo Hash broj 6.

221
00:10:48,460 --> 00:10:52,100
Mi pogledamo, vidimo 6
prazna, tako da možemo staviti Bart tamo.

222
00:10:52,100 --> 00:10:55,410
>> Sada smo razmotrili Lisa i da
Također generira Hash broj 6.

223
00:10:55,410 --> 00:10:58,330
Pa sad da smo koristeći ovaj
Linearni sondiranje način možemo početi u 6,

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

225
00:10:59,330 --> 00:11:00,990
Ne možemo staviti Lisu u 6.

226
00:11:00,990 --> 00:11:02,090
Pa gdje idemo?

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

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

229
00:11:04,610 --> 00:11:06,510
Tako ćemo staviti Lisa postoji.

230
00:11:06,510 --> 00:11:10,200
>> Sada smo razmotrili Homera i dobili smo 7.

231
00:11:10,200 --> 00:11:13,380
OK dobro znamo da 7 je pun
sada, pa ne možemo staviti Homera postoji.

232
00:11:13,380 --> 00:11:14,850
Dakle, idemo do 8.

233
00:11:14,850 --> 00:11:15,664
Je li 8 dostupan?

234
00:11:15,664 --> 00:11:18,330
Da, i 8 bliski do 7, tako da ako
moramo početi u potrazi smo

235
00:11:18,330 --> 00:11:20,020
neće morati ići predaleko.

236
00:11:20,020 --> 00:11:22,860
I tako ćemo staviti Homera u 8.

237
00:11:22,860 --> 00:11:25,151
>> Sada smo razmotrili Maggie i
vraća 3, hvala Bogu

238
00:11:25,151 --> 00:11:26,650
smo mogli samo staviti Maggie postoji.

239
00:11:26,650 --> 00:11:29,070
Ne morate učiniti bilo
vrsta sondiranje za to.

240
00:11:29,070 --> 00:11:32,000
Sada smo razmotrili Marge i
Marge se vraća 6.

241
00:11:32,000 --> 00:11:39,560
>> Pa 6 pun, 7 je pun, 8 je pun,
9, u redu hvala Bogu, 9 je prazna.

242
00:11:39,560 --> 00:11:41,600
Ja mogu staviti Marge na 9.

243
00:11:41,600 --> 00:11:45,280
Već možemo vidjeti da smo početkom
da imaju ovaj problem, gdje sada smo

244
00:11:45,280 --> 00:11:48,780
počinju se protežu stvari vrsta
od daleko od svojih hash kodova.

245
00:11:48,780 --> 00:11:52,960
I to theta od 1, da prosječna
Slučaj se vremenska konstanta,

246
00:11:52,960 --> 00:11:56,560
počinje se malo more--
počinju obično malo više

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

248
00:11:58,050 --> 00:12:01,270
Mi smo počeli gubiti da
Prednost hash tablica.

249
00:12:01,270 --> 00:12:03,902
>> Ovaj problem koji smo upravo vidjeli
nešto što se zove klastera.

250
00:12:03,902 --> 00:12:06,360
A što je stvarno loše
grupiranje je da nakon što se sada

251
00:12:06,360 --> 00:12:09,606
imaju dva elementa koji su rame uz
stranu to ga čini još vjerojatnije,

252
00:12:09,606 --> 00:12:11,480
imate dvostruko
šanse, da idete

253
00:12:11,480 --> 00:12:13,516
imati još jedan sudar
s tim klastera,

254
00:12:13,516 --> 00:12:14,890
a klaster će rasti po jedan.

255
00:12:14,890 --> 00:12:19,640
A vi ćete zadržati raste i raste
Vaš vjerojatnost da sudar.

256
00:12:19,640 --> 00:12:24,470
I na kraju to je jednako loše
kako ne sortiranja podataka na sve.

257
00:12:24,470 --> 00:12:27,590
>> Drugi problem je ipak ćemo
dalje, i sada do ove točke,

258
00:12:27,590 --> 00:12:30,336
upravo smo bili vrsta
razumijevanje što je hash tablica,

259
00:12:30,336 --> 00:12:31,960
još samo mjesta za 10 žice.

260
00:12:31,960 --> 00:12:37,030
Ako želimo nastaviti hash
građani Springfield,

261
00:12:37,030 --> 00:12:38,790
možemo dobiti samo 10 od njih tamo.

262
00:12:38,790 --> 00:12:42,619
A ako ćemo pokušati dodati 11. ili 12.,
nemamo mjesta da ih stavi.

263
00:12:42,619 --> 00:12:45,660
Mi smo samo mogli biti vrti oko u
krugovi pokušavaju pronaći prazno mjesto,

264
00:12:45,660 --> 00:12:49,000
i mi možda zapeti
u beskonačnu petlju.

265
00:12:49,000 --> 00:12:51,810
>> Dakle, ova vrsta posuđuje ideje
nešto naziva ulančavanje.

266
00:12:51,810 --> 00:12:55,790
I ovo je mjesto gdje ćemo donijeti
povezani popisi natrag u sliku.

267
00:12:55,790 --> 00:13:01,300
Što ako, umjesto pohranjivanja jednostavno
sama podataka u nizu,

268
00:13:01,300 --> 00:13:04,471
svaki element polja mogla
držite više komada podataka?

269
00:13:04,471 --> 00:13:05,970
Pa to nema smisla, zar ne?

270
00:13:05,970 --> 00:13:09,280
Znamo da niz može samo
hold-- svaki element niza

271
00:13:09,280 --> 00:13:12,930
mogu držati samo jedan komad
podataka te vrste podataka.

272
00:13:12,930 --> 00:13:16,750
>> Ali što ako je tip podataka
je popis povezani, zar ne?

273
00:13:16,750 --> 00:13:19,830
Pa što ako svaki
element polja je

274
00:13:19,830 --> 00:13:22,790
pointer na čelu liste povezane?

275
00:13:22,790 --> 00:13:24,680
A onda smo mogli izgraditi
oni povezani popisi

276
00:13:24,680 --> 00:13:27,120
i rastu im proizvoljno,
jer povezani popisi omogućuju

277
00:13:27,120 --> 00:13:32,090
da rastemo i smanjiti mnogo više
fleksibilno nego niz radi.

278
00:13:32,090 --> 00:13:34,210
Pa što ako smo sada koristite,
smo iskoristiti ovu, zar ne?

279
00:13:34,210 --> 00:13:37,760
Mi početi rasti ove lance
iz tih array mjestima.

280
00:13:37,760 --> 00:13:40,740
>> Sada možemo stati beskonačna
Količina podataka, ili nije beskonačna,

281
00:13:40,740 --> 00:13:44,170
proizvoljna količina
podataka, u našu hash tablicu

282
00:13:44,170 --> 00:13:47,760
bez trčanje u
problem sudara.

283
00:13:47,760 --> 00:13:50,740
Također smo eliminirani
grupiranje po to.

284
00:13:50,740 --> 00:13:54,380
A dobro znamo da kad smo umetnuti
u popisu povezani, ako sjetiti

285
00:13:54,380 --> 00:13:57,779
iz naše video na povezanim popisima, pojedinačno
povezani popisi i dvostruko vezane liste,

286
00:13:57,779 --> 00:13:59,070
to je konstanta vrijeme operacije.

287
00:13:59,070 --> 00:14:00,710
Mi samo dodao da je ispred.

288
00:14:00,710 --> 00:14:04,400
>> A za pogledati, ali znamo
kako gledate na popisu povezan

289
00:14:04,400 --> 00:14:05,785
može biti problem, zar ne?

290
00:14:05,785 --> 00:14:07,910
Moramo pretraživanje
je od početka do kraja.

291
00:14:07,910 --> 00:14:10,460
Nema slučajnih
Pristup na popisu povezane.

292
00:14:10,460 --> 00:14:15,610
Ali ako umjesto jednog povezani
Lista gdje pretraživanja će biti O n,

293
00:14:15,610 --> 00:14:19,590
sada imamo 10 povezane liste,
ili 1.000 povezani popisi,

294
00:14:19,590 --> 00:14:24,120
sada je O n podijeljena 10,
ili O n podijeljen 1000.

295
00:14:24,120 --> 00:14:26,940
>> I dok smo razgovarali
teoretski o složenosti

296
00:14:26,940 --> 00:14:30,061
možemo zanemariti konstante u pravi
Svijet te stvari zapravo smeta,

297
00:14:30,061 --> 00:14:30,560
zar ne?

298
00:14:30,560 --> 00:14:33,080
Zapravo ćemo primijetiti
da se to događa

299
00:14:33,080 --> 00:14:36,610
pokrenuti 10 puta brže,
ili 1.000 puta brže,

300
00:14:36,610 --> 00:14:41,570
jer mi smo distribuciju jednu dugu
lanac preko 1.000 manjih lanaca.

301
00:14:41,570 --> 00:14:45,090
I tako svaki put moramo tražiti
kroz jedan od onih lanaca možemo

302
00:14:45,090 --> 00:14:50,290
ignorirati 999 lance ne brinu
o, i samo traži da je jedan.

303
00:14:50,290 --> 00:14:53,220
>> Što je u prosjeku za
biti 1000 puta kraće.

304
00:14:53,220 --> 00:14:56,460
I tako smo još uvijek su vrsta
naginjanje prema ovom prosječnom slučaju

305
00:14:56,460 --> 00:15:01,610
bude konstantan vremena, ali
samo zato što se utjecati

306
00:15:01,610 --> 00:15:03,730
dijeljenjem nekim ogromnim konstantnim faktorom.

307
00:15:03,730 --> 00:15:05,804
Pogledajmo kako bi to moglo
zapravo izgleda ipak.

308
00:15:05,804 --> 00:15:08,720
Dakle, to je hash tablicu smo imali
prije nego što smo proglašen hash tablicu koja

309
00:15:08,720 --> 00:15:10,270
bio je sposoban za pohranu 10 žice.

310
00:15:10,270 --> 00:15:11,728
Nećemo to učiniti više.

311
00:15:11,728 --> 00:15:13,880
Mi već znamo
ograničenja tog postupka.

312
00:15:13,880 --> 00:15:20,170
Sada naša hash tablicu će biti
niz od 10 čvorova, upućuje

313
00:15:20,170 --> 00:15:22,120
na glavama povezanim popisima.

314
00:15:22,120 --> 00:15:23,830
>> A sada je null.

315
00:15:23,830 --> 00:15:26,170
Svaki od tih 10 upućuje je null.

316
00:15:26,170 --> 00:15:29,870
Nema ništa u našem
hash tablicu odmah.

317
00:15:29,870 --> 00:15:32,690
>> Sada krenimo staviti neke
stvari u ovom hash tablicu.

318
00:15:32,690 --> 00:15:35,440
I neka je vidjeti kako ova metoda
će nam koristiti malo.

319
00:15:35,440 --> 00:15:36,760
Idemo sada hash Joey.

320
00:15:36,760 --> 00:15:40,210
Mi ćemo će se izvoditi niz Joey kroz
hash funkcija i vraćamo 6.

321
00:15:40,210 --> 00:15:41,200
Pa što ćemo sad?

322
00:15:41,200 --> 00:15:44,090
>> Pa sad radi s povezanim popisima,
mi ne radimo s polja.

323
00:15:44,090 --> 00:15:45,881
I kad radimo
s povezanim popisima smo

324
00:15:45,881 --> 00:15:49,790
Znaš moramo početi dinamički
dodjeljivanje prostora i izgradnju lanaca.

325
00:15:49,790 --> 00:15:54,020
To je vrsta how-- oni su srž
elementi izgradnje popis povezani.

326
00:15:54,020 --> 00:15:57,670
Toliko je neka dinamički
izdvojiti prostor za Joey,

327
00:15:57,670 --> 00:16:00,390
a onda ćemo ga dodati na lancu.

328
00:16:00,390 --> 00:16:03,170
>> Pa sad vidi što smo učinili.

329
00:16:03,170 --> 00:16:06,440
Kad smo razmotrili Joey dobili smo Hash broj 6.

330
00:16:06,440 --> 00:16:11,790
Sada se kazaljka na polja lokaciji 6
ukazuje na čelu popisa povezane,

331
00:16:11,790 --> 00:16:14,900
a sada je to jedina
element popisa povezane.

332
00:16:14,900 --> 00:16:18,350
A čvor u koji
povezani popis je Joey.

333
00:16:18,350 --> 00:16:22,300
>> Dakle, ako moramo pogledati Joey
kasnije, samo smo razmotrili Joey opet,

334
00:16:22,300 --> 00:16:26,300
dobili smo 6 opet jer je naš
hash funkcija je deterministička.

335
00:16:26,300 --> 00:16:30,400
A onda smo počeli na glavu
popisa povezane istaknuo

336
00:16:30,400 --> 00:16:33,360
na koju array mjestu
6, i mi možemo ponoviti

337
00:16:33,360 --> 00:16:35,650
preko koje pokušava pronaći Joey.

338
00:16:35,650 --> 00:16:37,780
A ako gradimo naš
hash tablicu učinkovito,

339
00:16:37,780 --> 00:16:41,790
a naš hash funkcija učinkovito
distribuirati podatke i,

340
00:16:41,790 --> 00:16:45,770
u prosjeku je svaki od njih povezan
lista na svakom mjestu poljem

341
00:16:45,770 --> 00:16:50,110
će biti 1/10 veličine ako
samo ga je imao kao jedan veliki

342
00:16:50,110 --> 00:16:51,650
povezani popis sa svime u njemu.

343
00:16:51,650 --> 00:16:55,670
>> Ako smo distribuirati da ogroman povezan
Lista preko 10 povezanih liste

344
00:16:55,670 --> 00:16:57,760
svaki popis će biti 1/10 veličine.

345
00:16:57,760 --> 00:17:01,432
I tako 10 puta brže
za pretraživanje.

346
00:17:01,432 --> 00:17:02,390
Tako ćemo to učiniti opet.

347
00:17:02,390 --> 00:17:04,290
Idemo sada hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> I recimo Ross, kad smo to
hash kod se vratimo 2.

349
00:17:07,540 --> 00:17:10,630
Pa sad smo dinamički dodijeliti
novi čvor, stavili smo Ross u tom čvoru,

350
00:17:10,630 --> 00:17:14,900
i mi sada reći niz lokacija
2, umjesto da ukazuje na null,

351
00:17:14,900 --> 00:17:18,579
ukazuje na glavu povezan
Popis čiji je jedini čvor je Ross.

352
00:17:18,579 --> 00:17:22,660
A mi možemo učiniti još jednom, mi
može hash Rachel i dobiti Hash broj 4.

353
00:17:22,660 --> 00:17:25,490
malloc novi čvor, stavite Rachel u
čvor, i reći lokacije array

354
00:17:25,490 --> 00:17:27,839
4. ukazuje na glavi
od povezanog popisa čije

355
00:17:27,839 --> 00:17:31,420
Jedini element koji se događa da se Rachel.

356
00:17:31,420 --> 00:17:33,470
>> U redu, ali što će se dogoditi ako
imamo sudar?

357
00:17:33,470 --> 00:17:38,560
Da vidimo kako možemo nositi sudara
koristite zasebnu metodu ulančavanje.

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

359
00:17:39,800 --> 00:17:41,094
Mi smo dobili Hash broj 6.

360
00:17:41,094 --> 00:17:44,010
U našem prethodnom primjeru smo bili samo
pohranjivanje konce u nizu.

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

362
00:17:45,980 --> 00:17:48,444
>> Mi ne želimo clobber
Joey, a mi smo već

363
00:17:48,444 --> 00:17:51,110
vidjeti da možemo dobiti neki klastera
Problemi ako ćemo pokušati i korak

364
00:17:51,110 --> 00:17:52,202
kroz i probe.

365
00:17:52,202 --> 00:17:54,660
Ali što ako smo samo vrsta
tretirati na isti način, zar ne?

366
00:17:54,660 --> 00:17:57,440
To je baš kao i dodavanje element
na glavu popisa povezane.

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

368
00:18:00,220 --> 00:18:04,764
>> Mi ćemo reći Phoebe je sljedeće pokazivač bodova
na staru glavu na popisu povezane,

369
00:18:04,764 --> 00:18:07,180
a onda 6 samo ukazuje na
Novi šef popisa povezane.

370
00:18:07,180 --> 00:18:10,150
A sada pogledajte, promijenili smo Phoebe u.

371
00:18:10,150 --> 00:18:14,210
Sada možete pohraniti dva
elementi s Hash broj 6,

372
00:18:14,210 --> 00:18:17,170
i nemamo nikakvih problema.

373
00:18:17,170 --> 00:18:20,147
>> To je ljepušan velik dio sve
tu je ulančavanje.

374
00:18:20,147 --> 00:18:21,980
I ulančavanje je definitivno
metoda koja je

375
00:18:21,980 --> 00:18:27,390
će biti najučinkovitiji za vas ako
vi ste pohranjivanje podataka u hash tablici.

376
00:18:27,390 --> 00:18:30,890
No, ova kombinacija
polja i povezane liste

377
00:18:30,890 --> 00:18:36,080
zajedno tvore hash tablice stvarno
dramatično poboljšava vaše sposobnosti

378
00:18:36,080 --> 00:18:40,550
za pohranu velike količine podataka, te
vrlo brzo i učinkovito traženje

379
00:18:40,550 --> 00:18:41,630
kroz te podatke.

380
00:18:41,630 --> 00:18:44,150
>> Postoji još jedan
struktura podataka vani

381
00:18:44,150 --> 00:18:48,700
to bi čak moglo biti malo
bolje u smislu jamčenja

382
00:18:48,700 --> 00:18:51,920
da je naš umetanje, brisanje i
gledate vremena su čak i brže.

383
00:18:51,920 --> 00:18:55,630
I vidjet ćemo da je u video na pokušaja.

384
00:18:55,630 --> 00:18:58,930
Ja sam Doug Lloyd, ovo je CS50.

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