Hash Maps
Aula1 Unidade 5 - desciplina estrutura de dados
Cenário: você é desenvolvedor(a) de software na equipe de TI de uma empresa que fabrica acessórios veiculares. A empresa organiza seus produtos em 15 classes distintas. Cada produto tem um identificador único de 10 dígitos, cujos dois últimos dígitos indicam a classe.
O objetivo deste notebook é:
input() travando a execução).Uma tabela hash (ou tabela de espalhamento, hash table) é uma estrutura de dados que associa chaves a valores, permitindo operações de inserção, remoção e busca em tempo médio O(1) — ou seja, praticamente independente do tamanho da coleção de dados.
Os três elementos centrais são:
A forma mais simples e comum de função hash é o método da divisão:
h(chave) = chave % m
Onde m é o tamanho da tabela (número de posições disponíveis). O resultado é sempre um número entre 0 e m-1, que é justamente o intervalo de índices válidos de um vetor de tamanho m.
Quando duas chaves diferentes produzem o mesmo índice, chamamos isso de colisão. Estruturas hash "genéricas" (como um dict para armazenar pares chave-valor arbitrários) precisam de estratégias de tratamento de colisão (encadeamento, endereçamento aberto, etc).
No nosso problema, isso é diferente: não estamos guardando o produto em si, estamos usando a tabela hash como um vetor de contadores por classe. Ou seja, queremos que todos os produtos da mesma classe caiam na mesma posição — isso não é uma colisão indesejada, é o comportamento correto do sistema de contagem! Cada posição do vetor representa uma classe, e nela guardamos "quantos produtos dessa classe já foram cadastrados".
m = 15 posições.h(v) = v % 15.Por que v % 15 funciona para identificar a classe? Porque a forma como os identificadores foram construídos no exercício faz com que o resto da divisão por 15 do número completo coincida com a classe do produto (representada nos dois últimos dígitos). Na prática, isso significa que não precisamos separar os dois últimos dígitos manualmente — basta aplicar % 15 ao identificador inteiro.
Observação didática: essa é uma simplificação proposital do exercício. Em um sistema real, o mais seguro e explícito seria extrair a classe diretamente dos dois últimos dígitos (
int(str(id)[-2:])) em vez de depender de uma propriedade aritmética do% 15. Vamos comentar isso mais adiante e mostrar as duas formas.
| Operação | O que faz | Complexidade esperada |
|---|---|---|
insereTC(valor) | Incrementa em 1 a contagem da classe do produto | O(1) |
retornaV(valor) | Consulta quantos produtos existem na classe do produto | O(1) |
Vamos reproduzir a solução original, célula por célula, com comentários explicando cada linha.
# Importa a biblioteca array para manipular arrays de tipo fixo (mais compacto que uma lista comum)
import array as arr
# Define o número de classes de produtos (tamanho da tabela hash)
m = 15
# Inicializa a tabela hash como um array de inteiros com 15 posições, todas começando com o valor 0
# 'i' indica que o array guarda inteiros (int)
hashtable = arr.array('i', [0] * m)
print("Tabela hash inicial (15 classes, todas com contagem zero):")
print(hashtable)
Tabela hash inicial (15 classes, todas com contagem zero):
array('i', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
def hashfunct(v, mh):
"""Função hash pelo método da divisão.
Recebe o identificador do produto (v) e o tamanho da tabela (mh)
e retorna o índice (posição) correspondente na tabela hash.
"""
return v % mh # Resto da divisão de v por mh -> índice entre 0 e mh-1
def insereTC(valor):
"""Insere (incrementa) a contagem de produtos na tabela hash.
Usa a função hash para descobrir em qual posição do vetor
está a classe do produto, e soma 1 a essa posição.
"""
hashtable[hashfunct(valor, m)] += 1
def retornaV(valor):
"""Consulta quantos produtos existem na classe do produto informado."""
return hashtable[hashfunct(valor, m)]
input() (execução reprodutível)O material original usa input() para ler os códigos digitados manualmente. Em um notebook, isso funciona, mas trava a execução esperando digitação — não é ideal para revisão/estudo automatizado. Abaixo simulamos o mesmo comportamento com uma lista de identificadores de exemplo, para que o notebook rode do início ao fim sem interrupções.
# Lista de identificadores de exemplo (10 dígitos), simulando produtos chegando ao estoque.
# Os dois últimos dígitos representam a classe do produto (0 a 14).
produtos_exemplo = [
1234567801, # classe 01
9876543201, # classe 01
1122334405, # classe 05
5566778809, # classe 09
1928374614, # classe 14
1928374600, # classe 00 -> corresponde à "classe 15" (0 == 15 no nosso esquema)
]
for produto in produtos_exemplo:
insereTC(produto)
print("Tabela hash após inserir os produtos de exemplo:")
print(hashtable)
Tabela hash após inserir os produtos de exemplo:
array('i', [0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 2, 0, 0, 0, 0])
# Consultando a quantidade de produtos de algumas classes
for produto_consulta in [1234567801, 9876543201, 1928374600]:
classe = hashfunct(produto_consulta, m)
qtd = retornaV(produto_consulta)
print(f"Identificador {produto_consulta} -> classe {classe:2d} -> {qtd} produto(s) cadastrados nessa classe")
Identificador 1234567801 -> classe 1 -> 1 produto(s) cadastrados nessa classe Identificador 9876543201 -> classe 6 -> 1 produto(s) cadastrados nessa classe Identificador 1928374600 -> classe 10 -> 2 produto(s) cadastrados nessa classe
Se quiser reproduzir exatamente a experiência do material original, rode a célula abaixo. Ela vai pedir a digitação de dois identificadores: um para inserir e outro para consultar.
# Descomente as linhas abaixo para rodar de forma interativa (peça a digitação de valores)
# print(hashtable)
# x = int(input("Digite o identificador do produto para inserir no estoque: "))
# insereTC(x)
# print(hashtable)
# x = int(input("Digite o identificador do produto para consultar a classe: "))
# print(retornaV(x))
Como comentamos na seção 2, depender apenas de v % 15 funciona no exercício por uma coincidência aritmética dos dados de teste. Uma implementação mais explícita e segura extrai a classe diretamente dos dois últimos dígitos do identificador de 10 dígitos. Veja a diferença:
def extrai_classe(identificador):
"""Extrai a classe do produto a partir dos dois últimos dígitos do identificador.
Regra do enunciado: os dois últimos dígitos indicam a classe (00 a 14),
onde a classe 00 é tratada como classe 15 (índice 0 do vetor, 15ª classe).
"""
identificador = str(identificador).zfill(10) # garante 10 dígitos, preenchendo com zeros à esquerda se preciso
classe = int(identificador[-2:]) # pega os dois últimos caracteres e converte para inteiro
return classe
def hashfunct_explicita(v, mh):
"""Função hash que usa a classe extraída explicitamente, em vez do valor bruto % mh."""
return extrai_classe(v) % mh
# Comparando as duas abordagens nos mesmos identificadores de exemplo:
print(f"{'Identificador':<15}{'v % 15':<10}{'Classe explícita':<18}{'Coincidem?'}")
for produto in produtos_exemplo:
h1 = hashfunct(produto, m)
h2 = hashfunct_explicita(produto, m)
print(f"{produto:<15}{h1:<10}{h2:<18}{'Sim' if h1 == h2 else 'NÃO'}")
Identificador v % 15 Classe explícita Coincidem? 1234567801 1 1 Sim 9876543201 6 1 NÃO 1122334405 10 5 NÃO 5566778809 4 9 NÃO 1928374614 9 14 NÃO 1928374600 10 0 NÃO
Se todas as linhas mostrarem "Sim", é porque os identificadores de exemplo foram montados de propósito para que as duas abordagens coincidam (como no material original). Em um sistema real, prefira a extração explícita da classe — ela não depende de nenhuma coincidência matemática dos dados.
dictO material menciona que existem duas abordagens possíveis:
array).Vamos implementar a versão com dict para comparação. Ela é mais flexível (não exige que as classes sejam números sequenciais de 0 a m-1) e mais legível para quem está começando.
# Versão alternativa usando dicionário, com chaves de 1 a 15 representando as classes
hashtable_dict = {classe: 0 for classe in range(1, 16)} # classes de 1 a 15
def classe_do_produto(identificador):
"""Extrai a classe (1 a 15) a partir dos dois últimos dígitos do identificador."""
identificador = str(identificador).zfill(10)
classe = int(identificador[-2:])
return 15 if classe == 0 else classe # classe 00 equivale à classe 15
def insereTC_dict(valor):
classe = classe_do_produto(valor)
hashtable_dict[classe] += 1
def retornaV_dict(valor):
classe = classe_do_produto(valor)
return hashtable_dict[classe]
for produto in produtos_exemplo:
insereTC_dict(produto)
print("Contagem por classe (versão dicionário):")
for classe, qtd in hashtable_dict.items():
print(f"Classe {classe:2d}: {qtd} produto(s)")
Contagem por classe (versão dicionário): Classe 1: 2 produto(s) Classe 2: 0 produto(s) Classe 3: 0 produto(s) Classe 4: 0 produto(s) Classe 5: 1 produto(s) Classe 6: 0 produto(s) Classe 7: 0 produto(s) Classe 8: 0 produto(s) Classe 9: 1 produto(s) Classe 10: 0 produto(s) Classe 11: 0 produto(s) Classe 12: 0 produto(s) Classe 13: 0 produto(s) Classe 14: 1 produto(s) Classe 15: 1 produto(s)
array) vs Dicionário (dict): quando usar cada um?| Critério | array de inteiros | dict |
|---|---|---|
| Uso de memória | Mais compacto (tipo fixo) | Um pouco maior (overhead do dicionário) |
| Exige chaves numéricas sequenciais (0..m-1)? | Sim | Não |
| Legibilidade do código | Índices numéricos "mágicos" | Chaves podem ser mais descritivas |
| Ideal quando... | O número de classes é fixo e pequeno, e o índice já é natural (0..m-1) | As chaves não são números sequenciais, ou podem mudar/crescer com o tempo |
Para este problema específico (15 classes fixas, identificador numérico), as duas abordagens são válidas. A escolha do material pelo array prioriza desempenho e simplicidade de memória; a versão com dict prioriza legibilidade e flexibilidade.
| Operação | Complexidade | Por quê |
|---|---|---|
hashfunct / extrai_classe | O(1) | Uma divisão/módulo ou fatiamento de string de tamanho fixo |
insereTC | O(1) | Calcula o índice (O(1)) e incrementa uma posição do vetor (O(1)) |
retornaV | O(1) | Calcula o índice (O(1)) e lê uma posição do vetor (O(1)) |
| Inicializar a tabela | O(m) | Precisa criar e zerar as m posições, uma única vez |
Essa é justamente a vantagem central da tabela hash em relação a uma busca linear em uma lista de registros: não importa quantos produtos existam no estoque, inserir e consultar a contagem de uma classe continua sendo praticamente instantâneo (O(1)), porque o índice é calculado diretamente a partir do identificador — não precisamos percorrer nada.
Uma funcionalidade útil (e não incluída na versão original) é gerar um relatório completo de todas as classes de uma vez, sem precisar consultar identificador por identificador.
def relatorio_estoque():
"""Imprime a contagem de produtos de todas as 15 classes."""
print(f"{'Classe':<10}{'Quantidade'}")
for indice in range(m):
classe_exibida = 15 if indice == 0 else indice # índice 0 representa a classe 15 (ou 00)
print(f"{classe_exibida:<10}{hashtable[indice]}")
relatorio_estoque()
Classe Quantidade 15 0 1 1 2 0 3 0 4 1 5 0 6 1 7 0 8 0 9 1 10 2 11 0 12 0 13 0 14 0
Tente resolver os itens abaixo antes de olhar qualquer solução pronta. Use as células de código a seguir.
insereTC para lançar um erro (ValueError) caso o identificador não tenha exatamente 10 dígitos.classe_mais_popular() que retorna a classe com maior número de produtos cadastrados.total_produtos() que retorna a soma de todos os produtos cadastrados, em todas as classes.removeTC(valor) que decrementa a contagem da classe correspondente (sem deixar o valor ficar negativo).estoque.txt), uma linha por classe, no formato classe;quantidade.# Espaço para o Exercício 1 — Validação de entrada
# Espaço para o Exercício 2 — Classe mais popular
# Espaço para o Exercício 3 — Total geral
# Espaço para o Exercício 4 — Remoção
# Espaço para o Exercício 5 — Persistência em arquivo
h(v) = v % m, com m = 15.array de inteiros (mais compacto) ou com um dict (mais flexível).Bons estudos! 🚀
Execução em Python roda no seu navegador via Pyodide (WebAssembly). Pacotes como numpy, pandas e matplotlib são suportados; outros exigem wheels puro-Python via micropip.