[REPRODUCCIÓN DE MÚSICA] DOUG LLOYD: A estas alturas ya saber mucho acerca de las matrices, y usted sabe mucho sobre listas enlazadas. Y hemos discutir la pros y contras, hemos discutido que unía las listas puede conseguir más grande y más pequeño, pero ocupan más tamaño. Las matrices son mucho más fáciles de utilizan, pero son restrictivos en la medida ya que tenemos que ajustar el tamaño de la matriz desde el principio y después nos pegan con ella. Pero eso es, tenemos más o menos agotado todos nuestros temas sobre listas enlazadas y matrices. O tenemos? Tal vez podamos hacer algo aún más creativo. Y ese tipo de presta la idea de una tabla hash. Así que en una tabla hash que vamos a tratar combinar una matriz con una lista enlazada. Vamos a tomar las ventajas de la matriz, como de acceso aleatorio, ser capaz de ir a la matriz elemento 4 o matriz elemento 8 sin tener que recorrer a través. Eso es bastante rápido, ¿verdad? Pero también queremos tener nuestros datos estructura de poder crecer y encogerse. No necesitamos, no lo hacemos quieren ser restringido. Y nosotros queremos ser capaces para agregar y quitar cosas muy fácilmente, lo que si usted recuerda, es muy complejo con una matriz. Y podemos llamar a esto Lo nuevo una tabla hash. Y si se aplica correctamente, estamos especie de tomar las ventajas de ambos datos estructuras que ya has visto, matrices y listas enlazadas. La inserción puede empezar a tender hacia theta de 1. Theta no hemos discutido realmente, pero theta es sólo el caso promedio, lo que en realidad va a suceder. No siempre vas a tener el peor de los casos, y no siempre vas a tener el mejor de los casos, así que cuál es el escenario promedio? Bueno una inserción media en una tabla hash puede empezar a acercarse a la constante de tiempo. Y eliminación puede conseguir cerca de constante de tiempo. Y las operaciones de búsqueda puede obtener cerca de constante de tiempo. Eso es-- no tenemos un dato estructura hasta ahora de que puede hacer eso, por lo que este ya suena como un muy gran cosa. Realmente hemos mitigado los desventajas de cada uno por su cuenta. Para obtener este rendimiento actualizar sin embargo, nos necesidad de repensar cómo añadimos los datos en la estructura. Específicamente queremos que el sí los datos que nos diga donde debe ir en la estructura. Y si luego tenemos que ver si está en la estructura, si tenemos que encontrarlo, queremos mirar los datos de nuevo y ser capaz de eficacia, utilizando los datos, acceder aleatoriamente ella. Sólo mirando a la datos que debemos tener una idea de dónde exactamente estamos ir a encontrarlo en la tabla hash. Ahora la desventaja de un hash mesa es que son realmente bastante mal en ordenar o clasificar los datos. Y de hecho, si se inicia utilizarlos para pedir u ordenar los datos se pierde toda la ventajas previamente tenido en términos de inserción y eliminación. El tiempo se convierte en más cerca de theta de n, y hemos básicamente retrocedido en una lista enlazada. Y por lo que sólo queremos utilizar de hash tablas si no importan si los datos se ordena. Para el contexto en el cual que vamos a usar en CS50 es probable que no importa que los datos se clasifican. Así que una tabla hash es una combinación de dos piezas distintas con la que estamos familiarizados. La primera es una función, la cual que se suele llamar una función hash. Y esa función hash va a volver algún entero no negativo, que que se suele llamar un código hash, OK? La segunda pieza es una matriz, que es capaz de almacenar datos del tipo que que desee colocar en la estructura de datos. Vamos a mantenerse a distancia de la vinculado lista de elementos por el momento y acaba de comenzar con los fundamentos de un hash de mesa para conseguir su cabeza alrededor de ella, y luego vamos a tal soplamos tu mente un poco cuando nos combinar las matrices y listas de enlaces juntos. La idea básica aunque es que tomamos algunos datos. Corremos que los datos a través de la función hash. Y así se procesan los datos y escupe un número, ¿de acuerdo? Y luego con ese número sólo almacenamos los datos queremos almacenar en la array en esa ubicación. Así por ejemplo tenemos quizá esta tabla hash de cadenas. Tiene 10 elementos en él, así podemos encajar 10 cuerdas en el mismo. Digamos que queremos para discutir Juan. Así que Juan como los datos que queremos insertar en esta tabla hash en alguna parte. ¿Dónde lo ponemos? Bien típicamente con un gama hasta ahora es probable lo pondría en un lugar matriz 0. Pero ahora tenemos esta nueva función hash. Y digamos que corremos John a través de esta función hash y se escupe 4. Bueno, eso es donde estamos va a querer poner John. Queremos poner a Juan en lugar array 4, porque si hash John nuevo-- digamos más tarde desee buscar y ver si John existe en este hash table-- todo lo que necesitamos hacer se ejecuta a través de el mismo hash función, obtener el número 4, y ser capaz de encontrar John inmediatamente en nuestra estructura de datos. Eso es bastante bueno. Digamos que ahora hacemos de nuevo, queremos hash de Pablo. Queremos añadir Paul en esta tabla hash. Digamos que en esta ocasión se corre Paul a través de la función hash, el código hash que se genera es 6. Bueno, ahora podemos poner Paul en la ubicación matriz 6. Y si tenemos que mirar hacia arriba si Paul es en esta tabla hash, todo lo que necesitamos hacer es ejecutar Paul a través de la función hash de nuevo y vamos a conseguir 6 de nuevo. Y entonces sólo miramos en la localización matriz 6. ¿Es Paul allí? Si es así, está en la tabla hash. Es Pablo no existe? No está en la tabla hash. Es bastante sencillo. Ahora ¿cómo se define una función hash? Bueno realmente no hay límite a la número de posibles funciones de hash. De hecho hay un número de realidad, realmente buenos en el Internet. Hay una serie de realidad, los realmente malos en el Internet. También es bastante fácil escribir una mala. Entonces, ¿qué hace que una buena función hash, ¿verdad? Bueno una buena función hash debe utilizan sólo los datos que se hash, y todos los datos que se están hash. Así que no queremos utilizar anything-- no incorporamos nada más aparte de los datos. Y queremos utilizar todos los datos. No queremos utilizar sólo una pieza de la misma, queremos utilizar todo. Una función hash debe también ser determinista. ¿Que significa eso? Bueno, significa que cada vez que pasar la misma pieza exacta de los datos en la función hash siempre obtener el mismo código hash a cabo. Si paso John en el función hash que salir 4. Yo debería ser capaz de hacer eso 10000 veces y siempre obtendrá 4. Así que no hay números aleatorios eficazmente pueden participar en nuestro picadillo tables-- en nuestras funciones hash. Una función hash debe también distribuir uniformemente datos. Si cada vez que ejecute datos a través del función hash a obtener el código hash 0, que probablemente no es tan grande, ¿no? Usted probablemente querrá grande una serie de códigos hash. También las cosas se pueden propagar a lo largo de la mesa. Y también sería genial si realmente datos similares, como John y Jonathan, tal vez se extendieron a sopesar diferentes ubicaciones en la tabla hash. Eso sería una buena ventaja. He aquí un ejemplo de una función hash. Escribí este uno antes. No es un particular buena función hash por razones que realmente no soportar entrar en este momento. Pero, ¿ves lo que está pasando aquí? Parece como que estamos declarando una variable llamada suma y se establece igual a 0. Y luego aparentemente estoy haciendo algo siempre que strstr [j] no es igual a 0 barra invertida. ¿Qué estoy haciendo allí? Esto es básicamente sólo otro forma de implementar [? STRL?] y detectar cuando has alcanzado el final de la cadena. Así que no tengo que realmente calcular la longitud de la cadena, Sólo estoy usando cuando pulso el barra invertida 0 caracteres sé He llegado al final de la cadena. Y entonces yo voy a seguir iteración a través de esa cadena, añadiendo strstr [j] para resumir, y luego en la final del día va a regresar suma mod HASH_MAX. Básicamente todo este hash función está haciendo es sumar todos los valores ASCII de mi cuerda, y entonces es regresar algún código hash modded por HASH_MAX. Es probablemente el tamaño de mi serie, ¿no? No quiero estar recibiendo de hash códigos si mi arsenal es de tamaño 10, Yo no quiero ser conseguir códigos hash fuera 11, 12, 13, no puedo poner las cosas en esos lugares de la matriz, eso sería ilegal. Yo sufro un fallo de segmentación. Ahora aquí es otra rápida a un lado. En general, usted está probablemente no va a quiere escribir sus propias funciones hash. En realidad, es un poco de un arte, no una ciencia. Y hay mucho que va en ellos. El Internet, como he dicho, está llena de muy buenas funciones hash, y usted debe utilizar el Internet para encontrar funciones hash porque es realmente sólo un poco de una innecesaria pérdida de tiempo para crear el suyo propio. Usted puede escribir los simples para propósitos de prueba. Pero cuando realmente se va a iniciar hashing de datos y su almacenamiento en una tabla hash estás probablemente va a querer utilizar alguna función que se ha generado para usted, lo que existe en Internet. Si sólo asegúrese para citar sus fuentes. No hay razón para plagiar nada aquí. La comunidad de la informática es sin duda creciente, y realmente los valores de código abierto, y es muy importante para citar sus fuentes para que la gente puede obtener la atribución de el trabajo que están haciendo en beneficio de la comunidad. Así que siempre sure-- y no sólo para hachís funciones, pero generalmente cuando usar el código de una fuente externa, siempre citar su fuente. Dar crédito a la persona que lo hizo algunos de los trabajos por lo que no tienen que. OK, así que vamos a revisar este tabla hash para un segundo. Aquí es donde nos fuimos después insertamos John y Paul en esta tabla hash. ¿Ve usted algún problema? Es posible que vea dos. Pero, en particular, ¿verdad ver a este posible problema? ¿Qué hago si hash Ringo, y Resulta que después de procesar que los datos a través de la función hash Ringo también ha generado el código hash 6. Ya tengo los datos a ubicación matriz hashcode-- 6. Así que probablemente va a ser un poco de un problema para mí, ¿no? A esto le llamamos una colisión. Y la colisión se produce cuando dos piezas de datos pasan por el mismo hash función dió el mismo código hash. Es de suponer que todavía queremos conseguir tanto piezas de datos en la tabla hash, de lo contrario no estaríamos corriendo Ringo arbitrariamente a través de la función hash. Presumiblemente Queremos llegar Ringo en esa matriz. ¿Cómo lo hacemos sin embargo, si y Paul tanto el rendimiento código hash 6? No queremos sobrescribir Pablo, queremos Pablo a estar allí también. Así que tenemos que encontrar una manera de conseguir elementos en la tabla hash que aún conserva nuestra rápida inserción y rápida mirada hacia arriba. Y una manera de tratar con él es hacer algo llamado sondeo lineal. Usando este método si tenemos una colisión, bueno, ¿qué hacemos? Bueno, no lo podemos poner en la localización matriz 6, o lo que sea código hash se generó, vamos a ponerlo en código hash más 1. Y si eso es let está lleno lo puso en código hash más 2. El beneficio de este ser, si él es no exactamente donde creemos que él es, y tenemos que empezar a buscar, tal vez no tenemos que ir muy lejos. Tal vez no tenemos que buscar todos los n elementos de la tabla hash. Tal vez tenemos que buscar un par de ellos. Y así seguimos tendiendo hacia ese caso promedio es de cerca de 1 vs cerca de n, por lo que tal vez eso funcionará. Así que vamos a ver cómo esto podría funcionar en la realidad. Y vamos a ver si tal vez podamos detectar el problema que pueda ocurrir aquí. Digamos que hash Bart. Así que ahora vamos a correr un nuevo conjunto de cadenas a través de la función hash, y corremos Bart a través del hash función, obtenemos código hash 6. Echamos un vistazo, vemos 6 es vacío, para que podamos poner Bart allí. Ahora HASH Lisa y que también genera código hash 6. Bueno, ahora que estamos utilizando este lineal método empezamos a las 6 de sondeo, vemos que 6 es completa. No podemos poner Lisa en 6. Entonces, ¿dónde vamos? Vamos a 7. 7 de vacío, así que funciona. Así que vamos a poner Lisa allí. Ahora HASH Homero y obtenemos 7. OK, así que sabemos que el 7 de plena Ahora, lo que no podemos poner Homero allí. Así que vamos a ir a 8. Es 8 disponibles? Sí, y de 8 cerca de 7, así que si tenemos que empezar a buscar somos No va a tener que ir demasiado lejos. Y así vamos a poner Homero a las 8. Ahora HASH Maggie y devuelve 3, gracias a Dios somos capaces de simplemente poner Maggie allí. No tenemos que hacer ningún especie de sondeo para eso. Ahora HASH Marge, y Marge también devuelve 6. Bueno 6 es completa, 7 es completa, 8 es completa, 9, gracias bien Dios, 9 está vacía. Puedo poner Marge a las 9. Ya podemos ver que estamos empezando tener este problema por el que ahora estamos empezando a estirar cosas tipo de lejos de sus códigos hash. Y eso theta de 1, ese promedio caso de ser constante de tiempo, está empezando a conseguir un poco más-- empezando a cuidar un poco más hacia theta de n. Estamos empezando a perder ese ventaja de tablas hash. Este problema que acabamos de ver es algo que se llama la agrupación. Y lo que es realmente mal por agrupación es que una vez que ahora tener dos elementos que están lado a lado que hace que sea aún más probable, usted tiene el doble de la oportunidad, que te vas tener otra colisión con ese grupo, y el grupo crecerá a una. Y seguirás creciendo y creciendo su probabilidad de tener una colisión. Y, finalmente, es tan malo como no clasificar los datos en absoluto. El otro problema sin embargo es que Todavía, y hasta ahora hasta este punto, sólo hemos sido una especie de comprensión de lo que es una tabla hash, todavía sólo tenemos espacio para 10 cuerdas. Si queremos seguir para discutir los ciudadanos de Springfield, sólo podemos obtener 10 de ellos en ese país. Y si lo intentamos y añadimos un 11 o 12, no tenemos un lugar para ponerlas. Podríamos simplemente estar girando en torno a círculos tratando de encontrar un lugar vacío, y que tal vez estancamos en un bucle infinito. Así que este tipo de presta a la idea de algo llamado encadenamiento. Y aquí es donde vamos a traer listas enlazadas de nuevo en la imagen. ¿Y si en lugar de almacenar solo los datos en sí en la matriz, cada elemento de la matriz podría mantener múltiples piezas de datos? Bueno, eso no tiene sentido, ¿verdad? Sabemos que un array sólo puede hold-- cada elemento de una matriz sólo puede contener una sola pieza de datos de ese tipo de datos. Pero ¿y si ese tipo de datos es una lista enlazada, ¿verdad? ¿Y qué si todos los elemento de la matriz era un puntero a la cabeza de una lista enlazada? Y entonces podríamos construir esas listas enlazadas y crecer arbitrariamente, porque listas enlazadas permiten a crecer y encogerse mucho más flexible que una matriz hace. ¿Y qué si ahora usamos, aprovechamos esto, ¿verdad? Empezamos a cultivar estas cadenas fuera de estos lugares de matriz. Ahora podemos encajar un infinito cantidad de datos, o no infinito, una cantidad arbitraria de datos, en nuestra tabla hash sin toparse el problema de la colisión. También hemos eliminado agrupamiento por hacer esto. Y bien sabemos que cuando insertamos en una lista enlazada, si recuerdas de nuestro video en listas enlazadas, por separado listas enlazadas y listas doblemente enlazadas, que es una operación de tiempo constante. Estamos añadiendo a la parte delantera. Y para la mirada hacia arriba, así que sabemos esa mirada en una lista enlazada puede ser un problema, ¿verdad? Tenemos que buscar a través de de principio a fin. No hay azar el acceso en una lista enlazada. Pero si en lugar de tener uno vinculado lista donde una búsqueda sería O de n, ahora tenemos 10 listas enlazadas, o 1.000 listas enlazadas, ahora es el O de n dividido por 10, o O de n dividido por 1.000. Y mientras hablábamos teóricamente sobre la complejidad dejamos de lado las constantes, en lo real mundo estas cosas realmente importan, ¿derecho? En realidad nos daremos cuenta que esto sucede para ejecutar 10 veces más rápido, o 1.000 veces más rápido, porque estamos distribuyendo una larga cadena a través de 1.000 cadenas más pequeñas. Y así, cada vez que tenemos que buscar a través de una de esas cadenas que podamos ignorar las cadenas 999 no importan aproximadamente, y simplemente buscar que uno. Lo cual es en promedio de ser 1.000 veces más corto. Y por lo que todavía estamos especie de tendiendo hacia este caso la media de ser constante de tiempo, pero sólo porque estamos aprovechando dividiendo por un enorme factor constante. Vamos a ver cómo esto podría realmente se ven sin embargo. Así que esta era la tabla hash que teníamos antes de que declaramos una tabla hash que era capaz de almacenar 10 cuerdas. No vamos a hacer eso. Ya sabemos que el limitaciones de ese método. Ahora nuestra tabla hash va a ser un conjunto de 10 nodos, punteros a los jefes de las listas enlazadas. Y en este momento es nulo. Cada uno de esos 10 indicadores es nulo. No hay nada en nuestra hash de mesa ahora mismo. Ahora vamos a empezar a poner un poco de las cosas en esta tabla hash. Y vamos a ver cómo este método es nos va a beneficiar un poco. Ahora vamos a hash Joey. Vamos a ejecutar la cadena de Joey a través una función hash y volvemos 6. Bueno, ¿qué hacemos ahora? Bueno, ahora se trabaja con listas enlazadas, no estamos trabajando con matrices. Y cuando estamos trabajando con listas enlazadas que Sabemos que tenemos que empezar de forma dinámica asignar cadenas de espacio y de construcción. Eso es una especie de cómo-- esos son el núcleo elementos de la construcción de una lista enlazada. Así que vamos a dinámicamente asignar espacio para Joey, y luego vamos a añadirlo a la cadena. Así que ahora mira lo que hemos hecho. Cuando hash Joey nos dieron el código hash 6. Ahora el puntero en la ubicación matriz 6 apunta a la cabeza de una lista enlazada, y en este momento es la única elemento de una lista enlazada. Y el nodo en ese lista enlazada es Joey. Así que si tenemos que mirar hacia arriba Joey después, acabamos hash Joey de nuevo, obtenemos 6 otra vez porque nuestra función hash es determinista. Y entonces empezamos a la cabeza de la lista enlazada señalado que por ubicación array 6, y podemos iterar a través de esa tratando de encontrar Joey. Y si construimos nuestra hash de mesa con eficacia, y nuestra función hash con eficacia para distribuir bien los datos, en promedio cada uno de los vinculados listas en cada ubicación de matriz será 1/10 del tamaño de si sólo tenía como una sola gran lista enlazada con todo su contenido. Si distribuimos ese enorme vinculados lista en 10 listas enlazadas cada lista será un décimo del tamaño. Y por lo tanto 10 veces más rápida para buscar a través de. Así que vamos a hacer esto otra vez. Ahora vamos a hash de Ross. Y digamos Ross, cuando lo hacemos el código hash volvamos es 2. Bueno, ahora nos dinámicamente asignamos un nuevo nodo, ponemos Ross en ese nodo, y decimos ahora ubicación array 2, en lugar de señalar a null, apunta a la cabeza de un ligado lista cuyo único nodo es Ross. Y podemos hacer esto una vez más, nos puede hash de Rachel y obtener código hash 4. malloc un nuevo nodo, puesto Raquel en el nodo, y decir una ubicación array 4 ahora apunta a la cabeza de una lista enlazada cuya único elemento pasa a ser Rachel. Bien, pero ¿qué pasa si tenemos una colisión? Vamos a ver cómo manejamos las colisiones utilizando el método de encadenamiento separado. Vamos a hash Phoebe. Obtenemos el código hash 6. En nuestro ejemplo anterior estábamos almacenar las cadenas en la matriz. Esto era un problema. No queremos darle una paliza Joey, y ya hemos visto que podemos conseguir algo de agrupación problemas si tratamos de paso a través y la sonda. Pero ¿y si sólo un poco tratar este de la misma manera, ¿no? Es como la adición de un elemento a la cabeza de una lista enlazada. Vamos espacio justo malloc para Phoebe. Diremos próximos puntero de Phoebe al antiguo jefe de la lista enlazada, y luego 6 simplemente apunta a la nuevo jefe de la lista enlazada. Y ahora mira, hemos cambiado en Phoebe. Ahora podemos almacenar de dos elementos con código hash 6, y no tenemos ningún problema. Eso es más o menos todo hay que encadenamiento. Y encadenamiento es definitivamente el método que es va a ser más efectivo para usted si está almacenando datos en una tabla hash. Pero esta combinación de matrices y listas enlazadas entre sí para formar una tabla hash realmente mejora dramáticamente su capacidad para almacenar grandes cantidades de datos, y muy rápida y eficiente buscar a través de esos datos. Todavía hay una más estructura de datos por ahí que incluso podría ser un poco mejor en términos de garantizar que nuestra inserción, eliminación y mirar los tiempos son aún más rápido. Y veremos que en un video en intentos. Soy Doug Lloyd, esto es CS50.