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?
(b) h(x)=x % 14

Passo 1

O enunciado diz que temos um conjunto de chaves x formadas pelos primeiros n múltiplos de 7, isto é, xk = 7k para k=1,2,dots,n. O hash usado é h(x)=x % 14. 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 xk=7k, temos
h(xk)=7k ;%;14,
Note que 7equiv7pmod14 e 14equiv0pmod14. Assim, se k é ímpar, 7kequiv7pmod14, e se k é par, 7kequiv0pmod14. Logo só aparecem dois valores de hash possíveis: 7 e 0.

Passo 3

Agora, vamos contar quantas chaves caem em cada bucket:
  • Bucket 7: chaves com k ímpar. Há lceil n/2rceil desses.
  • Bucket 0: chaves com k par. Há lfloor n/2rfloor 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
max(0,lceil n/2rceil-1)emax(0,lfloor n/2rfloor-1),
Somando as colisões dos dois buckets, para n>=2
l(lceil n/2rceil-1r)+l(lfloor n/2rfloor-1r)=n-2,

Resposta

O número de colisões é max(0,,n-2), ou seja, para n>=2 teremos exatamente n-2 colisões.

Exercícios relacionados