Considerando uma tabela Hash com uma boa função de Hash e carga balanceada, qual é a complexidade de tempo médio para a operação de busca?

Gabarito

A

Comentário do professor

Na tabela Hash a resposta correta é O(1): tempo constante em média para a operação de busca. Isso significa que, para uma **busca por chave exata**, a obtenção do índice a partir da chave pela função de hash é feita em tempo constante, permitindo acesso direto ao balde apropriado.

Com o fator de carga controlado — \( \alpha = n/m \) mantido aproximadamente constante — e uma função que espalhe bem as chaves, o número esperado de elementos por balde permanece limitado. Dessa forma, a inspeção dentro do balde demanda um número médio de passos constante.

Quando ocorrem colisões, técnicas como encadeamento, endereçamento aberto e o redimensionamento periódico preservam a expectativa de custo de busca em \(O(1)\) no tempo médio.