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?
© h(x)=x % 5

Passo 1

O enunciado diz que temos um conjunto de n chaves x = {7, 14, 21, …, 7n} e queremos aplicar a função hash h(x) = x % 5. O conteúdo aqui é aritmética modular e contagem de colisões em hash.

Passo 2

Para ver em que bucket cada chave cai, note que se x = 7k então
h(x)=7kbmod5=(7bmod5),(kbmod5)bmod5=2,kbmod5
Isto significa que à medida que k varia de 1 a n, h(x) assume valores cíclicos em {0,1,2,3,4} com período 5.

Passo 3

Como 2 é invertível módulo 5, os valores 2k\bmod5 para k=1,…,5 são todos distintos, portanto o padrão de resíduos repete a cada 5 chaves. Logo temos 5 buckets, cada um recebendo ou ⌊n/5⌋ ou ⌊n/5⌋+1 chaves, dependendo do resto r=n\bmod5.

Passo 4

Em hashing, a primeira inserção em um bucket não causa colisão, e cada chave adicional naquele mesmo bucket causa uma colisão. Se chamarmos c_i o número de chaves no bucket i, as colisões totais são ∑₁⁵(c_i−1)=n−(#buckets não vazios).

Passo 5

Se n<5, teremos menos de 5 buckets preenchidos e nunca sobra chave para colidir, então colisões=0. Se n≥5, todos os 5 buckets estarão não vazios e teremos
colisões = n - 5 õ

Resposta

Colisões = max(0, n − 5)

Exercícios relacionados