🚀 Capítulo 09: Colisões em Tabelas Hash (Tema: Vingadores)
NOTE
Este capítulo utiliza a temática de Vingadores para explicar as Colisões. O sistema da SHIELD tentou colocar o Hulk e o Thor na mesma vaga do estacionamento; isso gerou uma colisão que precisamos resolver!
1. 🎯 Objetivo da Aula
Compreender o conceito de Colisão em tabelas hash e as principais técnicas para resolvê-las: Encadeamento Separado (Separated Chaining) e Endereçamento Aberto (Open Addressing).
2. 🏢 O Cenário Prático (Seu Desafio)
Na Torre dos Vingadores, o Jarvis usa uma Tabela Hash para guardar os dados dos heróis. A função hash calcula o número da vaga do estacionamento baseado no nome do herói.
- Para o
"Thor", a função calculou a vaga 5. - Para o
"Hulk", a função também calculou a vaga 5!
Dois heróis não podem estacionar na mesma vaga ao mesmo tempo. Isso é uma Colisão. Seu desafio é ajudar o Jarvis a resolver esse conflito sem deixar nenhum herói de fora!
3. 🧠 Fundamentos: A Teoria Traduzida
Como o universo de chaves possíveis (todos os nomes do mundo) é muito maior que o tamanho da nossa tabela (ex: 100 gavetas), é matematicamente impossível criar uma função hash perfeita que nunca repita um índice. As colisões vão acontecer.
🛡️ Técnicas de Resolução de Colisão:
1. Encadeamento Separado (Lista Ligada)
Em vez de guardar o herói direto na gaveta, cada gaveta guarda uma Lista Ligada (Capítulo 06).
- Se o Thor e o Hulk caírem na vaga 5, a vaga 5 terá uma lista contendo:
[Thor] -> [Hulk]. - Vantagem: Simples de implementar.
- Desvantagem: Se muitos heróis caírem na mesma vaga, a busca vira uma busca linear lenta.
2. Endereçamento Aberto (Procura Linear)
Se a vaga 5 já estiver ocupada pelo Thor, o Hulk tenta estacionar na vaga 6 (a próxima livre). Se a 6 estiver ocupada, tenta a 7.
- Vantagem: Não gasta memória extra com listas ligadas.
- Desvantagem: Se a tabela estiver cheia, fica muito lento achar uma vaga livre.
4. 📖 Exemplo Guiado: O Encadeamento na Prática
Tabela Hash de tamanho 5.
- Dado:
Thor(Hash = 2). Gaveta 2:[Thor] - Dado:
Hulk(Hash = 2). Gaveta 2:[Thor] -> [Hulk](Inseriu no final da lista).
5. 🛠️ Prática Obrigatória 1: Resolvendo a Colisão
Imagine uma tabela hash onde a vaga é calculada pela primeira letra do nome.
"Hulk"e"Hawkeye"(Gavião Arqueiro) começam com ‘H’ e vão para a mesma vaga.
- Se usarmos Encadeamento, como fica a representação dessa vaga?
- Se usarmos Endereçamento Aberto e o Hulk chegar primeiro, onde o Hawkeye vai estacionar?
6. 🛠️ Prática Obrigatória 2: A Degradação do Tempo
Se a nossa função hash for muito ruim e mandar TODOS os 1.000 heróis para a mesma vaga 0 (usando encadeamento), qual será o tempo de busca nessa tabela hash? Ela ainda será rápida como O(1) ou virou uma busca linear lenta?
7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)
- Faça o Commit: No GitHub Desktop, digite a mensagem (ex:
Finaliza Capítulo 09 Estruturas de Dados) e clique em Commit to main. - Envie para a Nuvem (Push): Clique em Push origin.
8. 📂 Estrutura de Pastas
mod_09_estruturas_de_dados/
├── capitulos/
│ ├── capitulo_09_colisoes.md
│ └── codigos/
│ └── cap09/
│ └── colisao_jarvis.js9. 💡 Checkpoint de Lógica
É melhor ter uma tabela hash com muitas gavetas vazias (desperdiçando memória) ou uma tabela pequena com muitas colisões (desperdiçando tempo)?
10. 🔥 Desafio de Fixação
Pesquise o que é Double Hashing (Hash Duplo) como forma de resolver colisões no endereçamento aberto.
🔑 Gabarito de Código/Fórmulas
Gabarito da Prática 1:
- A vaga ‘H’ terá uma lista:
["Hulk"] -> ["Hawkeye"]. - O Hawkeye vai procurar a vaga seguinte à vaga ‘H’ que esteja livre.