No uso de estruturas de transformação de chave (hashing), a ...

Gabarito: E (Errado)

A questão aborda o tema de hashing, uma técnica de estrutura de dados muito utilizada para a rápida localização de dados. Hashing envolve a utilização de uma função de hash para transformar chaves em índices de um array. No entanto, um dos desafios do hashing é lidar com colisões, que ocorrem quando diferentes chaves são mapeadas para o mesmo índice.

Para resolver colisões, uma das técnicas mais comuns é o encadeamento (ou chaining), onde cada posição do array (bucket) aponta para uma lista ligada que contém todos os elementos mapeados para aquele índice.

Afirmar que o encadeamento "tem como principal característica o fato de nunca transbordar" está incorreto. O encadeamento realmente previne o transbordo do bucket no array principal, mas podemos considerar que há um "transbordamento" na lista ligada quando ela se torna muito longa, o que pode afetar o desempenho.

A segunda parte da questão menciona que o tempo de busca pode ser reduzido se uma lista duplamente encadeada for utilizada. Isto também está incorreto. O uso de uma lista duplamente encadeada em vez de uma lista simplesmente encadeada não melhora o tempo de busca. Na busca, o tempo é normalmente O(n) (onde n é o número de elementos na lista) independentemente de ser uma lista simplesmente ou duplamente encadeada. O benefício de uma lista duplamente encadeada está na facilidade de remoção e inserção de elementos, não na busca.

Agora, vamos analisar com mais detalhes as situações mencionadas:

• Encadeamento: Cada posição do array aponta para uma lista ligada. Esta técnica é eficiente para lidar com colisões porque permite armazenar múltiplos elementos por índice sem necessidade de reestruturação do array.
• Transbordamento: No contexto de hashing, geralmente se refere a uma situação onde não há mais espaço em um bucket. No encadeamento, este tipo de transbordamento é evitado, mas listas muito longas no bucket podem ocorrer.
• Listas Duplamente Encadeadas: São úteis para operações de remoção e inserção, pois permitem um acesso bidirecional, mas não melhoram o tempo de busca em comparação com listas simplesmente encadeadas.

Portanto, a alternativa correta é E (Errado) porque a afirmação faz uma generalização equivocada sobre as características do encadeamento e atribui melhorias de desempenho na busca que não são atribuíveis a listas duplamente encadeadas.

Uso da posição consecutiva livre:
• Os elementos que colidem são armazenados em posições da tabela ainda não ocupadas;
• Uma das estratégias consiste em buscar a próxima posição livre (utilizando incremento circular):

Usa-se somente um a Lsta Encadeada

Se eu quiser eu posso utilizar uma lista duplamente encadeada no meu hashing. Mas isso significa aumento do gasto de memória para armezenar 1 ponteiro a mais desnecessário. O erro da questão está em dizer que "Adicionalmente, o tempo de busca na lista ligada pode ser reduzido se uma lista duplamente encadeada for utilizada." 


A complexidade temporal para a busca de um elemento numa lista encadeada é(em termos assintóticos) a mesma se comparada com uma lista duplamente encadeada. O(n) no tamanho da lista.

Um método alternativo citado por Wirth é o método de endereçamento aberto. 

(ERRO EM VERMELHO) No uso de estruturas de transformação de chave (hashing), a solução de colisões usando encadeamento tem como principal característica o fato de nunca transbordar. Adicionalmente, o tempo de busca na lista ligada pode ser reduzido se uma lista duplamente encadeada for utilizada.

 

---> Tanto lista encadeada quanto lista duplamente encadeada possuem A MESMA COMPLEXIDADE, portanto o tempo não pode ser reduzido na lista duplamente encadeada.