[Música tocando] Doug LLOYD: Ata agora sabe moito sobre arrays, e vostede sabe moito sobre listas ligadas. E nós discutir a pros e contras, temos discutido que ligaba listas pode estar máis grande e pequena, pero elas ocupan máis tamaño. Arrays son moito máis simple de usar, pero son restritivos, na medida en como temos que axustar o tamaño da o array no inicio e entón nós está preso con el. 

Pero iso é, temos practicamente esgotado todos os nosos temas sobre listas ligadas e matrices. Ou non é? Quizais poidamos facer algo aínda máis creativo. E este tipo de presta a idea dunha táboa hash. 

Así, nunha táboa hash imos tratar combinar unha matriz cunha lista ligada. Nós imos ter as vantaxes da matriz, como a de acceso aleatorio, poder simplemente ir a matriz elemento 4 ou matriz elemento 8 sen ter que interactuar transversalmente. Iso é moi rápido, non? 

Pero tamén queremos ter os nosos datos estrutura capaz de aumentar e diminuír. Non necesitamos, non pretende ser restrinxida. E nós queremos ser capaces para engadir e eliminar as cousas moi facilmente, o que se recorda, é moi complexo, cunha matriz. E podemos chamar iso de cousa nova unha táboa hash. 

E, se aplicada correctamente, estamos especie de tomar as vantaxes de ambos os datos estruturas que xa viu, matrices e listas ligadas. A inserción pode comezar a tenden a teta dunha. Theta non temos realmente discutido, pero é só o caso teta media, o que realmente vai ocorrer. Vostede non sempre vai ten o peor escenario, e non está indo sempre ter o mellor escenario, entón o que é o escenario de media? 

Ben unha inserción media nunha táboa hash Pode comezar a chegar preto de tempo constante. E eliminación pode obter pechar co tempo constante. E busca pode obter pechar co tempo constante. That's-- non temos un conxunto de datos estrutura aínda que pode facelo, e por iso este xa soa como unha cousa moi grande. Nós realmente mitigados o desvantaxes de cada un pola súa conta. 

Para obter este rendemento actualizar, pero, temos Necesitamos repensar como podemos engadir de datos na estrutura. Especialmente queremos que o datos en si para dicir onde debe ir na estrutura. E se nós entón necesitamos ver se está en a estrutura, se necesitamos atopalo, queremos ollar os datos de novo e ser capaz de efectivamente, usando os datos, acceder a ela de forma aleatoria. Basta ollar para o datos que deben ter unha idea de onde exactamente estamos Vai atopalo na táboa de hash. 

Agora, a desvantaxe dun hash mesa é que son realmente moi malo en comprar ou ordenar datos. E, de feito, se comezar para usalos para ordenar ou clasificar datos perde toda a vantaxes anteriormente tivo en termos de inserción e exclusión. O tempo pasa a ser máis preto theta n, e nós temos, basicamente, comezou a desaparecer nunha lista ligada. E así nós só quere usar de hash táboas se non se preocupan se os datos son ordenados. Ao contexto en que vai usalos en CS50 probablemente non me importa que os datos son clasificados. 

Así, unha táboa hash é unha combinación de dúas pezas distintas coa que estamos familiarizados. A primeira é unha función, que que adoitamos chamar unha función hash. E esa función hash vai voltar algún número enteiro non negativo, que que adoitamos chamar dun hashcode, OK? A segunda peza é unha matriz, que é capaz de almacenar datos do tipo que pretende poñer na estrutura de datos. Nós imos adiar o ligada elemento da lista para agora e só comezar co básico dun hash de táboa para obter a súa cabeza en torno a el, e despois imos quizais explotar súa mente un pouco cando combinar matrices e listas de enlaces xuntos. 

A idea básica aínda é tomamos uns datos. Corremos que os datos a través de a función hash. E así os datos son procesados e el cospe un número, OK? E, a continuación, co número nós só almacenar os datos queremos almacenar na matriz nese local. Así, por exemplo, temos quizais esta táboa hash de cordas. Ten 10 elementos en que, de xeito podemos encaixar 10 cordas nel. 

Imos dicir que queremos botar John. Entón John como os datos que desexa inserir para esta táboa de hash en algún lugar. Onde é que imos poñelas? Ben tipicamente cun matriz, ata agora, probablemente ía poñelo en orde de localización 0. Pero agora temos esta nova función hash. 

E imos dicir que corremos John a través desta función hash e é cospe 4. Ben, iso é onde estamos vai querer poñer John. Queremos poñer Xoán no lugar da matriz 4 porque se nós botar John novamente-- digamos que logo nós quere buscar e ver John se existe neste haxix mesa-- todo o que necesitamos facer é executa-lo a través do mesmo hash función, conseguir o número 4, e ser capaz de atopar John inmediatamente na nosa estrutura de datos. Iso é moi bo. 

Imos dicir que nós agora facelo de novo, queremos botar Paul. Queremos engadir Paul para esta táboa hash. Imos dicir que, esta vez, corremos Paul través da función hash, o hashcode que se xera é 6. Ben, agora podemos poñer Paul no lugar da matriz 6. E se necesitamos a ollar para arriba se Paul está nesta táboa hash, todo o que necesitamos facer é executar Paul a través da función hash novo e nós estamos indo a chegar en 6º de novo. 

E entón nós só ollar no lugar da matriz 6. Paul é alí? Se é así, está na táboa hash. Paul non é alí? Non está na táboa hash. É moi sinxelo. 

Agora, como define unha función hash? Ben, non hai realmente ningún límite para o número de posibles funcións hash. En realidade hai un número de verdade, realmente bos en internet. Hai un número de verdade, realmente malas en internet. Tamén é moi fácil para escribir un mal. 

Entón, o que fai un bo función hash, non? Ben unha boa función hash debe usar só os datos que están sendo hash, e todos os datos a ser hash. Entón, nós non quere empregar anything-- non incorporar algo outra cousa que non sexa os datos. E queremos usar todos os datos. Non queremos usar só unha peza diso, queremos utilizar todo isto. A función hash debe tamén ser determinista. Que significa iso? Ben, iso significa que cada vez que pasar a mesma peza exacta de datos para a función hash sempre obter o mesmo hashcode para fóra. Se eu pasar ao John función hash saio 4. Eu debería ser capaz de facelo 10.000 veces e sempre terá 4. Así, non números aleatorios de forma eficaz pode ser parte de noso hash de tables-- nas nosas funcións hash. 

A función hash debe uniformemente distribuír datos. Cada vez que realizar datos a través do función hash que obteña o hashcode 0, que probablemente non é tan grande, non? Probablemente vai querer gran unha variedade de códigos de hash. Tamén cousas poden estenderse ao longo do cadro. E tamén sería óptimo se realmente datos semellantes, como John e Jonathan, quizais foron espallados para pesar sitios diferentes na táboa de hash. Isto sería unha boa vantaxe. 

Aquí está un exemplo dunha función hash. Escribín este antes. Non é un particularmente boa función hash por motivos que non o fan realmente Oso que vai agora. Pero ve o que está pasando aquí? Parece que estamos declarando unha variable chamado de suma e define-la igual a 0. E entón, ao parecer, eu estou facendo algo sempre que strstr [j] non é igual a barra invertida 0. O que estou facendo alí? 

Este é basicamente só outro forma de aplicar [? strl?] e detectar cando ten chegou ao fin da cadea. Entón, eu non teño que, en realidade, calcular a lonxitude da corda, Eu só estou usando cando bati o barra invertida 0 personaxe que sei Cheguei ao final da cadea. E entón eu vou seguir iteración través desa cadea, engadindo strstr [j] a suma, e, a continuación, no final do día volverá suma mod HASH_MAX. 

Basicamente todo isto de hash función está facendo é sumando todos os valores de ASCII miña corda, e entón é volver algún hashcode modded por HASH_MAX. É probabelmente o tamaño da miña matriz, non? Non quero estar quedando de hash códigos se miña matriz é de tamaño 10, Eu non quero ser como chegar códigos de hash para fóra 11, 12, 13, eu non podo poñer as cousas en eses locais da matriz, que sería ilegal. Eu sufrir un fallo de segmento. 

Agora, aquí é outra rápida de lado. Xeralmente probablemente non vai quere escribir as súas propias funcións hash. É realmente un pouco de unha arte, non unha ciencia. E hai moito que para eles. A internet, como dixen, está cheo realmente bos funcións hash, e ten que usar internet para atopar funcións hash porque é realmente só unha especie de un innecesario perda de tempo para crear o seu propio. 

Podes escribir máis simple para fins de proba. Pero cando realmente está indo iniciar hash datos e almacena-lo nunha táboa hash que é probablemente vai querer utilizar algunhas das funcións que foi xerado para ti, que hai en internet. Se só non esqueza por citar as súas fontes. Non hai ningunha razón para plagiar calquera cousa aquí. 

A comunidade de ciencia da computación é definitivamente crecendo, e realmente valores código aberto, e é realmente importante por citar as súas fontes para que a xente Pode obter a concesión o traballo que están facendo para o beneficio da comunidade. Polo tanto, sexa sempre sure-- e non só para haxix funcións, pero normalmente cando usar o código dunha fonte externa, sempre citar a súa fonte. Dea crédito para a persoa que fixo parte do traballo para que non precisa. 

OK, entón imos voltar a esta táboa hash para un segundo. Este é o lugar onde paramos off despois inserimos John e Paul para esta táboa hash. Ve un problema aquí? Podes ver dous. Pero, en particular, facer vexa este posible problema? 

E se eu botar Ringo, e Acontece que despois do procesamento que os datos a través da función hash Ringo tamén xerou o hashcode 6. Eu xa teño os datos no hashcode-- localización matriz 6. Por iso, probablemente vai ser un pouco dun problema para min agora, non? 

Chamamos iso dunha colisión. E a colisión ocorre cando dous anacos de datos percorren o mesmo hash función de producir o mesmo código hash. Presuntamente, aínda queremos obter tanto anacos de datos para a táboa hash, se non, non estaría correndo Ringo arbitrariamente a través da función hash. Nós presuntamente quere obter Ringo para esa matriz. 

Como podemos facelo, pero, se e Paul ambos rendemento hashcode 6? Non queremos substituír Paul, queremos Paul estar alí tamén. Por iso, necesitamos atopar unha forma de obter elementos para a táboa hash que aínda preserva a nosa rápida inserción e rápido ollar para arriba. E un xeito de tratar con isto é para facer algo chamado lineal enquisa. 

Usando este método, se temos un colisión, así, o que imos facer? Ben, non podemos poñelas no lugar da matriz 6, ou o que quere hashcode foi xerado, imos poñelas hashcode máis 1. E se isto é deixar de chea poñelas hashcode máis 2. O propósito de este ser se é non exactamente onde pensamos que é, e temos que comezar a buscar, quizais a xente non ten que ir lonxe de máis. Quizais a xente non ten que buscar todos os elementos n da táboa hash. Quizais a xente ten que buscar un par deles. 

E así nós aínda estamos tendendo para Nese caso, media de preto de 1 vs preto de n, quizais por iso que vou traballar. Entón, imos ver como iso pode exercitar-se realidade. E imos ver se é posible poidamos detectar o problema que poida ocorrer aquí. 

Imos dicir que o hash Bart. Entón, agora imos facer un novo conxunto de cordas a través da función hash, e corremos Bart través do hash función, temos hashcode 6. Imos dar un ollo, vemos 6 é baleiro, para que poidamos poñer Bart alí. 

Agora imos botar Lisa e que tamén xera hashcode 6. Ben, agora que estamos a usar esta método que comezan en 6 lineal enquisa, vemos que 6 está cheo. Non podemos poñer en 6 Lisa. Entón, a onde imos? Imos para 7. 7 de baleiro, de xeito que funciona. Entón, imos poñer Lisa alí. 

Agora imos botar a Homer e temos 7. OK así sabemos que 7 do total agora, polo que non podemos poñer Homer alí. Entón imos a 8. É 8 está dispoñible? Si, e 8 de preto de 7, polo que se temos que comezar a buscar estamos non terá que ir lonxe de máis. E así imos poñer Homer ás 8. 

Agora imos botar para Maggie e volve 3, grazas a Deus somos capaces de simplemente poñer Maggie alí. Non temos que facer calquera tipo de enquisa para iso. Agora imos botar Marge, e Marge tamén retorna 6. 

Ben 6 está cheo, 7 é completa, 8 está cheo, 9, todo ben grazas a Deus, 9 está baleiro. Podo poñer Marge, ás 9. Xa podemos ver que estamos comezando para ter este problema en que agora estamos comezando a estirar cousas tipo de lonxe dos seus códigos de hash. E esa teta de 1, esa media caso de ser de tempo constante, está empezando a ser un pouco more-- comezando a tendencia algo máis no sentido de n teta. Estamos empezando a perder esa vantaxe de táboas de hash. 

Este problema que acabamos de ver é algo chamado de agrupación. E o que é realmente malo sobre agrupación é que unha vez que agora ten dous elementos que están xunto a outro tórnase aínda máis probable, ten o dobre da oportunidade, que vai para ter outra colisión con ese cluster, eo cluster crecerá a un. E vai seguir crecendo e crecendo a probabilidade de ter unha colisión. E, finalmente, el é tan malo como non a clasificación dos datos de todo. 

O outro problema, con todo, é que Aínda así, ata o momento e, ata este punto, fomos só unha especie de comprender o que é unha táboa hash, aínda só ten espazo para 10 cordas. Se queremos continuar hash os cidadáns de Springfield, só podemos obter 10 deles alí. E se nós intentamos e engade un 11º ou 12º, non temos un lugar para poñelos. Nós só podería ser xirando en torno a círculos tentando atopar un lugar baleiro, e nós quizais queda preso en un loop infinito. 

Polo tanto, este tipo de presta ao idea de algo chamado fío. E este é o lugar onde nós estamos indo a traer listas ligadas ao a imaxe. E se en vez de almacenar só os datos en si na matriz, cada elemento da matriz podería realizar múltiples pezas de datos? Ben, iso non ten sentido, non? Sabemos que unha matriz só pode hold-- cada elemento dunha matriz só pode conter unha peza de datos deste tipo de datos. 

Pero e se este tipo de datos é unha lista ligada, non? Entón, o que cada elemento da matriz foi un punteiro para a cabeza dunha lista vinculada? E entón poderíamos construír esas listas ligadas e cultiva-las arbitrariamente, porque listas ligadas permitir nos a medrar e encoller máis flexibilidade que unha matriz fai. Entón, o que se usan agora, aproveitamos iso, non? Comezamos a medrar estas cadeas fóra deses lugares matriz. 

Agora podemos encaixar un infinito cantidade de datos, ou non é infinito, unha cantidade arbitraria de datos, na nosa táboa hash sen nunca correr en o problema da colisión. Tamén eliminamos agrupación, facendo iso. E ben sabemos que cando inserimos nunha lista ligada, se recorda do noso vídeo sobre listas ligadas, illadamente listas ligadas e listas dobremente vinculadas, é unha operación de tempo constante. Estamos só engadindo á fronte. 

E para ollar para arriba, ben sabemos que mirar para arriba nunha lista encadeada pode ser un problema, non? Temos que buscar Lo do comezo ao fin. Non hai ningunha chou acceso a unha lista vinculada. Pero, en vez de ter un conectado lista onde unha procura sería O n, agora temos 10 listas ligadas, ou 1.000 listas ligadas, agora é o de n dividido por 10, ou O n dividido por 1,000. 

E mentres nós estabamos falando teoricamente sobre a complexidade desconsiderarmos constantes, no real mundo estas cousas realmente importa, non? Nós, en realidade, vai notar que isto ocorre para realizar 10 veces máis rápido, ou 1.000 veces máis rápida, porque estamos distribuíndo unha longa cadea en toda 1.000 cadeas menores. E así cada vez que ten que buscar mediante unha desas cadeas que podemos ignorar as 999 cadeas de nós non nos importa aproximadamente, e pode buscar aquel. 

Que é, en media, ser 1000 veces máis curto. E así aínda son unha especie de tendendo a este caso medio de ser de tempo constante, pero só porque estamos panca dividindo-se por un enorme factor constante. Imos ver como iso pode realmente ollar aínda. Polo tanto, esta foi a táboa hash tivemos antes de que declarou unha táboa hash que era capaz de almacenar 10 cordas. Non imos máis facelo. Xa sabemos o limitacións deste método. Agora a nosa táboa de hash será unha matriz de 10 nós, punteiros aos xefes de listas ligadas. 

E agora é nulo. Cada un destes 10 punteiros é nulo. Non hai nada na nosa hash de táboa agora. 

Agora imos comezar a poñer algúns cousas para esta táboa hash. E imos ver como este método é vai beneficiar un pouco. Imos agora botar Joey. Imos executará a secuencia de Joey través unha función hash e volvemos 6. Ben, o que facemos agora? 

Ben, agora a traballar con listas ligadas, non estamos a traballar con arrays. E cando estamos a traballar con listas ligadas nós sabemos que necesitamos para comezar dinamicamente distribución de espazo e construción de cadeas. Isto é unha especie de how-- aqueles son o núcleo elementos de construción dunha lista ligada. Entón, imos dinamicamente reservar espazo para Joey, e, a continuación, imos engadir lo á cadea. 

Entón agora mira o que fixemos. Cando o hash Joey temos o hashcode 6. Agora o punteiro no lugar da matriz 6 apunta a cabeza dunha lista ligada, e agora é o único elemento dunha lista ligada. E en que o nodo lista ligada é Joey. 

Entón, se necesitamos a ollar para arriba Joey despois, nós só o hash Joey de novo, temos 6 de novo porque a nosa función hash é determinista. E entón comezamos na cabeza da lista ligada apuntou a matriz por localización 6, e podemos facer unha iteración do outro lado que tentar atopar Joey. E se nós construírmos noso Táboa de Hash de forma eficaz, ea nosa función hash de forma eficaz para distribuír datos ben, en media, cada un dos os ligados listas en cada lugar da matriz será de 1/10 do tamaño de só tiña el como un único gran lista ligada con todo na mesma. 

Distribuir este enorme conectado lista en 10 listas ligadas cada lista será de 1/10 do tamaño. E, polo tanto, 10 veces máis rápido buscar. Entón imos facelo de novo. Imos agora botar Ross. 

E digamos que Ross, cando facemos iso o código de hash volvemos é 2. Ben, agora imos reservar dinamicamente un novo nodo, poñemos Ross nese no, e dicimos agora local da matriz 2, no canto de ligar a null, apunta a cabeza dun conectado lista cuxo único nodo é Ross. E podemos facer iso unha vez máis, nós pode botar para Rachel e obter hashcode 4. malloc un novo nodo, coloque Rachel o no, e dicir un lugar matriz 4 agora apunta á cabeza dunha lista ligada cuxo único elemento pasa a ser Rachel. 

OK, pero o que ocorre se temos unha colisión? Imos ver como lidamos con colisións mediante a entrada de fío separado. Imos botar Phoebe. Estivemos coa hashcode 6. No noso exemplo anterior estabamos só almacenar as cordas na matriz. Este foi un problema. 

Non debe sobreescribir Joey, e nós xa visto que podemos obter un agrupamento problemas se nós intentamos e paso e mediante sonda. Pero e se nós só unha especie de tratar isto do mesmo xeito, non? É como engadir un elemento á cabeza dunha lista ligada. Imos espazo só malloc para Phoebe. 

Digamos próximos punteiro puntos Phoebe ao antigo xefe da lista ligada, e, a continuación, só 6 apunta á novo xefe da lista ligada. E agora mira, nós cambiamos Phoebe in. Agora podemos almacenar dous elementos con hashcode 6, e non temos ningún problema. 

Iso é moi fermoso todo existe ao fío. E fío é sempre o método que é vai ser máis eficaz para se está almacenando datos nunha táboa hash. Pero esta combinación de matrices e listas ligadas en conxunto para formar unha táboa hash realmente mellora notablemente a súa capacidade para almacenar grandes cantidades de datos, e moi rapidamente e eficiente buscar por medio de que os datos. 

Aínda hai unha estrutura de datos por aí que pode ata ser un pouco mellor en termos de garantía que a nosa inserción, exclusión e mirar para arriba as horas son aínda máis rápido. E nós imos ver que nun vídeo no intentos. Eu son Doug Lloyd, este é CS50.