A voir également:
- Table de hachage
- Table ascii - Guide
- Table des matières word - Guide
- No bootable partition in table ✓ - Forum Windows
- Table des annexes word ✓ - Forum Word
- Table des matières et table des annexes - Forum Word
8 réponses
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:11
15 juin 2008 à 21:11
Salut,
Pour faire une table de hachage chaînée tu dois tous d'abord d'écrire une fonction de hash.
Ensuite tu dois créer un tableau de pointeur de type d'élément de ta liste
Quand tu va passer le terme à insérer à la fonction de hash l'entier retourner sera l'index de tableau de pointeur où ton élément sera inséré
En bref chaque élément de ton tableau de pointeur sera la tête d'une liste chaînée.
// le nombre de conteneurs doit être choisi en général comme un nombre premier assez eloigné d'une puissance de deux
Il ne faut pas non plus oublié le facteur de charge d'une table de hash
F = éléments / conteneurs
si tu as 10000 éléments et le nombre de conteneurs sera par exemple 997 le facteur de charge
F = 10000 / 997 = 10
ce qui veut dire que un conteneur peut s'attendra à contenir au maximum 10 éléments.
En réalité on n'obtiendra pas une table de hash uniforme, mais on arrive plus au moins à la valeur de facteur de charge.
Pour faire une table de hachage chaînée tu dois tous d'abord d'écrire une fonction de hash.
Ensuite tu dois créer un tableau de pointeur de type d'élément de ta liste
Quand tu va passer le terme à insérer à la fonction de hash l'entier retourner sera l'index de tableau de pointeur où ton élément sera inséré
En bref chaque élément de ton tableau de pointeur sera la tête d'une liste chaînée.
typedef struct L {
char donnee[100];
struct *suivant;
}Liste;
Liste **TdH;
TdH = (Liste **) malloc (conteneurs * sizeof(Liste *);
// le nombre de conteneurs doit être choisi en général comme un nombre premier assez eloigné d'une puissance de deux
Il ne faut pas non plus oublié le facteur de charge d'une table de hash
F = éléments / conteneurs
si tu as 10000 éléments et le nombre de conteneurs sera par exemple 997 le facteur de charge
F = 10000 / 997 = 10
ce qui veut dire que un conteneur peut s'attendra à contenir au maximum 10 éléments.
En réalité on n'obtiendra pas une table de hash uniforme, mais on arrive plus au moins à la valeur de facteur de charge.
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:17
15 juin 2008 à 21:17
Par exemple une insertion donnera quelque chose comme ça
cle = hash(donnee); InsertionEnTete(TdH[cle],donnee);
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:21
15 juin 2008 à 21:21
Si tu diras d'où collecte tu les données et comment tu veux les insérer dans la table de hash, ça sera plus facile de comprendre. ;-)
ok; merci, c'est gentil de ta part.
jai fait la 1ere partie du programme, ne fait je possede maintenant un liste des mots , leurs positions dans la phrase et leurs num de ligne, donc maintenant il me reste de placer ces mots dans une table de hachage avec leurs informations(leurs positions dans la phrase et leurs num de ligne)
voila , c tout, ce travail est pour demain ;)
merci
jai fait la 1ere partie du programme, ne fait je possede maintenant un liste des mots , leurs positions dans la phrase et leurs num de ligne, donc maintenant il me reste de placer ces mots dans une table de hachage avec leurs informations(leurs positions dans la phrase et leurs num de ligne)
voila , c tout, ce travail est pour demain ;)
merci
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:26
15 juin 2008 à 21:26
As-tu écrit ta fonction de hash?
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Bon pas encore, mais lami je trouve un souci c'est que je pense que le mot lui meme devient la clé de hachage, non?
té d'accords?
té d'accords?
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:29
15 juin 2008 à 21:29
Exactement. C'est comme ça que tu trouves l'index du tableau où tu dois insérer le mot
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:34
15 juin 2008 à 21:34
Voici un exemple avec une fonction simple
Donc tu remarque bien que pour chaque terme j'ai obtenu un indice de tableau où le mot sera insérer
lami20j@debian:~/trash$ gcc -o hash_cle hash_chaine.c lami20j@debian:~/trash$ ./hash_cle Entrez une clé : azerty Cle = azerty; Valhash : 96 lami20j@debian:~/trash$ ./hash_cle Entrez une clé : lami20j Cle = lami20j; Valhash : 8 lami20j@debian:~/trash$ ./hash_cle Entrez une clé : hashage Cle = hashage; Valhash : 15 lami20j@debian:~/trash$ ./hash_cle Entrez une clé : stroumpf Cle = stroumpf; Valhash : 60 lami20j@debian:~/trash$
Donc tu remarque bien que pour chaque terme j'ai obtenu un indice de tableau où le mot sera insérer
voila ce que j'ai trouvé comme exemple:
int func_h(ELEMENT c,struct table_hachage *h,int a)
{
double res=0;
int i;
ELEMENT p=c;/*copie de c pour ne pas le modifier lors du calcul*/
for(i=0;*p!='\0';p++,i++)
{
res+= pow(a,i)*(*p);/*calcul de la somme de proche en proche*/
}
i=abs((int)res%(h->N));/*res peu etre negatif d'où l'utilisation de abs(),on convertit le resultat en entier*/
return i;/* on retourne un entier en non un entier double precision*/
}
mais je comprends pas son fonctionnement
merci
int func_h(ELEMENT c,struct table_hachage *h,int a)
{
double res=0;
int i;
ELEMENT p=c;/*copie de c pour ne pas le modifier lors du calcul*/
for(i=0;*p!='\0';p++,i++)
{
res+= pow(a,i)*(*p);/*calcul de la somme de proche en proche*/
}
i=abs((int)res%(h->N));/*res peu etre negatif d'où l'utilisation de abs(),on convertit le resultat en entier*/
return i;/* on retourne un entier en non un entier double precision*/
}
mais je comprends pas son fonctionnement
merci
lami20j
Messages postés
21331
Date d'inscription
jeudi 4 novembre 2004
Statut
Modérateur, Contributeur sécurité
Dernière intervention
30 octobre 2019
3 569
15 juin 2008 à 21:42
15 juin 2008 à 21:42
Voici un exemple
#include<stdio.h>
#include<stdlib.h>
#define TAILLE 997
unsigned hash_cle(char *chaine);
int main()
{
char *chaine;
unsigned int val;
if((chaine = (char *) malloc (50 * sizeof(char)))
== NULL)
return -1;
printf("Entrez une clé : ");
scanf("%s",chaine);
val = hash_cle(chaine);
printf("Cle = %s; ValeurHash : %u\n",chaine,val);
return -1;
}
unsigned hash_cle(char *chaine){
unsigned i;
for(i=0;*chaine != '\0';++chaine)
i = *chaine + 31 * i;
return i%TAILLE;
}
Bonsoir Lami,
jai essayé mais ca na pas marché :(
il maffiche rien en faite, ni la valeur de la clé, ni rien.
merci
int fonctHachage(liste_mot* s)
{ int val;
liste_mot* m=s;
char *mot;
mot=m->mot;
while(m!=NULL)
{
val = hash_cle(mot);
}
printf("%d", val);
printf("gggggggggggggggggggggggggg");
return(val);
}
unsigned hash_cle(char *chaine){
unsigned i;
for(i=0;*chaine != '\0';++chaine)
i = *chaine + 31 * i;
return i%TAILLEMAX;
}
int main(int argc, char *argv[])
{ char c;
int A;
int val;
liste_mot* s =NULL;
Trouver_mots (&s,"C:\\Documents\\text.txt" );
Affiche_mots(s);
printf("\n\n la liste filtree \n\n");
frequent( &s , 1);
Affiche_mots(s);
//calcul_nbre_mot(s);
// printf("%d",A);
val=fonctHachage(s);
scanf("%c",c);
return 0;
}
La fonction ne marche pas, il naccede pas a la fonction
je c pas pk?
jai essayé mais ca na pas marché :(
il maffiche rien en faite, ni la valeur de la clé, ni rien.
merci
int fonctHachage(liste_mot* s)
{ int val;
liste_mot* m=s;
char *mot;
mot=m->mot;
while(m!=NULL)
{
val = hash_cle(mot);
}
printf("%d", val);
printf("gggggggggggggggggggggggggg");
return(val);
}
unsigned hash_cle(char *chaine){
unsigned i;
for(i=0;*chaine != '\0';++chaine)
i = *chaine + 31 * i;
return i%TAILLEMAX;
}
int main(int argc, char *argv[])
{ char c;
int A;
int val;
liste_mot* s =NULL;
Trouver_mots (&s,"C:\\Documents\\text.txt" );
Affiche_mots(s);
printf("\n\n la liste filtree \n\n");
frequent( &s , 1);
Affiche_mots(s);
//calcul_nbre_mot(s);
// printf("%d",A);
val=fonctHachage(s);
scanf("%c",c);
return 0;
}
La fonction ne marche pas, il naccede pas a la fonction
je c pas pk?
15 juin 2008 à 21:17
mais je compte faire une Table de hachage dynamique; c'a dire je veux pas fixé un nobre d'element, car jai du texte qui contient des mots à inserer et las c un gros corpus, donc je c pas d'avancv le nombre d'elemnt
merci
15 juin 2008 à 21:19
Donc seulement la mémoire te pourra limiter.
En revanche le nombre de conteneur tu dois l'établir.
Bref, tu auras un tableau de liste chainées.
15 juin 2008 à 21:21
je v essayer et je v te montrer mon essai.
merci