Pular para o conteúdo

O básico de tabelas hash

Aula 1 de 8 · 4 min

O básico de tabelas hash

Passo 1 de 6

Uma tabela hash é um conjunto de caixas numeradas. A própria chave decide qual: sem percorrer prateleiras, sem ordenar.

A ideia

Uma tabela hash passa cada chave por uma função hash que retorna o número de um bucket. Armazenar e buscar pulam direto para esse bucket, então o custo médio fica em O(1), não importa quantas chaves existam. O preço: as chaves precisam ser hashable, e a ordem nunca é garantida.

Exemplo do mundo real

Uma farmácia guarda as receitas prontas em caixas numeradas pelos dois últimos dígitos do número do pedido. Ninguém percorre as prateleiras lendo etiquetas — o número no seu comprovante é a caixa. Duzentas sacolas esperando custam a mesma busca que cinco.

O código

Sua vez

O que isto imprime?

shelf = {"a": 1, "b": 2}
shelf["c"] = 3
shelf["a"] = 9
print(len(shelf), shelf["a"])

Mini quiz

1 / 3

O que uma função hash produz a partir de uma chave?