Hashing na estrutura de dados: função, técnicas [com exemplos]

Introdução

Hashing é uma importante estrutura de dados projetada para resolver o problema de encontrar e armazenar dados de forma eficiente em uma matriz. Por exemplo, se você tiver uma lista de 20.000 números e tiver dado um número para pesquisar nessa lista, você examinará cada número na lista até encontrar uma correspondência.

Requer uma quantidade significativa de seu tempo para pesquisar em toda a lista e localizar esse número específico. Este processo manual de digitalização não é apenas demorado, mas também ineficiente. Com o hashing na estrutura de dados, você pode restringir a pesquisa e encontrar o número em segundos.

Este blog fornecerá uma compreensão mais profunda do método de hash, tabelas de hash e sondagem linear com exemplos.

O que é Hashing na Estrutura de Dados?

Hashing na estrutura de dados é uma técnica de mapeamento de um grande pedaço de dados em pequenas tabelas usando uma função de hash. Também é conhecida como função de resumo da mensagem. É uma técnica que identifica exclusivamente um item específico de uma coleção de itens semelhantes.

Ele usa tabelas de hash para armazenar os dados em um formato de matriz. Cada valor na matriz atribuiu um número de índice exclusivo. As tabelas de hash usam uma técnica para gerar esses números de índice exclusivos para cada valor armazenado em um formato de matriz. Essa técnica é chamada de técnica de hash.

Você só precisa encontrar o índice do item desejado, em vez de encontrar os dados. Com a indexação, você pode escanear rapidamente toda a lista e recuperar o item desejado. A indexação também ajuda na inserção de operações quando você precisa inserir dados em um local específico. Não importa quão grande ou pequena seja a tabela, você pode atualizar e recuperar dados em segundos.

Hashing em uma estrutura de dados é um processo de duas etapas.

1. A função hash converte o item em um pequeno inteiro ou valor de hash. Este inteiro é usado como um índice para armazenar os dados originais.
2. Ele armazena os dados em uma tabela de hash. Você pode usar uma chave de hash para localizar dados rapidamente.

Exemplos de hash na estrutura de dados

A seguir estão exemplos da vida real de hash na estrutura de dados –

• Nas escolas, o professor atribui um número de registro único a cada aluno. Mais tarde, o professor usa esse número de rolo para recuperar informações sobre esse aluno.
• Uma biblioteca tem um número infinito de livros. O bibliotecário atribui um número único a cada livro. Este número único ajuda a identificar a posição dos livros na estante.

Checkout: classificação na estrutura de dados

Função de hash

A função hash em uma estrutura de dados mapeia tamanhos arbitrários de dados para dados de tamanho fixo. Ele retorna os seguintes valores: um pequeno valor inteiro (também conhecido como valor de hash), códigos de hash e somas de hash.

hash = hashfunc(chave)

índice = hash % array_size

A função has deve atender aos seguintes requisitos:

• Uma boa função hash é fácil de calcular.
• Uma boa função de hash nunca fica presa no cluster e distribui as chaves uniformemente pela tabela de hash.
• Uma boa função de hash evita colisões quando dois elementos ou itens são atribuídos ao mesmo valor de hash.

Tabela de hash

O hash na estrutura de dados usa tabelas de hash para armazenar os pares chave-valor. A tabela de hash então usa a função de hash para gerar um índice. O hashing usa esse índice exclusivo para executar operações de inserção, atualização e pesquisa.

Como funciona o hash na estrutura de dados?

No hashing, a função hashing mapeia strings ou números para um pequeno valor inteiro. As tabelas de hash recuperam o item da lista usando uma função de hash. O objetivo da técnica de hash é distribuir os dados uniformemente em uma matriz. O hash atribui a todos os elementos uma chave exclusiva. A tabela de hash usa essa chave para acessar os dados na lista.

A tabela de hash armazena os dados em um par chave-valor. A chave atua como uma entrada para a função de hash. A função de hash gera um número de índice exclusivo para cada valor armazenado. O número de índice mantém o valor que corresponde a essa chave. A função hash retorna um pequeno valor inteiro como saída. A saída da função de hash é chamada de valor de hash.

Vamos entender o hash em uma estrutura de dados com um exemplo. Imagine que você precise armazenar alguns itens (organizados em um par chave-valor) dentro de uma tabela de hash com 30 células.

Os valores são: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

A tabela de hash terá a seguinte aparência:

Leia também: Tipos de estruturas de dados em Python

Técnicas de resolução de colisões

O hash na estrutura de dados entra em colisão se duas chaves forem atribuídas ao mesmo número de índice na tabela de hash. A colisão cria um problema porque cada índice em uma tabela de hash deve armazenar apenas um valor. O hashing na estrutura de dados usa várias técnicas de resolução de colisão para gerenciar o desempenho de uma tabela de hash.

Sondagem Linear

O hash na estrutura de dados resulta em um índice de matriz que já está ocupado para armazenar um valor. Nesse caso, o hashing executa uma operação de pesquisa e sonda linearmente a próxima célula vazia.

Exemplo de sondagem linear

Imagine que você foi solicitado a armazenar alguns itens dentro de uma tabela de hash de tamanho 30. Os itens já estão ordenados em um formato de par chave-valor. Os valores indicados são: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

O hash(n) é o índice calculado usando uma função hash e T é o tamanho da tabela. Se o índice do slot = ( hash(n) % T) estiver cheio, procuramos o próximo índice do slot adicionando 1 ((hash(n) + 1) % T). Se (hash(n) + 1) % T também está cheio, então tentamos (hash(n) + 2) % T. Se (hash(n) + 2) % T também está cheio, então tentamos (hash( n) + 3) % T.

A tabela de hash terá a seguinte aparência:

Hash duplo

A técnica de hash duplo usa duas funções de hash. A segunda função de hash entra em uso quando a primeira função causa uma colisão. Ele fornece um índice de deslocamento para armazenar o valor.

A fórmula para a técnica de hash duplo é a seguinte:

(firstHash(chave) + i * secondHash(chave)) % sizeOfTable

Onde i é o valor de deslocamento. Este valor de deslocamento é incrementado até encontrar um slot vazio.

Por exemplo, você tem duas funções de hash: h1 e h2. Você deve executar as seguintes etapas para encontrar um slot vazio:

1. Verifique se hash1(chave) está vazio. Se sim, armazene o valor neste slot.
2. Se hash1(chave) não estiver vazio, encontre outro slot usando hash2(chave).
3. Verifique se hash1(chave) + hash2(chave) está vazio. Se sim, armazene o valor neste slot.
4. Continue incrementando o contador e repita com hash1(chave)+2hash2(chave), hash1(chave)+3hash2(chave), e assim por diante, até encontrar um slot vazio.

Exemplo de hash duplo

Imagine que você precise armazenar alguns itens dentro de uma tabela de hash de tamanho 20. Os valores fornecidos são: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

Conclusão

O hash duplo tem um alto custo de computação, mas procura o próximo slot livre mais rápido do que o método de sondagem linear. Os exemplos dados no artigo são apenas para fins explicativos. Você pode modificar as declarações fornecidas acima de acordo com suas necessidades. Neste blog, aprendemos sobre o conceito de hash na estrutura de dados .

Você pode experimentar o exemplo para fortalecer seu conhecimento de estrutura de dados. Se você tem curiosidade em saber mais sobre estrutura de dados , confira o curso upGrad Executive PG Program in Full Stack Development . Este curso é projetado para profissionais que trabalham e oferece treinamento rigoroso e colocação de trabalho nas principais empresas.