No estudo de tabelas hash, um problema comum é a ocorrência de colisões, que ocorrem quando duas cha...

Alternativa (A) - No encadeamento separado, elementos colididos são armazenados em uma lista encadeada associada à posição original da colisão.

Introdução

Tabelas hash são estruturas de dados eficientes para armazenamento e recuperação de informações, utilizando uma função hash para mapear chaves a posições (índices) em um array. Contudo, a natureza finita das tabelas e a potencial infinitude de chaves podem levar a colisões, onde diferentes chaves geram o mesmo índice. A resolução de colisões é um aspecto crítico na performance e correção de tabelas hash. Entre as técnicas existentes, o encadeamento separado é uma das mais diretas e comumente utilizadas.

Desenvolvimento

O problema de colisões em tabelas hash ocorre quando h(chave1) = h(chave2), mas chave1 ≠ chave2. Para lidar com isso, diversas estratégias de resolução de colisões foram desenvolvidas. O encadeamento separado (ou separate chaining) é uma abordagem que modifica a estrutura de cada "slot" ou "bucket" da tabela hash. Em vez de cada slot armazenar diretamente um único elemento, ele passa a armazenar um ponteiro para uma estrutura de dados secundária, que por sua vez, contém todos os elementos que mapearam para aquela mesma posição.

A estrutura de dados secundária mais comum para o encadeamento separado é a lista encadeada. Assim, cada posição da tabela hash torna-se o "cabeçalho" de uma lista encadeada. Quando um elemento é inserido e sua chave mapeia para uma posição já ocupada (ou seja, uma colisão ocorre), o novo elemento é simplesmente adicionado ao final (ou início) da lista encadeada associada àquela posição. Para buscar um elemento, a função hash é usada para encontrar a posição, e então a lista encadeada naquela posição é percorrida para encontrar o elemento desejado.

Análise

Vamos analisar cada alternativa à luz do funcionamento do encadeamento separado:

• (A) No encadeamento separado, elementos colididos são armazenados em uma lista encadeada associada à posição original da colisão. Esta alternativa descreve perfeitamente o encadeamento separado. Cada posição da tabela (chamada de bucket) passa a ser um ponteiro para o início de uma lista encadeada. Todos os elementos cujas chaves resultam no mesmo valor de hash são armazenados nessa lista encadeada específica. Isso significa que, mesmo havendo uma colisão, o elemento é armazenado na mesma posição inicial do hash, mas em uma subestrutura dedicada.

• (B) O encadeamento separado usa uma função hash secundária para realocar elementos colididos em diferentes posições na tabela. Esta descrição se refere a técnicas de endereçamento aberto, como o hashing duplo (double hashing), onde uma segunda função hash é usada para determinar os passos de sondagem para encontrar uma posição livre na própria tabela. No encadeamento separado, não há realocação em diferentes posições da tabela principal; os elementos permanecem logicamente associados ao seu slot de hash original.

• (C) O encadeamento separado utiliza uma técnica de sondagem para encontrar a próxima posição livre na tabela onde o elemento colidido será armazenado. Esta alternativa descreve técnicas de endereçamento aberto (open addressing), como o teste linear (linear probing), teste quadrático (quadratic probing) ou hashing duplo. Nesses métodos, em caso de colisão, o algoritmo "sonda" (testa) outras posições na tabela principal até encontrar um slot vago. O encadeamento separado não realiza sondagem na tabela principal, pois armazena os elementos em estruturas auxiliares nas posições já definidas.

• (D) O encadeamento separado implementa um algoritmo de ordenação para reordenar os elementos colididos em uma nova sequência. A ordenação não é uma técnica de resolução de colisões em tabelas hash. Embora os elementos dentro de uma lista encadeada em um bucket possam ser mantidos ordenados para otimizar buscas (o que é raro, pois introduz overhead de inserção), isso não é a essência da resolução de colisões do encadeamento separado, nem é o método primário para resolver a colisão em si. A colisão é resolvida pelo armazenamento em uma lista.

• (E) No encadeamento separado, elementos colididos são descartados e armazenados em uma tabela hash auxiliar. Descartar elementos que colidem é inaceitável em qualquer implementação de tabela hash, pois resultaria em perda de dados. Embora seja possível ter tabelas auxiliares para propósitos específicos, a técnica de encadeamento separado armazena os elementos colididos em listas encadeadas diretamente associadas aos slots da tabela hash principal, e não em uma "tabela hash auxiliar" separada, nem os "descarta" do fluxo principal.

Conclusão

O encadeamento separado é uma técnica robusta para lidar com colisões em tabelas hash. Sua principal característica é a utilização de estruturas de dados auxiliares, geralmente listas encadeadas, em cada posição da tabela. Quando ocorre uma colisão, os elementos são adicionados a essa lista associada ao índice gerado pela função hash, garantindo que todos os dados sejam armazenados e recuperáveis sem a necessidade de realocação ou busca por posições alternativas na tabela principal. A alternativa (A) captura com precisão essa mecânica fundamental.

Alternativa (A).