Quando se utiliza tabelas Hash, pode ocorrer colisão. Explique o que é uma colisão.

Passo 1

O enunciado pede para explicar o conceito de colisão em tabelas hash. O conteúdo envolve o funcionamento de uma tabela hash: uso de uma função de hash para mapear chaves em posições de um array e o surgimento de conflitos nesse mapeamento.

Passo 2

Em uma tabela hash, definimos uma função de hash que recebe uma chave (por exemplo, uma string ou um número) e retorna um índice de array. Esse índice indica onde armazenamos ou buscamos o valor associado àquela chave.

Passo 3

Como o número de possíveis chaves costuma ser muito maior que o tamanho do array da tabela, é inevitável que duas chaves diferentes acabem gerando o mesmo índice. Esse evento, em que duas chaves distintas são mapeadas para a mesma posição, é chamado de colisão.

Resposta

Colisão é o evento em que duas chaves distintas geram o mesmo valor de hash e, por isso, são mapeadas para a mesma posição na tabela hash.

Exercícios relacionados