Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
847 connectés 

  FORUM HardWare.fr
  Programmation
  C

  pbm partie de code table hashing

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

pbm partie de code table hashing

n°734701
tibobao
Posté le 22-05-2004 à 14:36:01  profilanswer
 

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+

mood
Publicité
Posté le 22-05-2004 à 14:36:01  profilanswer
 

n°734711
fabs0028
Posté le 22-05-2004 à 14:59:16  profilanswer
 

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  :whistle:  ... si tu as encore besoin n hesite pas .

n°735101
pospos
Posté le 23-05-2004 à 12:30:34  profilanswer
 

Code :
  1. int calcHash(char* str, int n)
  2. {
  3. unsigned short i;
  4. int dhash=0;
  5. for(i=0; i < strlen(str); i++)
  6. {
  7.   dhash += (str[i] & 31);
  8. }
  9. dhash %= n;
  10. return dhash;
  11. }


 
 
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:

Code :
  1. hash = 0;
  2.     while (klen--)
  3.         hash = (hash * 33) + *key++;
  4.     hash = hash + (hash >> 5);

n°736508
docmaboul
Posté le 24-05-2004 à 17:23:43  profilanswer
 

pospos a écrit :

Code :
  1. 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:
  2. [cpp]
  3.     hash = 0;
  4.     while (klen--)
  5.         hash = (hash * 33) + *key++;
  6.     hash = hash + (hash >> 5);




 
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.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  pbm partie de code table hashing

 

Sujets relatifs
Un code de recherche erronéinsertion d'un blob dans une table d'oracle
Swing, afficher une image en fond de jpanel (code inside)[Oracle] Problème d'insertion dans une table
Modifier le commentaire d'une table MySQL[php] arrive pas a afficher le contenu d'une table SQL [nb inside]
[c++/pascal] code de grey???Inserer un code ASCII dans une chaîne de caractère
Cherche code source pour bench compilationLe code D ?
Plus de sujets relatifs à : pbm partie de code table hashing


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR