Suponha um conjunto de n chaves x formado pelos n primeiros múltiplos do número 7 . Quantas colisões seriam obtidas mediante a aplicação das funções hash seguintes?
(a) h(x)=x % 7

Passo 1

Resumindo, temos um conjunto de n chaves que são os primeiros múltiplos de 7: 7, 14, 21, dots, 7n. O conteúdo é funções hash por módulo e colisões, e vamos precisar usar a operação de resto da divisão e a definição de colisão ao inserir em uma tabela hash.

Passo 2

Para cada chave x = 7k (com k variando de 1 a n), calculamos
h(x) = x % 7 = 7k % 7 = 0
Isso mostra que todas as chaves mapeiam para o mesmo valor 0.

Passo 3

Quando usamos uma tabela hash, a primeira inserção no slot 0 não gera colisão, mas cada uma das inserções das demais n-1 chaves encontra o slot já ocupado. Logo, o total de colisões é
n - 1

Resposta

n-1

Exercícios relacionados