DS & II

Capítulo 08 - Tabelas Hash

Leitura de 3 min

🚀 Capítulo 08: Tabelas Hash (Dicionários) (Tema: Sherlock Holmes)

NOTE

Este capítulo utiliza a temática de Sherlock Holmes para explicar as Tabelas Hash. Para encontrar o culpado instantaneamente, você precisa de um sistema que não exija ler todos os arquivos!

1. 🎯 Objetivo da Aula

Compreender o conceito de Tabela Hash (Dicionário), como funciona uma Função Hash e a vantagem da busca por chave-valor com tempo quase instantâneo.

2. 🏢 O Cenário Prático (Seu Desafio)

Sherlock Holmes tem um arquivo com a ficha de 1.000 suspeitos em Londres.

  • Se ele guardar tudo em um Array (Mochila do Pokémon), para achar o “Moriarty” ele precisa ler ficha por ficha até encontrar. Isso é muito lento!
  • Ele precisa de um sistema onde ele diga o nome "Moriarty" e o próprio sistema diga: “A ficha dele está na gaveta 45”.

Esse sistema existe na computação e se chama Tabela Hash (ou Dicionário). Seu desafio é entender a mágica por trás da função que calcula o número da gaveta!

3. 🧠 Fundamentos: A Teoria Traduzida

A Tabela Hash guarda os dados em pares de Chave-Valor.

  • Chave: O identificador único (Ex: O nome do suspeito).
  • Valor: O dado completo (Ex: A ficha com os crimes).

🧮 1. A Função Hash

É o cérebro da estrutura. É uma fórmula matemática que recebe a Chave (Texto) e cospe um Número (O índice do Array onde o valor será guardado).

  • Exemplo: A função lê a palavra “Moriarty”, faz um cálculo e retorna o número 45. O computador guarda a ficha do Moriarty direto na posição 45 do Array.
  • Na hora de buscar, o computador passa “Moriarty” na mesma função, ela retorna 45 de novo, e ele vai direto lá ler! Não precisa procurar.

⚡ 2. Eficiência O(1)

Como o acesso é direto pelo índice calculado, a busca, inserção e deleção demoram sempre o mesmo tempo, não importa se temos 10 ou 10 milhões de suspeitos!

4. 📖 Exemplo Guiado: Uma Função Hash Simples

Vamos criar uma função hash que soma o número de letras da palavra.

  • Chave: "Watson" → 6 letras. Guardamos na gaveta 6.
  • Chave: "Irene" → 5 letras. Guardamos na gaveta 5.

Para buscar a ficha da Irene, basta contar as letras (5) e ir direto na gaveta 5!

5. 🛠️ Prática Obrigatória 1: Calculando o Hash

Usando a nossa função hash simples (contar o número de letras), calcule em qual gaveta ficariam guardados os dados dos seguintes suspeitos:

  1. "Sherlock"
  2. "Lestrade"
  3. "Hudson"

6. 🛠️ Prática Obrigatória 2: O Problema das Palavras Iguais

O que acontece na nossa função hash simples se tentarmos guardar os dados do suspeito "Holmes"? (Dica: Conte as letras e olhe o Exemplo Guiado). O que aconteceu com a gaveta?

7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)

  1. Faça o Commit: No GitHub Desktop, digite a mensagem (ex: Finaliza Capítulo 08 Estruturas de Dados) e clique em Commit to main.
  2. Envie para a Nuvem (Push): Clique em Push origin.

8. 📂 Estrutura de Pastas

mod_09_estruturas_de_dados/
├── capitulos/
│   ├── capitulo_08_hash_tables.md
│   └── codigos/
│       └── cap08/
│           └── dicionario_suspeitos.js

9. 💡 Checkpoint de Lógica

As Tabelas Hash garantem que os dados fiquem guardados em ordem alfabética? Por quê?

10. 🔥 Desafio de Fixação

Pesquise o que é uma Colisão em tabelas hash (veremos isso no próximo capítulo!).

🔑 Gabarito de Código/Fórmulas

Gabarito da Prática 1:

  1. "Sherlock" → 8 letras. Gaveta 8.
  2. "Lestrade" → 8 letras. Gaveta 8.
  3. "Hudson" → 6 letras. Gaveta 6.

← Capitulo Anterior | Proximo Capitulo →

Visão de gráfico

Backlinks