Introdução à função hash em C
Este artigo possui uma breve observação sobre hash (tabela de hash e função de hash). O conceito mais importante é a pesquisa, que determina a complexidade do tempo. Para reduzir a complexidade do tempo, é introduzido qualquer outro conceito de hash da estrutura de dados que tenha O (1) tempo no caso médio e, no pior caso, levará tempo O (n).
Hashing é uma técnica com acesso mais rápido aos elementos que mapeia os dados fornecidos com uma chave menor para comparações. Em geral, nessa técnica, as chaves são rastreadas usando a função hash em uma tabela conhecida como tabela de hash.
O que é a função Hash?
A função hash é uma função que usa a operação de tempo constante para armazenar e recuperar o valor da tabela de hash, que é aplicada às chaves como números inteiros e usada como o endereço para valores na tabela de hash.
Tipos de uma função hash
Os tipos de funções de hash são explicados abaixo:
1. Método de divisão
Nesse método, a função hash depende do restante de uma divisão.
Exemplo: os elementos a serem colocados em uma tabela de hash são 42, 78, 89, 64 e vamos considerar o tamanho da tabela como 10.
Hash (chave) = Elementos% tamanho da tabela;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
A representação da tabela pode ser vista abaixo:
2. Método do quadrado médio
Nesse método, a parte do meio do elemento quadrado é tomada como índice.
O elemento a ser colocado na tabela de hash é 210, 350, 99, 890 e o tamanho da tabela é 100.
210 * 210 = 44100, índice = 1 como a parte do meio do resultado (44100) é 1.
350 * 350 = 122500, índice = 25 como a parte do meio do resultado (122500) é 25.
99 * 99 = 9801, índice = 80 como a parte do meio do resultado (9801) é 80.
890 * 890 = 792100, índice = 21 como a parte do meio do resultado (792100) é 21.
3. Método de Dobragem de Dígitos
Nesse método, o elemento a ser colocado na tabela uh é a chave de hash, que é obtida dividindo os elementos em várias partes e depois combinando as partes, executando algumas operações matemáticas simples.
O elemento a ser colocado é 23576623, 34687734.
- hash (chave) = 235 + 766 + 23 = 1024
- chave de hash) = 34 + 68 + 77 + 34 = 213
Nesses tipos de hash, suponha que tenhamos números de 1 a 100 e tamanho da tabela de hash = 10. Elementos = 23, 12, 32
Hash (chave) = 23% 10 = 3;
Hash (chave) = 12% 10 = 2;
Hash (chave) = 32% 10 = 2;
No exemplo acima, observe que os elementos 12 e 32 apontam para o 2º lugar na tabela, onde não é possível escrever os dois no mesmo local, esse problema é conhecido como colisão. Para evitar esse tipo de problema, existem algumas técnicas de funções de hash que podem ser usadas.
Tipos de técnicas de resolução de colisões
Vamos discutir os tipos de técnicas de resolução de colisões:
1. Encadeamento
Neste método, como o nome sugere, ele fornece uma cadeia de caixas para o registro na tabela com duas entradas de elementos. Portanto, sempre que essas colisões ocorrerem, as caixas agirão como uma lista vinculada.
Exemplo: 23, 12, 32 com tamanho de tabela 10.
Hash (chave) = 23% 10 = 3;
Hash (chave) = 12% 10 = 2;
Hash (chave) = 32% 10 = 2;
2. Abrir endereçamento
- Sondagem linear
Este é outro método para resolver problemas de colisão. Como o nome diz sempre que ocorre uma colisão, dois elementos devem ser colocados na mesma entrada na tabela, mas, por esse método, podemos procurar o próximo espaço vazio ou entrada na tabela e colocar o segundo elemento. Isso pode novamente levar a outro problema; se não encontrarmos nenhuma entrada vazia na tabela, isso resultará em cluster. Portanto, isso é conhecido como um problema de agrupamento, que pode ser resolvido pelo seguinte método.
Exemplo: 23, 12, 32 com tamanho de tabela 10
Hash (chave) = 23% 10 = 3;
Hash (chave) = 12% 10 = 2;
Hash (chave) = 32% 10 = 2;
Neste diagrama, 12 e 32 podem ser colocados na mesma entrada com o índice 2, mas por esse método, eles são colocados linearmente.
- Sondagem quadrática
Este método é uma resolução para o problema de agrupamento durante a análise linear. Neste método, a função hash com chave hash é calculada como hash (chave) = (hash (chave) + x * x)% do tamanho da tabela (onde x = 0, 1, 2 …).
Exemplo: 23, 12, 32 com tamanho de tabela 10
Hash (chave) = 23% 10 = 3;
Hash (chave) = 12% 10 = 2;
Hash (chave) = 32% 10 = 2;
Nesse sentido, podemos ver que 23 e 12 podem ser colocados facilmente, mas 32 não podem novamente 12 e 32 compartilham a mesma entrada com o mesmo índice na tabela, conforme esse método hash (key) = (32 + 1 * 1) % 10 = 3. Mas, neste caso, a entrada da tabela com o índice 3 é colocada com 23, portanto, temos que incrementar o valor x em 1. Hash (chave) = (32 + 2 * 2)% 10 = 6. Portanto, agora podemos colocar 32 na entrada com o índice 6 na tabela.
- Hash duplo
Neste método, temos que calcular 2 funções de hash para resolver o problema de colisão. O primeiro é calculado usando um método de divisão simples. O segundo tem que satisfazer duas regras; não deve ser igual a 0 e as entradas devem ser investigadas.
- 1 (chave) = tamanho da chave% da tabela.
- 2 (tecla) = p - (tecla mod p), em que p é números primos <tamanho da tabela.
Exemplo: 23, 12, 32 com tamanho de tabela 10
Hash (chave) = 23% 10 = 3;
Hash (chave) = 12% 10 = 2;
Hash (chave) = 32% 10 = 2;
Nisto, novamente, o elemento 32 pode ser colocado usando o hash2 (chave) = 5 - (32% 5) = 3. Portanto, 32 pode ser colocado no índice 5 da tabela que está vazia, pois precisamos pular 3 entradas para colocá-lo.
Função Conclusão-Hashing em C
O hash é uma das técnicas importantes em termos de pesquisa de dados fornecidos com métodos muito eficientes e rápidos usando a função hash e tabelas de hash. Cada elemento pode ser pesquisado e colocado usando diferentes métodos de hash. Essa técnica é muito mais rápida do que qualquer outra estrutura de dados em termos de coeficiente de tempo.
Artigos recomendados
Este é um guia para a função Hashing em C. Aqui discutimos a introdução da função Hashing em C, O que é a Função Hash, Tipos de uma função hash, etc. Você também pode consultar nossos outros artigos sugeridos para saber mais:
- Hashing no DBMS
- Processo de criptografia
- Como instalar o CakePHP?
- Como o Blockchain funciona
- Função hash em Java
- Função hash em PHP | Como trabalhar?