Crie uma lista ligada simples de tamanho n, onde cada nó contém uma chave k acompanhada de um valor hash h(k). Crie uma função de busca nesta lista que utilize o hash para reduzir as computações necessárias.

Passo 1

O que o enunciado pede e o que nos é dado:
  • Pedido: criar uma lista ligada simples de tamanho n em que cada nó armazena uma chave k e o valor do hash h(k); e criar uma função de busca nessa lista que utilize o hash para reduzir as operações necessárias.
  • Dados/assunções que vou usar (não foi explícito no enunciado, então escolhi hipóteses razoáveis):
    • A lista é simplesmente ligada (cada nó tem ponteiro para o próximo).
    • As chaves k são valores comparáveis (por exemplo, strings ou arrays de bytes).
    • Existe uma função de hash determinística h que mapeia uma chave para um inteiro.
    • O hash de cada nó é calculado e armazenado quando o nó é inserido (pré-computado).
  • O objetivo da busca: reduzir o custo de comparar chaves completas muitas vezes, usando comparações de hashes (mais baratas) como filtro rápido; validar igualdade completa somente quando os hashes coincidirem (para tratar colisões).

Passo 2

Estrutura do nó da lista (ideia geral) e por que armazenar o hash:
  • Cada nó vai conter:
    • a chave (por exemplo \text{key}),
    • o valor do hash armazenado (por exemplo \text{hash}),
    • ponteiro para o próximo nó ( \text{next}).
  • Por que armazenar h(k) no nó?
    • Comparar dois hashes inteiros é muito mais rápido do que comparar duas strings longas caractere a caractere.
    • Ao inserir, calcula-se h(k) uma vez e guarda-se. Em buscas repetidas a vantagem aparece: para cada nó só se faz comparação de inteiros; somente quando o inteiro bate é que se faz a comparação completa da chave para confirmar (corrigir colisões).
    • Custo extra: memória O(n) adicional para armazenar um inteiro por nó e custo de calcular o hash uma vez por inserção.

Passo 3

Escolha e propriedades do hash h:
  • Requisitos práticos:
    • Determinístico: mesma chave → mesmo hash.
    • Rápido de calcular.
    • Baixa taxa de colisões na prática (boa distribuição).
  • Exemplos:
    • Em aplicações reais usar a hash nativa da linguagem (por exemplo \text{hash()} em Python) ou um hash rápido como FNV-1a, MurmurHash, ou um polynomial rolling hash para strings.
  • Se quiser uma fórmula didática (rolling hash para strings): h(k)=\left(\sum_{i=0}^{m-1} \text{code}(k[i])\cdot p^{i}\right)\bmod Monde:
    • m é o comprimento da string k,
    • \text{code}(k[i]) é o código numérico do caractere i,
    • p é uma base pequena (ex.: p=31 ou p=131),
    • M é um módulo grande primo (ex.: 10^{9}+7) para reduzir colisões e evitar overflow.
  • Lembre: mesmo um bom hash pode colidir; por isso é obrigatório verificar igualdade completa da chave quando os hashes forem iguais.

Passo 4

Como construir a lista ligada de tamanho n (inserção inicial)
  • Estratégia: a partir de um array/lista de chaves \text{keys}[0..n-1], inserir cada nó no final (ou no início) calculando e armazenando seu hash.
  • Pseudocódigo (explicado linha a linha depois):
    • criar \text{head} \leftarrow \text{NULL}
    • para cada \text{key} em \text{keys}:
      • \text{node.key} \leftarrow \text{key}
      • \text{node.hash} \leftarrow h(\text{key}) (calcula o hash aqui)
      • inserir \text{node} na lista (atualizar ponteiros)
  • Observações:
    • Cálculo do hash por nó é feito uma vez na inserção: custo por inserção é o custo do hash + custo de manipular ponteiros.
    • Complexidade para construir a lista inteira: O(n\cdot H) onde H é custo de calcular h por chave (frequentemente O(m) onde m é comprimento médio da chave), mas isso é pago uma vez.

Passo 5

Projeto da função de busca que usa o hash como filtro
  • Ideia central:
    1. Calcular o hash do valor-procura q: \text{hq} = h(q).
    2. Percorrer a lista do head até NULL.
    3. Para cada nó, comparar primeiro \text{node.hash} com \text{hq}.
      • Se diferente, pular (rejeição rápida).
      • Se igual, comparar \text{node.key} com q (comparação completa). Se igual, retornar nó; se diferente, é colisão — continuar.
    4. Se chegar ao fim sem achar, retornar “não encontrado”.
  • Porque isto reduz trabalho:
    • Em vez de comparar q com cada chave completamente (custoso para strings longas), faz-se uma comparação de inteiros rápida na maioria dos nós. A comparação completa só ocorre em nós cujos hashes coincidem com \text{hq} (espera-se que sejam muito poucos se o hash for bom).
  • Complexidade:
    • Pior caso: O(n) comparações de hash (cada qual O(1)) e, no pior caso de muitas colisões, até O(n\cdot m) para comparações de chaves — mas isso é raro.
    • Caso típico/prático: O(n) trabalho de comparação de inteiros e apenas O(1) comparações de chave completas (quando existe correspondência) — claramente mais rápido que comparar strings em todos os nós.

Passo 6

Pseudocódigo da estrutura e das funções (explicando cada linha)
  • Estrutura do nó (descrição):
    • node.key : a chave completa (ex.: string)
    • node.hash : inteiro h(\text{key})
    • node.next : ponteiro para o próximo nó
  • Função de construção (build_list):
    • Entrada: lista/array \text{keys}[0..n-1]
    • Saída: \text{head} da lista ligada
    • Pseudocódigo (estilo Python/Psuedocode):
      • head = NULL
      • tail = NULL
      • para cada key em keys:
        • node = new Node()
        • node.key = key
        • node.hash = h(key) # calculado uma vez
        • node.next = NULL
        • se head == NULL:
          • head = node
          • tail = node
        • senão:
          • tail.next = node
          • tail = node
      • retornar head
    • Explicação: insere no final para manter ordem; calcular hash no momento da inserção.

Passo 7

Pseudocódigo da função de busca (search) com explicação linha a linha
  • Função search(head, q):
    • hq = h(q) # calcula o hash da chave procurada apenas uma vez
    • current = head
    • enquanto current != NULL:
      • se current.hash != hq:
        • current = current.next # rejeição rápida: hashes diferentes => chaves diferentes
        • continuar
      • se current.key == q:
        • retornar current # encontrou correspondência exata (hash e chave batem)
      • senão:
        • current = current.next # colisão de hash (mesmo hash mas chaves diferentes) -> continuar
    • retornar NULL # não encontrou
  • Explicação didática:
    • Primeiro se calcula \text{hq}=h(q) (uma vez). Isso é barato comparado a recalcular o hash em cada nó.
    • Em cada nó compara-se o inteiro armazenado \text{node.hash} com \text{hq}. Se diferirem, sabe-se imediatamente que a chave não coincide — evita-se a comparação completa da chave.
    • Só quando os hashes são iguais faz-se a comparação completa da chave, que confirma a igualdade verdadeira ou detecta colisão.

Passo 8

Exemplo pequeno passo a passo (ilustrativo)
  • Suponha chaves pequenas: \text{keys} = [\text{"ana"}, \text{"anastasia"}, \text{"bruno"}].
  • Ao construir:
    • calcula-se \text{h}(\text{"ana"}), \text{h}(\text{"anastasia"}), \text{h}(\text{"bruno"}) e guarda em cada nó.
  • Ao buscar q=\text{"ana"}:
    • \text{hq} \leftarrow h(\text{"ana"}).
    • Percorre-se: no primeiro nó \text{node.hash}==\text{hq} → compara-se as strings \text{"ana"}==\text{"ana"} → verdadeiro → retorna.
  • Se buscar q=\text{"amanda"} com \text{h}(\text{"amanda"}) que não bate com os hashes dos nós, a busca vai pular cada nó apenas pelas comparações de inteiros, sem comparar strings completas.

Passo 9

Tratamento de colisões, robustez e boas práticas
  • Colisões: quando \text{node.hash}==\text{hq} mas \text{node.key} \ne q. Solução: sempre comparar a chave completa depois do hash igual. Nunca confiar só no hash.
  • Mutabilidade das chaves: se as chaves podem ser mutáveis e mudam depois da inserção, o hash armazenado fica inconsistente. Convenção: usar chaves imutáveis ou recomputar/atualizar o hash quando a chave muda.
  • Escolha do hash: para eficiência escolha um hash rápido e não-criptográfico se a aplicação não exigir resistência a ataques (p.ex. FNV-1a ou MurmurHash). Para segurança (evitar ataques de colisão intencional), usar hash seguro.
  • Memória: armazenar um inteiro por nó aumenta a memória por nó, custo O(n) extra.
  • Quando usar: útil quando chaves são caras de comparar (strings longas, arrays) e buscas são frequentes.

Passo 10

Código final (pseudocódigo limpo, pronto para adaptar)
  • Definição do nó e funções essenciais:
class Node:
key # a chave completa (ex.: string)
hash # inteiro: h(key)
next # ponteiro para o próximo Node
def build_list(keys):
head = None
tail = None
for key in keys:
node = Node()
node.key = key
node.hash = h(key) # calcula e armazena o hash aqui
node.next = None
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head
def search(head, q):
hq = h(q) # calcula o hash do alvo uma vez
current = head
while current is not None:
if current.hash != hq:
current = current.next
continue
# hashes iguais: verificar chave completa para evitar colisão falsa
if current.key == q:
return current # encontrado
current = current.next
return None # não encontrado

Resposta

Definição da lista: cada nó armazena \text{key}, \text{hash}=h(\text{key}) e \text{next}.
Função de busca (pseudocódigo):
def search(head, q):
hq = h(q)
current = head
while current is not None:
if current.hash != hq:
current = current.next
continue
if current.key == q:
return current
current = current.next
return None
Complexidade típica: percorre a lista em O(n) fazendo comparações de inteiros por nó; comparações completas de chave ocorrem somente quando os hashes coincidem (muito raro com um bom hash).

Exercícios relacionados