8Fermer10
GodzilLe 27/01/2011 à 22:17
Zerosquare: Oui, d'ailleurs, mais je n'ai pas le bouquin, mais j'ai un algo de hash adapté aux chaines, faut que je le retrouve.

Pour les tables de hashage, la collision est plutot géré au niveau de l'insertion, recherche dans le tableau que dans l'algo de hash

edit: Retrouvé ^^
/**************************************************************** * * * Fonction de hashage adapté de "Compilers : Principles, * * Techniques, and Tools, de Alfred V. AHO, Ravi SETHI, * * et Jeffrey D. ULLMAN, qui l'attribuent à P. J. WEINBERGER * * * ****************************************************************/ /**************************************************************** * * * --------------------------- hashpjw.c --------------------- * * * ****************************************************************/ #include "hashpjw.h" /**************************************************************** * * * ------------------------- hashpjw ------------------------- * * * ****************************************************************/ int hashpjw(const void *cle) { const char *ptr; int val; /************************************************************** * * * Hache la clé à l'aide d'opérations bit à bit. * * * *************************************************************/ val = 0; ptr = cle; while (*ptr != '\0') { int tmp; val = (val << 4) + (*ptr); if (tmp = (val & 0xf0000000)) { val = val ^ (tmp >> 24); val = val ^ tmp; } ptr++; } /************************************************************** * * * En pratique, on remplace PRIME_TBLSIZ * * par la taille réelle de la table. * * * *************************************************************/ /* Petit ajout (02/05/2002) on empeche le retour de toute valeur négative */ if ((val % PRIME_TBLSIZ) < 0) { return 0-(val % PRIME_TBLSIZ); } else { return val % PRIME_TBLSIZ; } }