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?
(b)
(b)
Passo 1
O enunciado diz que temos um conjunto de chaves
formadas pelos primeiros
múltiplos de 7, isto é,
para
. O hash usado é
. Vamos precisar entender como funciona o operador
(resto da divisão) e depois contar quantas colisões isso gera.
Passo 2
Primeiro, observamos os valores de cada chave ao aplicar o hash. Como
, temos
Note que
Passo 3
Agora, vamos contar quantas chaves caem em cada bucket:
- Bucket
: chaves com ímpar. Há desses. - Bucket
: chaves com par. Há desses.
Passo 4
Cada bucket sofre colisões a partir da segunda chave que chega. Então as colisões em cada bucket são
Somando as colisões dos dois buckets, para
Resposta
O número de colisões é
, ou seja, para
teremos exatamente
colisões.