O que é hashing universal?

Passo 1

A questão pede para entender o que é hashing universal, que faz parte de estruturas de dados (tabelas de dispersão) e análise probabilística de algoritmos.

Passo 2

Primeiro, vamos lembrar o que é hashing: você tem uma função de hash que mapeia chaves de um universo grande para índices de uma tabela de tamanho m, mas colisões podem acontecer quando duas chaves diferentes caem no mesmo índice.
Hashing universal melhora o comportamento médio contra colisões ao não usar uma única função fixa, mas escolher aleatoriamente uma função h de uma família de funções H previamente definida.

Passo 3

Formalmente, uma família H de funções de hash de um universo U para {0,1,…,m−1} é dita universal se, para quaisquer chaves distintas x,y∈U, vale
Prhin H[h(x)=h(y)] <= 1m
Isso significa que a probabilidade de colisão entre x e y é, no máximo, 1/m, quando h é sorteada uniformemente de H.

Passo 4

Na prática, hashing universal garante que o número esperado de colisões por operação seja pequeno, levando tempo médio O(1) para inserções e buscas em tabelas de dispersão.

Resposta

Hashing universal é a técnica de usar uma família de funções de hash escolhidas aleatoriamente, de forma que a probabilidade de colisão entre quaisquer duas chaves distintas seja, no máximo, 1/m.

Exercícios relacionados