unsigned int DJBHash(char* str, unsigned int len)
{
unsigned int hash = 5381;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = ((hash << 5) + hash) + (*str);
}
return hash;
}
/* End Of DJB Hash Function */
on peut remplacer la constante initiale 5381 par n'importe quelle autre (appelons-là L comme level).
hash = ((hash << 5) + hash) + (*str);
est équivalent à
hash = 33*hash + (*str);
du coup quand on a deux sous-chaines s1 et s2, on a la propriété suivante (si l1 et l2 sont leurs longueurs respectives) :
h(s1s2) = 33^l2*(h(s1) - L) + h(s2)
y'a plus qu'à précalculer l'exponentiation rapide de base 33 et le tour est joué...
fonction (très) rapide, relativement efficace et calculable récursivement à l'aide des valeurs des sous-chaines...
mes 2 cents !
# la fonction de hash de Daniel J. Bernstein...
Posté par aedrin . En réponse au message fonction de hashage de chaine de characteres. Évalué à 2.
unsigned int DJBHash(char* str, unsigned int len) { unsigned int hash = 5381; unsigned int i = 0; for(i = 0; i < len; str++, i++) { hash = ((hash << 5) + hash) + (*str); } return hash; } /* End Of DJB Hash Function */- on peut remplacer la constante initiale 5381 par n'importe quelle autre (appelons-là L comme level).
- est équivalent à
du coup quand on a deux sous-chaines s1 et s2, on a la propriété suivante (si l1 et l2 sont leurs longueurs respectives) : y'a plus qu'à précalculer l'exponentiation rapide de base 33 et le tour est joué... fonction (très) rapide, relativement efficace et calculable récursivement à l'aide des valeurs des sous-chaines... mes 2 cents !