Funções de dispersão / Hash functions

Qualquer função que mapeie uma chave do universo U no intervalo 0..M−1 é uma função de dispersão em potencial

No entanto, uma tal função só é eficiente se distribuir as chaves pelo intervalo de uma forma razoavelmente uniforme

• mesmo quando existem regularidades nas chaves.

Uma função de dispersão ideal mapeia as chaves em inteiros de uma forma aleatória

• de forma a que as keys sejam igualmente distribuídos pelos buckets

É fundamental que a função de dispersão seja uma função no sentido matemático do termo,

• isto é, que para cada chave a função devolva sempre o mesmo código

Uma função de dispersão ideal mapeia as chaves em inteiros de uma forma aleatória

• De forma a que os valores sejam igualmente distribuídos, mesmo quando existem regularidades nas chaves

As funções de dispersão são tipicamente transformações matemáticas pseudo aleatórias, existindo uma grande variedade, com diferentes graus de complexidade e diferentes desempenhos

• Em geral o desempenho depende da aplicação pelo que é recomendável testar várias