Guia completo: Tabela Hash em Python

Visão geral da ideia

O script implementa uma tabela hash para armazenar nomes de pessoas (chaves) e seus telefones (valores). Ele usa:

• Uma função de hash para transformar o nome em um índice numérico.
• Uma classe TabelaHash que guarda a estrutura e as operações.
• Encadeamento (chaining) para lidar com colisões.
• Um método de impressão (__repr__) para visualizar a tabela inteira.
• Um trecho final que insere vários nomes e depois permite buscas interativas.

1. Função de hash: funcao_hash

def funcao_hash(chave, tamanho):
    return sum(ord(char) for char in chave) % tamanho

O que faz? Converte cada letra da chave em um número (ord), soma tudo e pega o resto da divisão (%) pelo tamanho da tabela. Esse resto é o índice onde o par [chave, valor] será guardado.

Linha a linha

• def funcao_hash(chave, tamanho): → define a função e declara que ela recebe dois parâmetros: a chave (string) e o tamanho da tabela (inteiro).
• return sum(ord(char) for char in chave) % tamanho → soma os códigos de cada caractere e devolve o resto da divisão por tamanho. Esse número entre 0 e tamanho-1 é o índice onde vamos guardar ou procurar a chave.

Exemplo completo (nome "Bruno", tabela com 30 posições)

Bruno
B (66) + r (114) + u (117) + n (110) + o (111) = 518
518 % 30 = 8 -> o par cai no índice 8

2. Classe TabelaHash e o construtor __init__

class TabelaHash:
    def __init__(self, tamanho):
        self.size = tamanho
        self.table = [[] for _ in range(tamanho)]

O que acontece ao criar TabelaHash(30)?

• self.size = 30 guarda o tamanho para ser usado nos cálculos.
• self.table = [[], [], ..., []] cria uma lista com 30 baldes vazios (cada posição é uma lista onde podem entrar vários pares).

O que é __init__ e o que é self?

• __init__ é o construtor: roda automaticamente sempre que você cria um novo objeto da classe, por exemplo, TabelaHash(30). É onde o objeto nasce configurado.
• self é a referência para o próprio objeto que está sendo criado ou manipulado. Dentro dos métodos, qualquer atributo que pertença ao objeto é acessado como self.alguma_coisa.

Linha a linha

• class TabelaHash: → declara a classe (o molde).
• def __init__(self, tamanho): → define o construtor que recebe o tamanho desejado.
• self.size = tamanho → salva o número de posições da tabela dentro do objeto.
• self.table = [ [] for _ in range(tamanho) ] → cria uma lista com tamanho listas vazias. O for _ in range(tamanho) repete a criação de [] tamanho vezes.

3. Inserindo dados: setar_item

def setar_item(self, chave, valor):
    indice = funcao_hash(chave, self.size)
    self.table[indice].append([chave, valor])

Calcula o índice com funcao_hash e faz append do par [chave, valor] no balde correspondente. Se já existirem outros pares ali, o novo fica encadeado no final da mesma lista (é assim que colisões são tratadas).

Linha a linha

• def setar_item(self, chave, valor): → define o método de inserção, recebendo a chave (nome) e o valor (telefone).
• indice = funcao_hash(chave, self.size) → calcula em qual posição a chave deve ficar.
• self.table[indice].append([chave, valor]) → pega o balde naquele índice e acrescenta o par no final da lista.

4. Buscando dados: obter_item

def obter_item(self, chave):
    indice = funcao_hash(chave, self.size)
    for par in self.table[indice]:
        if par[0] == chave:
            return par[1]
    return None

Recalcula o índice, percorre o balde daquela posição e compara a chave armazenada (par[0]) com a chave que você pediu. Se encontrar, devolve par[1] (o telefone); se não existir, retorna None.

Linha a linha

• def obter_item(self, chave): → método de busca, recebe a chave procurada.
• indice = funcao_hash(chave, self.size) → calcula o índice da chave usando a mesma função de hash.
• for par in self.table[indice]: → percorre cada par no balde daquele índice.
• if par[0] == chave: → compara a chave armazenada (posição 0 do par) com a chave procurada.
• return par[1] → se encontrou, devolve o valor (telefone) que está na posição 1.
• return None → se terminar o laço sem achar a chave, retorna None indicando ausência.

5. Visualizando a tabela: __repr__

def __repr__(self):
    linhas = []
    for indice, balde in enumerate(self.table):
        linhas.append(f"{indice:2}: {balde}")
    return "\\n".join(linhas)

Quando você faz print(tabela_hash), esse método monta uma linha por índice e junta tudo com quebras de linha, permitindo enxergar rapidamente onde cada par está.

O que é __repr__?

É o método especial usado para representar o objeto como texto. O Python chama __repr__ quando você faz print(objeto) ou vê o objeto no console. Aqui ele foi implementado para mostrar cada índice e seu balde.

Linha a linha

• def __repr__(self): → define a representação textual do objeto.
• linhas = [] → cria uma lista vazia que guardará cada linha de texto.
• for indice, balde in enumerate(self.table): → percorre todos os índices (indice) e baldes (balde) da tabela.
• linhas.append(f"{indice:2}: {balde}") → adiciona uma string formatada com o número do índice alinhado em 2 espaços e o conteúdo do balde.
• return "\\n".join(linhas) → junta todas as linhas com quebras de linha. O método join pega a lista linhas e cola os itens usando o separador "\n" (pula linha).

6. Criando a tabela e inserindo os contatos

tabela_hash = TabelaHash(30)
tabela_hash.setar_item("Bruno", "333")
tabela_hash.setar_item("Beto", "123")
tabela_hash.setar_item("Sammy", "222")
... (demais nomes) ...
tabela_hash.setar_item("Pabllo", "845")
print(tabela_hash)

Cada chamada de setar_item calcula o índice com a função de hash e adiciona o par no balde certo. O print final mostra como os contatos ficaram distribuídos.

Linha a linha

• tabela_hash = TabelaHash(30) → cria a tabela com 30 posições.
• tabela_hash.setar_item("Bruno", "333") (e as demais) → insere cada par nome/telefone usando o método explicado acima.
• print(tabela_hash) → chama __repr__ para exibir a tabela inteira.

7. Busca interativa

nome_busca = input("Digite o nome que deseja buscar: ")
resultado = tabela_hash.obter_item(nome_busca)
if resultado is not None:
    print("Telefone:", resultado)
else:
    print("Nome não encontrado na tabela hash.")

Pede um nome ao usuário, consulta com obter_item e mostra o telefone encontrado ou uma mensagem caso a chave não exista.

Linha a linha

• nome_busca = input("Digite o nome que deseja buscar: ") → lê do teclado e guarda na variável nome_busca.
• resultado = tabela_hash.obter_item(nome_busca) → chama o método de busca para recuperar o telefone.
• if resultado is not None: → verifica se a busca encontrou algo (diferente de None).
• print("Telefone:", resultado) → mostra o telefone quando encontrado.
• else: → caminho alternativo se não achou a chave.
• print("Nome não encontrado na tabela hash.") → informa que a chave não existe na estrutura.

8. Colisões e encadeamento (chaining)

Colisão acontece quando duas chaves diferentes geram o mesmo índice. O código resolve isso com encadeamento: cada índice guarda uma lista com todos os pares que caíram ali.

# Exemplo prático:
tabela_hash.setar_item("Beto", "123")  # soma = 394 -> índice 4
tabela_hash.setar_item("Karl", "617")  # soma = 394 -> índice 4 também
# O balde 4 fica: [["Beto", "123"], ["Karl", "617"]]

Na busca, obter_item calcula o índice e percorre a lista daquele balde para encontrar a chave exata.

9. Exemplos de cálculo com nomes do próprio script

Todos os valores abaixo foram calculados com funcao_hash(nome, 30):

Nome           Soma(ord)   Índice (soma % 30)
---------------------------------------------
Bruno              518     8
Beto               394     4
Karl               394     4  <- colisão com Beto
Bruce              497    17
Luana              497    17  <- colisão com Bruce
Ana Clara          787     7
Andressa           817     7  <- colisão com Ana Clara
Pablo              494    14
Pabllo             602     2
Michael            691     1
João               523    13  (ã vale 227 na soma)
Ana Cláudia       1123    13  (á vale 225)
André              622    22  (é vale 233)

Repare que os caracteres acentuados aumentam a soma, mas o processo é exatamente o mesmo: somar todos os ord() e tirar o resto da divisão pelo tamanho da tabela.

10. Como fica a tabela após inserir tudo

Rodando o código de inserção exatamente como está no Hash.py (tamanho 30), o print(tabela_hash) mostra algo assim:

 0: []
 1: [['Michael', '987']]
 2: [['Pabllo', '845']]
 3: [['Carla', '289']]
 4: [['Beto', '123'], ['Karl', '617']]
 5: []
 6: []
 7: [['Ana Clara', '975'], ['Andressa', '590']]
 8: [['Bruno', '333']]
 9: [['Sammy', '222']]
10: []
11: []
12: []
13: [['João', '801'], ['Ana Cláudia', '437'], ['Marcos', '455']]
14: [['Pablo', '386']]
15: []
16: [['João Silva', '642']]
17: [['Bruce', '444'], ['Luana', '567']]
18: []
19: [['Marcus', '993']]
20: [['Neymar', '512']]
21: []
22: [['André', '328']]
23: []
24: []
25: []
26: []
27: []
28: []
29: [['Roberta', '764']]

Os índices vazios aparecem como []. Quando há colisão, vários pares ficam no mesmo balde (veja os índices 4, 7, 13 e 17).

11. Conceitos rápidos de Python usados aqui

• Classe: define um molde (atributos e métodos). Aqui: TabelaHash.
• Método especial __init__: construtor; roda ao criar o objeto.
• Método especial __repr__: representação textual para print(objeto).
• self: referência ao próprio objeto; permite acessar atributos e métodos dele.
• list comprehension: [[] for _ in range(tamanho)] cria listas rapidamente.
• range(tamanho): gera sequência 0..tamanho-1.
• append: adiciona um item ao final de uma lista.
• enumerate: devolve pares (índice, valor) ao iterar sobre uma coleção.
• f"...{variavel}...": f-string, forma simples de embutir valores em texto.
• % (módulo): devolve o resto da divisão. Garantimos índice entre 0 e tamanho-1.
• for ... in ...: laço que percorre elementos de uma sequência (lista, string, etc.).
• None: valor especial para “nada/encontrou” em Python.

12. Fluxo completo explicado

1. Criação: TabelaHash(30) chama __init__, define self.size e cria 30 baldes vazios.
2. Inserção: cada setar_item(nome, telefone) calcula indice = funcao_hash(nome, 30) e faz append do par no balde table[indice].
3. Visualização: print(tabela_hash) chama __repr__, que percorre todos os baldes com enumerate e monta o texto com "\n".join(linhas).
4. Busca: obter_item(nome) recalcula o índice, percorre o balde correspondente e compara a chave armazenada; se achar, retorna o telefone, senão None.
5. Interação: input(...) lê o nome digitado e usa obter_item para mostrar o resultado.

13. Dicas rápidas para code review

• Complexidade: hash e inserção são O(1) na média; busca também O(1) média, O(n) no pior caso se muitas colisões caem no mesmo balde.
• Colisões: resolvidas por encadeamento; balde é uma lista de pares.
• Tamanho da tabela: aqui é 30; se muitos elementos forem inseridos, aumentar o tamanho ou rehash reduz colisões.
• Chaves iguais: o código atual não impede duplicatas; inserir o mesmo nome cria outro par no mesmo balde.
• Caracteres especiais: acentos mudam a soma e portanto o índice; usar sempre a mesma função de hash para inserir e buscar.

14. Código completo (Hash.py)

def funcao_hash(chave, tamanho):
    return sum(ord(char) for char in chave) % tamanho

class TabelaHash:
    def __init__(self, tamanho):
        self.size = tamanho
        self.table = [ [] for _ in range(tamanho) ]

    def setar_item(self, chave, valor):
        indice = funcao_hash(chave, self.size)
        self.table[indice].append([chave, valor])

    def obter_item(self, chave):
        indice = funcao_hash(chave, self.size)
        for par in self.table[indice]:
            if par[0] == chave:
                return par[1]
        return None

    def __repr__(self):
        linhas = []
        for indice, balde in enumerate(self.table):
            linhas.append(f"{indice:2}: {balde}")
        return "\n".join(linhas)

tabela_hash = TabelaHash(30)
tabela_hash.setar_item("Bruno", "333")
tabela_hash.setar_item("Beto", "123")
tabela_hash.setar_item("Sammy", "222")
tabela_hash.setar_item("Bruce", "444")
tabela_hash.setar_item("Luana", "567")
tabela_hash.setar_item("Michael", "987")
tabela_hash.setar_item("João", "801")
tabela_hash.setar_item("João Silva", "642")
tabela_hash.setar_item("Ana Clara", "975")
tabela_hash.setar_item("Ana Cláudia", "437")
tabela_hash.setar_item("Andressa", "590")
tabela_hash.setar_item("André", "328")
tabela_hash.setar_item("Roberta", "764")
tabela_hash.setar_item("Neymar", "512")
tabela_hash.setar_item("Carla", "289")
tabela_hash.setar_item("Karl", "617")
tabela_hash.setar_item("Marcos", "455")
tabela_hash.setar_item("Marcus", "993")
tabela_hash.setar_item("Pablo", "386")
tabela_hash.setar_item("Pabllo", "845")
print(tabela_hash)

nome_busca = input("Digite o nome que deseja buscar: ")
resultado = tabela_hash.obter_item(nome_busca)
if resultado is not None:
    print("Telefone:", resultado)
else:
print("Nome não encontrado na tabela hash.")

15. Apresentação para a turma

Imagina que você está explicando rápido para os colegas o que fez: é uma tabela hash simples em Python que guarda nomes e telefones. A função de hash soma os códigos das letras e tira o resto por 30 para achar o índice. A classe cria 30 baldes (listas) e usa encadeamento para lidar com colisões: se dois nomes caem no mesmo índice, eles ficam juntos no mesmo balde.

• Inserção: setar_item calcula o índice e faz append do par.
• Busca: obter_item recalcula o índice, percorre o balde e retorna o telefone.
• Visualização: __repr__ monta um texto com todos os índices e baldes.
• Interação: no fim, o código imprime a tabela e pede um nome para buscar.

Se alguém perguntar sobre colisão, você responde: “Quando dois nomes dão o mesmo índice, eu não perco nada; só coloco os dois na mesma lista dentro daquele índice e, na busca, percorro essa lista até achar a chave certa”.

16. Linha por linha do script

Explicação bem detalhada, linha a linha, incluindo o papel de cada variável e parâmetro:

1. def funcao_hash(chave, tamanho): cria a função. chave é a palavra (nome) que vamos transformar em número. tamanho é quantas posições existem na tabela (ex.: 30).
2. return sum(ord(char) for char in chave) % tamanho percorre cada letra (char) da chave, converte com ord em número, soma tudo com sum, e o % tamanho garante um índice entre 0 e tamanho-1. Esse número é o endereço que usaremos.
3. class TabelaHash: começa a “fôrma” do objeto. Tudo dentro define como a tabela funciona.
4. def __init__(self, tamanho): é o construtor. self é o próprio objeto que está nascendo. tamanho vem de fora, é o número de posições da tabela.
5. self.size = tamanho guarda dentro do objeto, para uso futuro, o total de posições.
6. self.table = [ [] for _ in range(tamanho) ] cria a estrutura interna: uma lista com tamanho listas vazias. Cada [] é um balde. O _ é só um contador que não usamos.
7. def setar_item(self, chave, valor): método para inserir. chave é o nome; valor é o telefone.
8. indice = funcao_hash(chave, self.size) calcula em que posição da tabela essa chave deve ficar. indice é um número de 0 até self.size-1.
9. self.table[indice].append([chave, valor]) vai até o balde na posição indice e coloca no final da lista o par [chave, valor]. Se já houver pares ali, ele apenas adiciona mais um (encadeamento).
10. def obter_item(self, chave): método de busca. Recebe a chave que queremos achar.
11. indice = funcao_hash(chave, self.size) recalcula onde a chave deveria estar. indice de novo é um número entre 0 e self.size-1.
12. for par in self.table[indice]: percorre cada item dentro do balde. Cada par é uma lista de dois itens: par[0] é a chave armazenada; par[1] é o valor (telefone).
13. if par[0] == chave: compara a chave guardada com a chave que estamos procurando. Se forem iguais, encontramos.
14. return par[1] devolve o valor (telefone) do par encontrado e encerra a função imediatamente.
15. return None se o laço terminou sem achar, devolve None para sinalizar “não existe”.
16. def __repr__(self): método especial para representar o objeto como texto quando você usa print.
17. linhas = [] cria uma lista vazia chamada linhas, onde guardaremos cada linha de texto que descreve a tabela.
18. for indice, balde in enumerate(self.table): percorre cada posição. indice é o número (0,1,2,...); balde é a lista de pares naquela posição.
19. linhas.append(f"{indice:2}: {balde}") cria um texto mostrando o número do índice e o conteúdo do balde e adiciona esse texto à lista linhas.
20. return "\n".join(linhas) junta todos os textos da lista linhas usando quebra de linha como separador e devolve o texto final para ser impresso.
21. tabela_hash = TabelaHash(30) cria um novo objeto da classe, com 30 posições. tabela_hash é a variável que guarda a tabela pronta para uso.
22. tabela_hash.setar_item("Bruno", "333") (e as demais chamadas) inserem nomes e telefones. Em cada chamada, chave é o nome, valor é o telefone, indice é calculado e o par é colocado no balde certo.
23. print(tabela_hash) pede ao Python para mostrar o objeto. O Python chama __repr__ e imprime todas as linhas com índices e baldes.
24. nome_busca = input("Digite o nome que deseja buscar: ") mostra uma mensagem na tela e espera o usuário digitar. O que foi digitado vira o valor da variável nome_busca.
25. resultado = tabela_hash.obter_item(nome_busca) chama o método de busca passando nome_busca. O retorno vai para resultado. Se achou, é o telefone; se não, é None.
26. if resultado is not None: verifica se resultado não é None. Isso significa que a chave foi encontrada.
27. print("Telefone:", resultado) se encontrou, imprime a palavra “Telefone:” seguida do número retornado.
28. else: caso contrário, segue para o bloco de “não achou”.
29. print("Nome não encontrado na tabela hash.") imprime a mensagem dizendo que o nome digitado não está na estrutura.