Notas de Aula: Funções de HASH

O "texto" abaixo é na verdade uma aglutinação de algumas notas que tomei na faculdade sobre o assunto. Estou postando pois talvez elas sejam interessantes para aqueles que estejam estudando alguma matéria de estrutura de dados.


Funções Hash são bem conhecidas no dia a dia da computação, principalmente devido a aplicativos semelhantes ao md5sum. Elas funcionam pegando uma entrada, geram um número aleatório que serve para identificar e validade o conteúdo deste. Por exemplo, um arquivo ou uma string transmitida, o receptor pode usar o hash para checar a validade dos dados.

Propriedades:

1) y = f(x)
2) Não existe f -1
3) X é uma string de bits de tamanho arbitrário.
4) Y é uma string de bits de tamanho fixo.
5) Dado y é virtualmente impossível obter x
6) Se x diferente de x’ à f(x) diferente f(x’)

As primeiras propriedade dizem que apartir do arquivo original podemos chegar ao hash, porém a partir do hash não podemos chegar ao arquivo original.

A função de hash é feita da seguinte maneira:

int HASH (char *s)
{
s-> inteiro (long int)
-> double
s / primo
retorna (resto);
}

ou seja
pega-se uma string, por exemplo, BOLA. Multiplica-se cada letra por sua posição, ou seja:

letra: B posição: 3
letra: O posição: 2
letra: L posição: 1
letra: A posição: 0

vira:

Ax2^0 + L x 2^1 + O x 2^2 + B x2^3

o número 2 foi escolhido arbitrariamente, podendo ser qualquer outro número.

No caso do C, ao se chamar uma variável caracter por %d ao invés de %c, o próprio compilador já faz a conversão da letra para um valor numérico.

Feita multiplicação e a soma, deve-se então dividir o valor por um número primo qualquer. A escolha por um número primo vem de uma característica próprias desses números, que no momento em que dividimos uma quantidade números quaisquer por um primo encontramos uma diversidade de resultados maior do que os que encontraríamos se fizessemos a divisão por outro número, o que tenderia a concentrar o resultado em alguns valores.

Feito isso pegamos o resto, ou seja, o valor após a vírgula, e esse será o nosso hash.

Sem comentários: