Re: Dúvidas

> O exercício 14.4 (hashing) pede para fazer um programa que calcula os
> valores de a e de M, com o valor de M menor possível, de modo que não haja
> colisões para uma certa lista de chaves. Como se faz isso? Se caísse essa
> questão na prova eu faria desse jeito, mas não sei se esse jeito faz muito
> sentido:
>
> v[] = vetor de chaves
> n = número de chaves
>
> void perfectHash (int v[], int n, float *a, int *M) {
> int i;
> for (*M = n + 1; ; (*M)++)
>     for (i = 0; i < 100; i++) {
>       *a = rand() / RAND_MAX;
>       if (!colisao (v, n, *a, *M))
>         return;
>     }
> }
>
> Eu começo com M = n + 1 (para deixar um espaço vazio) e vou testando valores
> aleatórios de a. A função colisao() retorna true se houver colisão entre as
> chaves. Se não achar um valor adequado de a após 100 tentativas, aumento o
> valor de M.

Não sei não, talvez eu esteja errada, mas por ele pedir o valor de M tal que a*x%M é o menor possível, para que todas as chaves daquela tabela sejam diferentes, não seria muito interessante deixar a variável a ser um float, exatamente por estar em uma operação de módulo. Eu faria assim:

Assim, ele começa com um M de menor valor possível de se construir a tabela (que é o próprio número de elementos N), e, para cada valor de a que altere o resultado final módulo M (para isso, a tem que estar entre 1 e M-1), verifico se M satisfaz número de colisões = 0.