bonjour a tous,
 
je suis nouveau sur le forum C
je suis aussi novice en matiere de C et g besoin de votre aide
 
voila g un pbm avec le developpement de la table de hashing ouverte
 pr m'aider un copain ma donner ce bout de code mais il a ete incapable de m'expliquer a quoi cela servait !!
 
a l'aide de plusieurs site g pu realiser cela un fichier hash.h fichier include:
 
typedef struct cell
{
 char key[100];
 int data;
 struct cell* next;
}Tcell;
 
typedef struct hash
{
 Tcell* last;
 Tcell* first;
}Thash;
 
typedef struct list
{
 int size;
 Thash* hash;
}Tlist;
 
Tlist* createEmptyTab(int n);
 
int searchCell(Tlist* list, char* str, int* i);
 
int insertCell(Tlist* list, char* str, int i);
 
Tcell* firstCell(Tlist* list);
 
void delTab(Tlist* list);
 
 
et dans un fichier hash.c kelke fonction comme celle ki suivent:
 
/*
* Effacer la liste des cellules
*/
void delCell(Tcell* cellptr)
{
 if(cellptr)
  delCell(cellptr->next);
 free(cellptr);
}
 
/*
* Effacer la table de hashage
*/
void delTab(Tlist* list)
{
 Tcell* cellptr;
 cellptr = firstCell(list);
 delCell(cellptr);
 free(list->hash); /*  free de la table de hashage */
 free(list);  /*  free de la liste */
}
 
 
Je ne vous demande pas de faire ma table bien au contraire. je voudrai juste que vous m'expliquiez a quoi sert cette partie de code que mon pote m'a fournit:
 
/*
* Calcul de la 'hash value'
*/
int calcHash(char* str, int n)
{
 unsigned short i;
 int dhash=0;
 for(i=0; i < strlen(str); i++)
 {
  dhash += (str[i] & 31);
 }
 dhash %= n;
 return dhash;
}
 
 
je m'en remets a vous
Merci pour votre aide
 
a+

Bon alors je vais essayer de t expliquer un peu ca.
 
ta table de hashage est de la forme un tableau de liste chainee, ca ne doit pas etre bien clair alors je t explique.
 
Prenons une chaine de caractere au hasard disons "test", la fonction calchash va calculer une valeur numerique en fonction de ta chaine, cette valeur sera comprise entre 0 et la taille de ton tableau -1, en fait elle permettra de choisir la case du tableau dans laquelle sera stockee ta chaine.
 
 
Ensuite , chaque case contient une liste chaine d element, car en effet au vu de la maniere dont est calculee ton hashage tu auras des problemes de collisions (c est a dire que plusieurs chaines de caractere auront la meme valeur de hashage et donc se retrouveront dans la meme case du tableau), ainsi pour pallier a ce probleme, chaque case du tableau est compose de deux pointeurs, un vers le debut de la liste et un autre vers la fin. Donc le principe est le suivant, a chaque fois qu une chaine de caractere a ajouter a la meme valeur de hashage, on rajoute cette chaine et les donnees correspondante a la suite de la liste chainee contenu dans la case correspondante a la valeur de hashage dans le tableau .
 
 
Pour retrouver un element il sufit de recalculer la valeur de hashage et de reparcourir la liste correspondante dans la tableau.
 
 
Voila pour le principe ... j espere avoir ete assez clair meme si plus ca va et plus j en doute    ... si tu as encore besoin n hesite pas .

 
 
c'est un hash additif, c'est à peu pres ce qu'il y a de plus pourri au niveau collision. Il faut trouver un algo de hashage à la fois suffisament rapide (surtout si tes clé de hash sont longues!) et avec le moins de risques de collisions pour eviter la recherche lineaire (résolition des collisions) et le rehasing (on augmente le nombre de "case" quand il y a trop de collisons)
 
voici par exemple la fonction de hashage utilisée en interne par perl pour ses tables de hash, et que je te conseil d'utiliser:

 
C'est la fameuse fonction de hashage 33. Pour la petite histoire, jusqu'à présent personne n'a réussi à démontrer mathématiquement pourquoi elle donnait une aussi bonne distribution.