Questão referente ao Texto-base: Estruturas de dados e seus algoritmos (Leia as páginas 232 a 250) | Jayme Luiz Szwarcfiter e Lilian Markezon O tra...

Questão referente ao Texto-base: Estruturas de dados e seus algoritmos (Leia as páginas 232 a 250) | Jayme Luiz Szwarcfiter e Lilian Markezon
O tratamento de colisões usando listas encadeadas fora do vetor é uma solução muito usada. Sobre esse mecanismo de tratamento de colisões, assinale a alternativa correta.


✅ É usual efetuar-se a inclusão dos elementos no final da lista encadeada correspondente à função de hash de sua chave, dado que a lista precisaria ser percorrida de qualquer maneira para garantir que a chave já não estava na lista antes.
Para remover o elemento de uma tabela hash quando o tratamento de colisões é feito externamente por listas encadeadas, precisamos procurar na lista encadeada correspondente à função de hash de sua chave. Se o elemento não for encontrado, procuramos na lista encadeada seguinte, e assim por diante, até encontrar o elemento.
Uma desvantagem da utilização de listas encadeadas é que o número de elementos na tabela hash deverá ser fixado em tempo de compilação, não sendo possível inserir novos elementos na estrutura quando o espaço alocado se esgotar.
Quando temos chaves sinônimas, isto é, chaves em que a função de hash mapeia para o mesmo endereço, alocamos os elementos em listas encadeadas diferentes para garantir que a busca por uma chave ocorrerá no menor tempo possível.
A utilização de listas encadeadas para tratamento de colisões permite a implementação de tabelas hash sem a necessidade de estudar o fator de carga, dado que este se torna irrelevante por podermos inserir e remover elementos em tempo constante de listas encadeadas.