Visão geral da tabela de hash simples
Como atualização, uma tabela de hash é uma maneira de armazenar um valor em uma chave específica em uma estrutura de dados. Por exemplo, eu poderia armazenar valor "a"sob a chave 1e depois recuperá-lo procurando a chave 1na tabela de hash.
O exemplo mais simples de uma tabela de hash que eu consigo pensar em cima da minha cabeça é uma tabela de hash que pode armazenar apenas números inteiros, onde a chave para a entrada da tabela de hash também é o valor que está sendo armazenado. Digamos que sua tabela seja do tamanho 8 e seja basicamente uma matriz na memória:
---------------------------------
| | | | | | | | |
---------------------------------
0 1 2 3 4 5 6 7
Função Hash
As funções de hash fornecem um índice de onde armazenar seu valor. Uma função hash bastante simples para esta tabela seria adicionar 1 ao valor que você deseja armazenar e modificá- lo por 8 (o tamanho da tabela). Em outras palavras, sua função hash é (n+1)%8onde né o número inteiro que você deseja armazenar.
Inserções
Se você deseja inserir um valor nessa tabela de hash, chame sua função de hash (neste caso (n+1)%8) no valor que deseja inserir para fornecer um índice. Por exemplo, se quisermos inserir 14, chamaríamos (14 + 1) % 8e obteríamos índice 7, portanto, inseriríamos o valor no índice 7.
---------------------------------
| | | | | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Da mesma forma, podemos inserir 33, 82 e 191 da seguinte maneira:
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Colisões
Mas o que acontece se tentarmos inserir algo que colidiria com uma entrada? 2 deve ir no índice 3, mas é adotado por 82. Existem várias maneiras de resolver esse problema, a mais simples é chamar nossa função hash repetidas vezes até encontrarmos um espaço vazio.
Portanto, a lógica é a seguinte:
- (2 + 1)% 8 = 3
- O índice 3 está cheio
- Conecte 3 novamente à nossa função hash. ( 3 + 1)% 8 = 4 , que está vazio.
- Coloque nosso valor no índice 4 .
Agora a tabela de hash se parece com isso, com o valor 2 armazenado no índice 4.
---------------------------------
|191| |33 |82 |2 | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
A desvantagem desta solução é que, em breve, nossa mesa ficará cheia! Se você souber que o tamanho dos dados é limitado, isso não deve ser um problema, desde que sua tabela seja grande o suficiente para armazenar todos os valores possíveis. Se você quiser aguentar mais, poderá lidar com colisões de maneira diferente. Vamos voltar para onde estávamos antes de inserir 2.
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Se você se lembra, (2+1)%8nos dá o índice 3, que é usado. Se você não deseja que sua tabela de hash seja preenchida, você pode usar cada índice de tabela como uma lista vinculada e anexá-la à lista nesse índice. Então, em vez de chamar a função hash novamente, simplesmente anexamos à lista no índice 3:
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Essa lista pode crescer tanto quanto a memória permitir. Eu posso inserir 18 e ele será anexado a 2:
-----
|18 |
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Pesquisas
A pesquisa de valores em sua tabela de hash é rápida, pois sua tabela de hash é de um tamanho bastante grande. Você simplesmente chama sua função hash e obtém o índice. Digamos que você queira ver se o 82 está na sua mesa. A função de pesquisa chamaria (82+1)%8= 3e examinaria o item no índice 3e o retornaria para você. Se você pesquisou 16, a função de pesquisa procuraria no índice 1e verificaria que ela não existe.
As pesquisas também precisam lidar com colisões!
Se você tentar procurar o valor 2, sua tabela de hash teria que usar a mesma lógica de colisão usada para armazenar os dados e para recuperá-los. Dependendo da maneira como sua tabela de hash funciona, você deve fazer o hash da chave repetidamente até encontrar a entrada que procura (ou encontrar um espaço em branco) ou percorrer a lista vinculada até encontrar o item (ou chegou ao fim da lista)
Sumário
Portanto, as tabelas de hash são uma boa maneira de armazenar e acessar pares de valores-chave rapidamente. Neste exemplo, usamos a mesma chave que o valor, mas nas tabelas de hash do mundo real, as chaves não são tão limitadas. As funções de hash funcionarão nas teclas para gerar um índice e, em seguida, a chave / valor poderá ser armazenada nesse índice. As tabelas de hash não devem ser iteradas, embora seja possível. Como você pode ver, as tabelas de hash podem ter muitos espaços em branco, e a iteração através deles seria uma perda de tempo. Mesmo que a tabela de hash tenha lógica para ignorar pesquisas de espaço em branco em seu iterador, você seria mais adequado usando uma estrutura de dados projetada para iteradores, como listas vinculadas.
Imagine uma biblioteca com milhares de livros. Você precisa organizar os livros para encontrar cada um deles por título o mais rápido possível.
Uma maneira (comum) de fazer isso é ordenar os livros em ordem alfabética. Se o seu título começar com dizer "G", você encontrará a área "G", procure a segunda letra, diga "ö", depois "d", "e", "l", restringindo sua pesquisa e assim por diante. , até encontrar o livro. Porém, isso pode levar muito tempo e, além disso, quando novos livros chegam, às vezes você precisa reorganizar seu layout para dar espaço para os recém-chegados.
Essa é a pesquisa binária. É bom.
Existe, no entanto, uma maneira mais rápida de fazer isso. Digamos que você enumere todas as estantes e prateleiras e, em seguida, para cada livro, calcule um número especial, espero que único, que mapeie para uma estante / estante onde o livro deve ser encontrado. A maneira como você calcula a "chave" não importa muito, desde que dê um número de aparência aleatória. Por exemplo, você pode adicionar códigos de caracteres de todas as letras no título e depois dividi-lo por algum número primo (possivelmente não o melhor método, mas funciona de qualquer maneira).
Isso é hash. É muito mais rápido, porque você não precisa passar por estantes e estantes inteiras procurando a próxima letra no título. Hashing é geralmente uma operação de uma só vez, a menos que você tenha uma "colisão" quando dois ou mais livros resolverem a mesma chave. Mas tudo bem, você sabe que eles ficam próximos um do outro e, dependendo da qualidade da função hash, não deve haver muitos na mesma chave.
As tabelas de hash têm algumas limitações e caprichos (reformulação / redimensionamento), que mantêm a pesquisa binária como um concorrente viável. Nem tudo é preto e branco em relação a qual método é melhor. Mas essa é uma história diferente.
PS Desculpe por não responder sua pergunta diretamente (escreva uma tabela de hash em PHP), mas isso é detalhes e se chama "programação";)
fonte
A tabela de hash em PHP, no que diz respeito a meu conhecimento, é simplesmente implementada por meio de:
Você acessa os dados por meio de chamadas como:
Você usa a função foreach () para iterar sobre o conteúdo da matriz.
A melhor maneira de entender as tabelas de hash é ler algo como http://en.wikipedia.org/wiki/Hash_table , mas, basicamente, tudo se resume a isso: o lado esquerdo de cada linha dentro dessa chamada de array () são as chaves . Essas chaves serão submetidas a um cálculo de hash e o resultado será um hash. Você provavelmente já viu hashes MD5 ou SHA antes, é bem parecido com isso. Uma parte específica desse hash, normalmente os primeiros caracteres X, mas às vezes o hash completo, será usada para identificar os chamados 'buckets', que são as áreas de armazenamento para os valores (no lado direito).
Então, sempre que você acessar sua hashtable, use a chave para obter o valor. A chave é calculada para um hash novamente e o hash é usado para procurar rapidamente o valor associado. Portanto, as tabelas de hash permitem uma pesquisa mais rápida do que apenas pesquisar linearmente se tudo estiver armazenado. A única desvantagem é que algumas implementações de hash sofrem colisões, que é o mesmo hash calculado para duas chaves diferentes. Em geral, não é algo com que você precise se preocupar muito.
Espero que isso forneça alguns antecedentes, mas tente ler mais sobre o assunto, se você estiver interessado. Minha explicação é muito rudimentar e tenho certeza de que há buracos suficientes, mas deve bastar para uma explicação rápida.
fonte