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

2
00:00:00,500 --> 00:00:01,900
[Música tocando]

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

4
00:00:05,710 --> 00:00:09,150
>> Doug LLOYD: Ata agora
sabe moito sobre arrays,

5
00:00:09,150 --> 00:00:11,610
e vostede sabe moito sobre listas ligadas.

6
00:00:11,610 --> 00:00:13,650
E nós discutir a
pros e contras, temos

7
00:00:13,650 --> 00:00:16,620
discutido que ligaba listas
pode estar máis grande e pequena,

8
00:00:16,620 --> 00:00:18,630
pero elas ocupan máis tamaño.

9
00:00:18,630 --> 00:00:22,359
Arrays son moito máis simple de
usar, pero son restritivos, na medida en

10
00:00:22,359 --> 00:00:24,900
como temos que axustar o tamaño da
o array no inicio

11
00:00:24,900 --> 00:00:26,910
e entón nós está preso con el.

12
00:00:26,910 --> 00:00:30,470
>> Pero iso é, temos practicamente
esgotado todos os nosos temas

13
00:00:30,470 --> 00:00:33,040
sobre listas ligadas e matrices.

14
00:00:33,040 --> 00:00:34,950
Ou non é?

15
00:00:34,950 --> 00:00:37,720
Quizais poidamos facer algo
aínda máis creativo.

16
00:00:37,720 --> 00:00:40,950
E este tipo de presta
a idea dunha táboa hash.

17
00:00:40,950 --> 00:00:46,680
>> Así, nunha táboa hash imos tratar
combinar unha matriz cunha lista ligada.

18
00:00:46,680 --> 00:00:49,520
Nós imos ter as vantaxes
da matriz, como a de acceso aleatorio,

19
00:00:49,520 --> 00:00:53,510
poder simplemente ir a matriz
elemento 4 ou matriz elemento 8

20
00:00:53,510 --> 00:00:55,560
sen ter que interactuar transversalmente.

21
00:00:55,560 --> 00:00:57,260
Iso é moi rápido, non?

22
00:00:57,260 --> 00:01:00,714
>> Pero tamén queremos ter os nosos datos
estrutura capaz de aumentar e diminuír.

23
00:01:00,714 --> 00:01:02,630
Non necesitamos, non
pretende ser restrinxida.

24
00:01:02,630 --> 00:01:04,588
E nós queremos ser capaces
para engadir e eliminar as cousas

25
00:01:04,588 --> 00:01:08,430
moi facilmente, o que se recorda,
é moi complexo, cunha matriz.

26
00:01:08,430 --> 00:01:11,650
E podemos chamar iso de
cousa nova unha táboa hash.

27
00:01:11,650 --> 00:01:15,190
>> E, se aplicada correctamente,
estamos especie de tomar

28
00:01:15,190 --> 00:01:18,150
as vantaxes de ambos os datos
estruturas que xa viu,

29
00:01:18,150 --> 00:01:19,880
matrices e listas ligadas.

30
00:01:19,880 --> 00:01:23,070
A inserción pode comezar a
tenden a teta dunha.

31
00:01:23,070 --> 00:01:26,207
Theta non temos realmente discutido,
pero é só o caso teta media,

32
00:01:26,207 --> 00:01:27,540
o que realmente vai ocorrer.

33
00:01:27,540 --> 00:01:29,680
Vostede non sempre vai
ten o peor escenario,

34
00:01:29,680 --> 00:01:32,555
e non está indo sempre ter
o mellor escenario, entón o que é

35
00:01:32,555 --> 00:01:33,900
o escenario de media?

36
00:01:33,900 --> 00:01:36,500
>> Ben unha inserción media
nunha táboa hash

37
00:01:36,500 --> 00:01:39,370
Pode comezar a chegar preto de tempo constante.

38
00:01:39,370 --> 00:01:41,570
E eliminación pode obter
pechar co tempo constante.

39
00:01:41,570 --> 00:01:44,440
E busca pode obter
pechar co tempo constante.

40
00:01:44,440 --> 00:01:48,600
That's-- non temos un conxunto de datos
estrutura aínda que pode facelo,

41
00:01:48,600 --> 00:01:51,180
e por iso este xa soa
como unha cousa moi grande.

42
00:01:51,180 --> 00:01:57,010
Nós realmente mitigados o
desvantaxes de cada un pola súa conta.

43
00:01:57,010 --> 00:01:59,160
>> Para obter este rendemento
actualizar, pero, temos

44
00:01:59,160 --> 00:02:03,580
Necesitamos repensar como podemos engadir
de datos na estrutura.

45
00:02:03,580 --> 00:02:07,380
Especialmente queremos que o
datos en si para dicir

46
00:02:07,380 --> 00:02:09,725
onde debe ir na estrutura.

47
00:02:09,725 --> 00:02:12,850
E se nós entón necesitamos ver se está en
a estrutura, se necesitamos atopalo,

48
00:02:12,850 --> 00:02:16,610
queremos ollar os datos
de novo e ser capaz de efectivamente,

49
00:02:16,610 --> 00:02:18,910
usando os datos, acceder a ela de forma aleatoria.

50
00:02:18,910 --> 00:02:20,700
Basta ollar para o
datos que deben ter

51
00:02:20,700 --> 00:02:25,890
unha idea de onde exactamente estamos
Vai atopalo na táboa de hash.

52
00:02:25,890 --> 00:02:28,770
>> Agora, a desvantaxe dun hash
mesa é que son realmente

53
00:02:28,770 --> 00:02:31,770
moi malo en comprar ou ordenar datos.

54
00:02:31,770 --> 00:02:34,970
E, de feito, se comezar
para usalos para ordenar ou clasificar

55
00:02:34,970 --> 00:02:37,990
datos perde toda a
vantaxes anteriormente

56
00:02:37,990 --> 00:02:40,710
tivo en termos de inserción e exclusión.

57
00:02:40,710 --> 00:02:44,060
O tempo pasa a ser máis preto
theta n, e nós temos, basicamente,

58
00:02:44,060 --> 00:02:45,530
comezou a desaparecer nunha lista ligada.

59
00:02:45,530 --> 00:02:48,850
E así nós só quere usar de hash
táboas se non se preocupan

60
00:02:48,850 --> 00:02:51,490
se os datos son ordenados.

61
00:02:51,490 --> 00:02:54,290
Ao contexto en que
vai usalos en CS50

62
00:02:54,290 --> 00:02:58,900
probablemente non me importa
que os datos son clasificados.

63
00:02:58,900 --> 00:03:03,170
>> Así, unha táboa hash é unha combinación
de dúas pezas distintas

64
00:03:03,170 --> 00:03:04,980
coa que estamos familiarizados.

65
00:03:04,980 --> 00:03:07,930
A primeira é unha función, que
que adoitamos chamar unha función hash.

66
00:03:07,930 --> 00:03:11,760
E esa función hash vai
voltar algún número enteiro non negativo, que

67
00:03:11,760 --> 00:03:14,870
que adoitamos chamar dun hashcode, OK?

68
00:03:14,870 --> 00:03:20,230
A segunda peza é unha matriz, que é
capaz de almacenar datos do tipo que

69
00:03:20,230 --> 00:03:22,190
pretende poñer na estrutura de datos.

70
00:03:22,190 --> 00:03:24,310
Nós imos adiar o
ligada elemento da lista para agora

71
00:03:24,310 --> 00:03:27,810
e só comezar co básico dun
hash de táboa para obter a súa cabeza en torno a el,

72
00:03:27,810 --> 00:03:30,210
e despois imos quizais explotar
súa mente un pouco cando

73
00:03:30,210 --> 00:03:32,920
combinar matrices e listas de enlaces xuntos.

74
00:03:32,920 --> 00:03:35,590
>> A idea básica aínda
é tomamos uns datos.

75
00:03:35,590 --> 00:03:37,860
Corremos que os datos a través de
a función hash.

76
00:03:37,860 --> 00:03:41,980
E así os datos son procesados
e el cospe un número, OK?

77
00:03:41,980 --> 00:03:44,890
E, a continuación, co número
nós só almacenar os datos

78
00:03:44,890 --> 00:03:48,930
queremos almacenar na
matriz nese local.

79
00:03:48,930 --> 00:03:53,990
Así, por exemplo, temos quizais
esta táboa hash de cordas.

80
00:03:53,990 --> 00:03:57,350
Ten 10 elementos en que, de xeito
podemos encaixar 10 cordas nel.

81
00:03:57,350 --> 00:03:59,320
>> Imos dicir que queremos botar John.

82
00:03:59,320 --> 00:04:02,979
Entón John como os datos que desexa inserir
para esta táboa de hash en algún lugar.

83
00:04:02,979 --> 00:04:03,770
Onde é que imos poñelas?

84
00:04:03,770 --> 00:04:05,728
Ben tipicamente cun
matriz, ata agora, probablemente

85
00:04:05,728 --> 00:04:07,610
ía poñelo en orde de localización 0.

86
00:04:07,610 --> 00:04:09,960
Pero agora temos esta nova función hash.

87
00:04:09,960 --> 00:04:13,180
>> E imos dicir que corremos John
a través desta función hash

88
00:04:13,180 --> 00:04:15,417
e é cospe 4.

89
00:04:15,417 --> 00:04:17,500
Ben, iso é onde estamos
vai querer poñer John.

90
00:04:17,500 --> 00:04:22,050
Queremos poñer Xoán no lugar da matriz
4 porque se nós botar John novamente--

91
00:04:22,050 --> 00:04:23,810
digamos que logo nós
quere buscar e ver

92
00:04:23,810 --> 00:04:26,960
John se existe neste haxix
mesa-- todo o que necesitamos facer

93
00:04:26,960 --> 00:04:30,310
é executa-lo a través do mesmo hash
función, conseguir o número 4,

94
00:04:30,310 --> 00:04:33,929
e ser capaz de atopar John
inmediatamente na nosa estrutura de datos.

95
00:04:33,929 --> 00:04:34,720
Iso é moi bo.

96
00:04:34,720 --> 00:04:36,928
>> Imos dicir que nós agora facelo
de novo, queremos botar Paul.

97
00:04:36,928 --> 00:04:39,446
Queremos engadir Paul
para esta táboa hash.

98
00:04:39,446 --> 00:04:42,070
Imos dicir que, esta vez, corremos
Paul través da función hash,

99
00:04:42,070 --> 00:04:44,600
o hashcode que se xera é 6.

100
00:04:44,600 --> 00:04:47,340
Ben, agora podemos poñer Paul
no lugar da matriz 6.

101
00:04:47,340 --> 00:04:50,040
E se necesitamos a ollar para arriba se
Paul está nesta táboa hash,

102
00:04:50,040 --> 00:04:53,900
todo o que necesitamos facer é executar Paul
a través da función hash novo

103
00:04:53,900 --> 00:04:55,830
e nós estamos indo a chegar en 6º de novo.

104
00:04:55,830 --> 00:04:57,590
>> E entón nós só ollar
no lugar da matriz 6.

105
00:04:57,590 --> 00:04:58,910
Paul é alí?

106
00:04:58,910 --> 00:05:00,160
Se é así, está na táboa hash.

107
00:05:00,160 --> 00:05:01,875
Paul non é alí?

108
00:05:01,875 --> 00:05:03,000
Non está na táboa hash.

109
00:05:03,000 --> 00:05:05,720
É moi sinxelo.

110
00:05:05,720 --> 00:05:07,770
>> Agora, como define unha función hash?

111
00:05:07,770 --> 00:05:11,460
Ben, non hai realmente ningún límite para o
número de posibles funcións hash.

112
00:05:11,460 --> 00:05:14,350
En realidade hai un número de verdade,
realmente bos en internet.

113
00:05:14,350 --> 00:05:17,560
Hai un número de verdade,
realmente malas en internet.

114
00:05:17,560 --> 00:05:21,080
Tamén é moi fácil
para escribir un mal.

115
00:05:21,080 --> 00:05:23,760
>> Entón, o que fai un bo
función hash, non?

116
00:05:23,760 --> 00:05:27,280
Ben unha boa función hash debe
usar só os datos que están sendo hash,

117
00:05:27,280 --> 00:05:29,420
e todos os datos a ser hash.

118
00:05:29,420 --> 00:05:32,500
Entón, nós non quere empregar anything--
non incorporar algo

119
00:05:32,500 --> 00:05:35,560
outra cousa que non sexa os datos.

120
00:05:35,560 --> 00:05:37,080
E queremos usar todos os datos.

121
00:05:37,080 --> 00:05:39,830
Non queremos usar só unha peza
diso, queremos utilizar todo isto.

122
00:05:39,830 --> 00:05:41,710
A función hash debe
tamén ser determinista.

123
00:05:41,710 --> 00:05:42,550
Que significa iso?

124
00:05:42,550 --> 00:05:46,200
Ben, iso significa que cada vez que
pasar a mesma peza exacta de datos

125
00:05:46,200 --> 00:05:50,040
para a función hash sempre
obter o mesmo hashcode para fóra.

126
00:05:50,040 --> 00:05:52,870
Se eu pasar ao John
función hash saio 4.

127
00:05:52,870 --> 00:05:56,110
Eu debería ser capaz de facelo 10.000
veces e sempre terá 4.

128
00:05:56,110 --> 00:06:00,810
Así, non números aleatorios de forma eficaz
pode ser parte de noso hash de tables--

129
00:06:00,810 --> 00:06:02,750
nas nosas funcións hash.

130
00:06:02,750 --> 00:06:05,750
>> A función hash debe
uniformemente distribuír datos.

131
00:06:05,750 --> 00:06:09,700
Cada vez que realizar datos a través do
función hash que obteña o hashcode 0,

132
00:06:09,700 --> 00:06:11,200
que probablemente non é tan grande, non?

133
00:06:11,200 --> 00:06:14,600
Probablemente vai querer gran
unha variedade de códigos de hash.

134
00:06:14,600 --> 00:06:17,190
Tamén cousas poden estenderse
ao longo do cadro.

135
00:06:17,190 --> 00:06:23,210
E tamén sería óptimo se realmente
datos semellantes, como John e Jonathan,

136
00:06:23,210 --> 00:06:26,320
quizais foron espallados para pesar
sitios diferentes na táboa de hash.

137
00:06:26,320 --> 00:06:28,750
Isto sería unha boa vantaxe.

138
00:06:28,750 --> 00:06:31,250
>> Aquí está un exemplo dunha función hash.

139
00:06:31,250 --> 00:06:33,150
Escribín este antes.

140
00:06:33,150 --> 00:06:35,047
Non é un particularmente
boa función hash

141
00:06:35,047 --> 00:06:37,380
por motivos que non o fan realmente
Oso que vai agora.

142
00:06:37,380 --> 00:06:41,040
Pero ve o que está pasando aquí?

143
00:06:41,040 --> 00:06:44,420
Parece que estamos declarando unha variable
chamado de suma e define-la igual a 0.

144
00:06:44,420 --> 00:06:50,010
E entón, ao parecer, eu estou facendo algo
sempre que strstr [j] non é igual

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

146
00:06:52,490 --> 00:06:54,870
O que estou facendo alí?

147
00:06:54,870 --> 00:06:57,440
>> Este é basicamente só outro
forma de aplicar [? strl?]

148
00:06:57,440 --> 00:06:59,773
e detectar cando ten
chegou ao fin da cadea.

149
00:06:59,773 --> 00:07:02,480
Entón, eu non teño que, en realidade,
calcular a lonxitude da corda,

150
00:07:02,480 --> 00:07:05,640
Eu só estou usando cando bati o
barra invertida 0 personaxe que sei

151
00:07:05,640 --> 00:07:07,185
Cheguei ao final da cadea.

152
00:07:07,185 --> 00:07:09,560
E entón eu vou seguir
iteración través desa cadea,

153
00:07:09,560 --> 00:07:15,310
engadindo strstr [j] a suma, e, a continuación, no
final do día volverá suma mod

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

155
00:07:16,200 --> 00:07:18,700
>> Basicamente todo isto de hash
función está facendo é sumando

156
00:07:18,700 --> 00:07:23,450
todos os valores de ASCII
miña corda, e entón é

157
00:07:23,450 --> 00:07:26,390
volver algún hashcode
modded por HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
É probabelmente o tamaño
da miña matriz, non?

159
00:07:29,790 --> 00:07:33,160
Non quero estar quedando de hash
códigos se miña matriz é de tamaño 10,

160
00:07:33,160 --> 00:07:35,712
Eu non quero ser como chegar
códigos de hash para fóra 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, eu non podo poñer as cousas en
eses locais da matriz,

162
00:07:38,690 --> 00:07:39,790
que sería ilegal.

163
00:07:39,790 --> 00:07:42,130
Eu sufrir un fallo de segmento.

164
00:07:42,130 --> 00:07:45,230
>> Agora, aquí é outra rápida de lado.

165
00:07:45,230 --> 00:07:48,470
Xeralmente probablemente non vai
quere escribir as súas propias funcións hash.

166
00:07:48,470 --> 00:07:50,997
É realmente un pouco de
unha arte, non unha ciencia.

167
00:07:50,997 --> 00:07:52,580
E hai moito que para eles.

168
00:07:52,580 --> 00:07:55,288
A internet, como dixen, está cheo
realmente bos funcións hash,

169
00:07:55,288 --> 00:07:58,470
e ten que usar internet para
atopar funcións hash porque é realmente

170
00:07:58,470 --> 00:08:03,230
só unha especie de un innecesario
perda de tempo para crear o seu propio.

171
00:08:03,230 --> 00:08:05,490
>> Podes escribir máis simple
para fins de proba.

172
00:08:05,490 --> 00:08:08,323
Pero cando realmente está indo
iniciar hash datos e almacena-lo

173
00:08:08,323 --> 00:08:10,780
nunha táboa hash que é
probablemente vai querer

174
00:08:10,780 --> 00:08:14,580
utilizar algunhas das funcións que foi xerado
para ti, que hai en internet.

175
00:08:14,580 --> 00:08:17,240
Se só non esqueza
por citar as súas fontes.

176
00:08:17,240 --> 00:08:21,740
Non hai ningunha razón para
plagiar calquera cousa aquí.

177
00:08:21,740 --> 00:08:25,370
>> A comunidade de ciencia da computación é
definitivamente crecendo, e realmente valores

178
00:08:25,370 --> 00:08:28,796
código aberto, e é realmente importante
por citar as súas fontes para que a xente

179
00:08:28,796 --> 00:08:30,670
Pode obter a concesión
o traballo que están

180
00:08:30,670 --> 00:08:32,312
facendo para o beneficio da comunidade.

181
00:08:32,312 --> 00:08:34,020
Polo tanto, sexa sempre sure--
e non só para haxix

182
00:08:34,020 --> 00:08:37,270
funcións, pero normalmente cando
usar o código dunha fonte externa,

183
00:08:37,270 --> 00:08:38,299
sempre citar a súa fonte.

184
00:08:38,299 --> 00:08:43,500
Dea crédito para a persoa que fixo
parte do traballo para que non precisa.

185
00:08:43,500 --> 00:08:46,720
>> OK, entón imos voltar a esta
táboa hash para un segundo.

186
00:08:46,720 --> 00:08:48,780
Este é o lugar onde paramos
off despois inserimos

187
00:08:48,780 --> 00:08:53,300
John e Paul para esta táboa hash.

188
00:08:53,300 --> 00:08:55,180
Ve un problema aquí?

189
00:08:55,180 --> 00:08:58,410
Podes ver dous.

190
00:08:58,410 --> 00:09:02,240
Pero, en particular, facer
vexa este posible problema?

191
00:09:02,240 --> 00:09:06,770
>> E se eu botar Ringo, e
Acontece que despois do procesamento

192
00:09:06,770 --> 00:09:14,000
que os datos a través da función hash
Ringo tamén xerou o hashcode 6.

193
00:09:14,000 --> 00:09:16,810
Eu xa teño os datos no
hashcode-- localización matriz 6.

194
00:09:16,810 --> 00:09:22,000
Por iso, probablemente vai ser un pouco
dun problema para min agora, non?

195
00:09:22,000 --> 00:09:23,060
>> Chamamos iso dunha colisión.

196
00:09:23,060 --> 00:09:26,460
E a colisión ocorre cando dous
anacos de datos percorren o mesmo hash

197
00:09:26,460 --> 00:09:29,200
función de producir o mesmo código hash.

198
00:09:29,200 --> 00:09:32,850
Presuntamente, aínda queremos obter tanto
anacos de datos para a táboa hash,

199
00:09:32,850 --> 00:09:36,330
se non, non estaría correndo Ringo
arbitrariamente a través da función hash.

200
00:09:36,330 --> 00:09:40,870
Nós presuntamente quere obter
Ringo para esa matriz.

201
00:09:40,870 --> 00:09:46,070
>> Como podemos facelo, pero, se
e Paul ambos rendemento hashcode 6?

202
00:09:46,070 --> 00:09:49,520
Non queremos substituír Paul,
queremos Paul estar alí tamén.

203
00:09:49,520 --> 00:09:52,790
Por iso, necesitamos atopar unha forma de obter
elementos para a táboa hash que

204
00:09:52,790 --> 00:09:56,550
aínda preserva a nosa rápida
inserción e rápido ollar para arriba.

205
00:09:56,550 --> 00:10:01,350
E un xeito de tratar con isto é para
facer algo chamado lineal enquisa.

206
00:10:01,350 --> 00:10:04,170
>> Usando este método, se temos un
colisión, así, o que imos facer?

207
00:10:04,170 --> 00:10:08,580
Ben, non podemos poñelas no lugar da matriz
6, ou o que quere hashcode foi xerado,

208
00:10:08,580 --> 00:10:10,820
imos poñelas hashcode máis 1.

209
00:10:10,820 --> 00:10:13,670
E se isto é deixar de chea
poñelas hashcode máis 2.

210
00:10:13,670 --> 00:10:17,420
O propósito de este ser se é
non exactamente onde pensamos que é,

211
00:10:17,420 --> 00:10:20,850
e temos que comezar a buscar,
quizais a xente non ten que ir lonxe de máis.

212
00:10:20,850 --> 00:10:23,900
Quizais a xente non ten que buscar
todos os elementos n da táboa hash.

213
00:10:23,900 --> 00:10:25,790
Quizais a xente ten que buscar
un par deles.

214
00:10:25,790 --> 00:10:30,680
>> E así nós aínda estamos tendendo para
Nese caso, media de preto de 1 vs

215
00:10:30,680 --> 00:10:34,280
preto de n, quizais por iso que vou traballar.

216
00:10:34,280 --> 00:10:38,010
Entón, imos ver como iso
pode exercitar-se realidade.

217
00:10:38,010 --> 00:10:41,460
E imos ver se é posible poidamos detectar
o problema que poida ocorrer aquí.

218
00:10:41,460 --> 00:10:42,540
>> Imos dicir que o hash Bart.

219
00:10:42,540 --> 00:10:45,581
Entón, agora imos facer un novo conxunto
de cordas a través da función hash,

220
00:10:45,581 --> 00:10:48,460
e corremos Bart través do hash
función, temos hashcode 6.

221
00:10:48,460 --> 00:10:52,100
Imos dar un ollo, vemos 6 é
baleiro, para que poidamos poñer Bart alí.

222
00:10:52,100 --> 00:10:55,410
>> Agora imos botar Lisa e que
tamén xera hashcode 6.

223
00:10:55,410 --> 00:10:58,330
Ben, agora que estamos a usar esta
método que comezan en 6 lineal enquisa,

224
00:10:58,330 --> 00:10:59,330
vemos que 6 está cheo.

225
00:10:59,330 --> 00:11:00,990
Non podemos poñer en 6 Lisa.

226
00:11:00,990 --> 00:11:02,090
Entón, a onde imos?

227
00:11:02,090 --> 00:11:03,280
Imos para 7.

228
00:11:03,280 --> 00:11:04,610
7 de baleiro, de xeito que funciona.

229
00:11:04,610 --> 00:11:06,510
Entón, imos poñer Lisa alí.

230
00:11:06,510 --> 00:11:10,200
>> Agora imos botar a Homer e temos 7.

231
00:11:10,200 --> 00:11:13,380
OK así sabemos que 7 do total
agora, polo que non podemos poñer Homer alí.

232
00:11:13,380 --> 00:11:14,850
Entón imos a 8.

233
00:11:14,850 --> 00:11:15,664
É 8 está dispoñible?

234
00:11:15,664 --> 00:11:18,330
Si, e 8 de preto de 7, polo que se
temos que comezar a buscar estamos

235
00:11:18,330 --> 00:11:20,020
non terá que ir lonxe de máis.

236
00:11:20,020 --> 00:11:22,860
E así imos poñer Homer ás 8.

237
00:11:22,860 --> 00:11:25,151
>> Agora imos botar para Maggie e
volve 3, grazas a Deus

238
00:11:25,151 --> 00:11:26,650
somos capaces de simplemente poñer Maggie alí.

239
00:11:26,650 --> 00:11:29,070
Non temos que facer calquera
tipo de enquisa para iso.

240
00:11:29,070 --> 00:11:32,000
Agora imos botar Marge, e
Marge tamén retorna 6.

241
00:11:32,000 --> 00:11:39,560
>> Ben 6 está cheo, 7 é completa, 8 está cheo,
9, todo ben grazas a Deus, 9 está baleiro.

242
00:11:39,560 --> 00:11:41,600
Podo poñer Marge, ás 9.

243
00:11:41,600 --> 00:11:45,280
Xa podemos ver que estamos comezando
para ter este problema en que agora estamos

244
00:11:45,280 --> 00:11:48,780
comezando a estirar cousas tipo
de lonxe dos seus códigos de hash.

245
00:11:48,780 --> 00:11:52,960
E esa teta de 1, esa media
caso de ser de tempo constante,

246
00:11:52,960 --> 00:11:56,560
está empezando a ser un pouco more--
comezando a tendencia algo máis

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

248
00:11:58,050 --> 00:12:01,270
Estamos empezando a perder esa
vantaxe de táboas de hash.

249
00:12:01,270 --> 00:12:03,902
>> Este problema que acabamos de ver
é algo chamado de agrupación.

250
00:12:03,902 --> 00:12:06,360
E o que é realmente malo sobre
agrupación é que unha vez que agora

251
00:12:06,360 --> 00:12:09,606
ten dous elementos que están xunto a
outro tórnase aínda máis probable,

252
00:12:09,606 --> 00:12:11,480
ten o dobre da
oportunidade, que vai

253
00:12:11,480 --> 00:12:13,516
para ter outra colisión
con ese cluster,

254
00:12:13,516 --> 00:12:14,890
eo cluster crecerá a un.

255
00:12:14,890 --> 00:12:19,640
E vai seguir crecendo e crecendo
a probabilidade de ter unha colisión.

256
00:12:19,640 --> 00:12:24,470
E, finalmente, el é tan malo
como non a clasificación dos datos de todo.

257
00:12:24,470 --> 00:12:27,590
>> O outro problema, con todo, é que
Aínda así, ata o momento e, ata este punto,

258
00:12:27,590 --> 00:12:30,336
fomos só unha especie de
comprender o que é unha táboa hash,

259
00:12:30,336 --> 00:12:31,960
aínda só ten espazo para 10 cordas.

260
00:12:31,960 --> 00:12:37,030
Se queremos continuar hash
os cidadáns de Springfield,

261
00:12:37,030 --> 00:12:38,790
só podemos obter 10 deles alí.

262
00:12:38,790 --> 00:12:42,619
E se nós intentamos e engade un 11º ou 12º,
non temos un lugar para poñelos.

263
00:12:42,619 --> 00:12:45,660
Nós só podería ser xirando en torno a
círculos tentando atopar un lugar baleiro,

264
00:12:45,660 --> 00:12:49,000
e nós quizais queda preso
en un loop infinito.

265
00:12:49,000 --> 00:12:51,810
>> Polo tanto, este tipo de presta ao idea
de algo chamado fío.

266
00:12:51,810 --> 00:12:55,790
E este é o lugar onde nós estamos indo a traer
listas ligadas ao a imaxe.

267
00:12:55,790 --> 00:13:01,300
E se en vez de almacenar só
os datos en si na matriz,

268
00:13:01,300 --> 00:13:04,471
cada elemento da matriz podería
realizar múltiples pezas de datos?

269
00:13:04,471 --> 00:13:05,970
Ben, iso non ten sentido, non?

270
00:13:05,970 --> 00:13:09,280
Sabemos que unha matriz só pode
hold-- cada elemento dunha matriz

271
00:13:09,280 --> 00:13:12,930
só pode conter unha peza
de datos deste tipo de datos.

272
00:13:12,930 --> 00:13:16,750
>> Pero e se este tipo de datos
é unha lista ligada, non?

273
00:13:16,750 --> 00:13:19,830
Entón, o que cada
elemento da matriz foi

274
00:13:19,830 --> 00:13:22,790
un punteiro para a cabeza dunha lista vinculada?

275
00:13:22,790 --> 00:13:24,680
E entón poderíamos construír
esas listas ligadas

276
00:13:24,680 --> 00:13:27,120
e cultiva-las arbitrariamente,
porque listas ligadas permitir

277
00:13:27,120 --> 00:13:32,090
nos a medrar e encoller máis
flexibilidade que unha matriz fai.

278
00:13:32,090 --> 00:13:34,210
Entón, o que se usan agora,
aproveitamos iso, non?

279
00:13:34,210 --> 00:13:37,760
Comezamos a medrar estas cadeas
fóra deses lugares matriz.

280
00:13:37,760 --> 00:13:40,740
>> Agora podemos encaixar un infinito
cantidade de datos, ou non é infinito,

281
00:13:40,740 --> 00:13:44,170
unha cantidade arbitraria de
datos, na nosa táboa hash

282
00:13:44,170 --> 00:13:47,760
sen nunca correr en
o problema da colisión.

283
00:13:47,760 --> 00:13:50,740
Tamén eliminamos
agrupación, facendo iso.

284
00:13:50,740 --> 00:13:54,380
E ben sabemos que cando inserimos
nunha lista ligada, se recorda

285
00:13:54,380 --> 00:13:57,779
do noso vídeo sobre listas ligadas, illadamente
listas ligadas e listas dobremente vinculadas,

286
00:13:57,779 --> 00:13:59,070
é unha operación de tempo constante.

287
00:13:59,070 --> 00:14:00,710
Estamos só engadindo á fronte.

288
00:14:00,710 --> 00:14:04,400
>> E para ollar para arriba, ben sabemos
que mirar para arriba nunha lista encadeada

289
00:14:04,400 --> 00:14:05,785
pode ser un problema, non?

290
00:14:05,785 --> 00:14:07,910
Temos que buscar
Lo do comezo ao fin.

291
00:14:07,910 --> 00:14:10,460
Non hai ningunha chou
acceso a unha lista vinculada.

292
00:14:10,460 --> 00:14:15,610
Pero, en vez de ter un conectado
lista onde unha procura sería O n,

293
00:14:15,610 --> 00:14:19,590
agora temos 10 listas ligadas,
ou 1.000 listas ligadas,

294
00:14:19,590 --> 00:14:24,120
agora é o de n dividido por 10,
ou O n dividido por 1,000.

295
00:14:24,120 --> 00:14:26,940
>> E mentres nós estabamos falando
teoricamente sobre a complexidade

296
00:14:26,940 --> 00:14:30,061
desconsiderarmos constantes, no real
mundo estas cousas realmente importa,

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

298
00:14:30,560 --> 00:14:33,080
Nós, en realidade, vai notar
que isto ocorre

299
00:14:33,080 --> 00:14:36,610
para realizar 10 veces máis rápido,
ou 1.000 veces máis rápida,

300
00:14:36,610 --> 00:14:41,570
porque estamos distribuíndo unha longa
cadea en toda 1.000 cadeas menores.

301
00:14:41,570 --> 00:14:45,090
E así cada vez que ten que buscar
mediante unha desas cadeas que podemos

302
00:14:45,090 --> 00:14:50,290
ignorar as 999 cadeas de nós non nos importa
aproximadamente, e pode buscar aquel.

303
00:14:50,290 --> 00:14:53,220
>> Que é, en media,
ser 1000 veces máis curto.

304
00:14:53,220 --> 00:14:56,460
E así aínda son unha especie de
tendendo a este caso medio

305
00:14:56,460 --> 00:15:01,610
de ser de tempo constante, pero
só porque estamos panca

306
00:15:01,610 --> 00:15:03,730
dividindo-se por un enorme factor constante.

307
00:15:03,730 --> 00:15:05,804
Imos ver como iso pode
realmente ollar aínda.

308
00:15:05,804 --> 00:15:08,720
Polo tanto, esta foi a táboa hash tivemos
antes de que declarou unha táboa hash que

309
00:15:08,720 --> 00:15:10,270
era capaz de almacenar 10 cordas.

310
00:15:10,270 --> 00:15:11,728
Non imos máis facelo.

311
00:15:11,728 --> 00:15:13,880
Xa sabemos o
limitacións deste método.

312
00:15:13,880 --> 00:15:20,170
Agora a nosa táboa de hash será
unha matriz de 10 nós, punteiros

313
00:15:20,170 --> 00:15:22,120
aos xefes de listas ligadas.

314
00:15:22,120 --> 00:15:23,830
>> E agora é nulo.

315
00:15:23,830 --> 00:15:26,170
Cada un destes 10 punteiros é nulo.

316
00:15:26,170 --> 00:15:29,870
Non hai nada na nosa
hash de táboa agora.

317
00:15:29,870 --> 00:15:32,690
>> Agora imos comezar a poñer algúns
cousas para esta táboa hash.

318
00:15:32,690 --> 00:15:35,440
E imos ver como este método é
vai beneficiar un pouco.

319
00:15:35,440 --> 00:15:36,760
Imos agora botar Joey.

320
00:15:36,760 --> 00:15:40,210
Imos executará a secuencia de Joey través
unha función hash e volvemos 6.

321
00:15:40,210 --> 00:15:41,200
Ben, o que facemos agora?

322
00:15:41,200 --> 00:15:44,090
>> Ben, agora a traballar con listas ligadas,
non estamos a traballar con arrays.

323
00:15:44,090 --> 00:15:45,881
E cando estamos a traballar
con listas ligadas nós

324
00:15:45,881 --> 00:15:49,790
sabemos que necesitamos para comezar dinamicamente
distribución de espazo e construción de cadeas.

325
00:15:49,790 --> 00:15:54,020
Isto é unha especie de how-- aqueles son o núcleo
elementos de construción dunha lista ligada.

326
00:15:54,020 --> 00:15:57,670
Entón, imos dinamicamente
reservar espazo para Joey,

327
00:15:57,670 --> 00:16:00,390
e, a continuación, imos engadir lo á cadea.

328
00:16:00,390 --> 00:16:03,170
>> Entón agora mira o que fixemos.

329
00:16:03,170 --> 00:16:06,440
Cando o hash Joey temos o hashcode 6.

330
00:16:06,440 --> 00:16:11,790
Agora o punteiro no lugar da matriz 6
apunta a cabeza dunha lista ligada,

331
00:16:11,790 --> 00:16:14,900
e agora é o único
elemento dunha lista ligada.

332
00:16:14,900 --> 00:16:18,350
E en que o nodo
lista ligada é Joey.

333
00:16:18,350 --> 00:16:22,300
>> Entón, se necesitamos a ollar para arriba Joey
despois, nós só o hash Joey de novo,

334
00:16:22,300 --> 00:16:26,300
temos 6 de novo porque a nosa
función hash é determinista.

335
00:16:26,300 --> 00:16:30,400
E entón comezamos na cabeza
da lista ligada apuntou

336
00:16:30,400 --> 00:16:33,360
a matriz por localización
6, e podemos facer unha iteración

337
00:16:33,360 --> 00:16:35,650
do outro lado que tentar atopar Joey.

338
00:16:35,650 --> 00:16:37,780
E se nós construírmos noso
Táboa de Hash de forma eficaz,

339
00:16:37,780 --> 00:16:41,790
ea nosa función hash de forma eficaz
para distribuír datos ben,

340
00:16:41,790 --> 00:16:45,770
en media, cada un dos os ligados
listas en cada lugar da matriz

341
00:16:45,770 --> 00:16:50,110
será de 1/10 do tamaño de
só tiña el como un único gran

342
00:16:50,110 --> 00:16:51,650
lista ligada con todo na mesma.

343
00:16:51,650 --> 00:16:55,670
>> Distribuir este enorme conectado
lista en 10 listas ligadas

344
00:16:55,670 --> 00:16:57,760
cada lista será de 1/10 do tamaño.

345
00:16:57,760 --> 00:17:01,432
E, polo tanto, 10 veces máis rápido
buscar.

346
00:17:01,432 --> 00:17:02,390
Entón imos facelo de novo.

347
00:17:02,390 --> 00:17:04,290
Imos agora botar Ross.

348
00:17:04,290 --> 00:17:07,540
>> E digamos que Ross, cando facemos iso
o código de hash volvemos é 2.

349
00:17:07,540 --> 00:17:10,630
Ben, agora imos reservar dinamicamente un
novo nodo, poñemos Ross nese no,

350
00:17:10,630 --> 00:17:14,900
e dicimos agora local da matriz
2, no canto de ligar a null,

351
00:17:14,900 --> 00:17:18,579
apunta a cabeza dun conectado
lista cuxo único nodo é Ross.

352
00:17:18,579 --> 00:17:22,660
E podemos facer iso unha vez máis, nós
pode botar para Rachel e obter hashcode 4.

353
00:17:22,660 --> 00:17:25,490
malloc un novo nodo, coloque Rachel
o no, e dicir un lugar matriz

354
00:17:25,490 --> 00:17:27,839
4 agora apunta á cabeza
dunha lista ligada cuxo

355
00:17:27,839 --> 00:17:31,420
único elemento pasa a ser Rachel.

356
00:17:31,420 --> 00:17:33,470
>> OK, pero o que ocorre se
temos unha colisión?

357
00:17:33,470 --> 00:17:38,560
Imos ver como lidamos con colisións
mediante a entrada de fío separado.

358
00:17:38,560 --> 00:17:39,800
Imos botar Phoebe.

359
00:17:39,800 --> 00:17:41,094
Estivemos coa hashcode 6.

360
00:17:41,094 --> 00:17:44,010
No noso exemplo anterior estabamos só
almacenar as cordas na matriz.

361
00:17:44,010 --> 00:17:45,980
Este foi un problema.

362
00:17:45,980 --> 00:17:48,444
>> Non debe sobreescribir
Joey, e nós xa

363
00:17:48,444 --> 00:17:51,110
visto que podemos obter un agrupamento
problemas se nós intentamos e paso

364
00:17:51,110 --> 00:17:52,202
e mediante sonda.

365
00:17:52,202 --> 00:17:54,660
Pero e se nós só unha especie de
tratar isto do mesmo xeito, non?

366
00:17:54,660 --> 00:17:57,440
É como engadir un elemento
á cabeza dunha lista ligada.

367
00:17:57,440 --> 00:18:00,220
Imos espazo só malloc para Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Digamos próximos punteiro puntos Phoebe
ao antigo xefe da lista ligada,

369
00:18:04,764 --> 00:18:07,180
e, a continuación, só 6 apunta á
novo xefe da lista ligada.

370
00:18:07,180 --> 00:18:10,150
E agora mira, nós cambiamos Phoebe in.

371
00:18:10,150 --> 00:18:14,210
Agora podemos almacenar dous
elementos con hashcode 6,

372
00:18:14,210 --> 00:18:17,170
e non temos ningún problema.

373
00:18:17,170 --> 00:18:20,147
>> Iso é moi fermoso todo
existe ao fío.

374
00:18:20,147 --> 00:18:21,980
E fío é sempre
o método que é

375
00:18:21,980 --> 00:18:27,390
vai ser máis eficaz para se
está almacenando datos nunha táboa hash.

376
00:18:27,390 --> 00:18:30,890
Pero esta combinación de
matrices e listas ligadas

377
00:18:30,890 --> 00:18:36,080
en conxunto para formar unha táboa hash realmente
mellora notablemente a súa capacidade

378
00:18:36,080 --> 00:18:40,550
para almacenar grandes cantidades de datos, e
moi rapidamente e eficiente buscar

379
00:18:40,550 --> 00:18:41,630
por medio de que os datos.

380
00:18:41,630 --> 00:18:44,150
>> Aínda hai unha
estrutura de datos por aí

381
00:18:44,150 --> 00:18:48,700
que pode ata ser un pouco
mellor en termos de garantía

382
00:18:48,700 --> 00:18:51,920
que a nosa inserción, exclusión e
mirar para arriba as horas son aínda máis rápido.

383
00:18:51,920 --> 00:18:55,630
E nós imos ver que nun vídeo no intentos.

384
00:18:55,630 --> 00:18:58,930
Eu son Doug Lloyd, este é CS50.

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