João pretende armazenar uma coleção de dados referentes a cerca de um milhão de pessoas. Cada pessoa tem como chave de acesso um número inteiro sequencial, que não se repete. Empregando uma estrutura de Tabela Hash, João conseguiria obter, praticamente, acesso com complexidade:
- A)O(1)
Correta, porque a tabela hash permite acesso médio praticamente constante à posição associada à chave.
- B)O(log N)
Errada, pois O(log N) é típico de estruturas ordenadas, como árvores balanceadas, e não da tabela hash.
- C)O(N)
Errada, porque O(N) indicaria varredura linear da coleção, o que a hash justamente evita.
- D)O(N log N)
Errada, já que O(N log N) aparece em algoritmos de ordenação e processamento mais custoso, não no acesso por hash.
- E)O(N2)
Errada, porque O(N2) é um custo muito maior e não corresponde ao acesso direto fornecido por tabela hash.
Gabarito: A
Tabela hash é a clássica estrutura usada quando você quer acesso muito rápido a um dado pela sua chave. A ideia é transformar a chave em um índice por meio de uma função hash, indo quase direto ao endereço do elemento. Por isso, em condições normais e com uma boa função hash, o acesso fica praticamente constante, sem precisar varrer a coleção inteira. Neste caso, a chave já é um número inteiro sequencial e sem repetição, o que facilita ainda mais a organização dos dados. Mesmo assim, o ponto central da questão não é a sequencialidade, mas o fato de a tabela hash permitir busca, inserção e remoção em tempo médio constante. Em provas, isso costuma aparecer como complexidade O(1). Claro que, no pior cenário, colisões podem atrapalhar e degradar o desempenho. Mas a banca perguntou o acesso "praticamente", isto é, no uso esperado da estrutura, e não no caso extremo. Então a resposta correta é a alternativa A, porque a tabela hash entrega acesso médio em O(1), que é justamente sua grande vantagem. Resumo de bolso: se a questão falar em tabela hash e acesso por chave, pense primeiro em tempo constante. Se não houver pegadinha explícita sobre colisões ou pior caso, a resposta quase sempre aponta para O(1).