Hash tables · Tabelas hash
Hash tables: fast lookup
- A hash table stores items so you can find them very fast — usually in one step.
- It is a list of slots. A hash function turns a key into a slot number.
- Instead of searching every item, you jump straight to the slot the key belongs in.
Tabelas hash: busca rápida
- Uma tabela hash armazena itens para que você possa encontrá-los muito rápido — geralmente em um passo.
- É uma lista de slots. Uma função hash converte uma chave em um número de slot.
- Em vez de buscar cada item, você salta direto para o slot onde a chave pertence.
A hash function
- A hash function takes a key and returns a slot index from
0tosize - 1. - The same key always gives the same slot, so you can find it again later.
- A simple one: add the character codes, then take
% sizeto stay in range.
Uma função hash
- Uma função hash pega uma chave e retorna um índice de slot de
0asize - 1. - A mesma chave sempre dá o mesmo slot, assim você pode encontrá-la novamente depois.
- Uma simples: some os códigos dos caracteres, depois aplique
% sizepara permanecer no intervalo.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Collisions
- Two different keys can hash to the same slot. That is a collision.
- A table has limited slots, so collisions are unavoidable as it fills up.
- We need a rule for what to do when the slot we want is already taken.
Colisões
- Duas chaves diferentes podem hashar para o mesmo slot. Isso é uma colisão.
- Uma tabela tem slots limitados, então colisões são inevitáveis à medida que enche.
- Precisamos de uma regra para o que fazer quando o slot desejado já estiver ocupado.
Linear probing
- Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
- Keep stepping
(slot + 1) % sizeuntil you find a free slot. - Below,
AandFboth want slot 0, soFis pushed to slot 1.
Sonda linear
- Sonda linear: se um slot estiver cheio, tente o próximo slot, depois o seguinte, voltando ao início.
- Continue avançando
(slot + 1) % sizeaté encontrar um slot livre. - Abaixo,
AeFambos querem o slot 0, entãoFé empurrado para o slot 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Looking up a key
- To find a key: hash it, then probe forward, comparing each slot to the key.
- Stop and return the index when you find it.
- If you reach an empty slot (or check every slot), the key is not there — return
-1.
Buscando uma chave
- Para encontrar uma chave: faça o hash dela, depois sonde para frente, comparando cada slot com a chave.
- Pare e retorne o índice quando encontrá-la.
- Se você chegar a um slot vazio (ou verificar todos os slots), a chave não está lá — retorne
-1.
Why hash tables are fast
- With few collisions, insert and find take about one step — we call this
O(1). - As the table fills, probing gets longer, so it is wise to keep some slots free.
- In the worst case (everything collides) it slows to a linear scan,
O(n).
Por que tabelas hash são rápidas
- Com poucas colisões, inserir e encontrar levam cerca de um passo — chamamos isso de
O(1). - À medida que a tabela enche, a sonda fica mais longa, então é prudente deixar alguns slots livres.
- No pior caso (tudo colide), desacelera para uma varredura linear,
O(n).
Common mistakes
- A hash function maps a key to an index in the table.
- Two keys can collide at the same index — handle it, for example by chaining.
Erros comuns
- Uma função hash mapeia uma chave para um índice na tabela.
- Duas chaves podem colidir no mesmo índice — trate isso, por exemplo, usando encadeamento.
Now you try
- Build the three parts: the hash function, insert with probing, and find.
- Each task checks your function on collisions and wrap-around cases.
- Press Check answer to test it.
Agora você tenta
- Construa as três partes: a função hash, inserção com sonda e busca.
- Cada tarefa verifica sua função em casos de colisão e wrap-around.
- Pressione Check answer para testá-lo.
Hashing to a bucket · Hashing para um bucket
A hash function sends each key to a bucket · balde; clashes chain. · Uma função hash envia cada chave para um bucket · balde; colisões formam cadeias.
Write hash_key(key, size). Add the character codes of key (use ord(ch)) and return the total % size, so the result is a slot from 0 to · até size - 1. Example: hash_key("AB", 10) is (65 + 66) % 10 = 1. The empty string gives 0. · Escreva hash_key(key, size). Some os códigos de caractere de key (use ord(ch)) e retorne o total % size, para que o resultado seja um slot de 0 a size - 1. Exemplo: hash_key("AB", 10) é (65 + 66) % 10 = 1. A string vazia dá 0.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
hash_key is provided. Write insert(table, key) using linear probing: go to the key's hash slot; while that slot is full (not None), step to (slot + 1) % len(table); put the key in the first free slot and return its index. · hash_key é fornecido. Escreva insert(table, key) usando probing linear: vá para o slot hash da chave; enquanto esse slot estiver cheio (não None), avance para (slot + 1) % len(table); coloque a chave no primeiro slot livre e retorne seu índice.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
hash_key is provided. Write find(table, key) that returns the index of key, or -1 if it is missing. Start at the hash slot and probe forward, comparing each slot. Stop at an empty · vazios slot (key not there). Make sure it ends even if the table is full · pleno — never loop forever. · hash_key é fornecido. Escreva find(table, key) que retorna o índice de key, ou -1 se estiver ausente. Comece no slot hash e probe para frente, comparando cada slot. Pare em um slot vazio (chave não está lá). Certifique-se de que termine mesmo se a tabela estiver cheia — nunca瞪ue infinitamente.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.