Questão de Tecnologia da Informação · FGV TCE-SP 2023 (nº 41)

Hash Tables (Tabelas Hash) são estruturas que usam uma função para transformar uma "chave" (como um ID) em um endereço direto na memória, permitindo encontrar dados muito rapidamente. B-trees são estruturas de dados em forma de árvore que mantêm os dados ordenados, o que é ótimo para buscas por faixas de valores e para lidar com grandes volumes de dados em disco.

• (A) Incorreta: A complexidade de busca em tabelas Hash, no caso médio ideal (sem muitas colisões), é O(1) (tempo constante), e no pior caso é O(N) (tempo linear). O(N/2) não é uma complexidade padrão para tabelas Hash; ela se assemelha mais a uma busca linear em uma lista não ordenada, o que não é o objetivo de uma tabela Hash. A complexidade O(log N) para B-trees está correta.
• (B) Correta: B-trees armazenam as chaves em ordem. Isso significa que, uma vez encontrada a chave inicial de um intervalo, é possível percorrer a árvore sequencialmente para encontrar todas as chaves dentro daquele intervalo de forma muito eficiente. Essa é uma das grandes vantagens das B-trees sobre as tabelas Hash.
• (C) Incorreta: Tabelas Hash mapeiam uma chave para um valor. Se você tem "múltiplas chaves para o mesmo objeto indexado" (por exemplo, chave1 -> objetoA e chave2 -> objetoA), isso significa que você terá duas entradas distintas na tabela Hash, cada uma com sua própria chave e seu próprio hash, apontando para o mesmo objeto. Embora o objeto em si não seja redundante, as entradas do índice para chave1 e chave2 são distintas e ocupam espaço. Uma tabela Hash não "gerencia" intrinsecamente múltiplas chaves para um único item de índice de forma especial; ela simplesmente trata cada chave como única. A armadilha aqui é confundir a não redundância do dado com a não redundância das entradas do índice para chaves diferentes.