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

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

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

4
00:00:05,710 --> 00:00:09,150
>> DOUG LLOYD: A estas alturas ya
saber mucho acerca de las matrices,

5
00:00:09,150 --> 00:00:11,610
y usted sabe mucho sobre listas enlazadas.

6
00:00:11,610 --> 00:00:13,650
Y hemos discutir la
pros y contras, hemos

7
00:00:13,650 --> 00:00:16,620
discutido que unía las listas
puede conseguir más grande y más pequeño,

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

9
00:00:18,630 --> 00:00:22,359
Las matrices son mucho más fáciles de
utilizan, pero son restrictivos en la medida

10
00:00:22,359 --> 00:00:24,900
ya que tenemos que ajustar el tamaño de
la matriz desde el principio

11
00:00:24,900 --> 00:00:26,910
y después nos pegan con ella.

12
00:00:26,910 --> 00:00:30,470
>> Pero eso es, tenemos más o menos
agotado todos nuestros temas

13
00:00:30,470 --> 00:00:33,040
sobre listas enlazadas y matrices.

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

15
00:00:34,950 --> 00:00:37,720
Tal vez podamos hacer algo
aún más creativo.

16
00:00:37,720 --> 00:00:40,950
Y ese tipo de presta
la idea de una tabla hash.

17
00:00:40,950 --> 00:00:46,680
>> Así que en una tabla hash que vamos a tratar
combinar una matriz con una lista enlazada.

18
00:00:46,680 --> 00:00:49,520
Vamos a tomar las ventajas
de la matriz, como de acceso aleatorio,

19
00:00:49,520 --> 00:00:53,510
ser capaz de ir a la matriz
elemento 4 o matriz elemento 8

20
00:00:53,510 --> 00:00:55,560
sin tener que recorrer a través.

21
00:00:55,560 --> 00:00:57,260
Eso es bastante rápido, ¿verdad?

22
00:00:57,260 --> 00:01:00,714
>> Pero también queremos tener nuestros datos
estructura de poder crecer y encogerse.

23
00:01:00,714 --> 00:01:02,630
No necesitamos, no lo hacemos
quieren ser restringido.

24
00:01:02,630 --> 00:01:04,588
Y nosotros queremos ser capaces
para agregar y quitar cosas

25
00:01:04,588 --> 00:01:08,430
muy fácilmente, lo que si usted recuerda,
es muy complejo con una matriz.

26
00:01:08,430 --> 00:01:11,650
Y podemos llamar a esto
Lo nuevo una tabla hash.

27
00:01:11,650 --> 00:01:15,190
>> Y si se aplica correctamente,
estamos especie de tomar

28
00:01:15,190 --> 00:01:18,150
las ventajas de ambos datos
estructuras que ya has visto,

29
00:01:18,150 --> 00:01:19,880
matrices y listas enlazadas.

30
00:01:19,880 --> 00:01:23,070
La inserción puede empezar a
tender hacia theta de 1.

31
00:01:23,070 --> 00:01:26,207
Theta no hemos discutido realmente,
pero theta es sólo el caso promedio,

32
00:01:26,207 --> 00:01:27,540
lo que en realidad va a suceder.

33
00:01:27,540 --> 00:01:29,680
No siempre vas a
tener el peor de los casos,

34
00:01:29,680 --> 00:01:32,555
y no siempre vas a tener
el mejor de los casos, así que cuál es

35
00:01:32,555 --> 00:01:33,900
el escenario promedio?

36
00:01:33,900 --> 00:01:36,500
>> Bueno una inserción media
en una tabla hash

37
00:01:36,500 --> 00:01:39,370
puede empezar a acercarse a la constante de tiempo.

38
00:01:39,370 --> 00:01:41,570
Y eliminación puede conseguir
cerca de constante de tiempo.

39
00:01:41,570 --> 00:01:44,440
Y las operaciones de búsqueda puede obtener
cerca de constante de tiempo.

40
00:01:44,440 --> 00:01:48,600
Eso es-- no tenemos un dato
estructura hasta ahora de que puede hacer eso,

41
00:01:48,600 --> 00:01:51,180
por lo que este ya suena
como un muy gran cosa.

42
00:01:51,180 --> 00:01:57,010
Realmente hemos mitigado los
desventajas de cada uno por su cuenta.

43
00:01:57,010 --> 00:01:59,160
>> Para obtener este rendimiento
actualizar sin embargo, nos

44
00:01:59,160 --> 00:02:03,580
necesidad de repensar cómo añadimos
los datos en la estructura.

45
00:02:03,580 --> 00:02:07,380
Específicamente queremos que el
sí los datos que nos diga

46
00:02:07,380 --> 00:02:09,725
donde debe ir en la estructura.

47
00:02:09,725 --> 00:02:12,850
Y si luego tenemos que ver si está en
la estructura, si tenemos que encontrarlo,

48
00:02:12,850 --> 00:02:16,610
queremos mirar los datos
de nuevo y ser capaz de eficacia,

49
00:02:16,610 --> 00:02:18,910
utilizando los datos, acceder aleatoriamente ella.

50
00:02:18,910 --> 00:02:20,700
Sólo mirando a la
datos que debemos tener

51
00:02:20,700 --> 00:02:25,890
una idea de dónde exactamente estamos
ir a encontrarlo en la tabla hash.

52
00:02:25,890 --> 00:02:28,770
>> Ahora la desventaja de un hash
mesa es que son realmente

53
00:02:28,770 --> 00:02:31,770
bastante mal en ordenar o clasificar los datos.

54
00:02:31,770 --> 00:02:34,970
Y de hecho, si se inicia
utilizarlos para pedir u ordenar

55
00:02:34,970 --> 00:02:37,990
los datos se pierde toda la
ventajas previamente

56
00:02:37,990 --> 00:02:40,710
tenido en términos de inserción y eliminación.

57
00:02:40,710 --> 00:02:44,060
El tiempo se convierte en más cerca de
theta de n, y hemos básicamente

58
00:02:44,060 --> 00:02:45,530
retrocedido en una lista enlazada.

59
00:02:45,530 --> 00:02:48,850
Y por lo que sólo queremos utilizar de hash
tablas si no importan

60
00:02:48,850 --> 00:02:51,490
si los datos se ordena.

61
00:02:51,490 --> 00:02:54,290
Para el contexto en el cual
que vamos a usar en CS50

62
00:02:54,290 --> 00:02:58,900
es probable que no importa
que los datos se clasifican.

63
00:02:58,900 --> 00:03:03,170
>> Así que una tabla hash es una combinación
de dos piezas distintas

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

65
00:03:04,980 --> 00:03:07,930
La primera es una función, la cual
que se suele llamar una función hash.

66
00:03:07,930 --> 00:03:11,760
Y esa función hash va a
volver algún entero no negativo, que

67
00:03:11,760 --> 00:03:14,870
que se suele llamar un código hash, OK?

68
00:03:14,870 --> 00:03:20,230
La segunda pieza es una matriz, que es
capaz de almacenar datos del tipo que

69
00:03:20,230 --> 00:03:22,190
que desee colocar en la estructura de datos.

70
00:03:22,190 --> 00:03:24,310
Vamos a mantenerse a distancia de la
vinculado lista de elementos por el momento

71
00:03:24,310 --> 00:03:27,810
y acaba de comenzar con los fundamentos de un
hash de mesa para conseguir su cabeza alrededor de ella,

72
00:03:27,810 --> 00:03:30,210
y luego vamos a tal soplamos
tu mente un poco cuando nos

73
00:03:30,210 --> 00:03:32,920
combinar las matrices y listas de enlaces juntos.

74
00:03:32,920 --> 00:03:35,590
>> La idea básica aunque
es que tomamos algunos datos.

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

76
00:03:37,860 --> 00:03:41,980
Y así se procesan los datos
y escupe un número, ¿de acuerdo?

77
00:03:41,980 --> 00:03:44,890
Y luego con ese número
sólo almacenamos los datos

78
00:03:44,890 --> 00:03:48,930
queremos almacenar en la
array en esa ubicación.

79
00:03:48,930 --> 00:03:53,990
Así por ejemplo tenemos quizá
esta tabla hash de cadenas.

80
00:03:53,990 --> 00:03:57,350
Tiene 10 elementos en él, así
podemos encajar 10 cuerdas en el mismo.

81
00:03:57,350 --> 00:03:59,320
>> Digamos que queremos para discutir Juan.

82
00:03:59,320 --> 00:04:02,979
Así que Juan como los datos que queremos insertar
en esta tabla hash en alguna parte.

83
00:04:02,979 --> 00:04:03,770
¿Dónde lo ponemos?

84
00:04:03,770 --> 00:04:05,728
Bien típicamente con un
gama hasta ahora es probable

85
00:04:05,728 --> 00:04:07,610
lo pondría en un lugar matriz 0.

86
00:04:07,610 --> 00:04:09,960
Pero ahora tenemos esta nueva función hash.

87
00:04:09,960 --> 00:04:13,180
>> Y digamos que corremos John
a través de esta función hash

88
00:04:13,180 --> 00:04:15,417
y se escupe 4.

89
00:04:15,417 --> 00:04:17,500
Bueno, eso es donde estamos
va a querer poner John.

90
00:04:17,500 --> 00:04:22,050
Queremos poner a Juan en lugar array
4, porque si hash John nuevo--

91
00:04:22,050 --> 00:04:23,810
digamos más tarde
desee buscar y ver

92
00:04:23,810 --> 00:04:26,960
si John existe en este hash
table-- todo lo que necesitamos hacer

93
00:04:26,960 --> 00:04:30,310
se ejecuta a través de el mismo hash
función, obtener el número 4,

94
00:04:30,310 --> 00:04:33,929
y ser capaz de encontrar John
inmediatamente en nuestra estructura de datos.

95
00:04:33,929 --> 00:04:34,720
Eso es bastante bueno.

96
00:04:34,720 --> 00:04:36,928
>> Digamos que ahora hacemos
de nuevo, queremos hash de Pablo.

97
00:04:36,928 --> 00:04:39,446
Queremos añadir Paul
en esta tabla hash.

98
00:04:39,446 --> 00:04:42,070
Digamos que en esta ocasión se corre
Paul a través de la función hash,

99
00:04:42,070 --> 00:04:44,600
el código hash que se genera es 6.

100
00:04:44,600 --> 00:04:47,340
Bueno, ahora podemos poner Paul
en la ubicación matriz 6.

101
00:04:47,340 --> 00:04:50,040
Y si tenemos que mirar hacia arriba si
Paul es en esta tabla hash,

102
00:04:50,040 --> 00:04:53,900
todo lo que necesitamos hacer es ejecutar Paul
a través de la función hash de nuevo

103
00:04:53,900 --> 00:04:55,830
y vamos a conseguir 6 de nuevo.

104
00:04:55,830 --> 00:04:57,590
>> Y entonces sólo miramos
en la localización matriz 6.

105
00:04:57,590 --> 00:04:58,910
¿Es Paul allí?

106
00:04:58,910 --> 00:05:00,160
Si es así, está en la tabla hash.

107
00:05:00,160 --> 00:05:01,875
Es Pablo no existe?

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

109
00:05:03,000 --> 00:05:05,720
Es bastante sencillo.

110
00:05:05,720 --> 00:05:07,770
>> Ahora ¿cómo se define una función hash?

111
00:05:07,770 --> 00:05:11,460
Bueno realmente no hay límite a la
número de posibles funciones de hash.

112
00:05:11,460 --> 00:05:14,350
De hecho hay un número de realidad,
realmente buenos en el Internet.

113
00:05:14,350 --> 00:05:17,560
Hay una serie de realidad,
los realmente malos en el Internet.

114
00:05:17,560 --> 00:05:21,080
También es bastante fácil
escribir una mala.

115
00:05:21,080 --> 00:05:23,760
>> Entonces, ¿qué hace que una buena
función hash, ¿verdad?

116
00:05:23,760 --> 00:05:27,280
Bueno una buena función hash debe
utilizan sólo los datos que se hash,

117
00:05:27,280 --> 00:05:29,420
y todos los datos que se están hash.

118
00:05:29,420 --> 00:05:32,500
Así que no queremos utilizar anything--
no incorporamos nada

119
00:05:32,500 --> 00:05:35,560
más aparte de los datos.

120
00:05:35,560 --> 00:05:37,080
Y queremos utilizar todos los datos.

121
00:05:37,080 --> 00:05:39,830
No queremos utilizar sólo una pieza
de la misma, queremos utilizar todo.

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

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

124
00:05:42,550 --> 00:05:46,200
Bueno, significa que cada vez que
pasar la misma pieza exacta de los datos

125
00:05:46,200 --> 00:05:50,040
en la función hash siempre
obtener el mismo código hash a cabo.

126
00:05:50,040 --> 00:05:52,870
Si paso John en el
función hash que salir 4.

127
00:05:52,870 --> 00:05:56,110
Yo debería ser capaz de hacer eso 10000
veces y siempre obtendrá 4.

128
00:05:56,110 --> 00:06:00,810
Así que no hay números aleatorios eficazmente
pueden participar en nuestro picadillo tables--

129
00:06:00,810 --> 00:06:02,750
en nuestras funciones hash.

130
00:06:02,750 --> 00:06:05,750
>> Una función hash debe también
distribuir uniformemente datos.

131
00:06:05,750 --> 00:06:09,700
Si cada vez que ejecute datos a través del
función hash a obtener el código hash 0,

132
00:06:09,700 --> 00:06:11,200
que probablemente no es tan grande, ¿no?

133
00:06:11,200 --> 00:06:14,600
Usted probablemente querrá grande
una serie de códigos hash.

134
00:06:14,600 --> 00:06:17,190
También las cosas se pueden propagar
a lo largo de la mesa.

135
00:06:17,190 --> 00:06:23,210
Y también sería genial si realmente
datos similares, como John y Jonathan,

136
00:06:23,210 --> 00:06:26,320
tal vez se extendieron a sopesar
diferentes ubicaciones en la tabla hash.

137
00:06:26,320 --> 00:06:28,750
Eso sería una buena ventaja.

138
00:06:28,750 --> 00:06:31,250
>> He aquí un ejemplo de una función hash.

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

140
00:06:33,150 --> 00:06:35,047
No es un particular
buena función hash

141
00:06:35,047 --> 00:06:37,380
por razones que realmente no
soportar entrar en este momento.

142
00:06:37,380 --> 00:06:41,040
Pero, ¿ves lo que está pasando aquí?

143
00:06:41,040 --> 00:06:44,420
Parece como que estamos declarando una variable
llamada suma y se establece igual a 0.

144
00:06:44,420 --> 00:06:50,010
Y luego aparentemente estoy haciendo algo
siempre que strstr [j] no es igual

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

146
00:06:52,490 --> 00:06:54,870
¿Qué estoy haciendo allí?

147
00:06:54,870 --> 00:06:57,440
>> Esto es básicamente sólo otro
forma de implementar [? STRL?]

148
00:06:57,440 --> 00:06:59,773
y detectar cuando has
alcanzado el final de la cadena.

149
00:06:59,773 --> 00:07:02,480
Así que no tengo que realmente
calcular la longitud de la cadena,

150
00:07:02,480 --> 00:07:05,640
Sólo estoy usando cuando pulso el
barra invertida 0 caracteres sé

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

152
00:07:07,185 --> 00:07:09,560
Y entonces yo voy a seguir
iteración a través de esa cadena,

153
00:07:09,560 --> 00:07:15,310
añadiendo strstr [j] para resumir, y luego en la
final del día va a regresar suma mod

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

155
00:07:16,200 --> 00:07:18,700
>> Básicamente todo este hash
función está haciendo es sumar

156
00:07:18,700 --> 00:07:23,450
todos los valores ASCII de
mi cuerda, y entonces es

157
00:07:23,450 --> 00:07:26,390
regresar algún código hash
modded por HASH_MAX.

158
00:07:26,390 --> 00:07:29,790
Es probablemente el tamaño
de mi serie, ¿no?

159
00:07:29,790 --> 00:07:33,160
No quiero estar recibiendo de hash
códigos si mi arsenal es de tamaño 10,

160
00:07:33,160 --> 00:07:35,712
Yo no quiero ser conseguir
códigos hash fuera 11, 12,

161
00:07:35,712 --> 00:07:38,690
13, no puedo poner las cosas en
esos lugares de la matriz,

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

163
00:07:39,790 --> 00:07:42,130
Yo sufro un fallo de segmentación.

164
00:07:42,130 --> 00:07:45,230
>> Ahora aquí es otra rápida a un lado.

165
00:07:45,230 --> 00:07:48,470
En general, usted está probablemente no va a
quiere escribir sus propias funciones hash.

166
00:07:48,470 --> 00:07:50,997
En realidad, es un poco de
un arte, no una ciencia.

167
00:07:50,997 --> 00:07:52,580
Y hay mucho que va en ellos.

168
00:07:52,580 --> 00:07:55,288
El Internet, como he dicho, está llena
de muy buenas funciones hash,

169
00:07:55,288 --> 00:07:58,470
y usted debe utilizar el Internet para
encontrar funciones hash porque es realmente

170
00:07:58,470 --> 00:08:03,230
sólo un poco de una innecesaria
pérdida de tiempo para crear el suyo propio.

171
00:08:03,230 --> 00:08:05,490
>> Usted puede escribir los simples
para propósitos de prueba.

172
00:08:05,490 --> 00:08:08,323
Pero cuando realmente se va a
iniciar hashing de datos y su almacenamiento

173
00:08:08,323 --> 00:08:10,780
en una tabla hash estás
probablemente va a querer

174
00:08:10,780 --> 00:08:14,580
utilizar alguna función que se ha generado
para usted, lo que existe en Internet.

175
00:08:14,580 --> 00:08:17,240
Si sólo asegúrese
para citar sus fuentes.

176
00:08:17,240 --> 00:08:21,740
No hay razón para
plagiar nada aquí.

177
00:08:21,740 --> 00:08:25,370
>> La comunidad de la informática es
sin duda creciente, y realmente los valores

178
00:08:25,370 --> 00:08:28,796
de código abierto, y es muy importante
para citar sus fuentes para que la gente

179
00:08:28,796 --> 00:08:30,670
puede obtener la atribución de
el trabajo que están

180
00:08:30,670 --> 00:08:32,312
haciendo en beneficio de la comunidad.

181
00:08:32,312 --> 00:08:34,020
Así que siempre sure--
y no sólo para hachís

182
00:08:34,020 --> 00:08:37,270
funciones, pero generalmente cuando
usar el código de una fuente externa,

183
00:08:37,270 --> 00:08:38,299
siempre citar su fuente.

184
00:08:38,299 --> 00:08:43,500
Dar crédito a la persona que lo hizo
algunos de los trabajos por lo que no tienen que.

185
00:08:43,500 --> 00:08:46,720
>> OK, así que vamos a revisar este
tabla hash para un segundo.

186
00:08:46,720 --> 00:08:48,780
Aquí es donde nos fuimos
después insertamos

187
00:08:48,780 --> 00:08:53,300
John y Paul en esta tabla hash.

188
00:08:53,300 --> 00:08:55,180
¿Ve usted algún problema?

189
00:08:55,180 --> 00:08:58,410
Es posible que vea dos.

190
00:08:58,410 --> 00:09:02,240
Pero, en particular, ¿verdad
ver a este posible problema?

191
00:09:02,240 --> 00:09:06,770
>> ¿Qué hago si hash Ringo, y
Resulta que después de procesar

192
00:09:06,770 --> 00:09:14,000
que los datos a través de la función hash
Ringo también ha generado el código hash 6.

193
00:09:14,000 --> 00:09:16,810
Ya tengo los datos a
ubicación matriz hashcode-- 6.

194
00:09:16,810 --> 00:09:22,000
Así que probablemente va a ser un poco
de un problema para mí, ¿no?

195
00:09:22,000 --> 00:09:23,060
>> A esto le llamamos una colisión.

196
00:09:23,060 --> 00:09:26,460
Y la colisión se produce cuando dos
piezas de datos pasan por el mismo hash

197
00:09:26,460 --> 00:09:29,200
función dió el mismo código hash.

198
00:09:29,200 --> 00:09:32,850
Es de suponer que todavía queremos conseguir tanto
piezas de datos en la tabla hash,

199
00:09:32,850 --> 00:09:36,330
de lo contrario no estaríamos corriendo Ringo
arbitrariamente a través de la función hash.

200
00:09:36,330 --> 00:09:40,870
Presumiblemente Queremos llegar
Ringo en esa matriz.

201
00:09:40,870 --> 00:09:46,070
>> ¿Cómo lo hacemos sin embargo, si
y Paul tanto el rendimiento código hash 6?

202
00:09:46,070 --> 00:09:49,520
No queremos sobrescribir Pablo,
queremos Pablo a estar allí también.

203
00:09:49,520 --> 00:09:52,790
Así que tenemos que encontrar una manera de conseguir
elementos en la tabla hash que

204
00:09:52,790 --> 00:09:56,550
aún conserva nuestra rápida
inserción y rápida mirada hacia arriba.

205
00:09:56,550 --> 00:10:01,350
Y una manera de tratar con él es
hacer algo llamado sondeo lineal.

206
00:10:01,350 --> 00:10:04,170
>> Usando este método si tenemos una
colisión, bueno, ¿qué hacemos?

207
00:10:04,170 --> 00:10:08,580
Bueno, no lo podemos poner en la localización matriz
6, o lo que sea código hash se generó,

208
00:10:08,580 --> 00:10:10,820
vamos a ponerlo en código hash más 1.

209
00:10:10,820 --> 00:10:13,670
Y si eso es let está lleno
lo puso en código hash más 2.

210
00:10:13,670 --> 00:10:17,420
El beneficio de este ser, si él es
no exactamente donde creemos que él es,

211
00:10:17,420 --> 00:10:20,850
y tenemos que empezar a buscar,
tal vez no tenemos que ir muy lejos.

212
00:10:20,850 --> 00:10:23,900
Tal vez no tenemos que buscar
todos los n elementos de la tabla hash.

213
00:10:23,900 --> 00:10:25,790
Tal vez tenemos que buscar
un par de ellos.

214
00:10:25,790 --> 00:10:30,680
>> Y así seguimos tendiendo hacia
ese caso promedio es de cerca de 1 vs

215
00:10:30,680 --> 00:10:34,280
cerca de n, por lo que tal vez eso funcionará.

216
00:10:34,280 --> 00:10:38,010
Así que vamos a ver cómo esto
podría funcionar en la realidad.

217
00:10:38,010 --> 00:10:41,460
Y vamos a ver si tal vez podamos detectar
el problema que pueda ocurrir aquí.

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

219
00:10:42,540 --> 00:10:45,581
Así que ahora vamos a correr un nuevo conjunto
de cadenas a través de la función hash,

220
00:10:45,581 --> 00:10:48,460
y corremos Bart a través del hash
función, obtenemos código hash 6.

221
00:10:48,460 --> 00:10:52,100
Echamos un vistazo, vemos 6 es
vacío, para que podamos poner Bart allí.

222
00:10:52,100 --> 00:10:55,410
>> Ahora HASH Lisa y que
también genera código hash 6.

223
00:10:55,410 --> 00:10:58,330
Bueno, ahora que estamos utilizando este
lineal método empezamos a las 6 de sondeo,

224
00:10:58,330 --> 00:10:59,330
vemos que 6 es completa.

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

226
00:11:00,990 --> 00:11:02,090
Entonces, ¿dónde vamos?

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

228
00:11:03,280 --> 00:11:04,610
7 de vacío, así que funciona.

229
00:11:04,610 --> 00:11:06,510
Así que vamos a poner Lisa allí.

230
00:11:06,510 --> 00:11:10,200
>> Ahora HASH Homero y obtenemos 7.

231
00:11:10,200 --> 00:11:13,380
OK, así que sabemos que el 7 de plena
Ahora, lo que no podemos poner Homero allí.

232
00:11:13,380 --> 00:11:14,850
Así que vamos a ir a 8.

233
00:11:14,850 --> 00:11:15,664
Es 8 disponibles?

234
00:11:15,664 --> 00:11:18,330
Sí, y de 8 cerca de 7, así que si
tenemos que empezar a buscar somos

235
00:11:18,330 --> 00:11:20,020
No va a tener que ir demasiado lejos.

236
00:11:20,020 --> 00:11:22,860
Y así vamos a poner Homero a las 8.

237
00:11:22,860 --> 00:11:25,151
>> Ahora HASH Maggie y
devuelve 3, gracias a Dios

238
00:11:25,151 --> 00:11:26,650
somos capaces de simplemente poner Maggie allí.

239
00:11:26,650 --> 00:11:29,070
No tenemos que hacer ningún
especie de sondeo para eso.

240
00:11:29,070 --> 00:11:32,000
Ahora HASH Marge, y
Marge también devuelve 6.

241
00:11:32,000 --> 00:11:39,560
>> Bueno 6 es completa, 7 es completa, 8 es completa,
9, gracias bien Dios, 9 está vacía.

242
00:11:39,560 --> 00:11:41,600
Puedo poner Marge a las 9.

243
00:11:41,600 --> 00:11:45,280
Ya podemos ver que estamos empezando
tener este problema por el que ahora estamos

244
00:11:45,280 --> 00:11:48,780
empezando a estirar cosas tipo
de lejos de sus códigos hash.

245
00:11:48,780 --> 00:11:52,960
Y eso theta de 1, ese promedio
caso de ser constante de tiempo,

246
00:11:52,960 --> 00:11:56,560
está empezando a conseguir un poco más--
empezando a cuidar un poco más

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

248
00:11:58,050 --> 00:12:01,270
Estamos empezando a perder ese
ventaja de tablas hash.

249
00:12:01,270 --> 00:12:03,902
>> Este problema que acabamos de ver
es algo que se llama la agrupación.

250
00:12:03,902 --> 00:12:06,360
Y lo que es realmente mal por
agrupación es que una vez que ahora

251
00:12:06,360 --> 00:12:09,606
tener dos elementos que están lado a
lado que hace que sea aún más probable,

252
00:12:09,606 --> 00:12:11,480
usted tiene el doble de la
oportunidad, que te vas

253
00:12:11,480 --> 00:12:13,516
tener otra colisión
con ese grupo,

254
00:12:13,516 --> 00:12:14,890
y el grupo crecerá a una.

255
00:12:14,890 --> 00:12:19,640
Y seguirás creciendo y creciendo
su probabilidad de tener una colisión.

256
00:12:19,640 --> 00:12:24,470
Y, finalmente, es tan malo
como no clasificar los datos en absoluto.

257
00:12:24,470 --> 00:12:27,590
>> El otro problema sin embargo es que
Todavía, y hasta ahora hasta este punto,

258
00:12:27,590 --> 00:12:30,336
sólo hemos sido una especie de
comprensión de lo que es una tabla hash,

259
00:12:30,336 --> 00:12:31,960
todavía sólo tenemos espacio para 10 cuerdas.

260
00:12:31,960 --> 00:12:37,030
Si queremos seguir para discutir
los ciudadanos de Springfield,

261
00:12:37,030 --> 00:12:38,790
sólo podemos obtener 10 de ellos en ese país.

262
00:12:38,790 --> 00:12:42,619
Y si lo intentamos y añadimos un 11 o 12,
no tenemos un lugar para ponerlas.

263
00:12:42,619 --> 00:12:45,660
Podríamos simplemente estar girando en torno a
círculos tratando de encontrar un lugar vacío,

264
00:12:45,660 --> 00:12:49,000
y que tal vez estancamos
en un bucle infinito.

265
00:12:49,000 --> 00:12:51,810
>> Así que este tipo de presta a la idea
de algo llamado encadenamiento.

266
00:12:51,810 --> 00:12:55,790
Y aquí es donde vamos a traer
listas enlazadas de nuevo en la imagen.

267
00:12:55,790 --> 00:13:01,300
¿Y si en lugar de almacenar solo
los datos en sí en la matriz,

268
00:13:01,300 --> 00:13:04,471
cada elemento de la matriz podría
mantener múltiples piezas de datos?

269
00:13:04,471 --> 00:13:05,970
Bueno, eso no tiene sentido, ¿verdad?

270
00:13:05,970 --> 00:13:09,280
Sabemos que un array sólo puede
hold-- cada elemento de una matriz

271
00:13:09,280 --> 00:13:12,930
sólo puede contener una sola pieza
de datos de ese tipo de datos.

272
00:13:12,930 --> 00:13:16,750
>> Pero ¿y si ese tipo de datos
es una lista enlazada, ¿verdad?

273
00:13:16,750 --> 00:13:19,830
¿Y qué si todos los
elemento de la matriz era

274
00:13:19,830 --> 00:13:22,790
un puntero a la cabeza de una lista enlazada?

275
00:13:22,790 --> 00:13:24,680
Y entonces podríamos construir
esas listas enlazadas

276
00:13:24,680 --> 00:13:27,120
y crecer arbitrariamente,
porque listas enlazadas permiten

277
00:13:27,120 --> 00:13:32,090
a crecer y encogerse mucho más
flexible que una matriz hace.

278
00:13:32,090 --> 00:13:34,210
¿Y qué si ahora usamos,
aprovechamos esto, ¿verdad?

279
00:13:34,210 --> 00:13:37,760
Empezamos a cultivar estas cadenas
fuera de estos lugares de matriz.

280
00:13:37,760 --> 00:13:40,740
>> Ahora podemos encajar un infinito
cantidad de datos, o no infinito,

281
00:13:40,740 --> 00:13:44,170
una cantidad arbitraria de
datos, en nuestra tabla hash

282
00:13:44,170 --> 00:13:47,760
sin toparse
el problema de la colisión.

283
00:13:47,760 --> 00:13:50,740
También hemos eliminado
agrupamiento por hacer esto.

284
00:13:50,740 --> 00:13:54,380
Y bien sabemos que cuando insertamos
en una lista enlazada, si recuerdas

285
00:13:54,380 --> 00:13:57,779
de nuestro video en listas enlazadas, por separado
listas enlazadas y listas doblemente enlazadas,

286
00:13:57,779 --> 00:13:59,070
que es una operación de tiempo constante.

287
00:13:59,070 --> 00:14:00,710
Estamos añadiendo a la parte delantera.

288
00:14:00,710 --> 00:14:04,400
>> Y para la mirada hacia arriba, así que sabemos
esa mirada en una lista enlazada

289
00:14:04,400 --> 00:14:05,785
puede ser un problema, ¿verdad?

290
00:14:05,785 --> 00:14:07,910
Tenemos que buscar a través de
de principio a fin.

291
00:14:07,910 --> 00:14:10,460
No hay azar
el acceso en una lista enlazada.

292
00:14:10,460 --> 00:14:15,610
Pero si en lugar de tener uno vinculado
lista donde una búsqueda sería O de n,

293
00:14:15,610 --> 00:14:19,590
ahora tenemos 10 listas enlazadas,
o 1.000 listas enlazadas,

294
00:14:19,590 --> 00:14:24,120
ahora es el O de n dividido por 10,
o O de n dividido por 1.000.

295
00:14:24,120 --> 00:14:26,940
>> Y mientras hablábamos
teóricamente sobre la complejidad

296
00:14:26,940 --> 00:14:30,061
dejamos de lado las constantes, en lo real
mundo estas cosas realmente importan,

297
00:14:30,061 --> 00:14:30,560
¿derecho?

298
00:14:30,560 --> 00:14:33,080
En realidad nos daremos cuenta
que esto sucede

299
00:14:33,080 --> 00:14:36,610
para ejecutar 10 veces más rápido,
o 1.000 veces más rápido,

300
00:14:36,610 --> 00:14:41,570
porque estamos distribuyendo una larga
cadena a través de 1.000 cadenas más pequeñas.

301
00:14:41,570 --> 00:14:45,090
Y así, cada vez que tenemos que buscar
a través de una de esas cadenas que podamos

302
00:14:45,090 --> 00:14:50,290
ignorar las cadenas 999 no importan
aproximadamente, y simplemente buscar que uno.

303
00:14:50,290 --> 00:14:53,220
>> Lo cual es en promedio de
ser 1.000 veces más corto.

304
00:14:53,220 --> 00:14:56,460
Y por lo que todavía estamos especie de
tendiendo hacia este caso la media

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

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

307
00:15:03,730 --> 00:15:05,804
Vamos a ver cómo esto podría
realmente se ven sin embargo.

308
00:15:05,804 --> 00:15:08,720
Así que esta era la tabla hash que teníamos
antes de que declaramos una tabla hash que

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

310
00:15:10,270 --> 00:15:11,728
No vamos a hacer eso.

311
00:15:11,728 --> 00:15:13,880
Ya sabemos que el
limitaciones de ese método.

312
00:15:13,880 --> 00:15:20,170
Ahora nuestra tabla hash va a ser
un conjunto de 10 nodos, punteros

313
00:15:20,170 --> 00:15:22,120
a los jefes de las listas enlazadas.

314
00:15:22,120 --> 00:15:23,830
>> Y en este momento es nulo.

315
00:15:23,830 --> 00:15:26,170
Cada uno de esos 10 indicadores es nulo.

316
00:15:26,170 --> 00:15:29,870
No hay nada en nuestra
hash de mesa ahora mismo.

317
00:15:29,870 --> 00:15:32,690
>> Ahora vamos a empezar a poner un poco de
las cosas en esta tabla hash.

318
00:15:32,690 --> 00:15:35,440
Y vamos a ver cómo este método es
nos va a beneficiar un poco.

319
00:15:35,440 --> 00:15:36,760
Ahora vamos a hash Joey.

320
00:15:36,760 --> 00:15:40,210
Vamos a ejecutar la cadena de Joey a través
una función hash y volvemos 6.

321
00:15:40,210 --> 00:15:41,200
Bueno, ¿qué hacemos ahora?

322
00:15:41,200 --> 00:15:44,090
>> Bueno, ahora se trabaja con listas enlazadas,
no estamos trabajando con matrices.

323
00:15:44,090 --> 00:15:45,881
Y cuando estamos trabajando
con listas enlazadas que

324
00:15:45,881 --> 00:15:49,790
Sabemos que tenemos que empezar de forma dinámica
asignar cadenas de espacio y de construcción.

325
00:15:49,790 --> 00:15:54,020
Eso es una especie de cómo-- esos son el núcleo
elementos de la construcción de una lista enlazada.

326
00:15:54,020 --> 00:15:57,670
Así que vamos a dinámicamente
asignar espacio para Joey,

327
00:15:57,670 --> 00:16:00,390
y luego vamos a añadirlo a la cadena.

328
00:16:00,390 --> 00:16:03,170
>> Así que ahora mira lo que hemos hecho.

329
00:16:03,170 --> 00:16:06,440
Cuando hash Joey nos dieron el código hash 6.

330
00:16:06,440 --> 00:16:11,790
Ahora el puntero en la ubicación matriz 6
apunta a la cabeza de una lista enlazada,

331
00:16:11,790 --> 00:16:14,900
y en este momento es la única
elemento de una lista enlazada.

332
00:16:14,900 --> 00:16:18,350
Y el nodo en ese
lista enlazada es Joey.

333
00:16:18,350 --> 00:16:22,300
>> Así que si tenemos que mirar hacia arriba Joey
después, acabamos hash Joey de nuevo,

334
00:16:22,300 --> 00:16:26,300
obtenemos 6 otra vez porque nuestra
función hash es determinista.

335
00:16:26,300 --> 00:16:30,400
Y entonces empezamos a la cabeza
de la lista enlazada señalado

336
00:16:30,400 --> 00:16:33,360
que por ubicación array
6, y podemos iterar

337
00:16:33,360 --> 00:16:35,650
a través de esa tratando de encontrar Joey.

338
00:16:35,650 --> 00:16:37,780
Y si construimos nuestra
hash de mesa con eficacia,

339
00:16:37,780 --> 00:16:41,790
y nuestra función hash con eficacia
para distribuir bien los datos,

340
00:16:41,790 --> 00:16:45,770
en promedio cada uno de los vinculados
listas en cada ubicación de matriz

341
00:16:45,770 --> 00:16:50,110
será 1/10 del tamaño de si
sólo tenía como una sola gran

342
00:16:50,110 --> 00:16:51,650
lista enlazada con todo su contenido.

343
00:16:51,650 --> 00:16:55,670
>> Si distribuimos ese enorme vinculados
lista en 10 listas enlazadas

344
00:16:55,670 --> 00:16:57,760
cada lista será un décimo del tamaño.

345
00:16:57,760 --> 00:17:01,432
Y por lo tanto 10 veces más rápida
para buscar a través de.

346
00:17:01,432 --> 00:17:02,390
Así que vamos a hacer esto otra vez.

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

348
00:17:04,290 --> 00:17:07,540
>> Y digamos Ross, cuando lo hacemos
el código hash volvamos es 2.

349
00:17:07,540 --> 00:17:10,630
Bueno, ahora nos dinámicamente asignamos un
nuevo nodo, ponemos Ross en ese nodo,

350
00:17:10,630 --> 00:17:14,900
y decimos ahora ubicación array
2, en lugar de señalar a null,

351
00:17:14,900 --> 00:17:18,579
apunta a la cabeza de un ligado
lista cuyo único nodo es Ross.

352
00:17:18,579 --> 00:17:22,660
Y podemos hacer esto una vez más, nos
puede hash de Rachel y obtener código hash 4.

353
00:17:22,660 --> 00:17:25,490
malloc un nuevo nodo, puesto Raquel en
el nodo, y decir una ubicación array

354
00:17:25,490 --> 00:17:27,839
4 ahora apunta a la cabeza
de una lista enlazada cuya

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

356
00:17:31,420 --> 00:17:33,470
>> Bien, pero ¿qué pasa si
tenemos una colisión?

357
00:17:33,470 --> 00:17:38,560
Vamos a ver cómo manejamos las colisiones
utilizando el método de encadenamiento separado.

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

359
00:17:39,800 --> 00:17:41,094
Obtenemos el código hash 6.

360
00:17:41,094 --> 00:17:44,010
En nuestro ejemplo anterior estábamos
almacenar las cadenas en la matriz.

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

362
00:17:45,980 --> 00:17:48,444
>> No queremos darle una paliza
Joey, y ya hemos

363
00:17:48,444 --> 00:17:51,110
visto que podemos conseguir algo de agrupación
problemas si tratamos de paso

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

365
00:17:52,202 --> 00:17:54,660
Pero ¿y si sólo un poco
tratar este de la misma manera, ¿no?

366
00:17:54,660 --> 00:17:57,440
Es como la adición de un elemento
a la cabeza de una lista enlazada.

367
00:17:57,440 --> 00:18:00,220
Vamos espacio justo malloc para Phoebe.

368
00:18:00,220 --> 00:18:04,764
>> Diremos próximos puntero de Phoebe
al antiguo jefe de la lista enlazada,

369
00:18:04,764 --> 00:18:07,180
y luego 6 simplemente apunta a la
nuevo jefe de la lista enlazada.

370
00:18:07,180 --> 00:18:10,150
Y ahora mira, hemos cambiado en Phoebe.

371
00:18:10,150 --> 00:18:14,210
Ahora podemos almacenar de dos
elementos con código hash 6,

372
00:18:14,210 --> 00:18:17,170
y no tenemos ningún problema.

373
00:18:17,170 --> 00:18:20,147
>> Eso es más o menos todo
hay que encadenamiento.

374
00:18:20,147 --> 00:18:21,980
Y encadenamiento es definitivamente
el método que es

375
00:18:21,980 --> 00:18:27,390
va a ser más efectivo para usted si
está almacenando datos en una tabla hash.

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

377
00:18:30,890 --> 00:18:36,080
entre sí para formar una tabla hash realmente
mejora dramáticamente su capacidad

378
00:18:36,080 --> 00:18:40,550
para almacenar grandes cantidades de datos, y
muy rápida y eficiente buscar

379
00:18:40,550 --> 00:18:41,630
a través de esos datos.

380
00:18:41,630 --> 00:18:44,150
>> Todavía hay una más
estructura de datos por ahí

381
00:18:44,150 --> 00:18:48,700
que incluso podría ser un poco
mejor en términos de garantizar

382
00:18:48,700 --> 00:18:51,920
que nuestra inserción, eliminación y
mirar los tiempos son aún más rápido.

383
00:18:51,920 --> 00:18:55,630
Y veremos que en un video en intentos.

384
00:18:55,630 --> 00:18:58,930
Soy Doug Lloyd, esto es CS50.

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