[Música tocando] DOUG LLOYD: Até agora você sabe muito sobre arrays, e você sabe muito sobre listas ligadas. E nós discutir a prós e contras, temos discutido que ligava listas pode ficar maior e menor, mas elas ocupam mais tamanho. Arrays são muito mais simples de usar, mas eles são restritivos, na medida em como temos de definir o tamanho da o array no início e então nós está preso com ele. 

Mas isso é, nós temos praticamente esgotado todos os nossos temas sobre listas ligadas e matrizes. Ou não é? Talvez possamos fazer algo ainda mais criativo. E esse tipo de empresta a idéia de uma tabela hash. 

Assim, em uma tabela hash vamos tentar combinar uma matriz com uma lista ligada. Nós vamos ter as vantagens da matriz, como a de acesso aleatório, ser capaz de simplesmente ir a matriz elemento 4 ou matriz elemento 8 sem ter que interagir transversalmente. Isso é muito rápido, certo? 

Mas também queremos ter nossos dados estrutura capaz de aumentar e diminuir. Nós não precisamos, nós não pretende ser restrita. E nós queremos ser capazes para adicionar e remover as coisas muito facilmente, o que se você se lembra, é muito complexo, com uma matriz. E nós podemos chamar isso de coisa nova uma tabela hash. 

E, se implementada corretamente, estamos espécie de tomar as vantagens de ambos os dados estruturas que você já viu, matrizes e listas ligadas. A inserção pode começar a tendem a teta de uma. Theta não temos realmente discutido, mas é apenas o caso teta média, o que realmente vai acontecer. Você nem sempre vai tem o pior cenário, e você não está indo sempre ter o melhor cenário, então o que é o cenário de média? 

Bem uma inserção média em uma tabela hash pode começar a chegar perto de tempo constante. E eliminação pode obter fechar com o tempo constante. E pesquisa pode obter fechar com o tempo constante. That's-- não temos um conjunto de dados estrutura ainda que pode fazer isso, e por isso este já soa como uma coisa muito grande. Nós realmente mitigados o desvantagens de cada um por conta própria. 

Para obter este desempenho atualizar, porém, temos Precisamos repensar como podemos adicionar de dados na estrutura. Especificamente queremos que o dados em si para nos dizer onde ele deve ir na estrutura. E se nós então precisamos ver se ele está em a estrutura, se precisamos encontrá-lo, nós queremos olhar para os dados de novo e ser capaz de eficazmente, usando os dados, acessá-lo de forma aleatória. Basta olhar para o dados que devem ter uma idéia de onde exatamente estamos vai encontrá-lo na tabela de hash. 

Agora, a desvantagem de um hash mesa é que eles são realmente muito ruim em encomendar ou ordenar dados. E, de fato, se você começar para usá-los para ordenar ou classificar dados você perde toda a vantagens anteriormente teve em termos de inserção e exclusão. O tempo torna-se mais perto theta de n, e nós temos, basicamente, regrediu em uma lista ligada. E assim nós só quer usar de hash tabelas se não se preocupam se os dados são ordenados. Para o contexto em que você vai usá-los em CS50 você provavelmente não me importo que os dados são classificados. 

Assim, uma tabela hash é uma combinação de duas peças distintas com a qual estamos familiarizados. A primeira é uma função, que que costumamos chamar uma função hash. E essa função hash vai retornar algum número inteiro não negativo, que que costumamos chamar de um hashcode, OK? A segunda peça é uma matriz, que é capaz de armazenar dados do tipo que pretende colocar na estrutura de dados. Nós vamos adiar o ligada elemento da lista para agora e só começar com o básico de um hash de tabela para obter a sua cabeça em torno dele, e depois vamos talvez explodir sua mente um pouco quando nós combinar matrizes e listas de links juntos. 

A idéia básica embora é tomarmos alguns dados. Corremos que os dados através de a função hash. E assim os dados são processados e ele cospe um número, OK? E, em seguida, com o número nós apenas armazenar os dados queremos armazenar na matriz nesse local. Assim, por exemplo, temos talvez esta tabela hash de cordas. Ele tem 10 elementos em que, de modo podemos encaixar 10 cordas nele. 

Vamos dizer que queremos botar John. Então John como os dados que deseja inserir para esta tabela de hash em algum lugar. Onde é que vamos colocá-lo? Bem tipicamente com um matriz, até agora, provavelmente iria colocá-lo em ordem de localização 0. Mas agora temos essa nova função hash. 

E vamos dizer que corremos John através desta função hash e é cospe 4. Bem, isso é onde estamos vai querer colocar John. Queremos colocar João no local da matriz 4, porque se nós botar John novamente-- digamos que depois nós deseja pesquisar e ver John se existe neste haxixe mesa-- tudo o que precisamos fazer é executá-lo através do mesmo hash função, obter o número 4, e ser capaz de encontrar John imediatamente na nossa estrutura de dados. Isso é muito bom. 

Vamos dizer que nós agora fazer isso novamente, queremos botar Paul. Queremos adicionar Paul para esta tabela hash. Vamos dizer que, desta vez, corremos Paul através da função hash, o hashcode que é gerado é 6. Bem, agora podemos colocar Paul no local da matriz 6. E se nós precisamos de olhar para cima se Paul está nesta tabela hash, tudo o que precisamos fazer é executar Paul através da função hash novamente e nós estamos indo para chegar em 6º novamente. 

E então nós apenas olhar no local da matriz 6. Paul é lá? Se assim for, ele está na tabela hash. Paul não é lá? Ele não está na tabela hash. É bastante simples. 

Agora, como você define uma função hash? Bem, não há realmente nenhum limite para o número de possíveis funções hash. Na verdade há um número de realmente, realmente bons na internet. Há um número de realmente, realmente ruins na internet. É também muito fácil para escrever um mau. 

Então, o que faz um bom função hash, certo? Bem uma boa função hash deve usar somente os dados que estão sendo hash, e todos os dados a ser hash. Então, nós não deseja usar anything-- nós não incorporar qualquer coisa outra coisa que não seja os dados. E nós queremos usar todos os dados. Nós não queremos usar apenas um pedaço disso, nós queremos usar tudo isso. A função hash deve também ser determinista. O que isso significa? Bem, isso significa que cada vez que passar a mesma peça exata de dados para a função hash sempre obter o mesmo hashcode para fora. Se eu passar para o John função hash eu saio 4. Eu deveria ser capaz de fazer isso 10.000 vezes e eu sempre terá 4. Assim, não números aleatórios de forma eficaz pode ser envolvido em nosso hash de tables-- em nossas funções hash. 

A função hash deve também uniformemente distribuir dados. Se cada vez que você executar dados através do função hash que você obtenha o hashcode 0, que provavelmente não é tão grande, certo? Você provavelmente vai querer grande uma gama de códigos de hash. Também coisas podem se espalhar ao longo do quadro. E também seria ótimo se realmente dados semelhantes, como John e Jonathan, talvez foram espalhados para pesar locais diferentes na tabela de hash. Isso seria uma boa vantagem. 

Aqui está um exemplo de uma função hash. Eu escrevi este mais cedo. Não é um particularmente boa função hash por motivos que não o fazem realmente Urso que vai para agora. Mas você vê o que está acontecendo aqui? Parece que estamos declarando uma variável chamado de soma e defini-la igual a 0. E então, aparentemente, eu estou fazendo algo contanto que strstr [j] não é igual a barra invertida 0. O que estou fazendo lá? 

Este é basicamente apenas um outro forma de implementar [? strl?] e detectar quando você tem chegou ao fim da cadeia. Então, eu não tenho que, na verdade, calcular o comprimento da corda, Eu só estou usando quando eu bati o barra invertida 0 personagem que eu sei Cheguei ao fim da cadeia. E então eu vou continuar iteração através dessa cadeia, adicionando strstr [j] a soma, e, em seguida, no final do dia vai voltar soma mod HASH_MAX. 

Basicamente tudo isso de hash função está fazendo é somando todos os valores de ASCII minha corda, e então é voltar algum hashcode modded por HASH_MAX. É provavelmente o tamanho da minha matriz, certo? Eu não quero estar ficando de hash códigos se minha matriz é de tamanho 10, Eu não quero ser como chegar códigos de hash para fora 11, 12, 13, eu não posso colocar as coisas em esses locais da matriz, que seria ilegal. Eu sofrer uma falha de segmentação. 

Agora, aqui é outra rápida de lado. Geralmente você provavelmente não vai quer escrever suas próprias funções hash. É realmente um pouco de uma arte, não uma ciência. E há muito que vai para eles. A internet, como eu disse, está cheio de realmente bons funções hash, e você deve usar a internet para encontrar funções hash porque é realmente apenas uma espécie de um desnecessário desperdício de tempo para criar o seu próprio. 

Você pode escrever mais simples para fins de teste. Mas quando você realmente está indo para iniciar hash dados e armazená-lo em uma tabela hash que você é provavelmente vai querer utilizar algumas das funções que foi gerado para você, que existe na internet. Se você só não se esqueça para citar suas fontes. Não há nenhuma razão para plagiar qualquer coisa aqui. 

A comunidade de ciência da computação é definitivamente crescendo, e realmente valores open source, e é realmente importante para citar suas fontes para que as pessoas pode obter para atribuição o trabalho que eles estão fazendo para o benefício da comunidade. Portanto, seja sempre sure-- e não apenas para haxixe funções, mas geralmente quando você usar o código de uma fonte externa, sempre citar sua fonte. Dê crédito para a pessoa que fez algum do trabalho para que você não precisa. 

OK, então vamos voltar a esta tabela hash para um segundo. Este é onde paramos off depois inserimos John e Paul para esta tabela hash. Você vê um problema aqui? Você pode ver dois. Mas, em particular, fazer você veja este possível problema? 

E se eu botar Ringo, e Acontece que após o processamento que os dados através da função hash Ringo também gerou o hashcode 6. Eu já tenho os dados no hashcode-- localização matriz 6. Por isso, provavelmente vai ser um pouco de um problema para mim agora, certo? 

Chamamos isso de uma colisão. E a colisão ocorre quando dois pedaços de dados percorrem o mesmo hash função de produzir o mesmo código hash. Presumivelmente, ainda queremos obter tanto pedaços de dados para a tabela hash, caso contrário, não estaria correndo Ringo arbitrariamente através da função hash. Nós presumivelmente deseja obter Ringo para essa matriz. 

Como podemos fazê-lo, porém, se ele e Paul ambos rendimento hashcode 6? Nós não queremos substituir Paul, queremos Paul estar lá também. Por isso, precisamos encontrar uma maneira de obter elementos para a tabela hash que ainda preserva a nossa rápida inserção e rápido olhar para cima. E uma maneira de lidar com isso é para fazer algo chamado linear sondagem. 

Usando este método, se temos um colisão, bem, o que vamos fazer? Bem, não podemos colocá-lo no local da matriz 6, ou o que quer hashcode foi gerado, vamos colocá-lo em hashcode mais 1. E se isso é deixar de cheia colocá-lo em hashcode mais 2. O benefício de este ser se ele é não exatamente onde nós pensamos que ele é, e nós temos que começar a procurar, talvez a gente não tem que ir longe demais. Talvez a gente não tem que procurar todos os elementos n da tabela hash. Talvez a gente tem que procurar um par deles. 

E assim nós ainda estamos tendendo para Nesse caso, média de perto de 1 vs perto de n, talvez por isso que vou trabalhar. Então, vamos ver como isso pode exercitar-se realidade. E vamos ver se talvez possamos detectar o problema que possa ocorrer aqui. 

Vamos dizer que o hash Bart. Então, agora nós estamos indo para executar um novo conjunto de cordas através da função hash, e corremos Bart através do hash função, temos hashcode 6. Vamos dar uma olhada, vemos 6 é vazio, para que possamos colocar Bart lá. 

Agora vamos botar Lisa e que também gera hashcode 6. Bem, agora que estamos usando esta método que começam em 6 linear sondagem, vemos que 6 está cheio. Não podemos colocar em 6 Lisa. Então, para onde vamos? Vamos para 7. 7 de vazio, de modo que funciona. Então, vamos colocar Lisa lá. 

Agora vamos botar para Homer e temos 7. OK bem sabemos que 7 do total agora, por isso não podemos colocar Homer lá. Então vamos a 8. É 8 está disponível? Sim, e 8 de perto de 7, por isso, se temos de começar a procurar estamos não vai ter que ir longe demais. E assim vamos colocar Homer às 8. 

Agora vamos botar para Maggie e retorna 3, graças a Deus somos capazes de simplesmente colocar Maggie lá. Nós não temos que fazer qualquer tipo de sondagem para isso. Agora vamos botar Marge, e Marge também retorna 6. 

Bem 6 está cheio, 7 é completa, 8 é cheio, 9, tudo bem graças a Deus, 9 está vazio. Eu posso colocar Marge, às 9. Já podemos ver que estamos começando para ter este problema em que agora estamos começando a esticar coisas tipo de longe de seus códigos de hash. E essa teta de 1, essa média caso de ser de tempo constante, está começando a ficar um pouco more-- começando a tendência um pouco mais no sentido de n teta. Estamos começando a perder essa vantagem de tabelas de hash. 

Este problema que acabamos de ver é algo chamado de agrupamento. E o que é realmente ruim sobre agrupamento é que uma vez que você agora tem dois elementos que estão lado a o outro torna-se ainda mais provável, você tem o dobro da oportunidade, que você está indo para ter uma outra colisão com esse cluster, eo cluster irá crescer a um. E você vai continuar crescendo e crescendo a sua probabilidade de ter uma colisão. E, eventualmente, ele é tão ruim como não a classificação dos dados de todo. 

O outro problema, porém, é que Ainda assim, até agora e, até este ponto, temos sido apenas uma espécie de compreender o que é uma tabela hash, nós ainda só tem espaço para 10 cordas. Se queremos continuar para hash os cidadãos de Springfield, só podemos obter 10 deles lá. E se nós tentamos e adicione um 11º ou 12º, não temos um lugar para colocá-los. Nós só poderia ser girando em torno de círculos tentando encontrar um lugar vazio, e nós talvez ficar preso em um loop infinito. 

Portanto, este tipo de empresta ao idéia de algo chamado de encadeamento. E este é o lugar onde nós estamos indo para trazer listas ligadas volta para a imagem. E se em vez de armazenar apenas os dados em si na matriz, cada elemento da matriz poderia realizar múltiplas peças de dados? Bem, isso não faz sentido, certo? Sabemos que uma matriz só pode hold-- cada elemento de uma matriz só pode conter uma peça de dados desse tipo de dados. 

Mas e se esse tipo de dados é uma lista ligada, certo? Então, o que se cada elemento da matriz foi um ponteiro para a cabeça de uma lista vinculada? E então nós poderíamos construir essas listas ligadas e cultivá-las arbitrariamente, porque listas ligadas permitir nos a crescer e encolher muito mais flexibilidade do que uma matriz faz. Então, o que se usam agora, aproveitamos isso, certo? Começamos a crescer estas cadeias fora desses locais matriz. 

Agora podemos encaixar um infinito quantidade de dados, ou não é infinito, uma quantidade arbitrária de dados, em nossa tabela hash sem nunca correr em o problema da colisão. Nós também eliminamos agrupamento, fazendo isso. E bem sabemos que quando nós inserimos em uma lista ligada, se você se lembra do nosso vídeo sobre listas ligadas, isoladamente listas ligadas e listas duplamente vinculadas, é uma operação de tempo constante. Nós estamos apenas adicionando para a frente. 

E para olhar para cima, bem sabemos que olhar para cima em uma lista encadeada pode ser um problema, certo? Temos que pesquisar -lo do começo ao fim. Não há nenhuma aleatório acesso em uma lista vinculada. Mas se, em vez de ter um ligado lista onde uma pesquisa seria O de n, agora temos 10 listas ligadas, ou 1.000 listas ligadas, agora é O de n dividido por 10, ou O de n dividido por 1,000. 

E enquanto nós estávamos falando teoricamente sobre a complexidade desconsiderarmos constantes, no real mundo estas coisas realmente importa, certo? Nós, na verdade, vai notar que isto acontece para executar 10 vezes mais rápido, ou 1.000 vezes mais rápida, porque nós estamos distribuindo uma longa cadeia em toda 1.000 cadeias menores. E assim cada vez que tem que procurar através de uma daquelas correntes que nós podemos ignorar as 999 cadeias de nós não nos importamos aproximadamente, e basta procurar aquele. 

Que é, em média, ser 1000 vezes mais curto. E assim nós ainda são uma espécie de tendendo para este caso médio de ser de tempo constante, mas só porque estamos alavancando dividindo-se por um enorme fator constante. Vamos ver como isso pode realmente olhar embora. Portanto, esta foi a tabela hash tivemos antes que declarou uma tabela hash que era capaz de armazenar 10 cordas. Nós não vamos mais fazer isso. Nós já sabemos o limitações desse método. Agora a nossa tabela de hash vai ser uma matriz de 10 nós, ponteiros aos chefes de listas ligadas. 

E agora é nulo. Cada um desses 10 ponteiros é nulo. Não há nada em nossa hash de tabela agora. 

Agora vamos começar a colocar alguns coisas para esta tabela hash. E vamos ver como esse método é vai nos beneficiar um pouco. Vamos agora botar Joey. Vamos irá executar a seqüência de Joey através uma função hash e voltamos 6. Bem, o que fazemos agora? 

Bem, agora trabalhando com listas ligadas, nós não estamos trabalhando com arrays. E quando estamos trabalhando com listas ligadas nós sabemos que precisamos para começar dinamicamente alocação de espaço e construção de cadeias. Isso é uma espécie de how-- aqueles são o núcleo elementos de construção de uma lista ligada. Então, vamos dinamicamente alocar espaço para Joey, e, em seguida, vamos adicioná-lo à cadeia. 

Então agora veja o que temos feito. Quando o hash Joey temos o hashcode 6. Agora o ponteiro no local da matriz 6 aponta para a cabeça de uma lista ligada, e agora é a única elemento de uma lista ligada. E em que o nó lista ligada é Joey. 

Então, se nós precisamos de olhar para cima Joey depois, nós apenas o hash Joey de novo, temos 6 novamente porque a nossa função hash é determinista. E então começamos na cabeça da lista ligada apontou a matriz por localização 6, e nós podemos fazer uma iteração do outro lado que tentar encontrar Joey. E se nós construirmos nosso Tabela de Hash de forma eficaz, e nossa função hash de forma eficaz para distribuir dados bem, em média, cada um dos aqueles ligados listas em cada local da matriz será de 1/10 do tamanho de se só tinha ele como um único grande lista ligada com tudo na mesma. 

Se distribuir esse enorme ligado lista em 10 listas ligadas cada lista será de 1/10 do tamanho. E, portanto, 10 vezes mais rápido pesquisar. Então vamos fazer isso de novo. Vamos agora botar Ross. 

E digamos que Ross, quando fazemos isso o código de hash voltarmos é 2. Bem, agora vamos alocar dinamicamente um novo nó, colocamos Ross nesse nó, e dizemos agora local da matriz 2, em vez de apontar para null, aponta para a cabeça de um ligado lista cujo único nó é Ross. E nós podemos fazer isso mais uma vez, nós pode botar para Rachel e obter hashcode 4. malloc um novo nó, coloque em Rachel o nó, e dizer um local matriz 4 agora aponta para a cabeça de uma lista ligada cujo único elemento passa a ser Rachel. 

OK, mas o que acontece se temos uma colisão? Vamos ver como lidamos com colisões utilizando o método de encadeamento separado. Vamos botar Phoebe. Ficamos com a hashcode 6. Em nosso exemplo anterior estávamos apenas armazenar as cordas na matriz. Este foi um problema. 

Nós não deve sobrescreve Joey, e nós já visto que podemos obter algum agrupamento problemas se nós tentamos e passo e através de sonda. Mas e se nós apenas uma espécie de tratar isso da mesma maneira, certo? É como adicionar um elemento para a cabeça de uma lista ligada. Vamos espaço apenas malloc para Phoebe. 

Vamos dizer próximos ponteiro pontos de Phoebe para o antigo chefe da lista ligada, e, em seguida, apenas 6 aponta para a novo chefe da lista ligada. E agora olha, nós mudamos Phoebe in. Agora podemos armazenar dois elementos com hashcode 6, e não temos quaisquer problemas. 

Isso é muito bonito tudo existe ao encadeamento. E encadeamento é definitivamente o método que é vai ser mais eficaz para você se você está armazenando dados em uma tabela hash. Mas esta combinação de matrizes e listas ligadas em conjunto para formar uma tabela hash realmente melhora drasticamente a sua capacidade para armazenar grandes quantidades de dados, e muito rapidamente e eficientemente procurar por meio de que os dados. 

Ainda há mais uma estrutura de dados lá fora que pode até ser um pouco melhor em termos de garantia que a nossa inserção, exclusão e olhar para cima os tempos são ainda mais rápido. E nós vamos ver que em um vídeo no tentativas. Eu sou Doug Lloyd, este é CS50.