Assinatura e Certificação Digital - Código Hash

Os chamados códigos hash, hash values, checksums, hash function, hash code ou apenas hashes são artifícios utilizados em ambientes onde se trabalham com grandes conjuntos ou massas de dados, isto porque a função hash tem como tarefa receber na entrada um grande conjunto de dados de tamanho variável e transformar essa entrada em um pequeno dado, sendo este normalmente um inteiro simples que pode servir como um índice de um vetor por exemplo.

As utilizações de códigos hash vão de simples aplicações até Sistemas Gerenciadores de Bancos de Dados, trabalhos com estruturas de dados complexas e criptografia. Os bancos de dados e estruturas de dados complexas em especial, fazem utilização de hash codes para diminuir o tempo de busca por determinadas informações, diminuindo o cargo das tarefas de comparação, visto que o hash code traz a possibilidade de indexar as informações, já que independe do tamanho da informação armazenada, logo o SGDB ou linguagens que trabalham com coleções de dados ganham em desempenho, pois a busca não vai varrer item por item na estrutura, mas sim irá diretamente ao item específico da tabela, normalmente chamada de tabela de hash ou “hash table”.

Há uma grande utilização do hash code também na computação gráfica e na geometria computacional, chamada de “Geometric Hashing”. É amplamente utilizado na resolução de problemas de um plano ou em espaço tridimensional, como por exemplo, a busca por pares mais próximos em um conjunto de pontos, formas similares em uma lista de formas, imagens similares em uma base de dados, e assim por diante.

Nas hash functions, ou seja, as funções que geram um hash value podem em algum momento ocorrer de duas ou mais chaves obterem o mesmo valor de hash, o que é denominado colisão de hash, para evitar então ao máximo estas ocorrências de colisão, faz-se necessário que a hash function gere valores de hash o mais uniformemente possível. Uniformidade é uma propriedade existente no conceito de hash function onde a definição da propriedade diz que: Uma boa função hash deve mapear as entradas esperadas o mais uniformemente possível sobre uma gama de produção. Isto quer dizer que cada valor de hash no intervalo de saída deveria ser gerado com aproximadamente a mesma probabilidade, tendendo a evitar colisões. A razão para isto é que o custo dos métodos baseados em busca de hash sobe bruscamente à medida que o número de colisões aumenta. Quando se refere a colisões, diz-se de duas ou mais entradas geram o mesmo valor de hash.

Para exemplificar, pode-se observar na Figura 1, onde as chaves (Keys) são as entradas; e passando pela função de hash (hash function), é gerado determinados valores de hash no qual forma uma tabela de hash (hash table). No exemplo, as entradas “John Smith” e “Sandra Dee” geram o mesmo hash que é o “02” no qual é uma colisão de hash. A uniformidade diz respeito a evitar ao máximo este número de colisões, porque o algoritmo de busca por hash, deveria buscar todos os itens que apontam para este hash e comparar um por um até encontrar o correto, de maneira que isto é oneroso e pode inviabilizar a abordagem de hash code, pois a performance desejada não seria obtida.

As propriedades existem para tentar garantir que a aplicação que faz utilização da abordagem por hash function tenha realmente ganhos reais no desempenho. Outras propriedades que podem ser citadas são:

• O valor de entrada deve possuir qualquer tamanho lógico. De maneira que em hipótese alguma a hash function poderia reclamar da entrada ser grande ou pequena de mais.
• Baixo custo de processamento: O custo do cálculo do valor de hash deve ser pequeno o bastante para a solução ser a melhor opção, e não outras abordagens alternativas.
• Determinista: Uma função de hash deve ser determinista, significando que para um dado valor de entrada, sempre deve ser gerado o mesmo valor de hash. Exceto para funções de hash onde dependem de outros parâmetros, como por exemplo, se depende da hora ou do dia corrente ou ainda outros fatores.
• One-Way (única direção): Ao encontrar o valor de hash para determinada String de entrada, deve ser computacionalmente impossível fazer o processo inverso, ou seja, encontrar o valor da entrada a partir do código hash.

Estes requerimentos denominados propriedades de hash functions foram concebidos na década de 1950, contudo o desenvolvimento de boas funções de hash continua sendo tópicos ativos nas buscas dos fóruns relacionados.