Quando se utiliza tabelas Hash, pode ocorrer colisão. Quais são os métodos de tratamento de colisão? Explique cada um deles com suas palavras.

Passo 1

O exercício pede para listarmos e explicarmos os métodos de tratamento de colisão em tabelas hash. O conteúdo aqui é estruturas de dados (tabelas hash) e precisamos entender como, quando duas chaves mapeiam para o mesmo índice, a gente resolve esse “conflito”.

Passo 2

Uma forma é o encadeamento separado (separate chaining). Aqui cada posição do vetor da tabela guarda uma lista (ou outro container) de pares (chave, valor). Quando ocorre colisão, a gente simplesmente insere o novo par no final (ou início) da lista naquele índice. Na hora de buscar, percorremos só a lista daquele slot. É simples e cresce proporcionalmente às colisões naquele índice.

Passo 3

Outra grande família é o endereçamento aberto (open addressing). Em vez de listas, todos os pares ficam na tabela original e, se der colisão, calculamos um novo índice pela própria função hash ou fórmulas auxiliares. Existem três abordagens principais:
  • Sondagem linear (linear probing): se o índice h(k) estiver ocupado, testamos (h(k)+1) mod m, depois (h(k)+2) mod m e assim por diante até achar uma vaga.
  • Sondagem quadrática (quadratic probing): em vez de andar um a um, saltamos de forma quadrática: testamos h(k)+1², h(k)+2², h(k)+3²… mod m, reduzindo agrupamentos longos.
  • Hashing duplo (double hashing): usamos uma segunda função hash g(k) para definir o passo do salto, testando índices h(k)+i·g(k) mod m. Isso espalha melhor e costuma reduzir colisões encadeadas.

Passo 4

Um refinamento comum é o rehashing ou redimensionamento. Quando a tabela atinge certa carga (por exemplo, 70% cheia), cria-se um novo vetor maior e reinserem-se todas as chaves com a função hash ajustada ao novo tamanho. Isso reduz colisões e mantém busca e inserção rápidas.

Resposta

Os métodos de tratamento de colisão são:
• Encadeamento separado (separate chaining)
• Endereçamento aberto (open addressing) com sondagem linear, quadrática e hashing duplo
• Rehashing (redimensionamento da tabela)

Exercícios relacionados