Suponha um conjunto de
chaves
formado pelos
primeiros múltiplos do número 7 . Quantas colisões seriam obtidas mediante a aplicação das funções hash seguintes?
(a)
(a)
Passo 1
Resumindo, temos um conjunto de
chaves que são os primeiros múltiplos de 7:
. 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
(com
variando de 1 a
), calculamos
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
chaves encontra o slot já ocupado. Logo, o total de colisões é