Função de dispersão de uma sequência de caracteres

Uma função de dispersão para cadeias de caracteres (strings) calcula a partir desta, qualquer que seja o seu tamanho, um inteiro

Como sabemos uma sequência de caracteres (String) é em geral representada como uma sequência de inteiros

Em consequência, a função de dispersão para Strings tem por entrada uma sequência de inteiros

• k = k1, ..., ki, ..., kn

e produz um número inteiro pequeno h(k)

Os algoritmos para este tipo de entrada assumem que os inteiros são de facto códigos de caracteres

Em muitas linguagens um caracter é representado em 8 bits

O código ASCII apenas usa 7 desses 8 bits

Desses 7, os caracteres comuns apenas usam os 6 menos significativos

• E o mais significativo desses 6 indica essencialmente se é maiúscula ou minúscula, muitas vezes pouco relevante

Em consequência os algoritmos concentram-se na preservação do máximo de informação dos 5 bits menos significativos, famultiplica-se por M e arredonda se para o maior inteiro menor ou igual ao valor obtidozendo muito menos uso dos 3 bits mais significativos

Em geral, o processamento efetuado consiste em:

• inicializar h com 0 ou outro valor inicial

• Percorrer a sequência de inteiros (representando os caracteres) combinando os inteiros 𝑘𝑖, um por um, com h

  • Os algoritmos diferem na forma como combinam ki com h

• Obtenção do resultado final através de h mod M (método da divisão).

Para evitar ao máximo problemas com overflow, em geral os inteiros ki são representados por números inteiros sem sinal (unsigned int)

• A utilização de representações de inteiros com sinal pode resultar em comportamentos estranhos