Crie uma lista ligada simples de tamanho
, onde cada nó contém uma chave
acompanhada de um valor hash
. 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
em que cada nó armazena uma chave e o valor do hash ; 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
são valores comparáveis (por exemplo, strings ou arrays de bytes). - Existe uma função de hash determinística
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
), - o valor do hash armazenado (por exemplo
), - ponteiro para o próximo nó (
).
- a chave (por exemplo
- Por que armazenar
no nó? - Comparar dois hashes inteiros é muito mais rápido do que comparar duas strings longas caractere a caractere.
- Ao inserir, calcula-se
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
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
:
- 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
em Python) ou um hash rápido como FNV-1a, MurmurHash, ou um polynomial rolling hash para strings.
- Em aplicações reais usar a hash nativa da linguagem (por exemplo
- Se quiser uma fórmula didática (rolling hash para strings):
onde: -
é o comprimento da string , -
é o código numérico do caractere , -
é uma base pequena (ex.: ou ), -
é um módulo grande primo (ex.: ) 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
(inserção inicial)
- Estratégia: a partir de um array/lista de chaves
, inserir cada nó no final (ou no início) calculando e armazenando seu hash. - Pseudocódigo (explicado linha a linha depois):
- criar
- para cada
em : -
-
(calcula o hash aqui) - inserir
na lista (atualizar ponteiros)
-
- criar
- 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:
onde é custo de calcular por chave (frequentemente onde é comprimento médio da chave), mas isso é pago uma vez.
- Cálculo do hash por nó é feito uma vez na inserção: custo por inserção é o custo do hash
Passo 5
Projeto da função de busca que usa o hash como filtro
- Ideia central:
- Calcular o hash do valor-procura
: . - Percorrer a lista do head até NULL.
- Para cada nó, comparar primeiro
com . - Se diferente, pular (rejeição rápida).
- Se igual, comparar
com (comparação completa). Se igual, retornar nó; se diferente, é colisão — continuar.
- Se chegar ao fim sem achar, retornar “não encontrado”.
- Calcular o hash do valor-procura
- Porque isto reduz trabalho:
- Em vez de comparar
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 (espera-se que sejam muito poucos se o hash for bom).
- Em vez de comparar
- Complexidade:
- Pior caso:
comparações de hash (cada qual ) e, no pior caso de muitas colisões, até para comparações de chaves — mas isso é raro. - Caso típico/prático:
trabalho de comparação de inteiros e apenas comparações de chave completas (quando existe correspondência) — claramente mais rápido que comparar strings em todos os nós.
- Pior caso:
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
- node.next : ponteiro para o próximo nó
- Função de construção (build_list):
- Entrada: lista/array
- Saída:
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.
- Entrada: lista/array
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
- se current.hash != hq:
- retornar NULL # não encontrou
- Explicação didática:
- Primeiro se calcula
(uma vez). Isso é barato comparado a recalcular o hash em cada nó. - Em cada nó compara-se o inteiro armazenado
com . 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.
- Primeiro se calcula
Passo 8
Exemplo pequeno passo a passo (ilustrativo)
- Suponha chaves pequenas:
. - Ao construir:
- calcula-se
, , e guarda em cada nó.
- calcula-se
- Ao buscar
: -
. - Percorre-se: no primeiro nó
→ compara-se as strings → verdadeiro → retorna.
-
- Se buscar
com 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
mas . 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
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
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
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
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
,
e
.
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
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
fazendo comparações de inteiros por nó; comparações completas de chave ocorrem somente quando os hashes coincidem (muito raro com um bom hash).