Estou procurando uma explicação de como uma tabela de hash funciona - em inglês simples para um simplório como eu!

Por exemplo, eu sei que ele pega a chave, calcula o hash (estou procurando uma explicação de como) e, em seguida, executa algum tipo de módulo para descobrir onde fica o array onde o valor é armazenado, mas é aí que meu conhecimento para .

Alguém poderia esclarecer o processo?

Edit: Eu não estou perguntando especificamente sobre como os códigos de hash são calculados, mas uma visão geral de como uma tabela de hash funciona.

Aqui está uma explicação nos termos do leigo.

Vamos supor que você queira preencher uma biblioteca com livros e não apenas colocá-los lá, mas você poderá encontrá-los facilmente novamente quando precisar.

Então, você decide que, se a pessoa que deseja ler um livro conhece o título do livro e o título exato a ser inicializado, isso é tudo o que deve ser necessário. Com o título, a pessoa, com a ajuda do bibliotecário, deve encontrar o livro com facilidade e rapidez.

Então, como você pode fazer isso? Bem, obviamente, você pode manter algum tipo de lista de onde você coloca cada livro, mas então você tem o mesmo problema de pesquisar na biblioteca, é necessário pesquisar na lista. Concedido, a lista seria menor e mais fácil de pesquisar, mas você ainda não deseja pesquisar sequencialmente de uma extremidade da biblioteca (ou lista) para a outra.

Você quer algo que, com o título do livro, possa lhe dar o lugar certo de uma só vez, então tudo o que você precisa fazer é apenas caminhar até a prateleira certa e pegar o livro.

Mas como isso pode ser feito? Bem, com um pouco de premeditação quando você enche a biblioteca e muito trabalho quando você enche a biblioteca.

Em vez de apenas começar a encher a biblioteca de uma extremidade à outra, você cria um método pequeno e inteligente. Você pega o título do livro, executa-o através de um pequeno programa de computador, que cospe um número de prateleira e um número de slot nessa prateleira. É aqui que você coloca o livro.

A vantagem desse programa é que, mais tarde, quando uma pessoa voltar para ler o livro, você passará o título pelo programa mais uma vez e receberá o mesmo número de prateleira e slot que você recebeu originalmente, e isso é onde o livro está localizado.

O programa, como outros já mencionaram, é chamado de algoritmo de hash ou cálculo de hash e geralmente funciona com os dados inseridos nele (o título do livro nesse caso) e calcula um número a partir dele.

Para simplificar, digamos que apenas converta cada letra e símbolo em um número e resuma todos eles. Na realidade, é muito mais complicado que isso, mas vamos deixar por enquanto.

A vantagem de um algoritmo é que, se você inserir a mesma entrada repetidamente, ele continuará emitindo o mesmo número a cada vez.

Ok, então é basicamente assim que uma tabela de hash funciona.

Material técnico segue.

Primeiro, há o tamanho do número. Normalmente, a saída de um algoritmo de hash está dentro de um intervalo de um número grande, geralmente muito maior que o espaço que você tem na sua tabela. Por exemplo, digamos que temos espaço para exatamente um milhão de livros na biblioteca. A saída do cálculo de hash pode estar na faixa de 0 a um bilhão, o que é muito maior.

Então, o que fazemos? Usamos algo chamado cálculo de módulo, que basicamente diz que, se você contasse o número desejado (ou seja, o número de um bilhão), mas desejasse permanecer dentro de um intervalo muito menor, cada vez que atingisse o limite desse intervalo menor, começaria 0, mas você deve acompanhar o quão longe na grande sequência você chegou.

Digamos que a saída do algoritmo de hash esteja no intervalo de 0 a 20 e você obtém o valor 17 de um título específico. Se o tamanho da biblioteca é de apenas 7 livros, você conta 1, 2, 3, 4, 5, 6 e, quando chega a 7, começa de novo em 0. Como precisamos contar 17 vezes, temos 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3 e o número final é 3.

É claro que o cálculo do módulo não é feito dessa maneira, é feito com divisão e um restante. O restante da divisão de 17 por 7 é 3 (7 passa 2 vezes para 17 aos 14 e a diferença entre 17 e 14 é 3).

Assim, você coloca o livro no slot número 3.

Isso leva ao próximo problema. Colisões. Como o algoritmo não tem como espaçar os livros para que eles preencham exatamente a biblioteca (ou a tabela de hash, se desejar), ele sempre acaba calculando um número que foi usado anteriormente. No sentido da biblioteca, quando você chega à prateleira e ao número do slot em que deseja colocar um livro, já existe um livro.

Existem vários métodos de manipulação de colisões, incluindo a execução de dados em outro cálculo para obter outro ponto na tabela ( hash duplo ) ou simplesmente para encontrar um espaço próximo ao que você recebeu (ou seja, ao lado do livro anterior, assumindo o slot estava disponível também conhecido como sondagem linear ). Isso significa que você precisa cavar algumas coisas quando tenta encontrar o livro mais tarde, mas ainda é melhor do que simplesmente começar em uma extremidade da biblioteca.

Finalmente, em algum momento, convém colocar mais livros na biblioteca do que a biblioteca permite. Em outras palavras, você precisa construir uma biblioteca maior. Como o local exato na biblioteca foi calculado usando o tamanho exato e atual da biblioteca, segue-se que, se você redimensionar a biblioteca, poderá ter que encontrar novos locais para todos os livros desde o cálculo feito para encontrar seus locais mudou.

Espero que esta explicação seja um pouco mais prática do que baldes e funções :)

Uso e linguagem:

1. As tabelas de hash são usadas para armazenar e recuperar rapidamente dados (ou registros).
2. Os registros são armazenados em buckets usando chaves de hash
3. As chaves de hash são calculadas aplicando um algoritmo de hash a um valor escolhido (o valor da chave ) contido no registro. Este valor escolhido deve ser um valor comum para todos os registros.
4. Cada bloco pode ter vários registros organizados em uma ordem específica.

Exemplo do mundo real:

A Hash & Co. , fundada em 1803 e sem qualquer tecnologia de computador, possuía um total de 300 arquivos para manter as informações detalhadas (registros) de seus aproximadamente 30.000 clientes. Cada pasta de arquivo foi claramente identificada com seu número de cliente, um número exclusivo de 0 a 29.999.

Os funcionários da época tinham que buscar e armazenar rapidamente os registros dos clientes para a equipe de trabalho. A equipe decidiu que seria mais eficiente usar uma metodologia de hash para armazenar e recuperar seus registros.

Para arquivar um registro de cliente, os funcionários de arquivamento usariam o número exclusivo do cliente gravado na pasta. Usando esse número de cliente, eles modulavam a chave de hash em 300 para identificar o arquivo em que está contido. Quando abriam o arquivo, descobriam que ele continha muitas pastas ordenadas pelo número do cliente. Depois de identificar o local correto, eles simplesmente o inseriam.

Para recuperar um registro de cliente, os funcionários do arquivo receberiam um número de cliente em um pedaço de papel. Usando esse número de cliente exclusivo (a chave de hash ), eles o modulavam em 300 para determinar qual arquivo tinha a pasta de clientes. Quando abriam o arquivo, descobriam que ele continha muitas pastas ordenadas pelo número do cliente. Pesquisando nos registros, eles encontrariam rapidamente a pasta do cliente e a recuperariam.

Em nosso exemplo do mundo real, nossos baldes são arquivos e nossos registros são pastas de arquivos .

Uma coisa importante a lembrar é que os computadores (e seus algoritmos) lidam com números melhor do que com strings. Portanto, acessar uma grande variedade usando um índice é significativamente muito mais rápido do que acessar sequencialmente.

Como Simon mencionou, o que acredito ser muito importante, é que a parte do hash é transformar um espaço grande (de comprimento arbitrário, geralmente cadeias de caracteres, etc) e mapeá-lo para um espaço pequeno (de tamanho conhecido, geralmente números) para indexação. Isso se é muito importante lembrar!

Portanto, no exemplo acima, os 30.000 clientes possíveis são mapeados para um espaço menor.

A idéia principal disso é dividir todo o conjunto de dados em segmentos para acelerar a pesquisa real, que geralmente consome tempo. No exemplo acima, cada um dos 300 arquivos (estatisticamente) conteria (estatisticamente) cerca de 100 registros. Pesquisando (independentemente do pedido) através de 100 registros é muito mais rápido do que ter que lidar com 30.000.

Você deve ter notado que alguns já fazem isso. Mas, em vez de criar uma metodologia de hash para gerar uma chave de hash, na maioria dos casos eles simplesmente usarão a primeira letra do sobrenome. Portanto, se você possui 26 arquivos cada um contendo uma letra de A a Z, em teoria você apenas segmentou seus dados e aprimorou o processo de arquivamento e recuperação.

Espero que isto ajude,

Jeach!

Isso acaba sendo uma área bastante profunda da teoria, mas o esboço básico é simples.

Essencialmente, uma função hash é apenas uma função que pega coisas de um espaço (digamos, cadeias de comprimento arbitrário) e as mapeia para um espaço útil para indexação (inteiros não assinados, por exemplo).

Se você tiver apenas um pequeno espaço de hash, poderá interpretar essas coisas como números inteiros e pronto (por exemplo, seqüências de caracteres de 4 bytes)

Geralmente, porém, você tem um espaço muito maior. Se o espaço das coisas que você permite como chave for maior que o espaço das coisas que você está usando para indexar (seu uint32 ou qualquer outra coisa), não será possível ter um valor único para cada uma. Quando duas ou mais coisas combinam com o mesmo resultado, você terá que lidar com a redundância de maneira adequada (isso geralmente é chamado de colisão, e como você lida com ou não depende um pouco do que você é). usando o hash para).

Isso implica que você não deve ter o mesmo resultado e provavelmente também gostaria que a função hash fosse rápida.

Equilibrar essas duas propriedades (e algumas outras) manteve muitas pessoas ocupadas!

Na prática, você geralmente deve conseguir encontrar uma função que funcione bem para o seu aplicativo e usá-la.

Agora, para fazer isso funcionar como uma hashtable: Imagine que você não se importava com o uso de memória. Em seguida, você pode criar uma matriz contanto que seu conjunto de indexação (todos os uint32, por exemplo). À medida que você adiciona algo à tabela, você faz o hash da chave e observa a matriz nesse índice. Se não houver nada lá, você coloca seu valor lá. Se já houver algo lá, adicione essa nova entrada a uma lista de itens nesse endereço, juntamente com informações suficientes (sua chave original ou algo inteligente) para descobrir qual entrada realmente pertence a qual chave.

Portanto, à medida que você avança, todas as entradas em sua tabela de hashtags (a matriz) ficam vazias ou contêm uma entrada ou uma lista de entradas. A recuperação é simples como indexar na matriz e retornar o valor ou percorrer a lista de valores e retornar a correta.

Claro que na prática você normalmente não pode fazer isso, desperdiça muita memória. Então, você faz tudo com base em uma matriz esparsa (onde as únicas entradas são as que você realmente usa, todo o resto é implicitamente nulo).

Existem muitos esquemas e truques para melhorar esse trabalho, mas esse é o básico.

Muitas respostas, mas nenhuma delas é muito visual , e as tabelas de hash podem "clicar" facilmente quando visualizadas.

As tabelas de hash geralmente são implementadas como matrizes de listas vinculadas. Se imaginarmos uma tabela que armazena os nomes das pessoas, após algumas inserções, ela pode ser apresentada na memória, como abaixo, onde ()números fechados são valores de hash do texto / nome.

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Alguns pontos:

• cada uma das entradas da matriz (índices [0], [1]...) é conhecida como bucket e inicia uma lista de valores - possivelmente vazia - vinculada (também conhecida como elementos , neste exemplo - pessoas) nomes )
• cada valor (por exemplo, "fred"com hash 42) é vinculado a partir do bucket, [hash % number_of_buckets]por exemplo 42 % 10 == [2]; %é o operador do módulo - o restante quando dividido pelo número de buckets
• vários valores de dados podem colidir e ser vinculados a partir do mesmo bucket, geralmente porque seus valores de hash colidem após a operação do módulo (por exemplo 42 % 10 == [2], e 9282 % 10 == [2]), mas ocasionalmente porque os valores de hash são os mesmos (por exemplo, "fred"e "jane"ambos mostrados com o hash 42acima)
  • a maioria das tabelas de hash lida com colisões - com desempenho ligeiramente reduzido, mas sem confusão funcional - comparando o valor total (aqui texto) de um valor que está sendo procurado ou inserido com cada valor já existente na lista vinculada no intervalo de hash para depósito

Os comprimentos da lista vinculada estão relacionados ao fator de carga, não ao número de valores

Se o tamanho da tabela aumentar, as tabelas de hash implementadas como acima tendem a se redimensionar (por exemplo, criar uma matriz maior de buckets, criar listas vinculadas novas / atualizadas, excluir a matriz antiga) para manter a proporção de valores em relação aos buckets (também conhecido como load fator ) em algum lugar na faixa de 0,5 a 1,0.

Hans fornece a fórmula real para outros fatores de carga em um comentário abaixo, mas para valores indicativos: com o fator de carga 1 e uma função de hash de força criptográfica, 1 / e (~ 36,8%) de caçambas tenderão a estar vazios, outros 1 / e (~ 36,8%) tem um elemento, 1 / (2e) ou ~ 18,4%, dois elementos, 1 / (3! E) cerca de 6,1%, três elementos, 1 / (4! E) ou ~ 1,5%, quatro elementos, 1 / (5! E) ~ .3% tem cinco etc. - o comprimento médio da corrente de caçambas não vazias é de ~ 1,58, independentemente de quantos elementos houver na tabela (ou seja, se existem 100 elementos e 100 caçambas, ou 100 milhões elementos e 100 milhões de baldes), e é por isso que dizemos que procurar / inserir / apagar são O (1) operações de tempo constante.

Como uma tabela de hash pode associar chaves a valores

Dada a implementação de uma tabela de hash, conforme descrito acima, podemos imaginar a criação de um tipo de valor, como struct Value { string name; int age; };comparação de igualdade e funções de hash, que apenas olham para o namecampo (ignorando a idade) e, em seguida, algo maravilhoso acontece: podemos armazenar Valueregistros como{"sue", 63} na tabela , depois procure "processar" sem saber a idade dela, encontre o valor armazenado e recupere ou atualize a idade dela
- parabéns Sue - que curiosamente não altera o valor do hash e não exige que movamos o registro de Sue para outro balde.

Quando fazemos isso, estamos usando a tabela de hash como um contêiner associativo, também conhecido como mapa , e os valores que ele armazena podem ser considerados como uma chave (o nome) e um ou mais outros campos ainda denominados - de maneira confusa - o valor ( no meu exemplo, apenas a idade). Uma implementação de tabela de hash usada como mapa é conhecida como mapa de hash .

Isso contrasta com o exemplo anterior nesta resposta, onde armazenamos valores discretos como "sue", que você poderia considerar como sendo sua própria chave: esse tipo de uso é conhecido como um conjunto de hash .

Existem outras maneiras de implementar uma tabela de hash

Nem todas as tabelas de hash usam listas vinculadas (conhecidas como encadeamento separado ), mas as de uso geral, como a principal alternativa de hash fechado (também conhecido como endereçamento aberto ) - particularmente com operações de exclusão suportadas - tem propriedades de desempenho menos estáveis ​​com chaves propensas a colisões / funções de hash.

Algumas palavras sobre funções hash

Hash forte ...

Um objetivo geral, no pior caso, da função de hash para minimizar a colisão é pulverizar as chaves em torno dos baldes da tabela de hash efetivamente aleatoriamente, sempre gerando o mesmo valor de hash para a mesma chave. Mesmo uma mudança de bit em qualquer lugar da chave seria ideal - aleatoriamente - girar cerca de metade dos bits no valor de hash resultante.

Isso normalmente é orquestrado com a matemática muito complicada para eu grocar. Mencionarei uma maneira fácil de entender - não a mais escalável ou amigável ao cache, mas inerentemente elegante (como criptografia com um teclado único!) - pois acho que ajuda a trazer para casa as qualidades desejáveis ​​mencionadas acima. Digamos que você esteja usando hash de 64 bits double- você pode criar 8 tabelas com 256 números aleatórios (código abaixo) e usar cada fatia de 8 bits / 1 byte da doublerepresentação de memória para indexar em uma tabela diferente. números aleatórios que você procura. Com essa abordagem, é fácil ver que um pouco (no sentido dos dígitos binários) muda em qualquer lugar nos doubleresultados em que um número aleatório diferente seja procurado em uma das tabelas e um valor final totalmente não correlacionado.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

Hash fraco, mas frequentemente rápido ...

Muitas funções de hash de bibliotecas passam números inteiros sem alterações (conhecida como função trivial ou de hash de identidade ); é o outro extremo do forte hash descrito acima. Um hash de identidade é extremamentepropenso a colisões nos piores casos, mas a esperança é que, no caso bastante comum de chaves inteiras que tendem a ser incrementadas (talvez com algumas lacunas), elas sejam mapeadas em intervalos sucessivos deixando menos folhas vazias do que as aleatórias (nossa ~ 36,8 % no fator de carga 1 mencionado anteriormente), com menos colisões e menos listas vinculadas de elementos colidentes mais longas do que as obtidas por mapeamentos aleatórios. Também é ótimo economizar o tempo necessário para gerar um hash forte e, se as chaves forem pesquisadas em ordem, elas serão encontradas em blocos próximos na memória, melhorando os acertos do cache. Quando as chaves não incrementar bem, a esperança é que eles sejam aleatórios o suficiente para que não precisem de uma forte função de hash para randomizar totalmente sua colocação em baldes.

Vocês estão muito perto de explicar isso completamente, mas faltam algumas coisas. A hashtable é apenas uma matriz. A matriz em si conterá algo em cada slot. No mínimo, você armazenará o valor de hash ou o próprio valor nesse slot. Além disso, você também pode armazenar uma lista de valores vinculados / encadeados que colidiram nesse slot ou usar o método de endereçamento aberto. Você também pode armazenar um ponteiro ou ponteiros em outros dados que deseja recuperar deste slot.

É importante observar que o próprio valor do hash geralmente não indica o slot no qual colocar o valor. Por exemplo, um valor de hash pode ser um valor inteiro negativo. Obviamente, um número negativo não pode apontar para um local da matriz. Além disso, os valores de hash tendem a ser muitas vezes maiores que os slots disponíveis. Portanto, outro cálculo precisa ser realizado pela própria hashtable para descobrir em qual slot o valor deve ser inserido. Isso é feito com uma operação matemática de módulo como:

uint slotIndex = hashValue % hashTableSize;

Este valor é o slot no qual o valor será inserido. No endereçamento aberto, se o slot já estiver preenchido com outro valor de hash e / ou outros dados, a operação do módulo será executada novamente para encontrar o próximo slot:

slotIndex = (remainder + 1) % hashTableSize;

Suponho que possa haver outros métodos mais avançados para determinar o índice de slots, mas este é o mais comum que eu já vi ... estaria interessado em outros que tenham melhor desempenho.

Com o método de módulo, se você tiver uma tabela com o tamanho 1000, qualquer valor de hash entre 1 e 1000 será inserido no slot correspondente. Quaisquer valores negativos e valores maiores que 1000 estarão colidindo potencialmente os valores dos slots. As chances de que isso aconteça dependem do método de hash e do total de itens adicionados à tabela de hash. Geralmente, é uma prática recomendada tornar o tamanho da hashtable de forma que o número total de valores adicionados a ele seja apenas igual a cerca de 70% do seu tamanho. Se sua função hash fizer um bom trabalho de distribuição uniforme, geralmente você encontrará muito poucas ou nenhuma colisão de balde / slot e ela executará muito rapidamente nas operações de pesquisa e gravação. Se o número total de valores a adicionar não for conhecido antecipadamente, faça um bom palpite usando qualquer meio,

Espero que isso tenha ajudado.

PS - Em C #, o GetHashCode()método é bastante lento e resulta em colisões de valores reais sob muitas condições que testei. Para se divertir de verdade, crie sua própria função de hash e tente fazê-la NUNCA colidir com os dados específicos que você está usando, execute mais rapidamente que GetHashCode e tenha uma distribuição bastante uniforme. Fiz isso usando valores hashcode longos, em vez de int, e funcionou muito bem em até 32 milhões de valores hash na hashtable com 0 colisões. Infelizmente, não posso compartilhar o código, pois ele pertence ao meu empregador ... mas posso revelar que é possível para determinados domínios de dados. Quando você pode conseguir isso, a hashtable é MUITO rápida. :)

É assim que funciona no meu entendimento:

Aqui está um exemplo: imagine a tabela inteira como uma série de baldes. Suponha que você tenha uma implementação com códigos de hash alfanuméricos e tenha um intervalo para cada letra do alfabeto. Esta implementação coloca cada item cujo código de hash começa com uma letra específica no intervalo correspondente.

Digamos que você tenha 200 objetos, mas apenas 15 deles têm códigos de hash que começam com a letra 'B.' A tabela de hash precisaria apenas procurar e pesquisar os 15 objetos no intervalo 'B', em vez de todos os 200 objetos.

Quanto ao cálculo do código hash, não há nada de mágico nisso. O objetivo é apenas que objetos diferentes retornem códigos diferentes e objetos iguais retornem códigos iguais. Você poderia escrever uma classe que sempre retornasse o mesmo número inteiro que um código hash para todas as instâncias, mas destruiria essencialmente a utilidade de uma tabela hash, pois ela se tornaria um balde gigante.

Curto e grosso:

Uma tabela de hash envolve uma matriz, vamos chamá-la internalArray. Os itens são inseridos na matriz desta maneira:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

Às vezes, duas chaves serão hash no mesmo índice na matriz e você deseja manter os dois valores. Eu gosto de armazenar os dois valores no mesmo índice, que é simples de codificar, criando internalArrayuma matriz de listas vinculadas:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Portanto, se eu quiser recuperar um item da minha tabela de hash, eu poderia escrever:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

As operações de exclusão são tão simples de escrever. Como você pode ver, inserções, pesquisas e remoção de nossa lista de listas vinculadas é quase O (1).

Quando nossa internalArray fica muito cheia, talvez com cerca de 85% da capacidade, podemos redimensionar a matriz interna e mover todos os itens da matriz antiga para a nova matriz.

É ainda mais simples que isso.

Uma hashtable nada mais é do que uma matriz (geralmente esparsa ) de vetores que contêm pares de chave / valor. O tamanho máximo dessa matriz é geralmente menor que o número de itens no conjunto de valores possíveis para o tipo de dados que está sendo armazenado na hashtable.

O algoritmo de hash é usado para gerar um índice nessa matriz com base nos valores do item que será armazenado na matriz.

É aqui que entram os vetores de armazenamento de pares de chave / valor na matriz. Como o conjunto de valores que podem ser índices na matriz é geralmente menor que o número de todos os valores possíveis que o tipo pode ter, é possível que seu hash O algoritmo gerará o mesmo valor para duas chaves separadas. Uma boa algoritmo de hash impedirá isso o máximo possível (é por isso que ele é relegado ao tipo geralmente porque possui informações específicas que um algoritmo geral de hash não pode saber), mas é impossível impedir.

Por esse motivo, você pode ter várias chaves que gerarão o mesmo código de hash. Quando isso acontece, os itens no vetor são iterados e uma comparação direta é feita entre a chave no vetor e a chave que está sendo pesquisada. Se for encontrado, ótimo e o valor associado à chave será retornado, caso contrário, nada será retornado.

Você pega um monte de coisas e uma matriz.

Para cada coisa, você cria um índice, chamado de hash. O importante sobre o hash é que ele 'dispersa' muito; você não quer que duas coisas semelhantes tenham hashes semelhantes.

Você coloca suas coisas na matriz na posição indicada pelo hash. Mais de uma coisa pode acabar com um determinado hash, para que você armazene as coisas em matrizes ou outra coisa apropriada, que geralmente chamamos de balde.

Quando você procura as coisas no hash, segue as mesmas etapas, descobrindo o valor do hash, vendo o que há no balde nesse local e verificando se é o que você está procurando.

Quando seu hash estiver funcionando bem e sua matriz for grande o suficiente, haverá apenas algumas coisas, no máximo, em qualquer índice específico da matriz, portanto você não precisará olhar muito.

Para pontos de bônus, faça com que, quando sua tabela de hash for acessada, ela mova a coisa encontrada (se houver) para o início do bucket, para que da próxima vez seja a primeira coisa verificada.

Todas as respostas até agora são boas e abordam aspectos diferentes de como uma hashtable funciona. Aqui está um exemplo simples que pode ser útil. Digamos que queremos armazenar alguns itens com seqüências alfabéticas minúsculas como chaves.

Como Simon explicou, a função hash é usada para mapear de um espaço grande para um espaço pequeno. Uma implementação simples e ingênua de uma função hash para o nosso exemplo pode pegar a primeira letra da string e mapeá-la para um número inteiro, para que "jacaré" tenha um código hash 0, "bee" tenha um código hash 1 ", zebra "seria 25 etc.

Em seguida, temos uma matriz de 26 buckets (podem ser ArrayLists em Java) e colocamos o item no bucket que corresponde ao código de hash da nossa chave. Se tivermos mais de um item que possua uma chave que comece com a mesma letra, eles terão o mesmo código de hash, portanto, todos iriam para o bucket desse código de hash, para que uma pesquisa linear tivesse que ser feita no bucket para encontre um item em particular.

No nosso exemplo, se tivéssemos apenas algumas dúzias de itens com teclas espalhadas pelo alfabeto, isso funcionaria muito bem. No entanto, se tivéssemos um milhão de itens ou todas as chaves começassem com 'a' ou 'b', nossa tabela de hash não seria ideal. Para obter um melhor desempenho, precisaríamos de uma função de hash diferente e / ou mais buckets.

Aqui está outra maneira de ver isso.

Suponho que você entenda o conceito de uma matriz A. Isso é algo que suporta a operação de indexação, onde você pode chegar ao I-ésimo elemento, A [I], em uma única etapa, não importa o tamanho de A.

Portanto, por exemplo, se você deseja armazenar informações sobre um grupo de pessoas com idades diferentes, uma maneira simples seria ter uma matriz grande o suficiente e usar a idade de cada pessoa como um índice na matriz. Dessa forma, você pode ter acesso em uma etapa às informações de qualquer pessoa.

Mas é claro que pode haver mais de uma pessoa com a mesma idade; portanto, o que você coloca na matriz em cada entrada é uma lista de todas as pessoas que têm essa idade. Assim, você pode acessar as informações de uma pessoa em uma única etapa, além de um pouco de pesquisa nessa lista (chamada de "balde"). Só diminui a velocidade se há tantas pessoas que os baldes ficam grandes. Então você precisa de uma matriz maior e de alguma outra maneira de obter mais informações de identificação sobre a pessoa, como as primeiras letras do sobrenome, em vez de usar a idade.

Essa é a ideia básica. Em vez de usar a idade, qualquer função da pessoa que produz uma boa disseminação de valores pode ser usada. Essa é a função hash. Como se você pudesse pegar cada terço da representação ASCII do nome da pessoa, embaralhada em alguma ordem. O que importa é que você não deseja que muitas pessoas façam o hash no mesmo balde, porque a velocidade depende dos baldes permanecerem pequenos.

Como o hash é calculado geralmente não depende da hashtable, mas dos itens adicionados a ela. Em estruturas / bibliotecas de classes base, como .net e Java, cada objeto possui um método GetHashCode () (ou similar) retornando um código de hash para esse objeto. O algoritmo ideal de código hash e a implementação exata dependem dos dados representados no objeto.

Uma tabela de hash funciona totalmente no fato de que a computação prática segue o modelo da máquina de acesso aleatório, ou seja, o valor em qualquer endereço da memória pode ser acessado no tempo O (1) ou no tempo constante.

Portanto, se eu tiver um universo de chaves (conjunto de todas as chaves possíveis que eu possa usar em um aplicativo, por exemplo, número de rolo para aluno, se tiver 4 dígitos, esse universo será um conjunto de números de 1 a 9999) e um Como mapeá-los para um conjunto finito de números de tamanho, posso alocar memória no meu sistema; teoricamente, minha tabela de hash está pronta.

Geralmente, em aplicativos, o tamanho do universo de chaves é muito grande que o número de elementos que eu quero adicionar à tabela de hash (não quero desperdiçar uma memória de 1 GB em valores de hash, por exemplo, 10000 ou 100000, porque são 32 um pouco longo em reprsentaion binário). Então, usamos esse hash. É uma espécie de mistura de operação "matemática", que mapeia meu grande universo para um pequeno conjunto de valores que posso acomodar na memória. Em casos práticos, geralmente o espaço de uma tabela de hash é da mesma "ordem" (big-O) que o (número de elementos * tamanho de cada elemento). Portanto, não desperdiçamos muita memória.

Agora, um conjunto grande mapeado para um conjunto pequeno, o mapeamento deve ser muitos-para-um. Portanto, chaves diferentes serão alocadas no mesmo espaço (?? não é justo). Existem algumas maneiras de lidar com isso, eu apenas conheço as duas populares:

• Use o espaço que deveria ser alocado para o valor como uma referência a uma lista vinculada. Essa lista vinculada armazenará um ou mais valores que residem no mesmo slot em muitos para um mapeamento. A lista vinculada também contém chaves para ajudar alguém que vem pesquisar. É como muitas pessoas no mesmo apartamento, quando um entregador chega, ele vai para o quarto e pergunta especificamente pelo cara.
• Use uma função hash dupla em uma matriz que forneça a mesma sequência de valores todas as vezes, em vez de um único valor. Quando vou armazenar um valor, vejo se o local de memória necessário está livre ou ocupado. Se for gratuito, posso armazenar meu valor lá, se estiver ocupado, pego o próximo valor da sequência e assim por diante até encontrar um local livre e armazenar meu valor lá. Ao pesquisar ou recuperar o valor, volto ao mesmo caminho indicado pela sequência e, em cada local, solicito o valor se ele estiver lá até encontrá-lo ou pesquiso todos os locais possíveis na matriz.

Introdução aos algoritmos pelo CLRS fornece uma visão muito boa sobre o tópico.

Para todos aqueles que procuram linguagem de programação, aqui está como isso funciona. A implementação interna de tabelas de hash avançadas possui muitos meandros e otimizações para alocação / desalocação e pesquisa de armazenamento, mas a ideia de nível superior será praticamente a mesma.

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

Onde calculate_bucket_from_val() está a função de hash, onde toda a mágica da singularidade deve acontecer.

A regra geral é: Para que um determinado valor seja inserido, o bucket deve ser ÚNICO E DERIVÍVEL DO VALOR que ele deve ARMAZENAR.

Bucket é qualquer espaço em que os valores são armazenados - pois aqui eu o mantive int como um índice de matriz, mas talvez também um local de memória.