Tabela hash na estrutura de dados: Python Exemplo

O que é Hashing?

Um hash é um valor de comprimento fixo e é gerado por meio de uma fórmula matemática. Os valores hash são usados ​​​​na compactação de dados, criptologia, etc. Na indexação de dados, os valores hash são usados ​​​​porque possuem tamanho de comprimento fixo, independentemente dos valores que foram usados ​​para gerá-los. Faz com que os valores 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.

O que é uma tabela hash?

A TABELA DE HASH é uma estrutura de dados que armazena valores usando um par de chaves e valores. Cada valor recebe uma chave exclusiva que é gerada usando uma função hash.

O nome da chave é usado para acessar seu valor associado. Isso torna a busca por valores em uma tabela hash muito rápida, independentemente do número de itens na tabela hash.

Funções de 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²) onde a variável m é o tamanho do ordem, e a variável n é o número de dígitos do número do funcionário. Esta abordagem introduz 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 hash inteiro, com dígitos fixos, otimizando o espaço de armazenamento. O objetivo de uma função hash é criar uma chave que será usada para referenciar o valor que queremos armazenar. A função recebe o valor a ser salvo e, em seguida, 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 queremos calcular a chave.
• k₁ % m é o algoritmo para nossa função hash onde 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

Podemos utilizar 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 que 1 ocupará o espaço em índice 1

Passo 2) Calcule a posição que será ocupada pelo segundo valor

h(2) = 2% 3

= 2

O valor que 2 ocupará o espaço em índice 2

Passo 3) Calcule a posição que será ocupada pelo terceiro valor.

h(3) = 3% 3

= 0

O valor que 3 ocupará o espaço em índice 0

Resultado Final

Nossa tabela hash preenchida será agora a seguinte.

Qualidades de uma boa função hash

Uma boa função hash deve ter as seguintes qualidades.

• A fórmula de geração do hash deve utilizar o valor dos dados a serem armazenados no algoritmo.
• A função hash deve gerar valores hash exclusivos, mesmo para dados de entrada que tenham 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 por 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

Vamos supor que o tamanho da tabela hash seja 7 e usaremos a fórmula (k₁ % m) onde m é o tamanho da tabela hash.

A tabela a seguir mostra os valores de hash que serão gerados.

Como podemos ver pelos resultados acima, os valores 2 e 9 possuem 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 sondagem em detalhes.

Encadeamento

Encadeamento é uma técnica usada para resolver o problema de colisão usando listas vinculadas, cada uma com índices exclusivos.

A imagem a seguir visualiza a aparência de uma lista encadeada

Tanto 2 quanto 9 ocupam o mesmo índice, mas são armazenados como listas vinculadas. Cada lista possui um identificador exclusivo.

Benefícios das listas encadeadas

A seguir estão os benefícios das listas encadeadas:

• Listas encadeadas têm melhor desempenho ao inserir dados porque 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 colisões é 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:

Usando nosso exemplo acima, a tabela hash após usar a sondagem ficaria da seguinte forma:

Operações de tabela hash

Aqui está o Operações suportadas por tabelas Hash:

• Inclusão - Esta Operação é usada para adicionar um elemento à tabela hash
• Busca - Esta Operação é usada para procurar elementos na tabela hash usando a chave
• Excluindo - Esta Operação é usada para excluir elementos da tabela hash

Inserindo operação de dados

A operação de inserção é usada para armazenar valores na tabela hash. Quando um novo valor é armazenado na tabela hash, é atribuído a ele um número de índice. O número do índice é calculado usando a função hash. A função hash resolve quaisquer 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 de í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 número de índice 2 retornará o valor 6.

Operação de exclusão de dados

A operação delete é usada para remover um valor de uma tabela hash. Para excluir o OperaA operação é feita usando o número de índice. Uma vez que um valor foi excluído, o número de índice é liberado. Ele pode ser usado para armazenar outros valores usando a operação de inserção.

Implementação de tabela hash com Python Exemplo

Vejamos um exemplo simples que calcula o valor hash de uma chave

def hash_key( key, m):
    return key % m


m = 7

print(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)}')

Tabela Hash Code Explicação

AQUI,

1. Define uma função hash_key que aceita os parâmetros key e m.
2. Usa uma operação de módulo simples para determinar o valor hash
3. Define uma variável m que é inicializada com o valor 7. Este é o tamanho da nossa tabela hash
4. Calcula e imprime o valor hash de 3
5. Calcula e imprime o valor hash de 2
6. Calcula e imprime o valor hash de 9
7. Calcula e imprime o valor hash de 11
8. Calcula e imprime o valor hash de 7

A execução do código acima produz os seguintes resultados.

The hash value for 3 is 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

Python Exemplo de dicionário

Python vem com um tipo de dados integrado chamado Dicionário. Um dicionário é um exemplo de tabela hash. Ele armazena valores usando um par de chaves e valores. Os valores hash são gerados automaticamente para nós e quaisquer colisões são resolvidas 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,

1. Define uma variável de dicionário funcionário. O nome da chave é usado para armazenar o valor John Doe, a idade armazena 36 e a posição armazena o valor Business Manager.
2. Recupera o valor do nome da chave e o imprime no terminal
3. Atualiza o valor da posição-chave para o valor Engenheiro de Software
4. Imprime os valores do nome e posição das chaves
5. Exclui todos os valores armazenados em nossa variável de dicionário funcionário
6. Imprime o valor do funcionário

A execução do 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 hash têm uma complexidade de tempo média de O (1) no melhor cenário. A complexidade de tempo do pior caso é 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.

Aplicações do mundo real

No mundo real, tabelas hash são usadas para armazenar dados para

• Bases de dados
• Matrizes associativas
• Conjuntos
• Cache de memória

Vantagens das tabelas hash

Aqui estão os prós/benefícios do uso de tabelas hash:

• As tabelas 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 quando trabalham com grandes conjuntos de dados.

Desvantagens das tabelas hash

Aqui estão os contras do uso de tabelas 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 hash tiver muitas colisões, isso pode levar à diminuição do desempenho.

Perguntas Frequentes