Funções de dispersão universais

Quaisquer duas chaves do universo colidem com probabilidade máxima igual a 1/M quando a função de dispersão h é extraída aleatoriamente de H

• exatamente a probabilidade de colisão esperada caso a função de dispersão gerasse códigos realmente aleatórios para cada chave

Esta solução garante um baixo número de colisões em média, mesmo no caso de os dados serem escolhidos por alguém interessado na ocorrência do pior cenário

Este tipo de funções pode utilizar mais operações do que as funções que vimos anteriormente