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?
©
©
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
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
Resposta
Colisões = max(0, n − 5)