Suponha que uma string com r caracteres é mapeada com hash em m slots ao tratá-la como um número de base 128 e então usando um método de divisão. O número m pode ser representado como uma palavra de 32 bits, mas a string de r caracteres demanda muitas palavras. Como podemos aplicar o método de divisão para computar o valor hash do caracter da string sem usar mais que um número constante de palavras de armazenamento fora aquelas da própria string?

Passo 1

O enunciado nos dá as seguintes informações e pede uma coisa clara:
  • Dado: uma string com r caracteres, cada caractere representado como um inteiro c_i na faixa 0 a 127 (base 128).
  • A string é tratada como um número em base 128 (ou seja, os caracteres são dígitos dessa base).
  • Queremos aplicar o método da divisão: o hash é o resto da divisão desse número por m.
  • Sabemos que m cabe em uma palavra de 32 bits.
  • A string inteira pode ser muito grande (não cabe em um número de poucas palavras).
  • Restrição: não podemos usar mais do que um número constante de palavras de armazenamento além da própria string.
O que se pede: explicar um procedimento para computar o valor do hash (o número em base 128 mod m) usando no máximo um número constante de palavras extras (independente de r).

Passo 2

Entendendo como o número da string é formado (representação em base 128).
Se os caracteres da string são c_1,c_2,\dots,c_r (onde c_1 é o caractere mais significativo), o inteiro correspondente é
N = c_1 128^{\,r-1} + c_2 128^{\,r-2} + \cdots + c_{r-1}128 + c_r.
Esse é exatamente o número em base 128. O hash pelo método da divisão é
\text{hash} = N \bmod m.
O problema é que N pode ser enorme (muito maior que o que cabe em algumas palavras), então não podemos calcular N explicitamente. Temos que achar uma maneira de obter N\bmod m sem formar N inteiro.

Passo 3

Propriedades úteis de aritmética modular (pequena “aula” prática).
As identidades que vamos usar são estas, simples e muito poderosas:
  1. Soma modular:
(a+b) \bmod m = \bigl((a\bmod m) + (b\bmod m)\bigr) \bmod m.
  1. Multiplicação modular:
(a\cdot b) \bmod m = \bigl((a\bmod m)\cdot(b\bmod m)\bigr) \bmod m.
Essas fórmulas dizem que podemos reduzir (tirar o resto) em qualquer etapa sem alterar o resultado final. Isso permite construir o resto de N por etapas sem armazenar N inteiro.

Passo 4

Aplicando Horner (método em cascata) para avaliar N e usando aritmética modular para manter tudo pequeno.
Horner reorganiza a soma da forma
N = ((\cdots((c_1\cdot 128 + c_2)\cdot 128 + c_3)\cdots )\cdot 128 + c_r).
Definimos recursivamente/iterativamente os valores parciais
h_0 = 0,\qquad h_i = 128\cdot h_{i-1} + c_i \quad\text{para } i=1,\dots,r.
Então h_r = N. Aplicando restos a cada passo, obtemos
H_0 = 0,\qquad H_i = \bigl(128\cdot H_{i-1} + c_i\bigr)\bmod m.
Pelo princípio das propriedades modulares, cada H_i é congruente a h_i módulo m; em particular
H_r = N \bmod m,
que é exatamente o hash desejado. Assim, basta percorrer os caracteres em ordem e atualizar um único acumulador H com a fórmula acima.

Passo 5

Implementação prática e discussão sobre espaço constante (como evitar usar muitas palavras).
  • Variáveis necessárias (constante, independente de r):
    • Um acumulador H (uma palavra de 32 bits, já que H<m<2^{32}).
    • Um índice de posição/ponteiro para percorrer a string (também uma palavra).
    • Eventualmente uma palavra extra temporária para multiplicação se a arquitetura exigir (no máximo um número constante de palavras, p.ex. 1 ou 2).
  • Operação por caractere: ler c_i, calcular t = 128\cdot H + c_i, então H = t \bmod m.
  • Preocupação prática: 128\cdot H pode exceder 32 bits (porque 128\cdot(H<2^{32}) < 2^{39}). Duas formas comuns de tratar isso, ambas com uso constante de palavras:
    Opção A — usar aritmética de palavra dupla (se disponível): usar um temporário de 64 bits (duas palavras) para calcular t exatamente e então dividir por m para obter o resto. Isso usa um número fixo de palavras extras (uma ou duas), logo cumpre a restrição.
    Opção B — evitar multiplicação de palavra dupla usando somas/dobramentos modulares: note que multiplicar por 128 é apenas 7 dobramentos (shift-left por 7). Podemos fazer, para cada caractere:
    \text{para } k=1\ldots 7:\quad H \leftarrow (2\cdot H)\bmod m,
    e depois
    H \leftarrow (H + c_i)\bmod m.
    Cada passo é uma soma/dobro seguida de redução por m. Todas as operações podem ser feitas em uma palavra de 32 bits: o dobro 2\cdot H pode ser computado como H+H e então, se houver overflow, toma-se o resto por m (uma subtração condicional de m ou operação de resto). Isso faz no máximo 7 dobramentos e uma adição por caractere — tempo constante por caractere e espaço apenas para H e contadores (constante).
  • Complexidade: tempo O(r), espaço extra O(1) palavras. Correção segue da construção por Horner e das propriedades modulares do Passo 3.

Passo 6

Exemplo numérico curtinho para fixar a ideia (modo “faça na prova” — passo a passo).
Considere uma string de 3 caracteres com valores \,c_1=65,\;c_2=66,\;c_3=67 (por exemplo “ABC”) e m=1000. Vamos simular rápido usando a regra iterativa:
H_0=0.
Processando c_1=65:
H_1 = (128\cdot 0 + 65)\bmod 1000 = 65.
Processando c_2=66:
H_2 = (128\cdot 65 + 66)\bmod 1000 = (8320 + 66)\bmod 1000 = 8386\bmod 1000 = 386.
Processando c_3=67:
H_3 = (128\cdot 386 + 67)\bmod 1000 = (49408 + 67)\bmod 1000 = 49475\bmod 1000 = 475.
Logo o hash é H_3=475. Perceba que em cada passo só foi mantido H (e o caractere lido); nunca foi necessário formar o número grande N.

Passo 7

Resumo final e dicas para a prova (motivação e como justificar rapidamente):
  • Diga que usa Horner + aritmética modular e que pela identidade (ab+c)\bmod m = ((a\bmod m)(b\bmod m)+c\bmod m)\bmod m é seguro reduzir a cada passo.
  • Escreva a iteração curta: H\leftarrow(128H+c_i)\bmod m para cada caractere.
  • Explique que o espaço extra é constante porque há apenas um acumulador H (mais contadores/temporários fixos). Se o examinador perguntar sobre overflow, descreva a opção de usar temporário de 64 bits ou a variante de 7 dobramentos modulares para uma máquina que só tenha aritmética de 32 bits.
Boa notícia: isto é direto de implementar na prova e dá uma justificativa teórica clara (Horner + propriedades modulares). Você consegue explicar isso rápido e escrever o algoritmo em poucas linhas.

Resposta

H_0=0 e, para i=1,\dots,r, \;H_i=\bigl(128\cdot H_{i-1}+c_i\bigr)\bmod m. O valor final H_r é o hash.

Exercícios relacionados