Em uma tabela hash, as colisões ocorrem quando duas chaves diferentes são mapeadas para o mesmo índi...

Alternativa A - Procurando outra posição livre na tabela.

Introdução

As tabelas hash são estruturas de dados eficientes para armazenar e recuperar informações rapidamente, mapeando chaves para índices de um array através de uma função de hash. Contudo, é inerente a esta estrutura a possibilidade de que duas chaves diferentes sejam mapeadas para o mesmo índice, um fenômeno conhecido como colisão. A forma como essas colisões são tratadas é crucial para a performance e a correção da tabela hash. Diversas técnicas de resolução de colisões existem, sendo o endereçamento aberto uma das mais proeminentes.

Desenvolvimento

O endereçamento aberto (ou open addressing) é uma família de técnicas de resolução de colisões em tabelas hash que, ao invés de usar estruturas de dados auxiliares (como listas encadeadas) para armazenar múltiplos elementos no mesmo índice, busca uma posição alternativa dentro da própria tabela hash quando uma colisão ocorre. O princípio fundamental é que todos os elementos são armazenados diretamente na tabela hash.

Quando uma colisão ocorre (ou seja, a função de hash mapeia uma nova chave para uma posição já ocupada), o algoritmo de endereçamento aberto inicia uma sequência de "provas" (em inglês, probe sequence) para encontrar o próximo slot vazio na tabela. Essa sequência de provas é determinada por um método específico e pode ser de diferentes tipos:

1. Sondagem Linear (Linear Probing): A cada colisão, o algoritmo tenta o próximo slot sequencialmente (índice + 1, índice + 2, etc., com wraparound ao final da tabela).
2. Sondagem Quadrática (Quadratic Probing): A cada colisão, o algoritmo tenta slots a uma distância quadrática da posição inicial (índice + 1², índice + 2², etc.).
3. Hashing Duplo (Double Hashing): Utiliza uma segunda função de hash para determinar o tamanho do "salto" na sequência de provas, oferecendo geralmente melhor distribuição e menor aglomeração.

Em todos os casos, o objetivo é sempre encontrar uma posição livre na tabela para inserir o novo elemento. Para buscar um elemento, a mesma sequência de provas é seguida até que o elemento seja encontrado ou um slot vazio seja alcançado (indicando que o elemento não está na tabela).

Análise

Vamos analisar cada alternativa à luz do conceito de endereçamento aberto:

• A) Procurando outra posição livre na tabela.

  • Correta. Esta afirmação descreve a essência do endereçamento aberto. Quando uma colisão ocorre, a técnica não desiste do item, mas sim inicia uma sequência de buscas (provas) por um slot vazio na própria tabela para armazenar o novo elemento.

• B) Aumentando o tamanho da tabela hash.

  • Incorreta. Aumentar o tamanho da tabela hash (conhecido como rehashing ou resizing) é uma estratégia para reduzir a probabilidade de futuras colisões e manter a eficiência da tabela à medida que ela se enenche. No entanto, não é um método para resolver uma colisão individual no momento em que ela ocorre. Colisões ainda podem ocorrer em tabelas maiores.

• C) Usando uma lista encadeada para cada posição da tabela.

  • Incorreta. Esta descrição corresponde à técnica de resolução de colisões conhecida como encadeamento separado (ou separate chaining). Neste método, cada posição do array da tabela hash aponta para uma lista encadeada (ou outra estrutura de dados) que armazena todos os elementos que mapeiam para aquele índice. Isso é fundamentalmente diferente do endereçamento aberto, que armazena todos os elementos diretamente no array principal.

• D) Utilizando duas funções de hash diferentes.

  • Incorreta. Embora o hashing duplo (um tipo de endereçamento aberto) utilize uma segunda função de hash, a resolução da colisão em si ainda é feita pela busca de uma posição livre na tabela, e não pela mera utilização de duas funções. A segunda função de hash apenas ajuda a determinar a sequência de provas de forma mais eficaz. Outras formas de endereçamento aberto (linear, quadrático) não usam duas funções de hash. Portanto, esta alternativa não descreve o mecanismo geral de resolução de colisões do endereçamento aberto, mas sim um detalhe de uma de suas sub-técnicas.

• E) Removendo elementos antigos para dar lugar aos novos.

  • Incorreta. Esta não é uma técnica de resolução de colisões em tabelas hash no sentido de garantir que todos os elementos possam ser armazenados e recuperados. A remoção de elementos antigos para dar lugar aos novos seria uma política de cache ou de substituição de dados, onde a perda de dados é aceitável, o que não é o objetivo de uma tabela hash padrão. Uma tabela hash deve ser capaz de armazenar todos os elementos inseridos (até sua capacidade máxima) e resolver colisões sem perda de dados.

Conclusão

O endereçamento aberto é uma técnica eficaz para gerenciar colisões em tabelas hash, diferenciando-se por sua abordagem de busca interna por slots vazios. A sua característica principal é que, diante de uma colisão, o algoritmo não desiste do slot original, mas sim procura por uma posição alternativa dentro do próprio array da tabela, seguindo uma sequência de tentativas pré-definida, até encontrar um local desocupado para o novo elemento.

Alternativa A.