As Tabelas Hash podem usar diferentes estratégias para lidar com colisões (quando duas chaves diferentes geram o mesmo índice). Suponha que estamos inserindo nomes em uma Tabela Hash de 10 posições. A função hash gera o índice 3 para “Carlos” e, em seguida, gera o mesmo índice 3 para “Amanda”. Se a Tabela Hash utilizar a estratégia de Encadeamento (Chaining), o que acontecerá ao inserir “Amanda”?

Alternativa C

Análise do Conceito

Para responder corretamente, é necessário entender como as Tabelas Hash lidam com colisões. Uma colisão acontece quando dois elementos distintos geram o mesmo índice após aplicação da função hash.

Existem duas abordagens principais para resolver esse problema:

1. Endereçamento Aberto (Open Addressing): Os elementos são armazenados diretamente no array. Se houver colisão, busca-se a próxima posição livre disponível.
2. Encadeamento (Chaining): Cada posição do array armazena um ponteiro para uma estrutura de dados externa (geralmente uma Lista Encadeada), onde todos os elementos que colidiram naquele índice são armazenados.

Justificativa Didática

No enunciado, temos a estratégia de Encadeamento (Chaining). Vamos analisar o cenário passo a passo:

• Passo 1: "Carlos" é inserido e gera o índice 3. Ele ocupa a lista naquele slot.
• Passo 2: "Amanda" é inserida e também gera o índice 3.
• Passo 3 (Resolução): Como a estratégia é Encadeamento, não buscamos outra posição no array (como faríamos na Sondagem Linear). Em vez disso, adicionamos "Amanda" à lista que já existe no índice 3.

Por que as outras alternativas estão incorretas?

Portanto, a alternativa C descreve exatamente o comportamento do Encadeamento: adicionar o novo elemento à lista encadeada existente no índice colidido.