O custo é esperado, não mágico.
Com distribuição próxima de uniforme e carga controlada, get, put e delete têm custo esperado O(1). Se muitas chaves formarem o mesmo bucket ou uma sequência longa de sondagem, o pior caso continua O(n).
LR / 04Hash
E se duas chaves caírem no mesmo lugar?
Uma função de dispersão (hash) transforma a chave em um índice para localizar dados rapidamente; colisões exigem uma estratégia de resolução.
instrumentação / estado atual
passo01 / 04Calcular endereço
foco4Nesta demonstração, a função mapeia a chave 'lua' para o índice 4; o próximo quadro verifica se esse endereço está livre.
complexidadeO(1)caso médio
índice4observado agora
/ visualização em execução
frame 01Calcular endereço
0·
1key
2·
3·
4·
5·
6·
7·
índice → sondagem → endereço/ decisão observadaO algoritmo compara o estado atual antes de avançar.
Passo 1 · Nesta demonstração, a função mapeia a chave 'lua' para o índice 4; o próximo quadro verifica se esse endereço está livre.
Passo 1: Nesta demonstração, a função mapeia a chave 'lua' para o índice 4; o próximo quadro verifica se esse endereço está livre.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o trabalho tende a crescer quando n, a quantidade de elementos na estrutura, aumenta.
operações
O(1) · Custo constante
A operação usa um ponto conhecido da estrutura, sem precisar percorrer todos os elementos. O número de passos não cresce com n.
Push, pop e acesso médio em uma Hash Table podem permanecer constantes quando a implementação preserva sua estrutura.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para contrastar operações locais de extremidade com uma decomposição recursiva cujo número de movimentos cresce exponencialmente. Stacks & Queues tende a crescer mais devagar do que Towers of Hanoi quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
/ raciocínio sincronizado
A mesma ideia, três leituras.
01
índice = hash(chave) % capacidade02
se posição livre: grave o par03
se houver colisão: avance para a próxima posição04
pare ao encontrar a chave ou um espaço livreO destaque acompanha o passo atual; leia a linha destacada antes de avançar.
/ leitura técnica · acesso por chave
Hash não elimina colisões; organiza a busca.
Uma Hash Table transforma uma chave em um índice provável de um vetor. O desempenho nasce da combinação entre função de dispersão, regra de igualdade, fator de carga e uma política correta para os conflitos inevitáveis.
chave→hash(chave)→índice / bucket
CONTRATO / IGUALDADE E HASH
Igualdade igual exige hash igual.
Se duas chaves representam o mesmo valor lógico, precisam gerar o mesmo hash. O inverso não vale: chaves diferentes podem cair no mesmo índice; por isso, a tabela ainda compara a chave antes de devolver, substituir ou remover uma associação.
Colisão pede uma política.
- Encadeamento separado: cada índice guarda um contêiner de pares; a remoção é direta e a carga pode superar 1.
- Endereçamento aberto: os pares ficam no próprio vetor e a busca segue uma sequência de sondagem até achar a chave ou um vazio verdadeiro.
Remover não é apenas esvaziar.
Em sondagem, limpar uma célula pode interromper o caminho de uma chave posterior. Um tombstone marca uma remoção sem encerrar a busca; acumulado demais, porém, aumenta sondagens e pede uma limpeza por rehash.
MEDIDA CRÍTICA / FATOR DE CARGA
αN / M
Tempo e memória negociam no mesmo controle.
Menos entradas por posição ou por sequência tende a reduzir comparações e sondagens. Em endereçamento aberto, α deve permanecer abaixo de 1 porque uma posição guarda no máximo um par.
Mudar a capacidade exige reinserir as entradas: o índice depende de M. Uma expansão pode custar O(n) em uma chamada, mas crescer geometricamente mantém o custo amortizado de inserções em O(1).
/ garantia depende da entrada
Uma chave mutável pode se tornar invisível.
Se uma chave muda depois de ser inserida e seus campos participam do hash ou da igualdade, uma busca futura pode seguir para outro índice. Prefira chaves imutáveis. Quando as chaves vêm de uma fonte adversarial, colisões fabricadas também podem concentrar trabalho; implementações expostas podem usar hash com chave e limites de carga para reduzir esse risco.
/ decidir pela consulta dominante
Uma tabela não é uma estrutura ordenada.
- Hash Table
- Escolha para pertinência ou associação por igualdade exata — por exemplo, caches, conjuntos e dicionários — quando a ordem não é requisito e o custo esperado constante é prioritário.
- BST balanceada
- Prefira quando predecessor, sucessor, percurso em ordem ou consulta por intervalo importam. A troca é custo logarítmico determinístico por operações ordenadas.
- Array ordenado
- É uma alternativa clara para conjuntos quase estáticos: Binary Search localiza em O(log n), enquanto inserções e remoções no meio deslocam elementos e tendem a custar O(n).