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

2
00:00:00,500 --> 00:00:01,900
[REPRODUCCIÓ DE MÚSICA]

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: A hores d'ara ja
saber molt sobre les matrius,

5
00:00:09,150 --> 00:00:11,610
i vostè sap molt sobre llistes enllaçades.

6
00:00:11,610 --> 00:00:13,650
I hem discutir la
pros i contres, hem

7
00:00:13,650 --> 00:00:16,620
discutit que unia les llistes
pot aconseguir més gran i més petit,

8
00:00:16,620 --> 00:00:18,630
però ocupen més grandària.

9
00:00:18,630 --> 00:00:22,359
Les matrius són molt més fàcils de
utilitzen, però són restrictius en la mesura

10
00:00:22,359 --> 00:00:24,900
ja que hem d'ajustar la mida de
la matriu des del principi

11
00:00:24,900 --> 00:00:26,910
i després ens peguen amb ella.

12
00:00:26,910 --> 00:00:30,470
>> Però això és, tenim més o menys
esgotat tots els nostres temes

13
00:00:30,470 --> 00:00:33,040
sobre llistes enllaçades i matrius.

14
00:00:33,040 --> 00:00:34,950
O tenim?

15
00:00:34,950 --> 00:00:37,720
Potser puguem fer alguna cosa
encara més creatiu.

16
00:00:37,720 --> 00:00:40,950
I aquest tipus de prestació
la idea d'una taula hash.

17
00:00:40,950 --> 00:00:46,680
>> Així que en una taula hash que tractarem
combinar una matriu amb una llista enllaçada.

18
00:00:46,680 --> 00:00:49,520
Anem a prendre les avantatges
de la matriu, com d'accés aleatori,

19
00:00:49,520 --> 00:00:53,510
ser capaç d'anar a la matriu
element 4 o matriu element agost

20
00:00:53,510 --> 00:00:55,560
sense haver de recórrer a través.

21
00:00:55,560 --> 00:00:57,260
Això és bastant ràpid, oi?

22
00:00:57,260 --> 00:01:00,714
>> Però també volem tenir les nostres dades
estructura de poder créixer i encongir-se.

23
00:01:00,714 --> 00:01:02,630
No necessitem, no ho fem
volen ser restringit.

24
00:01:02,630 --> 00:01:04,588
I nosaltres volem ser capaços
per afegir i treure coses

25
00:01:04,588 --> 00:01:08,430
molt fàcilment, el que si vostè recorda,
és molt complex amb una matriu.

26
00:01:08,430 --> 00:01:11,650
I podem cridar a això
El nou una taula hash.

27
00:01:11,650 --> 00:01:15,190
>> I si s'aplica correctament,
estem espècie de prendre

28
00:01:15,190 --> 00:01:18,150
els avantatges d'ambdós dades
estructures que ja has vist,

29
00:01:18,150 --> 00:01:19,880
matrius i llistes enllaçades.

30
00:01:19,880 --> 00:01:23,070
La inserció pot començar a
tendir cap a theta d'1.

31
00:01:23,070 --> 00:01:26,207
Theta no hem discutit realment,
però theta és només el cas mitjana,

32
00:01:26,207 --> 00:01:27,540
el que en realitat va a succeir.

33
00:01:27,540 --> 00:01:29,680
No sempre vas a
tenir el pitjor dels casos,

34
00:01:29,680 --> 00:01:32,555
i no sempre tindràs
el millor dels casos, així que quina és

35
00:01:32,555 --> 00:01:33,900
l'escenari mitjana?

36
00:01:33,900 --> 00:01:36,500
>> Bé una inserció mitjana
en una taula hash

37
00:01:36,500 --> 00:01:39,370
pot començar a acostar-se a la constant de temps.

38
00:01:39,370 --> 00:01:41,570
I eliminació pot aconseguir
prop de constant de temps.

39
00:01:41,570 --> 00:01:44,440
I les operacions de recerca pot obtenir
prop de constant de temps.

40
00:01:44,440 --> 00:01:48,600
Això és-- no tenim una dada
estructura fins ara que pot fer això,

41
00:01:48,600 --> 00:01:51,180
pel que aquest ja sona
com un molt gran cosa.

42
00:01:51,180 --> 00:01:57,010
Realment hem mitigat els
desavantatges de cada un pel seu compte.

43
00:01:57,010 --> 00:01:59,160
>> Per obtenir aquest rendiment
actualitzar però, ens

44
00:01:59,160 --> 00:02:03,580
necessitat de repensar com afegim
les dades en l'estructura.

45
00:02:03,580 --> 00:02:07,380
Específicament volem que el
sí les dades que ens digui

46
00:02:07,380 --> 00:02:09,725
on ha d'anar en l'estructura.

47
00:02:09,725 --> 00:02:12,850
I si després hem de veure si està en
l'estructura, si hem de trobar-lo,

48
00:02:12,850 --> 00:02:16,610
volem mirar les dades
de nou i ser capaç d'eficàcia,

49
00:02:16,610 --> 00:02:18,910
utilitzant les dades, accedir aleatòriament ella.

50
00:02:18,910 --> 00:02:20,700
Només mirant a la
dades que hem de tenir

51
00:02:20,700 --> 00:02:25,890
una idea d'on exactament estem
anar a trobar-lo en la taula hash.

52
00:02:25,890 --> 00:02:28,770
>> Ara el desavantatge d'un hash
taula és que són realment

53
00:02:28,770 --> 00:02:31,770
bastant malament en ordenar o classificar les dades.

54
00:02:31,770 --> 00:02:34,970
I de fet, si s'inicia
utilitzar-los per demanar o ordenar

55
00:02:34,970 --> 00:02:37,990
les dades es perd tota la
avantatges prèviament

56
00:02:37,990 --> 00:02:40,710
tingut en termes d'inserció i eliminació.

57
00:02:40,710 --> 00:02:44,060
El temps es converteix en més a prop de
theta de n, i hem bàsicament

58
00:02:44,060 --> 00:02:45,530
retrocedit en una llista enllaçada.

59
00:02:45,530 --> 00:02:48,850
I pel que només volem utilitzar de hash
taules si no importen

60
00:02:48,850 --> 00:02:51,490
si les dades s'ordena.

61
00:02:51,490 --> 00:02:54,290
Per al context en el qual
que farem servir en CS50

62
00:02:54,290 --> 00:02:58,900
és probable que no importa
que les dades es classifiquen.

63
00:02:58,900 --> 00:03:03,170
>> Així que una taula hash és una combinació
de dues peces diferents

64
00:03:03,170 --> 00:03:04,980
amb la qual estem familiaritzats.

65
00:03:04,980 --> 00:03:07,930
La primera és una funció, la qual
que se sol anomenar una funció hash.

66
00:03:07,930 --> 00:03:11,760
I aquesta funció hash va
tornar algun enter no negatiu, que

67
00:03:11,760 --> 00:03:14,870
que se sol anomenar un codi hash, OK?

68
00:03:14,870 --> 00:03:20,230
La segona peça és una matriu, que és
capaç d'emmagatzemar dades del tipus que

69
00:03:20,230 --> 00:03:22,190
que voleu posar en l'estructura de dades.

70
00:03:22,190 --> 00:03:24,310
Anem a mantenir-se a distància de la
vinculat llista d'elements de moment

71
00:03:24,310 --> 00:03:27,810
i acaba de començar amb els fonaments d'un
hash de taula per aconseguir el seu cap al voltant d'ella,

72
00:03:27,810 --> 00:03:30,210
i després anem a aquest bufem
la teva ment una mica quan ens

73
00:03:30,210 --> 00:03:32,920
combinar les matrius i llistes d'enllaços junts.

74
00:03:32,920 --> 00:03:35,590
>> La idea bàsica encara
és que prenem algunes dades.

75
00:03:35,590 --> 00:03:37,860
Correm que les dades a través de
la funció hash.

76
00:03:37,860 --> 00:03:41,980
I així es processen les dades
i escup un nombre, d'acord?

77
00:03:41,980 --> 00:03:44,890
I després amb aquest nombre
només emmagatzemem les dades

78
00:03:44,890 --> 00:03:48,930
volem emmagatzemar a la
array en aquesta ubicació.

79
00:03:48,930 --> 00:03:53,990
Així per exemple tenim potser
aquesta taula hash de cadenes.

80
00:03:53,990 --> 00:03:57,350
Té 10 elements en ell, així
podem encaixar 10 cordes al mateix.

81
00:03:57,350 --> 00:03:59,320
>> Diguem que volem per discutir Joan.

82
00:03:59,320 --> 00:04:02,979
Així que Joan com les dades que volem inserir
en aquesta taula hash en algun lloc.

83
00:04:02,979 --> 00:04:03,770
On el posem?

84
00:04:03,770 --> 00:04:05,728
Bé típicament amb un
gamma fins ara és probable

85
00:04:05,728 --> 00:04:07,610
ho posaria en un lloc matriu 0.

86
00:04:07,610 --> 00:04:09,960
Però ara tenim aquesta nova funció hash.

87
00:04:09,960 --> 00:04:13,180
>> I diguem que correm John
a través d'aquesta funció hash

88
00:04:13,180 --> 00:04:15,417
i es escup 4.

89
00:04:15,417 --> 00:04:17,500
Bé, això és on som
voldrà posar John.

90
00:04:17,500 --> 00:04:22,050
Volem posar a en Pep a lloc array
4, perquè si hash John nou--

91
00:04:22,050 --> 00:04:23,810
diguem més tard
voleu cercar i veure

92
00:04:23,810 --> 00:04:26,960
si John existeix en aquest hash
table-- tot el que necessitem fer

93
00:04:26,960 --> 00:04:30,310
s'executa a través de el mateix hash
funció, obtenir el número 4,

94
00:04:30,310 --> 00:04:33,929
i ser capaç de trobar John
immediatament en la nostra estructura de dades.

95
00:04:33,929 --> 00:04:34,720
Això és bastant bo.

96
00:04:34,720 --> 00:04:36,928
>> Diguem que ara fem
de nou, volem hash de Pablo.

97
00:04:36,928 --> 00:04:39,446
Volem afegir Paul
en aquesta taula hash.

98
00:04:39,446 --> 00:04:42,070
Diguem que en aquesta ocasió es corre
Paul a través de la funció hash,

99
00:04:42,070 --> 00:04:44,600
el codi hash que es genera és 6.

100
00:04:44,600 --> 00:04:47,340
Bé, ara podem posar Paul
en la ubicació matriu juny.

101
00:04:47,340 --> 00:04:50,040
I si hem de mirar cap amunt si
Paul és en aquesta taula hash,

102
00:04:50,040 --> 00:04:53,900
tot el que necessitem fer és executar Paul
a través de la funció hash de nou

103
00:04:53,900 --> 00:04:55,830
i anem a aconseguir 6 de nou.

104
00:04:55,830 --> 00:04:57,590
>> I llavors només mirem
en la localització matriu juny.

105
00:04:57,590 --> 00:04:58,910
És Paul allà?

106
00:04:58,910 --> 00:05:00,160
Si és així, està a la taula hash.

107
00:05:00,160 --> 00:05:01,875
És Pau no existeix?

108
00:05:01,875 --> 00:05:03,000
No està en la taula hash.

109
00:05:03,000 --> 00:05:05,720
És bastant senzill.

110
00:05:05,720 --> 00:05:07,770
>> Ara com es defineix una funció hash?

111
00:05:07,770 --> 00:05:11,460
Bé realment no hi ha límit a la
nombre de possibles funcions de hash.

112
00:05:11,460 --> 00:05:14,350
De fet hi ha un nombre de realitat,
realment bons a l'Internet.

113
00:05:14,350 --> 00:05:17,560
Hi ha una sèrie de realitat,
els realment dolents a l'Internet.

114
00:05:17,560 --> 00:05:21,080
També és bastant fàcil
escriure una dolenta.

115
00:05:21,080 --> 00:05:23,760
>> Llavors, què fa que una bona
funció hash, oi?

116
00:05:23,760 --> 00:05:27,280
Bé una bona funció hash ha de
utilitzen només les dades que es hash,

117
00:05:27,280 --> 00:05:29,420
i totes les dades que s'estan hash.

118
00:05:29,420 --> 00:05:32,500
Així que no volem utilitzar anything--
no incorporem res

119
00:05:32,500 --> 00:05:35,560
més a part de les dades.

120
00:05:35,560 --> 00:05:37,080
I volem utilitzar totes les dades.

121
00:05:37,080 --> 00:05:39,830
No volem utilitzar només una peça
de la mateixa, volem utilitzar tot.

122
00:05:39,830 --> 00:05:41,710
Una funció hash ha de
també ser determinista.

123
00:05:41,710 --> 00:05:42,550
Què vol dir això?

124
00:05:42,550 --> 00:05:46,200
Bé, significa que cada vegada que
passar la mateixa peça exacta de les dades

125
00:05:46,200 --> 00:05:50,040
en la funció hash sempre
obtenir el mateix codi hash a terme.

126
00:05:50,040 --> 00:05:52,870
Si pas John al
funció hash de sortir 4.

127
00:05:52,870 --> 00:05:56,110
Jo hauria de ser capaç de fer això 10000
vegades i sempre obtindrà 4.

128
00:05:56,110 --> 00:06:00,810
Així que no hi ha números aleatoris eficaçment
poden participar en el nostre picada tables--

129
00:06:00,810 --> 00:06:02,750
en les nostres funcions hash.

130
00:06:02,750 --> 00:06:05,750
>> Una funció hash ha també
distribuir uniformement dades.

131
00:06:05,750 --> 00:06:09,700
Si cada vegada que executi dades a través del
funció hash a obtenir el codi hash 0,

132
00:06:09,700 --> 00:06:11,200
que probablement no és tan gran, no?

133
00:06:11,200 --> 00:06:14,600
Vostè probablement voldrà gran
una sèrie de codis hash.

134
00:06:14,600 --> 00:06:17,190
També les coses es poden propagar
al llarg de la taula.

135
00:06:17,190 --> 00:06:23,210
I també seria genial si realment
dades similars, com John i Jonathan,

136
00:06:23,210 --> 00:06:26,320
potser es van estendre a sospesar
diferents ubicacions a la taula hash.

137
00:06:26,320 --> 00:06:28,750
Això seria un bon avantatge.

138
00:06:28,750 --> 00:06:31,250
>> Heus aquí un exemple d'una funció hash.

139
00:06:31,250 --> 00:06:33,150
Vaig escriure aquest un abans.

140
00:06:33,150 --> 00:06:35,047
No és un particular
bona funció hash

141
00:06:35,047 --> 00:06:37,380
per raons que realment no
suportar entrar en aquest moment.

142
00:06:37,380 --> 00:06:41,040
Però, ¿veus el que està passant aquí?

143
00:06:41,040 --> 00:06:44,420
Sembla com que estem declarant una variable
anomenada suma i s'estableix igual a 0.

144
00:06:44,420 --> 00:06:50,010
I després aparentment estic fent alguna cosa
sempre que strstr [j] no és igual

145
00:06:50,010 --> 00:06:52,490
a 0 barra invertida.

146
00:06:52,490 --> 00:06:54,870
Què estic fent allà?

147
00:06:54,870 --> 00:06:57,440
>> Això és bàsicament només un altre
forma d'implementar [? STRL?]

148
00:06:57,440 --> 00:06:59,773
i detectar quan has
arribat al final de la cadena.

149
00:06:59,773 --> 00:07:02,480
Així que no tinc que realment
calcular la longitud de la cadena,

150
00:07:02,480 --> 00:07:05,640
Només estic fent servir quan pols el
barra invertida 0 caràcters sé

151
00:07:05,640 --> 00:07:07,185
He arribat al final de la cadena.

152
00:07:07,185 --> 00:07:09,560
I llavors jo seguiré
iteració a través d'aquesta cadena,

153
00:07:09,560 --> 00:07:15,310
afegint strstr [j] per resumir, i després a la
final del dia va a tornar suma mod

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

155
00:07:16,200 --> 00:07:18,700
>> Bàsicament tot aquest hash
funció està fent és sumar

156
00:07:18,700 --> 00:07:23,450
tots els valors ASCII de
la meva corda, i llavors és

157
00:07:23,450 --> 00:07:26,390
tornar algun codi hash
MODDED per HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
És probablement la mida
de la meva sèrie, no?

159
00:07:29,790 --> 00:07:33,160
No vull estar rebent de hash
codis si el meu arsenal és de grandària 10,

160
00:07:33,160 --> 00:07:35,712
Jo no vull ser aconseguir
codis hash fora 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, no puc posar les coses en
aquests llocs de la matriu,

162
00:07:38,690 --> 00:07:39,790
això seria il·legal.

163
00:07:39,790 --> 00:07:42,130
Jo pateixo un error de segmentació.

164
00:07:42,130 --> 00:07:45,230
>> Ara aquí és una altra ràpida a un costat.

165
00:07:45,230 --> 00:07:48,470
En general, vostè està probablement no va a
vol escriure les seves pròpies funcions hash.

166
00:07:48,470 --> 00:07:50,997
En realitat, és una mica de
un art, no una ciència.

167
00:07:50,997 --> 00:07:52,580
I hi ha molt que va en ells.

168
00:07:52,580 --> 00:07:55,288
L'Internet, com he dit, és plena
de molt bones funcions hash,

169
00:07:55,288 --> 00:07:58,470
i vostè ha d'utilitzar l'Internet per
trobar funcions hash perquè és realment

170
00:07:58,470 --> 00:08:03,230
només una mica d'una innecessària
pèrdua de temps per crear el seu propi.

171
00:08:03,230 --> 00:08:05,490
>> Vostè pot escriure els simples
per a propòsits de prova.

172
00:08:05,490 --> 00:08:08,323
Però quan realment es va a
iniciar hashing de dades i el seu emmagatzematge

173
00:08:08,323 --> 00:08:10,780
en una taula hash estàs
probablement voldrà

174
00:08:10,780 --> 00:08:14,580
utilitzar alguna funció que s'ha generat
per a vostè, el que hi ha a Internet.

175
00:08:14,580 --> 00:08:17,240
Si només vos
per citar les seves fonts.

176
00:08:17,240 --> 00:08:21,740
No hi ha raó per
plagiar res aquí.

177
00:08:21,740 --> 00:08:25,370
>> La comunitat de la informàtica és
sens dubte creixent, i realment els valors

178
00:08:25,370 --> 00:08:28,796
de codi obert, i és molt important
per citar les seves fonts perquè la gent

179
00:08:28,796 --> 00:08:30,670
pot obtenir l'atribució de
el treball que estan

180
00:08:30,670 --> 00:08:32,312
fent en benefici de la comunitat.

181
00:08:32,312 --> 00:08:34,020
Així que sempre sure--
i no només per haixix

182
00:08:34,020 --> 00:08:37,270
funcions, però generalment quan
utilitzar el codi d'una font externa,

183
00:08:37,270 --> 00:08:38,299
sempre citar la seva font.

184
00:08:38,299 --> 00:08:43,500
Donar crèdit a la persona que ho va fer
alguns dels treballs de manera que no han de.

185
00:08:43,500 --> 00:08:46,720
>> OK, així que anem a revisar aquest
taula hash per a un segon.

186
00:08:46,720 --> 00:08:48,780
Aquí és on ens vam anar
després inserim

187
00:08:48,780 --> 00:08:53,300
John i Paul en aquesta taula hash.

188
00:08:53,300 --> 00:08:55,180
¿Veu vostè algun problema?

189
00:08:55,180 --> 00:08:58,410
És possible que vegi dues.

190
00:08:58,410 --> 00:09:02,240
Però, en particular, oi
veure a aquest possible problema?

191
00:09:02,240 --> 00:09:06,770
>> Què faig si hash Ringo, i
Resulta que després de processar

192
00:09:06,770 --> 00:09:14,000
que les dades a través de la funció hash
Ringo també ha generat el codi hash juny.

193
00:09:14,000 --> 00:09:16,810
Ja tinc les dades a
ubicació matriu hashcode-- juny.

194
00:09:16,810 --> 00:09:22,000
Així que probablement va a ser una mica
d'un problema per a mi, no?

195
00:09:22,000 --> 00:09:23,060
>> D'això en diem una col·lisió.

196
00:09:23,060 --> 00:09:26,460
I la col·lisió es produeix quan dues
peces de dades passen pel mateix hash

197
00:09:26,460 --> 00:09:29,200
funció va donar el mateix codi hash.

198
00:09:29,200 --> 00:09:32,850
És de suposar que encara volem aconseguir tant
peces de dades en la taula hash,

199
00:09:32,850 --> 00:09:36,330
en cas contrari no estaríem corrent Ringo
arbitràriament a través de la funció hash.

200
00:09:36,330 --> 00:09:40,870
Presumiblement Volem arribar
Ringo en aquesta matriu.

201
00:09:40,870 --> 00:09:46,070
>> Com ho fem però, si
i Paul tant el rendiment codi hash juny?

202
00:09:46,070 --> 00:09:49,520
No volem sobreescriure Pau,
volem Pau a ser-hi també.

203
00:09:49,520 --> 00:09:52,790
Així que hem de trobar una manera d'aconseguir
elements en la taula hash que

204
00:09:52,790 --> 00:09:56,550
encara conserva la nostra ràpida
inserció i ràpida mirada cap amunt.

205
00:09:56,550 --> 00:10:01,350
I una manera de tractar amb ell és
fer una cosa anomenada sondeig lineal.

206
00:10:01,350 --> 00:10:04,170
>> Usant aquest mètode si tenim una
col·lisió, bé, ¿què fem?

207
00:10:04,170 --> 00:10:08,580
Bé, no el podem posar a la localització matriu
6, o el que sigui codi hash es va generar,

208
00:10:08,580 --> 00:10:10,820
anem a posar-lo en codi hash més 1.

209
00:10:10,820 --> 00:10:13,670
I si això és let està ple
el va posar en codi hash més 2.

210
00:10:13,670 --> 00:10:17,420
El benefici d'aquest ésser, si ell és
no exactament on creiem que ell és,

211
00:10:17,420 --> 00:10:20,850
i hem de començar a buscar,
potser no hem d'anar molt lluny.

212
00:10:20,850 --> 00:10:23,900
Potser no hem de buscar
tots els n elements de la taula hash.

213
00:10:23,900 --> 00:10:25,790
Potser hem de buscar
un parell d'ells.

214
00:10:25,790 --> 00:10:30,680
>> I així seguim tendint cap
aquest cas mitjana és de prop d'1 vs

215
00:10:30,680 --> 00:10:34,280
a prop de n, de manera que potser això funcionarà.

216
00:10:34,280 --> 00:10:38,010
Així que anem a veure com això
podria funcionar en la realitat.

217
00:10:38,010 --> 00:10:41,460
I veurem si tal vegada puguem detectar
el problema que pugui passar aquí.

218
00:10:41,460 --> 00:10:42,540
>> Diguem que hash Bart.

219
00:10:42,540 --> 00:10:45,581
Així que ara anem a córrer un nou conjunt
de cadenes a través de la funció hash,

220
00:10:45,581 --> 00:10:48,460
i correm Bart mitjançant el hash
funció, obtenim codi hash juny.

221
00:10:48,460 --> 00:10:52,100
Fem una ullada, veiem 6 és
buit, perquè puguem posar Bart allà.

222
00:10:52,100 --> 00:10:55,410
>> Ara HASH Lisa i que
també genera codi hash juny.

223
00:10:55,410 --> 00:10:58,330
Bé, ara que estem utilitzant aquest
lineal mètode comencem a les 6 de sondeig,

224
00:10:58,330 --> 00:10:59,330
veiem que 6 és completa.

225
00:10:59,330 --> 00:11:00,990
No podem posar Lisa en 6.

226
00:11:00,990 --> 00:11:02,090
Llavors, on anem?

227
00:11:02,090 --> 00:11:03,280
Anem a 7.

228
00:11:03,280 --> 00:11:04,610
7 de buit, així que funciona.

229
00:11:04,610 --> 00:11:06,510
Així que posarem Lisa allà.

230
00:11:06,510 --> 00:11:10,200
>> Ara HASH Homer i obtenim 7.

231
00:11:10,200 --> 00:11:13,380
OK, així que sabem que el 7 de plena
Ara, el que no podem posar Homer allà.

232
00:11:13,380 --> 00:11:14,850
Així que anirem a 8.

233
00:11:14,850 --> 00:11:15,664
És agost disponibles?

234
00:11:15,664 --> 00:11:18,330
Sí, i de 8 prop de 7, així que si
hem de començar a buscar som

235
00:11:18,330 --> 00:11:20,020
No va a haver d'anar massa lluny.

236
00:11:20,020 --> 00:11:22,860
I així anem a posar Homer a les 8.

237
00:11:22,860 --> 00:11:25,151
>> Ara HASH Maggie i
retorna 3, gràcies a Déu

238
00:11:25,151 --> 00:11:26,650
som capaços de simplement posar Maggie allà.

239
00:11:26,650 --> 00:11:29,070
No hem de fer cap
espècie de sondeig per això.

240
00:11:29,070 --> 00:11:32,000
Ara HASH Marge, i
Marge també retorna juny.

241
00:11:32,000 --> 00:11:39,560
>> Bé 6 és completa, 7 és completa, 8 és completa,
9, gràcies bé Déu, 9 està buida.

242
00:11:39,560 --> 00:11:41,600
Puc posar Marge a les 9.

243
00:11:41,600 --> 00:11:45,280
Ja podem veure que estem començant
tenir aquest problema pel qual ara estem

244
00:11:45,280 --> 00:11:48,780
començant a estirar coses tipus
de lluny dels seus codis hash.

245
00:11:48,780 --> 00:11:52,960
I això theta d'1, aquesta mitjana
cas de ser constant de temps,

246
00:11:52,960 --> 00:11:56,560
està començant a aconseguir una mica més--
començant a cuidar una mica més

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

248
00:11:58,050 --> 00:12:01,270
Estem començant a perdre aquest
avantatge de taules hash.

249
00:12:01,270 --> 00:12:03,902
>> Aquest problema que acabem de veure
és una cosa que es diu l'agrupació.

250
00:12:03,902 --> 00:12:06,360
I el que és realment malament per
agrupació és que una vegada que ara

251
00:12:06,360 --> 00:12:09,606
tenir dos elements que estan costat a
costat que fa que sigui encara més probable,

252
00:12:09,606 --> 00:12:11,480
vostè té el doble de la
oportunitat, que et vas

253
00:12:11,480 --> 00:12:13,516
tenir una altra col·lisió
amb aquest grup,

254
00:12:13,516 --> 00:12:14,890
i el grup creixerà a un.

255
00:12:14,890 --> 00:12:19,640
I seguiràs creixent i creixent
seva probabilitat de tenir una col·lisió.

256
00:12:19,640 --> 00:12:24,470
I, finalment, és tan dolent
com no classificar les dades en absolut.

257
00:12:24,470 --> 00:12:27,590
>> L'altre problema però és que
Encara, i fins ara fins a aquest punt,

258
00:12:27,590 --> 00:12:30,336
només hem estat una mena de
comprensió del que és una taula hash,

259
00:12:30,336 --> 00:12:31,960
encara només tenim espai per a 10 cordes.

260
00:12:31,960 --> 00:12:37,030
Si volem seguir per discutir
els ciutadans de Springfield,

261
00:12:37,030 --> 00:12:38,790
només podem obtenir 10 d'ells en aquest país.

262
00:12:38,790 --> 00:12:42,619
I si ho intentem i afegim un 11 o 12,
no tenim un lloc per posar-les.

263
00:12:42,619 --> 00:12:45,660
Podríem simplement estar girant al voltant de
cercles tractant de trobar un lloc buit,

264
00:12:45,660 --> 00:12:49,000
i que potser estanquem
en un bucle infinit.

265
00:12:49,000 --> 00:12:51,810
>> Així que aquest tipus de presta a la idea
d'una cosa anomenada encadenament.

266
00:12:51,810 --> 00:12:55,790
I aquí és on anem a portar
llistes enllaçades de nou a la imatge.

267
00:12:55,790 --> 00:13:01,300
¿I si en lloc d'emmagatzemar només
les dades en si en la matriu,

268
00:13:01,300 --> 00:13:04,471
cada element de la matriu podria
mantenir múltiples peces de dades?

269
00:13:04,471 --> 00:13:05,970
Bé, això no té sentit, oi?

270
00:13:05,970 --> 00:13:09,280
Sabem que una matriu només pot
hold-- cada element d'una matriu

271
00:13:09,280 --> 00:13:12,930
només pot contenir una sola peça
de dades d'aquest tipus de dades.

272
00:13:12,930 --> 00:13:16,750
>> Però i si aquest tipus de dades
és una llista enllaçada, oi?

273
00:13:16,750 --> 00:13:19,830
¿I què si tots els
element de la matriu era

274
00:13:19,830 --> 00:13:22,790
un punter al capdavant d'una llista enllaçada?

275
00:13:22,790 --> 00:13:24,680
I llavors podríem construir
aquestes llistes enllaçades

276
00:13:24,680 --> 00:13:27,120
i créixer arbitràriament,
perquè llistes enllaçades permeten

277
00:13:27,120 --> 00:13:32,090
a créixer i encongir molt més
flexible que una matriu fa.

278
00:13:32,090 --> 00:13:34,210
¿I què si ara fem servir,
aprofitem això, oi?

279
00:13:34,210 --> 00:13:37,760
Comencem a conrear aquestes cadenes
fora d'aquests llocs de matriu.

280
00:13:37,760 --> 00:13:40,740
>> Ara podem encaixar un infinit
quantitat de dades, o no infinit,

281
00:13:40,740 --> 00:13:44,170
una quantitat arbitrària de
dades, en la nostra taula hash

282
00:13:44,170 --> 00:13:47,760
sense topar-se
el problema de la col·lisió.

283
00:13:47,760 --> 00:13:50,740
També hem eliminat
agrupament per fer això.

284
00:13:50,740 --> 00:13:54,380
I bé sabem que quan inserim
en una llista enllaçada, si recordes

285
00:13:54,380 --> 00:13:57,779
del nostre vídeo en llistes enllaçades, per separat
llistes enllaçades i llistes doblement enllaçades,

286
00:13:57,779 --> 00:13:59,070
que és una operació de temps constant.

287
00:13:59,070 --> 00:14:00,710
Estem afegint a la part davantera.

288
00:14:00,710 --> 00:14:04,400
>> I per la mirada cap amunt, així que sabem
aquesta mirada en una llista enllaçada

289
00:14:04,400 --> 00:14:05,785
pot ser un problema, oi?

290
00:14:05,785 --> 00:14:07,910
Hem de buscar a través de
de principi a fi.

291
00:14:07,910 --> 00:14:10,460
No hi ha atzar
l'accés en una llista enllaçada.

292
00:14:10,460 --> 00:14:15,610
Però si en lloc de tenir un vinculat
llista on una recerca seria O de n,

293
00:14:15,610 --> 00:14:19,590
ara tenim 10 llistes enllaçades,
o 1.000 llistes enllaçades,

294
00:14:19,590 --> 00:14:24,120
ara és el O de n dividit per 10,
o O de n dividit per 1.000.

295
00:14:24,120 --> 00:14:26,940
>> I mentre parlàvem
teòricament sobre la complexitat

296
00:14:26,940 --> 00:14:30,061
deixem de banda les constants, en la realitat
món aquestes coses realment importen,

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

298
00:14:30,560 --> 00:14:33,080
En realitat ens adonarem
que això succeeix

299
00:14:33,080 --> 00:14:36,610
per executar 10 vegades més ràpid,
o 1.000 vegades més ràpid,

300
00:14:36,610 --> 00:14:41,570
perquè estem distribuint una llarga
cadena a través de 1.000 cadenes més petites.

301
00:14:41,570 --> 00:14:45,090
I així, cada vegada que hem de buscar
a través d'una d'aquestes cadenes que puguem

302
00:14:45,090 --> 00:14:50,290
ignorar les cadenes 999 no importen
aproximadament, i simplement buscar que un.

303
00:14:50,290 --> 00:14:53,220
>> La qual cosa és de mitjana de
ser 1.000 vegades més curt.

304
00:14:53,220 --> 00:14:56,460
I pel que encara estem mena de
tendint cap a aquest cas la mitjana

305
00:14:56,460 --> 00:15:01,610
de ser constant de temps, però
només perquè estem aprofitant

306
00:15:01,610 --> 00:15:03,730
dividint per un enorme factor constant.

307
00:15:03,730 --> 00:15:05,804
Anem a veure com això podria
realment es veuen però.

308
00:15:05,804 --> 00:15:08,720
Així que aquesta era la taula hash que teníem
abans que declarem una taula hash que

309
00:15:08,720 --> 00:15:10,270
era capaç d'emmagatzemar 10 cordes.

310
00:15:10,270 --> 00:15:11,728
No farem això.

311
00:15:11,728 --> 00:15:13,880
Ja sabem que el
limitacions d'aquest mètode.

312
00:15:13,880 --> 00:15:20,170
Ara la nostra taula hash serà
un conjunt de 10 nodes, punters

313
00:15:20,170 --> 00:15:22,120
als caps de les llistes enllaçades.

314
00:15:22,120 --> 00:15:23,830
>> I en aquest moment és nul.

315
00:15:23,830 --> 00:15:26,170
Cada un d'aquests 10 indicadors és nul.

316
00:15:26,170 --> 00:15:29,870
No hi ha res en la nostra
hash de taula ara mateix.

317
00:15:29,870 --> 00:15:32,690
>> Ara anem a començar a posar una mica de
les coses en aquesta taula hash.

318
00:15:32,690 --> 00:15:35,440
I veurem com aquest mètode és
ens va a beneficiar una mica.

319
00:15:35,440 --> 00:15:36,760
Ara anem a hash Joey.

320
00:15:36,760 --> 00:15:40,210
Anem a executar la cadena de Joey a través
una funció hash i tornem juny.

321
00:15:40,210 --> 00:15:41,200
Bé, què fem ara?

322
00:15:41,200 --> 00:15:44,090
>> Bé, ara es treballa amb llistes enllaçades,
no estem treballant amb matrius.

323
00:15:44,090 --> 00:15:45,881
I quan estem treballant
amb llistes enllaçades que

324
00:15:45,881 --> 00:15:49,790
Sabem que hem de començar de forma dinàmica
assignar cadenes d'espai i de construcció.

325
00:15:49,790 --> 00:15:54,020
Això és una mena de com-- aquests són el nucli
elements de la construcció d'una llista enllaçada.

326
00:15:54,020 --> 00:15:57,670
Així que anem a dinàmicament
assignar espai per Joey,

327
00:15:57,670 --> 00:16:00,390
i després anem a afegir-lo a la cadena.

328
00:16:00,390 --> 00:16:03,170
>> Així que ara mira el que hem fet.

329
00:16:03,170 --> 00:16:06,440
Quan hash Joey ens van donar el codi hash juny.

330
00:16:06,440 --> 00:16:11,790
Ara el punter en la ubicació matriu juny
apunta al cap d'una llista enllaçada,

331
00:16:11,790 --> 00:16:14,900
i en aquest moment és l'única
element d'una llista enllaçada.

332
00:16:14,900 --> 00:16:18,350
I el node en aquest
llista enllaçada és Joey.

333
00:16:18,350 --> 00:16:22,300
>> Així que si hem de mirar cap amunt Joey
després, vam acabar hash Joey de nou,

334
00:16:22,300 --> 00:16:26,300
obtenim 6 altra vegada perquè la nostra
funció hash és determinista.

335
00:16:26,300 --> 00:16:30,400
I llavors vam començar al capdavant
de la llista enllaçada assenyalat

336
00:16:30,400 --> 00:16:33,360
que per ubicació array
6, i podem iterar

337
00:16:33,360 --> 00:16:35,650
a través d'aquesta tractant de trobar Joey.

338
00:16:35,650 --> 00:16:37,780
I si construïm la nostra
hash de taula amb eficàcia,

339
00:16:37,780 --> 00:16:41,790
i la nostra funció hash amb eficàcia
per distribuir bé les dades,

340
00:16:41,790 --> 00:16:45,770
de mitjana cada un dels vinculats
llistes en cada ubicació de matriu

341
00:16:45,770 --> 00:16:50,110
serà 1/10 de la mida de si
només tenia com una sola gran

342
00:16:50,110 --> 00:16:51,650
llista enllaçada amb tot el seu contingut.

343
00:16:51,650 --> 00:16:55,670
>> Si distribuïm aquest enorme vinculats
llista en 10 llistes enllaçades

344
00:16:55,670 --> 00:16:57,760
cada llista serà un dècim de la mida.

345
00:16:57,760 --> 00:17:01,432
I per tant 10 vegades més ràpida
per buscar a través d '.

346
00:17:01,432 --> 00:17:02,390
Així que anem a fer això una altra vegada.

347
00:17:02,390 --> 00:17:04,290
Ara anem a hash de Ross.

348
00:17:04,290 --> 00:17:07,540
>> I diguem Ross, quan ho fem
el codi hash tornem és 2.

349
00:17:07,540 --> 00:17:10,630
Bé, ara ens dinàmicament assignem un
nou node, posem Ross en aquest node,

350
00:17:10,630 --> 00:17:14,900
i diem ara ubicació array
2, en lloc d'assenyalar a null,

351
00:17:14,900 --> 00:17:18,579
apunta al cap d'un lligat
llista l'únic node és Ross.

352
00:17:18,579 --> 00:17:22,660
I podem fer això un cop més, ens
pot hash de Rachel i obtenir codi hash 4.

353
00:17:22,660 --> 00:17:25,490
malloc un nou node, ja Raquel en
el node, i dir una ubicació array

354
00:17:25,490 --> 00:17:27,839
4 ara apunta al cap
d'una llista enllaçada la

355
00:17:27,839 --> 00:17:31,420
únic element passa a ser Rachel.

356
00:17:31,420 --> 00:17:33,470
>> Bé, però què passa si
tenim una col·lisió?

357
00:17:33,470 --> 00:17:38,560
Anem a veure com fem servir les col·lisions
utilitzant el mètode d'encadenament separat.

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

359
00:17:39,800 --> 00:17:41,094
Obtenim el codi hash juny.

360
00:17:41,094 --> 00:17:44,010
En el nostre exemple anterior estàvem
emmagatzemar les cadenes a la matriu.

361
00:17:44,010 --> 00:17:45,980
Això era un problema.

362
00:17:45,980 --> 00:17:48,444
>> No volem donar-li una pallissa
Joey, i ja hem

363
00:17:48,444 --> 00:17:51,110
vist que podem aconseguir alguna cosa d'agrupació
problemes si tractem de pas

364
00:17:51,110 --> 00:17:52,202
a través i la sonda.

365
00:17:52,202 --> 00:17:54,660
Però, i si només una mica
tractar aquest de la mateixa manera, no?

366
00:17:54,660 --> 00:17:57,440
És com l'addició d'un element
al capdavant d'una llista enllaçada.

367
00:17:57,440 --> 00:18:00,220
Anem espai just malloc per Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Direm propers punter de Phoebe
l'antic cap de la llista enllaçada,

369
00:18:04,764 --> 00:18:07,180
i després 6 simplement apunta a la
nou cap de la llista enllaçada.

370
00:18:07,180 --> 00:18:10,150
I ara mira, hem canviat en Phoebe.

371
00:18:10,150 --> 00:18:14,210
Ara podem emmagatzemar de dos
elements amb codi hash 6,

372
00:18:14,210 --> 00:18:17,170
i no tenim cap problema.

373
00:18:17,170 --> 00:18:20,147
>> Això és més o menys tot
cal encadenament.

374
00:18:20,147 --> 00:18:21,980
I encadenament és definitivament
el mètode que és

375
00:18:21,980 --> 00:18:27,390
serà més efectiu per a vostè si
està emmagatzemant dades en una taula hash.

376
00:18:27,390 --> 00:18:30,890
Però aquesta combinació de
matrius i llistes enllaçades

377
00:18:30,890 --> 00:18:36,080
entre si per formar una taula hash realment
millora dramàticament la seva capacitat

378
00:18:36,080 --> 00:18:40,550
per emmagatzemar grans quantitats de dades, i
molt ràpida i eficient buscar

379
00:18:40,550 --> 00:18:41,630
a través d'aquestes dades.

380
00:18:41,630 --> 00:18:44,150
>> Encara hi ha una més
estructura de dades per aquí

381
00:18:44,150 --> 00:18:48,700
que fins i tot podria ser una mica
millor en termes de garantir

382
00:18:48,700 --> 00:18:51,920
que la nostra inserció, eliminació i
mirar els temps són encara més ràpid.

383
00:18:51,920 --> 00:18:55,630
I veurem que en un vídeo en intents.

384
00:18:55,630 --> 00:18:58,930
Sóc Doug Lloyd, això és CS50.

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