O que é Hashing?
Um hash é um valor de comprimento fixo e é gerado por meio de uma fórmula matemática. Os valores de hash são usados na compactação de dados, criptologia, etc. Na indexação de dados, os valores de hash são usados porque têm tamanho de comprimento fixo, independentemente dos valores usados para gerá-los. Faz com que os valores de hash ocupem um espaço mínimo em comparação com outros valores de comprimentos variados.
Uma função hash emprega um algoritmo matemático para converter a chave em um hash. Uma colisão ocorre quando uma função hash produz o mesmo valor hash para mais de uma chave.
Neste tutorial de algoritmo, você aprenderá:
- O que é Hashing?
- O que é uma tabela de hash?
- Funções Hash
- Qualidades de uma boa função hash
- Colisão
- Operações de tabela de hash
- Exemplo de Hash Table Python
- Explicação do código da tabela de hash
- Exemplo de dicionário Python
- Análise de Complexidade
- Aplicativos do mundo real
- Vantagens das tabelas de hash
- Desvantagens das tabelas de hash
O que é uma tabela de hash?
A HASH TABLE é uma estrutura de dados que armazena valores usando um par de chaves e valores. Cada valor é atribuído a uma chave exclusiva que é gerada usando uma função hash.
O nome da chave é usado para acessar seu valor associado. Isso torna a pesquisa de valores em uma tabela hash muito rápida, independentemente do número de itens na tabela hash.
Funções Hash
Por exemplo, se quisermos armazenar registros de funcionários, e cada funcionário for identificado exclusivamente por meio de um número de funcionário.
Podemos usar o número do funcionário como chave e atribuir os dados do funcionário como valor.
A abordagem acima exigirá espaço livre extra da ordem de (m * n 2 ), onde a variável m é o tamanho da matriz e a variável n é o número de dígitos do número do funcionário. Essa abordagem apresenta um problema de espaço de armazenamento.
Uma função hash resolve o problema acima obtendo o número do funcionário e usando-o para gerar um valor inteiro hash, dígitos fixos e otimizando o espaço de armazenamento. O objetivo de uma função hash é criar uma chave que será usada para fazer referência ao valor que queremos armazenar. A função aceita o valor a ser salvo e usa um algoritmo para calcular o valor da chave.
A seguir está um exemplo de uma função hash simples
h(k) = k1 % m
AQUI,
- h (k) é a função hash que aceita um parâmetro k. O parâmetro k é o valor para o qual desejamos calcular a chave.
- k 1 % m é o algoritmo para nossa função hash, em que k1 é o valor que queremos armazenar e m é o tamanho da lista. Usamos o operador de módulo para calcular a chave.
Exemplo
Vamos supor que temos uma lista com tamanho fixo de 3 e os seguintes valores
[1,2,3]
Podemos usar a fórmula acima para calcular as posições que cada valor deve ocupar.
A imagem a seguir mostra os índices disponíveis em nossa tabela hash.
Passo 1)
Calcule a posição que será ocupada pelo primeiro valor assim
h (1) = 1% 3
= 1
O valor 1 irá ocupar o espaço no índice 1
Passo 2)
Calcule a posição que será ocupada pelo segundo valor
h (2) = 2% 3
= 2
O valor 2 irá ocupar o espaço no índice 2
Etapa 3)
Calcule a posição que será ocupada pelo terceiro valor.
h (3) = 3% 3
= 0
O valor 3 irá ocupar o espaço no índice 0
Resultado final
Nossa tabela hash preenchida agora será a seguinte.
Qualidades de uma boa função hash
Uma boa função hash deve ter as seguintes qualidades.
- A fórmula para gerar o hash deve usar o valor dos dados a serem armazenados no algoritmo.
- A função hash deve gerar valores hash exclusivos, mesmo para dados de entrada com a mesma quantidade.
- A função deve minimizar o número de colisões. As colisões ocorrem quando o mesmo valor é gerado para mais de um valor.
- Os valores devem ser distribuídos de forma consistente em todos os hashes possíveis.
Colisão
Uma colisão ocorre quando o algoritmo gera o mesmo hash para mais de um valor.
Vejamos um exemplo.
Suponha que temos a seguinte lista de valores
[3,2,9,11,7]
Vamos supor que o tamanho da tabela hash seja 7 e usaremos a fórmula (k 1 % m) onde m é o tamanho da tabela hash.
A tabela a seguir mostra os valores de hash que serão gerados.
| Chave | Algoritmo de hash (k 1 % m) | Valor Hash |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Como podemos ver nos resultados acima, os valores 2 e 9 têm o mesmo valor de hash e não podemos armazenar mais de um valor em cada posição.
O problema fornecido pode ser resolvido usando encadeamento ou sondagem. As seções a seguir discutem o encadeamento e a verificação em detalhes.
Encadeamento
O encadeamento é uma técnica usada para resolver o problema de colisão usando listas vinculadas, cada uma com índices exclusivos.
A imagem a seguir mostra a aparência de uma lista encadeada
Ambos 2 e 9 ocupam o mesmo índice, mas são armazenados como listas vinculadas. Cada lista possui um identificador único.
Benefícios das listas encadeadas
A seguir estão os benefícios das listas encadeadas:
- Listas encadeadas apresentam melhor desempenho ao inserir dados, pois a ordem de inserção é O (1).
- Não é necessário redimensionar uma tabela hash que usa uma lista encadeada.
- Ele pode acomodar facilmente um grande número de valores, desde que haja espaço livre disponível.
Sondagem
A outra técnica usada para resolver a colisão é a sondagem. Ao usar o método de sondagem, se ocorrer uma colisão, podemos simplesmente seguir em frente e encontrar um slot vazio para armazenar nosso valor.
A seguir estão os métodos de sondagem:
| Método | Descrição |
| Sondagem Linear | Tal como o nome sugere, este método procura slots vazios linearmente a partir da posição onde ocorreu a colisão e avançando. Se o fim da lista for alcançado e nenhum slot vazio for encontrado. A sondagem começa no início da lista. |
| Sondagem quadrática | Este método usa expressões polinomiais quadráticas para encontrar o próximo slot livre disponível. |
| Hashing duplo | Essa técnica usa um algoritmo de função hash secundária para encontrar o próximo slot livre disponível. |
Usando nosso exemplo acima, a tabela de hash após o uso de sondagem teria a seguinte aparência:
Operações de tabela de hash
Aqui estão as operações suportadas por tabelas Hash:
- Inserção - esta operação é usada para adicionar um elemento à tabela de hash
- Pesquisando - esta operação é usada para pesquisar elementos na tabela de hash usando a chave
- Excluindo - esta operação é usada para excluir elementos da tabela hash
Inserir operação de dados
A operação de inserção é usada para armazenar valores na tabela hash. Quando um novo valor é armazenado na tabela de hash, é atribuído um número de índice. O número do índice é calculado usando a função hash. A função hash resolve todas as colisões que ocorrem ao calcular o número do índice.
Pesquisa de operação de dados
A operação de pesquisa é usada para pesquisar valores na tabela hash usando o número do índice. A operação de pesquisa retorna o valor que está vinculado ao número do índice de pesquisa. Por exemplo, se armazenarmos o valor 6 no índice 2, a operação de pesquisa com o número de índice 2 retornará o valor 6.
Excluir operação de dados
A operação de exclusão é usada para remover um valor de uma tabela hash. Para excluir a operação é feita usando o número de índice. Depois que um valor é excluído, o número do índice é liberado. Ele pode ser usado para armazenar outros valores usando a operação de inserção.
Implementação de tabela de hash com exemplo de Python
Vejamos um exemplo simples que calcula o valor hash de uma chave
def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')
Explicação do código da tabela de hash
AQUI,
- Define uma função hash_key que aceita a chave de parâmetros e m.
- Usa uma operação de módulo simples para determinar o valor de hash
- Define uma variável m que é inicializada com o valor 7. Este é o tamanho da nossa tabela hash
- Calcula e imprime o valor hash de 3
- Calcula e imprime o valor hash de 2
- Calcula e imprime o valor hash de 9
- Calcula e imprime o valor hash de 11
- Calcula e imprime o valor hash de 7
Executar o código acima produz os seguintes resultados.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Exemplo de dicionário Python
Python vem com um tipo de dados embutido chamado Dicionário. Um dicionário é um exemplo de tabela hash. Ele armazena valores usando um par de chaves e valores. Os valores de hash são gerados automaticamente para nós e todas as colisões são resolvidas para nós em segundo plano.
O exemplo a seguir mostra como você pode usar um tipo de dados de dicionário em python 3
employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)
AQUI,
- Define um funcionário variável do dicionário. O nome da chave é usado para armazenar o valor John Doe, idade armazena 36 e posição armazena o valor Business Manager.
- Recupera o valor do nome da chave e o imprime no terminal
- Atualiza o valor da posição-chave para o valor Engenheiro de Software
- Imprime os valores do nome e posição das chaves
- Exclui todos os valores que são armazenados em nossa variável de dicionário funcionário
- Imprime o valor do funcionário
Executar o código acima produz os seguintes resultados.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Análise de Complexidade
As tabelas de hash têm uma complexidade de tempo média de O (1) no melhor cenário. O pior caso de complexidade de tempo é O (n). O pior cenário ocorre quando muitos valores geram a mesma chave hash e temos que resolver a colisão por meio de sondagem.
Aplicativos do mundo real
No mundo real, as tabelas de hash são usadas para armazenar dados para
- Bancos de dados
- Matrizes associativas
- Jogos
- Cache de memória
Vantagens das tabelas de hash
Aqui, estão os prós / benefícios de usar tabelas de hash:
- As tabelas de hash têm alto desempenho ao pesquisar dados, inserir e excluir valores existentes.
- A complexidade de tempo para tabelas hash é constante, independentemente do número de itens na tabela.
- Eles funcionam muito bem mesmo ao trabalhar com grandes conjuntos de dados.
Desvantagens das tabelas de hash
Aqui, estão os contras do uso de tabelas de hash:
- Você não pode usar um valor nulo como chave.
- As colisões não podem ser evitadas ao gerar chaves usando. funções hash. As colisões ocorrem quando uma chave que já está em uso é gerada.
- Se a função de hashing tiver muitas colisões, isso pode levar à diminuição do desempenho.
Resumo:
- As tabelas de hash são usadas para armazenar dados usando um par de chaves e valores.
- Uma função hash usa um algoritmo matemático para calcular o valor do hash.
- Uma colisão ocorre quando o mesmo valor hash é gerado para mais de um valor.
- O encadeamento resolve a colisão criando listas vinculadas.
- A investigação resolve a colisão ao encontrar slots vazios na tabela hash.
- A sondagem linear procura o próximo slot livre para armazenar o valor a partir do slot onde ocorreu a colisão.
- A sondagem quadrática usa expressões polinomiais para encontrar o próximo slot livre quando ocorre uma colisão.
- O hash duplo usa um algoritmo de função de hash secundário para encontrar o próximo slot livre quando ocorre uma colisão.
- As tabelas de hash têm melhor desempenho quando comparadas a outras estruturas de dados.
- A complexidade de tempo médio das tabelas de hash é O (1)
- Um tipo de dados de dicionário em python é um exemplo de uma tabela hash.
- As tabelas de hash suportam operações de inserção, pesquisa e exclusão.
- Um valor nulo não pode ser usado como um valor de índice.
- As colisões não podem ser evitadas em funções hash. Uma boa função hash minimiza o número de colisões que ocorrem para melhorar o desempenho.