[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

Re: Dúvidas

Giuliano Mega wrote (on Thursday, 21 Jun 2001, at 22:17:22 -0300):
 > [...]
 > > 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:int M, int a;for( M = N; ; M++)   //N é o
 > > número de elementos    for(a = 1; a < M; a++)        //testo as
 > > colisões de todas as chaves 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.
 > 
 > É, pode ser. Também pensei nisso, mas foi ao olhar o texto que
 > verifiquei que o Sedgewick usa a razão áurea como 'a' num exemplo.
 > Professor, o senhor poderia nos dar uma mão com este aqui??

Voce deve de fato encontrar a funcao para cada conjunto de chaves dadas.  O
mais simples é testar todos os valores de a para cada M.  Existem jeitos
melhores, mas eles dependem de teoria.

Estas funcoes de hashing pefeitas sao uteis em situacoes onde o conjunto de
chaves é estatico (ou as atualizacoes são pouco frequentes).

Vejam a documentacao de gperf, o pacote GNU para a geracao de funcoes de
hashing perfeitas.

Yoshi

 > []'s
 > 
 > Giuliano