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
Last updated