Questão de Tecnologia da Informação · FGV BANESTES 2021 (nº 38)

Uma Tabela Hash (ou mapa, dicionário) é uma estrutura de dados que associa chaves a valores, usando uma função hash para calcular um índice (endereço) onde o valor pode ser armazenado ou recuperado rapidamente.

(A) Correta: O(1) significa que o tempo de acesso é constante, ou seja, não importa se há 10 ou 1 milhão de itens, o tempo para encontrar um dado é, em média, o mesmo. Em uma Tabela Hash bem implementada, com uma boa função hash e tratamento eficiente de colisões, o acesso é praticamente O(1) no caso médio, pois a função hash leva diretamente ao local do dado.
(B) Incorreta: O(log N) indica um tempo de acesso logarítmico, típico de estruturas como árvores binárias de busca balanceadas, onde a busca envolve dividir o espaço de busca pela metade a cada passo.
(C) Incorreta: O(N) indica um tempo de acesso linear, onde o tempo de busca aumenta proporcionalmente ao número de itens (N), como em uma busca sequencial em uma lista não ordenada. Esta é a armadilha da banca: embora uma Tabela Hash possa degenerar para O(N) no pior caso (quando há muitas colisões e todos os itens caem no mesmo "balde", transformando-o em uma lista linear), a pergunta usa o termo "praticamente", referindo-se ao desempenho médio e esperado de uma Tabela Hash bem projetada, que é O(1).
(D) Incorreta: O(N log N) é uma complexidade comum para algoritmos de ordenação eficientes, como Merge Sort ou Quick Sort, e não para acesso direto a dados.
(E) Incorreta: O(N²) indica um tempo de acesso quadrático, muito ineficiente, onde o tempo aumenta drasticamente com o número de itens, típico de algoritmos de ordenação ineficientes como Bubble Sort no pior caso.