GabaritoB — perfeito.
Gabarito: letra B. O hashing perfeito é a única técnica que garante, no pior caso, O(1) acessos à memória para executar uma busca, pois utiliza uma função hash injetora que elimina colisões (geralmente com duas camadas de hash).
A questão cobra o conhecimento das diferentes abordagens de hashing e suas garantias de complexidade. Vamos analisar cada alternativa.
Hashing direto (direct addressing) não é uma técnica de hashing no sentido estrito: ela usa a chave como índice em um array, exigindo que o universo de chaves seja pequeno e contíguo. Não se trata de uma função que "espalha" os dados, e no contexto de hashing com colisões, não garante O(1) no pior caso.
Hashing perfeito (perfect hashing) é uma técnica que, mediante duas funções hash, assegura que não haja colisões. A primeira função distribui as chaves em buckets, e a segunda, dentro de cada bucket, é uma função hash perfeita. Assim, qualquer busca requer exatamente duas sondagens (ou uma, dependendo da implementação), resultando em O(1) no pior caso.
Hashing fechado é sinônimo de endereçamento aberto (open addressing). Nessa técnica, as colisões são resolvidas por sondagem (linear, quadrática, duplo hash). No pior caso, quando a tabela está cheia, pode ser necessário percorrer toda a tabela, resultando em O(n).
Hashing uniforme é uma suposição teórica sobre a distribuição das chaves, não uma técnica. Ela afirma que cada chave tem igual probabilidade de ser mapeada para qualquer slot. Isso não garante O(1) no pior caso; apenas que o comportamento médio é bom.
Gabarito: letra B.
Link permanente: /questoes/qq455157