Suponha que uma string com
caracteres é mapeada com hash em
slots ao tratá-la como um número de base 128 e então usando um método de divisão. O número
pode ser representado como uma palavra de 32 bits, mas a string de
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
caracteres, cada caractere representado como um inteiro na faixa a (base ). - A string é tratada como um número em base
(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
. - Sabemos que
cabe em uma palavra de 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
mod
) usando no máximo um número constante de palavras extras (independente de
).
Passo 2
Entendendo como o número da string é formado (representação em base
).
Se os caracteres da string são
(onde
é o caractere mais significativo), o inteiro correspondente é
Esse é exatamente o número em base
. O hash pelo método da divisão é
O problema é que
pode ser enorme (muito maior que o que cabe em algumas palavras), então não podemos calcular
explicitamente. Temos que achar uma maneira de obter
sem formar
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:
- Soma modular:
- Multiplicação modular:
Essas fórmulas dizem que podemos reduzir (tirar o resto) em qualquer etapa sem alterar o resultado final. Isso permite construir o resto de
por etapas sem armazenar
inteiro.
Passo 4
Aplicando Horner (método em cascata) para avaliar
e usando aritmética modular para manter tudo pequeno.
Horner reorganiza a soma da forma
Definimos recursivamente/iterativamente os valores parciais
Então
. Aplicando restos a cada passo, obtemos
Pelo princípio das propriedades modulares, cada
é congruente a
módulo
; em particular
que é exatamente o hash desejado. Assim, basta percorrer os caracteres em ordem e atualizar um único acumulador
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
): - Um acumulador
(uma palavra de bits, já que ). - 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).
- Um acumulador
-
Operação por caractere: ler
, calcular , então . -
Preocupação prática:
pode exceder bits (porque ). 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 debits (duas palavras) para calcular exatamente e então dividir por 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é apenas 7 dobramentos (shift-left por 7). Podemos fazer, para cada caractere: e depoisCada passo é uma soma/dobro seguida de redução por. Todas as operações podem ser feitas em uma palavra de bits: o dobro pode ser computado como e então, se houver overflow, toma-se o resto por (uma subtração condicional de ou operação de resto). Isso faz no máximo dobramentos e uma adição por caractere — tempo constante por caractere e espaço apenas para e contadores (constante). -
Complexidade: tempo
, espaço extra 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
(por exemplo “ABC”) e
. Vamos simular rápido usando a regra iterativa:
Processando
:
Processando
:
Processando
:
Logo o hash é
. Perceba que em cada passo só foi mantido
(e o caractere lido); nunca foi necessário formar o número grande
.
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
é seguro reduzir a cada passo. - Escreva a iteração curta:
para cada caractere. - Explique que o espaço extra é constante porque há apenas um acumulador
(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.