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

2
00:00:00,500 --> 00:00:01,900
[MUSIC JOC]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: Până acum
știu foarte multe despre matrice,

5
00:00:09,150 --> 00:00:11,610
și știți multe despre liste legate.

6
00:00:11,610 --> 00:00:13,650
Și am discuta
argumente pro și contra, am

7
00:00:13,650 --> 00:00:16,620
discutat că legat liste
pot obține mai mari și mai mici,

8
00:00:16,620 --> 00:00:18,630
dar ele ocupă mai mult dimensiune.

9
00:00:18,630 --> 00:00:22,359
Matrice sunt mult mai ușor de
folosesc, dar sunt restrictive în măsura în

10
00:00:22,359 --> 00:00:24,900
ca avem de a seta dimensiunea de
matrice de la bun început

11
00:00:24,900 --> 00:00:26,910
și apoi suntem blocați cu ea.

12
00:00:26,910 --> 00:00:30,470
>> Dar asta e, am destul de mult
epuizat toate subiectele noastre de

13
00:00:30,470 --> 00:00:33,040
despre liste legate și matrice.

14
00:00:33,040 --> 00:00:34,950
Sau avem?

15
00:00:34,950 --> 00:00:37,720
Poate putem face ceva
chiar mai creativ.

16
00:00:37,720 --> 00:00:40,950
Și la fel de bine împrumută
ideea unui tabel hash.

17
00:00:40,950 --> 00:00:46,680
>> Deci, într-un tabel hash vom încerca
combină un tablou cu o listă legată.

18
00:00:46,680 --> 00:00:49,520
Vom lua avantajele
de matrice, cum ar fi acces aleator,

19
00:00:49,520 --> 00:00:53,510
fiind capabil de a merge doar la matrice
Element 4 sau matrice element de 8

20
00:00:53,510 --> 00:00:55,560
fără a fi nevoie de a repeta peste.

21
00:00:55,560 --> 00:00:57,260
Asta e destul de repede, nu?

22
00:00:57,260 --> 00:01:00,714
>> Dar noi, de asemenea, doresc să aibă datele noastre
structură putea să crească și reduce.

23
00:01:00,714 --> 00:01:02,630
Nu avem nevoie de, noi nu
doresc să fie limitat.

24
00:01:02,630 --> 00:01:04,588
Și vrem să fie în măsură
pentru a adăuga și elimina lucruri

25
00:01:04,588 --> 00:01:08,430
foarte usor, care, dacă vă amintiți,
este foarte complex, cu o serie.

26
00:01:08,430 --> 00:01:11,650
Și putem apela acest
lucru nou un tabel hash.

27
00:01:11,650 --> 00:01:15,190
>> Și dacă implementat corect,
suntem un fel de a lua

28
00:01:15,190 --> 00:01:18,150
avantajele ambelor date
structuri le-ați văzut deja,

29
00:01:18,150 --> 00:01:19,880
tablouri si liste legate.

30
00:01:19,880 --> 00:01:23,070
Inserare poate începe să
tind spre teta de 1.

31
00:01:23,070 --> 00:01:26,207
Theta nu am discutat într-adevăr,
dar teta este doar cazul medie,

32
00:01:26,207 --> 00:01:27,540
ce de fapt se va întâmpla.

33
00:01:27,540 --> 00:01:29,680
Nu te întotdeauna o să
au cel mai rău caz,

34
00:01:29,680 --> 00:01:32,555
și nu sunteți întotdeauna va avea
cel mai bun caz, asa ca ce-i

35
00:01:32,555 --> 00:01:33,900
scenariul mediu?

36
00:01:33,900 --> 00:01:36,500
>> Ei bine, o inserție medie
într-un tabel hash

37
00:01:36,500 --> 00:01:39,370
poate începe să se apropie de timp constant.

38
00:01:39,370 --> 00:01:41,570
Și ștergerea pot obține
aproape de constanta de timp.

39
00:01:41,570 --> 00:01:44,440
Și de căutare pot obține
aproape de constanta de timp.

40
00:01:44,440 --> 00:01:48,600
That's-- nu avem un date
structură dar care pot face acest lucru,

41
00:01:48,600 --> 00:01:51,180
și așa mai departe acest lucru sună deja
ca un lucru destul de mare.

42
00:01:51,180 --> 00:01:57,010
Am atenuat într-adevăr
dezavantajele fiecărei pe cont propriu.

43
00:01:57,010 --> 00:01:59,160
>> Pentru a obține această performanță
de upgrade, deși, am

44
00:01:59,160 --> 00:02:03,580
Trebuie să regândim modul în care adăugăm
date în structura.

45
00:02:03,580 --> 00:02:07,380
Mai exact vrem
Datele în sine pentru a ne spune

46
00:02:07,380 --> 00:02:09,725
în cazul în care ar trebui să meargă în structura.

47
00:02:09,725 --> 00:02:12,850
Și dacă am nevoie pentru a vedea apoi dacă se află într-
structura, dacă avem nevoie să-l găsească,

48
00:02:12,850 --> 00:02:16,610
vrem să se uite la datele
din nou și să fie capabil de a în mod eficient,

49
00:02:16,610 --> 00:02:18,910
folosind datele, acesta avea acces aleatoriu.

50
00:02:18,910 --> 00:02:20,700
Doar uitandu-se la
date ar trebui să avem

51
00:02:20,700 --> 00:02:25,890
o idee de unde suntem
gând să-l găsiți în tabelul hash.

52
00:02:25,890 --> 00:02:28,770
>> Acum dezavantaj de un hash
Tabelul este că sunt foarte

53
00:02:28,770 --> 00:02:31,770
destul de rău la comanda sau de sortare a datelor.

54
00:02:31,770 --> 00:02:34,970
Și, de fapt, dacă începeți
să le folosească pentru a comanda sau de sortare

55
00:02:34,970 --> 00:02:37,990
datele pe care le pierde cele de mai
avantajele pe care le anterior

56
00:02:37,990 --> 00:02:40,710
a avut în ceea ce privește inserarea și ștergerea.

57
00:02:40,710 --> 00:02:44,060
Timpul devine mai aproape de
teta de n, și ne-am practic

58
00:02:44,060 --> 00:02:45,530
regresat într-o listă legată.

59
00:02:45,530 --> 00:02:48,850
Și așa ne-o dorim doar să utilizați hash
tabele, dacă nu le pasă

60
00:02:48,850 --> 00:02:51,490
dacă datele sunt sortate.

61
00:02:51,490 --> 00:02:54,290
Pentru contextul în care
vei le folosească în CS50

62
00:02:54,290 --> 00:02:58,900
probabil că nu-mi pasă
că datele sunt sortate.

63
00:02:58,900 --> 00:03:03,170
>> Deci, un tabel hash este o combinație
din două piese distincte

64
00:03:03,170 --> 00:03:04,980
cu care suntem familiarizați.

65
00:03:04,980 --> 00:03:07,930
Primul este o funcție, care
De obicei apela o funcție hash.

66
00:03:07,930 --> 00:03:11,760
Și că funcție hash este de gând să
reveni unele întreg non-negativ, care

67
00:03:11,760 --> 00:03:14,870
numim, de obicei, un hashCode, OK?

68
00:03:14,870 --> 00:03:20,230
Cea de a doua piesa este o matrice, care este
capabil de a stoca date de tip WE

69
00:03:20,230 --> 00:03:22,190
doriți să plasați în structura de date.

70
00:03:22,190 --> 00:03:24,310
Vom dețină în afara pe de
legat Element lista de acum

71
00:03:24,310 --> 00:03:27,810
și doar începe cu elementele de bază ale unei
hash tabel pentru a obține capul în jurul valorii de ea,

72
00:03:27,810 --> 00:03:30,210
și apoi vom sufla poate
mintea ta un pic atunci când am

73
00:03:30,210 --> 00:03:32,920
combina tablouri si liste de link împreună.

74
00:03:32,920 --> 00:03:35,590
>> Ideea de bază, deși
este luăm unele date.

75
00:03:35,590 --> 00:03:37,860
Vom rula ca date prin
funcția hash.

76
00:03:37,860 --> 00:03:41,980
Și astfel datele sunt procesate
și scuipa un număr, OK?

77
00:03:41,980 --> 00:03:44,890
Și apoi cu acel număr
ne-am stoca datele

78
00:03:44,890 --> 00:03:48,930
vrem să magazin din
matrice la acea locație.

79
00:03:48,930 --> 00:03:53,990
Deci, de exemplu, avem poate
acest tabel hash de siruri de caractere.

80
00:03:53,990 --> 00:03:57,350
Are 10 elemente în ea, astfel încât
putem potrivi 10 siruri de caractere în ea.

81
00:03:57,350 --> 00:03:59,320
>> Să presupunem că vrem să hash John.

82
00:03:59,320 --> 00:04:02,979
Deci Ioan ca datele pe care le doriți să introduceți
în acest tabel hash undeva.

83
00:04:02,979 --> 00:04:03,770
În cazul în care nu ne-am pus-o?

84
00:04:03,770 --> 00:04:05,728
Ei bine, de obicei, cu o
matrice până acum ne-am, probabil,

85
00:04:05,728 --> 00:04:07,610
l-ar pune în matrice locație 0.

86
00:04:07,610 --> 00:04:09,960
Dar acum avem această nouă funcție hash.

87
00:04:09,960 --> 00:04:13,180
>> Și să spunem că vom rula Ioan
prin această funcție hash

88
00:04:13,180 --> 00:04:15,417
și se scuipă 4.

89
00:04:15,417 --> 00:04:17,500
Ei bine, asta e în cazul în care suntem
O să vrea să pună John.

90
00:04:17,500 --> 00:04:22,050
Vrem să pună Ioan în locație matrice
4, pentru că dacă ne-am hash John again--

91
00:04:22,050 --> 00:04:23,810
să spunem mai târziu ne-am
doriți să căutați și să vedem

92
00:04:23,810 --> 00:04:26,960
dacă John există în acest hash
table-- tot ce trebuie să facem

93
00:04:26,960 --> 00:04:30,310
se rula prin același hash
funcția, obține numărul 4,

94
00:04:30,310 --> 00:04:33,929
și să fie capabil de a găsi John
imediat în structura noastra de date.

95
00:04:33,929 --> 00:04:34,720
Asta e destul de bun.

96
00:04:34,720 --> 00:04:36,928
>> Să presupunem că acum facem acest lucru
din nou, vrem să hash Paul.

97
00:04:36,928 --> 00:04:39,446
Vrem să adăugați Paul
în acest tabel hash.

98
00:04:39,446 --> 00:04:42,070
Să spunem că de data aceasta vom rula
Paul prin funcția hash,

99
00:04:42,070 --> 00:04:44,600
hashCode care este generat este 6.

100
00:04:44,600 --> 00:04:47,340
Ei bine, acum putem pune Paul
în locația matrice 6.

101
00:04:47,340 --> 00:04:50,040
Și dacă avem nevoie să se uite în sus dacă
Paul este în acest tabel hash,

102
00:04:50,040 --> 00:04:53,900
tot ce trebuie să faceți este să rulați Paul
prin funcția hash din nou

103
00:04:53,900 --> 00:04:55,830
și vom obține 6 din nou.

104
00:04:55,830 --> 00:04:57,590
>> Și apoi ne uităm doar
la matrice locație 6.

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

106
00:04:58,910 --> 00:05:00,160
Dacă este așa, e în tabelul hash.

107
00:05:00,160 --> 00:05:01,875
Paul nu-i așa?

108
00:05:01,875 --> 00:05:03,000
Nu e în tabel hash.

109
00:05:03,000 --> 00:05:05,720
E destul de simplu.

110
00:05:05,720 --> 00:05:07,770
>> Acum, cum ai defini o funcție hash?

111
00:05:07,770 --> 00:05:11,460
Ei bine, nu e chiar nici o limită la
Numărul de posibile funcții hash.

112
00:05:11,460 --> 00:05:14,350
De fapt, există un număr de adevărat,
cele foarte bine pe internet.

113
00:05:14,350 --> 00:05:17,560
Există o serie de adevărat,
cele foarte rău pe internet.

114
00:05:17,560 --> 00:05:21,080
Este, de asemenea, destul de ușor
pentru a scrie un rău.

115
00:05:21,080 --> 00:05:23,760
>> Deci, ceea ce face o bună
funcție hash, nu?

116
00:05:23,760 --> 00:05:27,280
Ei bine, o funcție hash bun ar trebui să
utilizați numai datele fiind distribuit,

117
00:05:27,280 --> 00:05:29,420
și toate datele fiind distribuit.

118
00:05:29,420 --> 00:05:32,500
Așa că nu doriți să utilizați anything--
noi nu includ nimic

119
00:05:32,500 --> 00:05:35,560
altceva, altele decât datele.

120
00:05:35,560 --> 00:05:37,080
Și vrem să folosească toate datele.

121
00:05:37,080 --> 00:05:39,830
Noi nu doriți să utilizați doar o bucată
de ea, vrem sa folosim toate.

122
00:05:39,830 --> 00:05:41,710
O funcție hash ar trebui
fi, de asemenea determinist.

123
00:05:41,710 --> 00:05:42,550
Ce înseamnă asta?

124
00:05:42,550 --> 00:05:46,200
Ei bine, aceasta înseamnă că de fiecare dată ne
trece exact aceeași bucată de date

125
00:05:46,200 --> 00:05:50,040
în funcție hash mereu am
obține același hashCode afară.

126
00:05:50,040 --> 00:05:52,870
Dacă trec Ioan în
funcție hash ies 4.

127
00:05:52,870 --> 00:05:56,110
Ar trebui să fiu în stare să fac asta 10.000
ori și voi avea întotdeauna 4.

128
00:05:56,110 --> 00:06:00,810
Deci, nu numere aleatoare în mod eficient
pot fi implicate în hash nostru tables--

129
00:06:00,810 --> 00:06:02,750
în funcțiile noastre hash.

130
00:06:02,750 --> 00:06:05,750
>> O funcție hash ar trebui, de asemenea,
distribuie uniform de date.

131
00:06:05,750 --> 00:06:09,700
Dacă de fiecare dată când executați date prin
funcție hash veți obține hashCode 0,

132
00:06:09,700 --> 00:06:11,200
care, probabil, nu e atât de mare, nu?

133
00:06:11,200 --> 00:06:14,600
Probabil că doriți să mare
o serie de coduri hash.

134
00:06:14,600 --> 00:06:17,190
De asemenea lucruri pot fi răspândite
pe toată masa.

135
00:06:17,190 --> 00:06:23,210
Și, de asemenea, ar fi grozav dacă într-adevăr
date similare, cum ar fi John și Ionatan,

136
00:06:23,210 --> 00:06:26,320
Poate s-au întins să cântărească
diferite locații din tabelul hash.

137
00:06:26,320 --> 00:06:28,750
Asta ar fi un avantaj frumos.

138
00:06:28,750 --> 00:06:31,250
>> Iată un exemplu de o funcție hash.

139
00:06:31,250 --> 00:06:33,150
Am scris asta mai devreme.

140
00:06:33,150 --> 00:06:35,047
Nu este o deosebit de
funcție hash bun

141
00:06:35,047 --> 00:06:37,380
pentru motive care nu prea
suportă intra în chiar acum.

142
00:06:37,380 --> 00:06:41,040
Dar vezi ce se întâmplă aici?

143
00:06:41,040 --> 00:06:44,420
Se pare că suntem de declarare a unei variabile
numit sumă și stabilirea-l egal cu 0.

144
00:06:44,420 --> 00:06:50,010
Și apoi se pare că fac ceva
atât timp cât strstr [j] nu este egal

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

146
00:06:52,490 --> 00:06:54,870
Ce fac acolo?

147
00:06:54,870 --> 00:06:57,440
>> Aceasta este de fapt doar un alt
mod de punere în aplicare [? strl?]

148
00:06:57,440 --> 00:06:59,773
și detectarea când ați
ajuns la sfârșitul șirului.

149
00:06:59,773 --> 00:07:02,480
Așa că nu trebuie să de fapt,
calcula lungimea șirului,

150
00:07:02,480 --> 00:07:05,640
Sunt doar folosind când am lovit
backslash 0 caracter știu

151
00:07:05,640 --> 00:07:07,185
Am ajuns la capătul șirului.

152
00:07:07,185 --> 00:07:09,560
Și apoi am de gând să păstreze
iterarea prin care șir,

153
00:07:09,560 --> 00:07:15,310
adăugând strstr [j] pentru a rezuma, iar apoi la
sfârșitul zilei de gând să se întoarcă sumă mod

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

155
00:07:16,200 --> 00:07:18,700
>> Practic toate acest hash
Funcția este de a face este însumarea

156
00:07:18,700 --> 00:07:23,450
toate valorile ASCII ale
șir meu, și apoi este

157
00:07:23,450 --> 00:07:26,390
revenind unele hashCode
modded de HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Este, probabil, dimensiunea
de matrice meu, nu?

159
00:07:29,790 --> 00:07:33,160
Nu vreau să fi obtinerea hash
coduri dacă gama meu este de mărime 10,

160
00:07:33,160 --> 00:07:35,712
Nu vreau să fie obtinerea
Codurile din hash 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, nu pot pune lucrurile în
acele locații de matrice,

162
00:07:38,690 --> 00:07:39,790
că ar fi ilegal.

163
00:07:39,790 --> 00:07:42,130
Aș suferi o eroare de segmentare.

164
00:07:42,130 --> 00:07:45,230
>> Acum, aici este un alt rapid deoparte.

165
00:07:45,230 --> 00:07:48,470
În general, esti, probabil, nu va
doresc pentru a scrie funcțiile propriile hash.

166
00:07:48,470 --> 00:07:50,997
Acesta este de fapt un pic de
o artă, nu o știință.

167
00:07:50,997 --> 00:07:52,580
Și există o mulțime care merge în ele.

168
00:07:52,580 --> 00:07:55,288
Internetul, cum am spus, este plin
de funcții foarte bun hash,

169
00:07:55,288 --> 00:07:58,470
și ar trebui să utilizeze internetul pentru a
găsi funcții hash, deoarece este într-adevăr

170
00:07:58,470 --> 00:08:03,230
doar un fel de inutil
pierdere de timp pentru a crea propriul.

171
00:08:03,230 --> 00:08:05,490
>> Puteți scrie cele simple
în scop de testare.

172
00:08:05,490 --> 00:08:08,323
Dar atunci când, de fapt de gând să
începe hashing date și stocarea acestuia

173
00:08:08,323 --> 00:08:10,780
într-un tabel hash esti
probabil, va dori

174
00:08:10,780 --> 00:08:14,580
pentru a utiliza o funcție care a fost generat
pentru tine, care există pe internet.

175
00:08:14,580 --> 00:08:17,240
Dacă nu doar să fie sigur
pentru a cita sursele.

176
00:08:17,240 --> 00:08:21,740
Nu e nici un motiv să
plagia nimic aici.

177
00:08:21,740 --> 00:08:25,370
>> Comunitatea informatică este
cu siguranta in crestere, și într-adevăr valori

178
00:08:25,370 --> 00:08:28,796
open source, și este foarte important
pentru a cita sursele, astfel încât oamenii

179
00:08:28,796 --> 00:08:30,670
pot obține atribuire pentru
lucrarea pe care acestea sunt

180
00:08:30,670 --> 00:08:32,312
face în beneficiul comunității.

181
00:08:32,312 --> 00:08:34,020
Astfel încât să fie întotdeauna sure--
și nu doar pentru distribuire

182
00:08:34,020 --> 00:08:37,270
funcții, dar în general, atunci când
folosi codul de la o sursă din afara,

183
00:08:37,270 --> 00:08:38,299
citează întotdeauna sursa.

184
00:08:38,299 --> 00:08:43,500
Da credit pentru persoana care a facut
o parte din munca, astfel încât să nu trebuie să.

185
00:08:43,500 --> 00:08:46,720
>> OK Să reexamineze acest
tabel hash pentru un al doilea.

186
00:08:46,720 --> 00:08:48,780
Acest lucru este în cazul în care am plecat
off după ce am introdus

187
00:08:48,780 --> 00:08:53,300
Ioan și Pavel în acest tabel hash.

188
00:08:53,300 --> 00:08:55,180
Vedeți o problemă aici?

189
00:08:55,180 --> 00:08:58,410
S-ar putea vedea două.

190
00:08:58,410 --> 00:09:02,240
Dar, în special, nu
vezi această problemă posibil?

191
00:09:02,240 --> 00:09:06,770
>> Ce se întâmplă dacă hash Ringo, și
se dovedește că, după prelucrare

192
00:09:06,770 --> 00:09:14,000
că date prin funcția hash
Ringo a generat, de asemenea, hashCode 6.

193
00:09:14,000 --> 00:09:16,810
Am deja date la
hashcode-- matrice locație 6.

194
00:09:16,810 --> 00:09:22,000
Deci, este, probabil, va fi un pic
de o problemă pentru mine acum, nu?

195
00:09:22,000 --> 00:09:23,060
>> Noi numim acest lucru o coliziune.

196
00:09:23,060 --> 00:09:26,460
Și coliziune are loc atunci când două
piese de date rula prin același hash

197
00:09:26,460 --> 00:09:29,200
Funcția se obține aceeași hashCode.

198
00:09:29,200 --> 00:09:32,850
Probabil tot doriți să obțineți atât
piese de date în tabel hash,

199
00:09:32,850 --> 00:09:36,330
altfel nu ne-ar fi difuzate Ringo
arbitrar prin intermediul funcției hash.

200
00:09:36,330 --> 00:09:40,870
Ne probabil doriți să obțineți
Ringo în această matrice.

201
00:09:40,870 --> 00:09:46,070
>> Cum o facem, deși, în cazul în care
și Paul atât randament hashCode 6?

202
00:09:46,070 --> 00:09:49,520
Noi nu vrem să suprascrie Paul,
vrem Pavel să fie acolo.

203
00:09:49,520 --> 00:09:52,790
Deci, trebuie să găsim o modalitate de a obține
elemente în tabelul hash care

204
00:09:52,790 --> 00:09:56,550
încă păstrează rapid nostru
inserție și scurtă privire în sus.

205
00:09:56,550 --> 00:10:01,350
Și o modalitate de a face cu ea este de a
face ceva numit liniar sondare.

206
00:10:01,350 --> 00:10:04,170
>> Folosind această metodă, dacă avem o
coliziune, ei bine, ce facem?

207
00:10:04,170 --> 00:10:08,580
Ei bine, nu-l pot pune în locație matrice
6, sau orice hashCode a fost generat,

208
00:10:08,580 --> 00:10:10,820
Să-l punem la hashCode plus 1.

209
00:10:10,820 --> 00:10:13,670
Și dacă asta e plin Să
l-au pus în hashCode plus 2.

210
00:10:13,670 --> 00:10:17,420
Avantajul acestei ființe dacă e
Nu exact unde credem noi că este,

211
00:10:17,420 --> 00:10:20,850
și trebuie să începem căutarea,
Poate că nu trebuie să mergem prea departe.

212
00:10:20,850 --> 00:10:23,900
Poate că nu trebuie să căutați
toate n elemente ale tabelului hash.

213
00:10:23,900 --> 00:10:25,790
Poate că trebuie să căutați
câteva dintre ele.

214
00:10:25,790 --> 00:10:30,680
>> Și așa suntem încă tinde spre
acest caz medie fiind de aproape de 1 vs

215
00:10:30,680 --> 00:10:34,280
aproape de n, astfel poate că va funcționa.

216
00:10:34,280 --> 00:10:38,010
Deci, hai sa vedem cum acest
ar putea să funcționeze în realitate.

217
00:10:38,010 --> 00:10:41,460
Și să vedem dacă poate putem detecta
problema care ar putea apărea aici.

218
00:10:41,460 --> 00:10:42,540
>> Să spunem că hash Bart.

219
00:10:42,540 --> 00:10:45,581
Deci, acum vom rula un nou set
de siruri de caractere prin intermediul funcției hash,

220
00:10:45,581 --> 00:10:48,460
si vom rula Bart prin hash
funcție, ne hashCode 6.

221
00:10:48,460 --> 00:10:52,100
Ne ia o privire, vom vedea 6 este
gol, astfel încât să putem pune Bart acolo.

222
00:10:52,100 --> 00:10:55,410
>> Acum ne hash Lisa și că
generează, de asemenea, hashCode 6.

223
00:10:55,410 --> 00:10:58,330
Ei bine, acum că suntem folosind acest
liniar metodă de a începe de la 6 palpare,

224
00:10:58,330 --> 00:10:59,330
vom vedea că 6 este plin.

225
00:10:59,330 --> 00:11:00,990
Nu putem pune Lisa în 6.

226
00:11:00,990 --> 00:11:02,090
Deci, unde mergem?

227
00:11:02,090 --> 00:11:03,280
Să mergem la 7.

228
00:11:03,280 --> 00:11:04,610
7 lui gol, astfel încât funcționează.

229
00:11:04,610 --> 00:11:06,510
Deci să punem Lisa acolo.

230
00:11:06,510 --> 00:11:10,200
>> Acum ne hash Homer și ajungem 7.

231
00:11:10,200 --> 00:11:13,380
OK bine știm că 7 e plin
acum, așa că nu se poate pune Homer acolo.

232
00:11:13,380 --> 00:11:14,850
Așa că hai să mergem la 8.

233
00:11:14,850 --> 00:11:15,664
Este de 8 disponibil?

234
00:11:15,664 --> 00:11:18,330
Da, și 8, aproape de 7, deci, dacă
trebuie să începem căutarea suntem

235
00:11:18,330 --> 00:11:20,020
nu va trebui să meargă prea departe.

236
00:11:20,020 --> 00:11:22,860
Și astfel să punem la Homer 8.

237
00:11:22,860 --> 00:11:25,151
>> Acum ne hash Maggie și
întoarce 3, slavă Domnului

238
00:11:25,151 --> 00:11:26,650
suntem în măsură să pună doar Maggie acolo.

239
00:11:26,650 --> 00:11:29,070
Noi nu trebuie să facem nici un
un fel de sondare pentru asta.

240
00:11:29,070 --> 00:11:32,000
Acum ne hash Marge, și
Marge întoarce, de asemenea, 6.

241
00:11:32,000 --> 00:11:39,560
>> Ei bine, 6 este plin, 7 este plin, 8 este plin,
9, mulțumesc lui Dumnezeu în regulă, 9 este gol.

242
00:11:39,560 --> 00:11:41,600
Pot pune Marge la 9.

243
00:11:41,600 --> 00:11:45,280
Deja putem vedea că suntem incepand
de a avea această problemă în cazul în care acum suntem

244
00:11:45,280 --> 00:11:48,780
Încep să se întindă lucruri fel
de departe de codurile lor de dispersie.

245
00:11:48,780 --> 00:11:52,960
Și că teta de 1, care medie
caz de a fi timp constant,

246
00:11:52,960 --> 00:11:56,560
începe pentru a obține un pic more--
incepand de la tendința de un pic mai mult

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

248
00:11:58,050 --> 00:12:01,270
Suntem început să-și piardă că
avantaj de tabele de dispersie.

249
00:12:01,270 --> 00:12:03,902
>> Această problemă pe care tocmai am văzut
este ceva numit grupare.

250
00:12:03,902 --> 00:12:06,360
Si ceea ce este cu adevărat rău despre
clustering este că, odată ce acum

251
00:12:06,360 --> 00:12:09,606
au două elemente care sunt una lângă
alta se face chiar mai probabil,

252
00:12:09,606 --> 00:12:11,480
aveți dubla
șansă, că ai de gând

253
00:12:11,480 --> 00:12:13,516
de a avea un alt coliziune
cu cluster,

254
00:12:13,516 --> 00:12:14,890
și clusterul va crește cu unul.

255
00:12:14,890 --> 00:12:19,640
Și veți continua sa creasca si in crestere
probabilitatea de a avea o coliziune.

256
00:12:19,640 --> 00:12:24,470
Și, eventual, e la fel de rău
ca nu sortarea datelor de la toate.

257
00:12:24,470 --> 00:12:27,590
>> O altă problemă, deși este ne
încă, și până în prezent până la acest moment,

258
00:12:27,590 --> 00:12:30,336
doar am fost un fel de
intelegerea a ceea ce un tabel hash este,

259
00:12:30,336 --> 00:12:31,960
avem încă doar camerei timp de 10 siruri de caractere.

260
00:12:31,960 --> 00:12:37,030
Dacă dorim să continuăm să hash
cetățenii Springfield,

261
00:12:37,030 --> 00:12:38,790
putem obține doar 10 dintre ele acolo.

262
00:12:38,790 --> 00:12:42,619
Și dacă vom încerca și adaugă un 11 sau 12,
nu avem un loc pentru a le-a pus.

263
00:12:42,619 --> 00:12:45,660
Tocmai am putea fi în jurul valorii de filare în
cercuri încercarea de a găsi un loc gol,

264
00:12:45,660 --> 00:12:49,000
si ne poate mă blochez
într-o buclă infinită.

265
00:12:49,000 --> 00:12:51,810
>> Deci, acest tip de împrumută ideea
de ceva numit înlănțuire.

266
00:12:51,810 --> 00:12:55,790
Și acest lucru este în cazul în care vom aduce
liste legate înapoi în imagine.

267
00:12:55,790 --> 00:13:01,300
Ce se întâmplă dacă în loc de a stoca doar
datele în sine în matrice,

268
00:13:01,300 --> 00:13:04,471
fiecare element de matrice ar putea
deține mai multe bucăți de date?

269
00:13:04,471 --> 00:13:05,970
Ei bine, asta nu are nici un sens, nu?

270
00:13:05,970 --> 00:13:09,280
Știm că o serie poate doar
hold-- fiecare element al unui tablou

271
00:13:09,280 --> 00:13:12,930
poate deține doar o singură bucată
de date de acest tip de date.

272
00:13:12,930 --> 00:13:16,750
>> Dar ce se întâmplă dacă acel tip de date
este o listă legată, nu?

273
00:13:16,750 --> 00:13:19,830
Deci, ce dacă fiecare
Element de matrice a fost

274
00:13:19,830 --> 00:13:22,790
un pointer la cap de o listă legată?

275
00:13:22,790 --> 00:13:24,680
Și apoi am putea construi
aceste liste legate de

276
00:13:24,680 --> 00:13:27,120
și să crească în mod arbitrar,
deoarece liste legate permite

277
00:13:27,120 --> 00:13:32,090
ne să crească și reduce mult mai mult
flexibil decât un tablou nu.

278
00:13:32,090 --> 00:13:34,210
Și ce dacă vom folosi acum,
am parghie asta, nu?

279
00:13:34,210 --> 00:13:37,760
Vom începe să crească aceste lanturi
din aceste locații matrice.

280
00:13:37,760 --> 00:13:40,740
>> Acum putem potrivi o infinit
cantitatea de date, sau nu infinit,

281
00:13:40,740 --> 00:13:44,170
o cantitate arbitrară de
date, în masa noastră hash

282
00:13:44,170 --> 00:13:47,760
fără să fie difuzate în
problema de coliziune.

283
00:13:47,760 --> 00:13:50,740
De asemenea, Am eliminat
clustering de a face acest lucru.

284
00:13:50,740 --> 00:13:54,380
Și bine știm că, atunci când vom introduce
într-o listă legată, dacă vă amintiți

285
00:13:54,380 --> 00:13:57,779
din videoclipul nostru pe liste legate, individual
liste legate și liste dublu legate,

286
00:13:57,779 --> 00:13:59,070
e o operațiune constantă de timp.

287
00:13:59,070 --> 00:14:00,710
Noi doar adăugarea în față.

288
00:14:00,710 --> 00:14:04,400
>> Și pentru look-up și știm
care căuta într-o listă legată

289
00:14:04,400 --> 00:14:05,785
poate fi o problemă, nu?

290
00:14:05,785 --> 00:14:07,910
Trebuie să căutați prin
l de la început până la sfârșit.

291
00:14:07,910 --> 00:14:10,460
Nu e nici o întâmplare
acces într-o listă legată.

292
00:14:10,460 --> 00:14:15,610
Dar dacă în loc de a avea o legătură
Lista în cazul în care o căutare ar fi O N,

293
00:14:15,610 --> 00:14:19,590
acum avem 10 de liste legate,
sau 1.000 de liste legate,

294
00:14:19,590 --> 00:14:24,120
acum e O n împărțit la 10,
sau O din n împărțit la 1,000.

295
00:14:24,120 --> 00:14:26,940
>> Și în timp ce noi vorbeam
teoretic despre complexitate

296
00:14:26,940 --> 00:14:30,061
ignorăm constante, în real
lumea aceste lucruri contează de fapt,

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

298
00:14:30,560 --> 00:14:33,080
Noi de fapt, va observa
că acest lucru se întâmplă

299
00:14:33,080 --> 00:14:36,610
pentru a rula 10 ori mai rapid,
sau de 1.000 de ori mai rapid,

300
00:14:36,610 --> 00:14:41,570
pentru că suntem distribuirea unul lung
lanț peste 1.000 de lanțuri mai mici.

301
00:14:41,570 --> 00:14:45,090
Și așa de fiecare dată când avem de a căuta
prin una din acele lanțuri putem

302
00:14:45,090 --> 00:14:50,290
ignora 999 lanturile noi nu le pasa
despre, si cauta doar ca unul.

303
00:14:50,290 --> 00:14:53,220
>> Care este, în medie, la
fi de 1.000 de ori mai scurtă.

304
00:14:53,220 --> 00:14:56,460
Și așa că încă mai sunt un fel de
tinde spre acest caz mediu

305
00:14:56,460 --> 00:15:01,610
de a fi constantă de timp, dar
doar pentru că suntem pârghie

306
00:15:01,610 --> 00:15:03,730
împărțirea de un factor imens constant.

307
00:15:03,730 --> 00:15:05,804
Să vedem cum acest lucru ar putea
de fapt uite totuși.

308
00:15:05,804 --> 00:15:08,720
Deci aceasta a fost tabel hash am avut
înainte de a ne declara un tabel hash care

309
00:15:08,720 --> 00:15:10,270
a fost capabil de a stoca 10 siruri de caractere.

310
00:15:10,270 --> 00:15:11,728
Noi nu vom mai face asta.

311
00:15:11,728 --> 00:15:13,880
Știm deja
limitări ale acestei metode.

312
00:15:13,880 --> 00:15:20,170
Acum, masa noastră hash va fi
o serie de 10 noduri, indicii

313
00:15:20,170 --> 00:15:22,120
șefilor de liste legate.

314
00:15:22,120 --> 00:15:23,830
>> Iar acum e nul.

315
00:15:23,830 --> 00:15:26,170
Fiecare dintre cele 10 indicii este nulă.

316
00:15:26,170 --> 00:15:29,870
Nu e nimic în nostru
hash masă acum.

317
00:15:29,870 --> 00:15:32,690
>> Acum să începem să pună unele
lucrurile în acest tabel hash.

318
00:15:32,690 --> 00:15:35,440
Și să vedem cum această metodă este
O să ne beneficia un pic.

319
00:15:35,440 --> 00:15:36,760
Să acum hash Joey.

320
00:15:36,760 --> 00:15:40,210
Vom va rula șir Joey prin
o funcție hash și ne întoarcem 6.

321
00:15:40,210 --> 00:15:41,200
Ei bine, ce facem acum?

322
00:15:41,200 --> 00:15:44,090
>> Ei bine, acum de lucru cu liste legate,
nu suntem de lucru cu tablouri.

323
00:15:44,090 --> 00:15:45,881
Și când lucrăm
cu liste legate noi

324
00:15:45,881 --> 00:15:49,790
că avem nevoie pentru a începe dinamic
alocarea de spațiu și de construcții lanțuri.

325
00:15:49,790 --> 00:15:54,020
Asta e un fel de how-- acestea sunt de bază
elemente de a construi o listă legată.

326
00:15:54,020 --> 00:15:57,670
Deci, haideți să dinamic
aloca spațiu pentru Joey,

327
00:15:57,670 --> 00:16:00,390
și apoi să-l adăugați la lanțul.

328
00:16:00,390 --> 00:16:03,170
>> Deci, uite acum ce am făcut.

329
00:16:03,170 --> 00:16:06,440
Când ne-am hash Joey am primit hashCode 6.

330
00:16:06,440 --> 00:16:11,790
Acum, indicatorul de la matrice locație 6
subliniază capul unei liste legate,

331
00:16:11,790 --> 00:16:14,900
iar acum este singurul
element al unei liste legate.

332
00:16:14,900 --> 00:16:18,350
Și nodul în care
Lista de legat este Joey.

333
00:16:18,350 --> 00:16:22,300
>> Deci, dacă trebuie să privim în sus Joey
mai târziu, ne-am hash Joey din nou,

334
00:16:22,300 --> 00:16:26,300
ajungem 6 din nou, deoarece nostru
funcție hash este determinist.

335
00:16:26,300 --> 00:16:30,400
Și apoi vom începe de la cap
listei de legătura subliniat

336
00:16:30,400 --> 00:16:33,360
a de locație matrice
6, și putem repeta

337
00:16:33,360 --> 00:16:35,650
peste care încearcă să găsească Joey.

338
00:16:35,650 --> 00:16:37,780
Și dacă vom construi nostru
hash masă în mod eficient,

339
00:16:37,780 --> 00:16:41,790
și funcția noastră hash eficient
de a distribui date bine,

340
00:16:41,790 --> 00:16:45,770
în medie, fiecare dintre cele legate
liste la fiecare locație matrice

341
00:16:45,770 --> 00:16:50,110
va fi 1/10 din mărimea dacă
la fel a avut ca un singur imens

342
00:16:50,110 --> 00:16:51,650
Lista legată de tot ceea ce în ea.

343
00:16:51,650 --> 00:16:55,670
>> Dacă vom distribui că imens legat
Lista peste 10 liste legate

344
00:16:55,670 --> 00:16:57,760
fiecare listă va fi 1/10 dimensiunea.

345
00:16:57,760 --> 00:17:01,432
Și astfel de 10 ori mai repede
pentru a căuta prin.

346
00:17:01,432 --> 00:17:02,390
Deci, hai sa facem asta din nou.

347
00:17:02,390 --> 00:17:04,290
Să acum hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Și să spunem Ross, atunci când facem asta
codul de distribuire ne intoarcem este 2.

349
00:17:07,540 --> 00:17:10,630
Ei bine, acum ne-am aloca dinamic un
nod nou, am pus Ross în acel nod,

350
00:17:10,630 --> 00:17:14,900
și spunem acum locație matrice
2, în loc de arătând spre nul,

351
00:17:14,900 --> 00:17:18,579
punctele de la cap de legat
Lista a căror numai nod este Ross.

352
00:17:18,579 --> 00:17:22,660
Și putem face asta de mai mult timp, ne-am
poate hash Rachel și de a lua hashCode 4.

353
00:17:22,660 --> 00:17:25,490
malloc un nou nod, a pus în Rachel
nodul, și spune o locație matrice

354
00:17:25,490 --> 00:17:27,839
4. atrage atenția asupra capului
a unei liste a cărui legat

355
00:17:27,839 --> 00:17:31,420
singurul element se întâmplă să fie Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, dar ce se întâmplă dacă
avem o coliziune?

357
00:17:33,470 --> 00:17:38,560
Să vedem cum ne ocupam de coliziuni
folosind metoda înlănțuirii separat.

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

359
00:17:39,800 --> 00:17:41,094
Vom obține hashCode 6.

360
00:17:41,094 --> 00:17:44,010
În exemplul nostru anterior am fost doar
stocarea siruri de caractere în matrice.

361
00:17:44,010 --> 00:17:45,980
Aceasta a fost o problemă.

362
00:17:45,980 --> 00:17:48,444
>> Noi nu vrem să rescrie
Joey și am deja

363
00:17:48,444 --> 00:17:51,110
văzut că putem obține unele clustering
probleme dacă am încerca și pas

364
00:17:51,110 --> 00:17:52,202
prin și sonda.

365
00:17:52,202 --> 00:17:54,660
Dar dacă am doar un fel de
trata acest fel, nu?

366
00:17:54,660 --> 00:17:57,440
E la fel ca adăugarea unui element
la capul unei liste legate.

367
00:17:57,440 --> 00:18:00,220
Să spațiu doar malloc pentru Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Vom spune următoarele indicatorul lui Phoebe
la vechiul cap al listei de legătura,

369
00:18:04,764 --> 00:18:07,180
și apoi 6 puncte doar la
noul șef al listei legate.

370
00:18:07,180 --> 00:18:10,150
Și acum uite, ne-am schimbat Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Putem stoca acum două
elemente cu hashCode 6,

372
00:18:14,210 --> 00:18:17,170
și nu avem nici o problemă.

373
00:18:17,170 --> 00:18:20,147
>> Asta e destul de mult tot
este de înlănțuire.

374
00:18:20,147 --> 00:18:21,980
Și înlănțuirea este cu siguranta
metoda care este

375
00:18:21,980 --> 00:18:27,390
va fi cel mai eficient pentru tine, dacă
sunteți stocarea datelor într-un tabel hash.

376
00:18:27,390 --> 00:18:30,890
Dar această combinație de
tablouri si liste legate

377
00:18:30,890 --> 00:18:36,080
împreună pentru a forma un tabel hash într-adevăr
îmbunătățește dramatic capacitatea de

378
00:18:36,080 --> 00:18:40,550
pentru a stoca cantități mari de date, și
căutare foarte rapid și eficient

379
00:18:40,550 --> 00:18:41,630
prin care datele.

380
00:18:41,630 --> 00:18:44,150
>> Există încă o mai
structură de date acolo

381
00:18:44,150 --> 00:18:48,700
care ar putea fi chiar un pic
mai bine în ceea ce privește garantarea

382
00:18:48,700 --> 00:18:51,920
că ne inserție, ștergere, și
privi în sus ori sunt chiar mai repede.

383
00:18:51,920 --> 00:18:55,630
Și vom vedea că într-un film pe incercari.

384
00:18:55,630 --> 00:18:58,930
Sunt Doug Lloyd, aceasta este CS50.

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