Discussion :

[étoile de mer]

Bonsoir à tous les developpeurs ici présentsi,
SVp, est ce quil ya quelqun qui peut m'aider a developper une fonction qui permet de parcourir les liste chainées de chaque element de la table de hachage.*
merci

[Climoo]

Une fois que tu as trouvé la bonne entrée dans ta table de hachage, tu as donc un pointeur sur une liste chainée. Tu la parcours jusqu'à trouver l'elément, comme tu parcourerais n'importe qu'elle autre liste chainée.

[nicodn02]

Une table de hashage fonctionne avec une fonction de hashage
table de hashage : tableau de listes chainées
fonction de hashage : permet de choisir dans quelle liste on sotck la donnée ou que établie la recherche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
struct table{
		unsigned int taille; 
		Liste* table;
	};
 
typedef struct table *TableH;

[Médinoc]

Plutôt que "tableau de listes chaînées", je préfère dire "tableau de conteneurs associatifs", car on peut y mettre autre chose que des listes chaînées.
Y compris des arbres binaires de recherche, ou même d'autres tables de hachage avec une fonction de hachage différente, et qui contiendraient elles-mêmes des tableaux de listes chaînées.

[nicodn02]

En effet, mais ceci n'était qu'un exemple.

[Vincent Rogier]

Juste une remarque, on dit en anglais "hash table", en français "table de hachage", mais ..... pas "table de hashage" !

La remarque de Médinoc est fort judicieuse car il existe plein d'implémentations (dont certaines sont réellement très complexe) et la résolution des collisions peut prendre différentes formes.

[étoile de mer]

à tous les developpeurs,
Comme débutant , jai fait un bon pas dans ce projet, mais la je suis tt à fait bloqué. et j'ai besoin de votre aide.
Là je possede une table de hachage qui contient des element.
chaque element est lié à une liste chainée.
le probleme là c'esi je que j'aime parcourir cette table elemnt par elemnt(2 compteurs) pour faire une jointure de chaque elment de la table.pour stocker l'elemnt joint il faut calculer sa clé de hacha_fonction deja developpé) afin de la stocker dans la table.
merci
jattends vos reponses

[nicodn02]

et en français ça donne quoi?

[étoile de mer]

Plutôt que "tableau de listes chaînées", je préfère dire "tableau de conteneurs associatifs", car on peut y mettre autre chose que des listes chaînées.
Y compris des arbres binaires de recherche, ou même d'autres tables de hachage avec une fonction de hachage différente, et qui contiendraient elles-mêmes des tableaux de listes chaînées.

Oué c ca en fait, mais le probleme c'est que je suis dans un cas ou j'ai des mots à stocker dans la table de hachage.
je voudrais savoir une fanction de hachage qui peut assuer l'absence des collisions.
merci

[nicodn02]

en recherchant sur internet tu aurais surement trouvé

Moi, lors d'un projet, sur une table de hashage avec liste simplement chaîné :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
unsigned int hachageString(char *chaine,int max){
	unsigned int hash = 0, i = 0;
	while( i < strlen(chaine) ){
		hash = ((hash *26) + chaine[i])% max;
		++i;
	}
	return hash;
}

retourne dans quelle case du tableau effectuer la rechercher

[Vincent Rogier]

en recherchant sur internet tu aurais surement trouvé

Moi, lors d'un projet, sur une table de hashage avec liste simplement chaîné :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
unsigned int hachageString(char *chaine,int max){
    unsigned int hash = 0, i = 0;
    while( i < strlen(chaine) ){
        hash = ((hash *26) + chaine[i])% max;
        ++i;
    }
    return hash;
}

retourne dans quelle case du tableau effectuer la rechercher

A choisir un code, surtout pas celui la : appel à strlen() à chaque tour de boucle. Le meilleur moyen de tuer les perfs.

De plus , on ne prends pas une fonction de hachage au hasard, mais la plus adaptée à son utilisation.

Enfin le modulo peut être calculé une seule fois à la fin...

[Vincent Rogier]

Si tu veux une fonction de hachage générique pour les chaines de caractères, tu peux utiliser celle que Kernighan montre dans son bouquin "The practice of programming" (que je te conseilles) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enum { MULTIPLIER = 31 };
 
unsigned int hash(char *str)
{
    unsigned int h;
    unsigned char *p;
 
    h = 0;
 
    for (p = (unsigned char *) str; *p != '\0' ; p++)
        h = MULTIPLIER * h + *p;        
 
    return h % NHASH;
}

NHASH étant la taille de la table..

Toujours selon Kernighan, le choix de 31 et 37 pour le multiplicateur sont empiriquement les meilleurs choix...

[wiztricks]

Oué c ca en fait, mais le probleme c'est que je suis dans un cas ou j'ai des mots à stocker dans la table de hachage.
je voudrais savoir une fanction de hachage qui peut assurer l'absence des collisions.
merci

Ouh là...
Par construction, une table de hash à N entrées et la fonction de hash va retourner un nombre entre 0 et N-1...

C'est une surjection et impossible d'empêcher les collisions. Dans ce cas, il y aura plusieurs éléments "associés" à l'entrée correspondante qu'on met en général dans une liste simple ou doublement chainée (si on veut les placer dans "l'ordre" de la clé).

Si on ne peut pas empêcher les collisions, on peut essayer de trouver une fonction de hash qui répartissent de façon plus uniforme les éléments.

Ex: Si la clé est toujours une chaine de 10 caractères, utiliser la longueur de la chaine comme fonction de hash 'fonctionne' mais toutes les éléments seront associés à la meme entrée.
- W

[wiztricks]

en recherchant sur internet tu aurais surement trouvé

Moi, lors d'un projet, sur une table de hashage avec liste simplement chaîné :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
unsigned int hachageString(char *chaine,int max){
	unsigned int hash = 0, i = 0;
	while( i < strlen(chaine) ){
		hash = ((hash *26) + chaine[i])% max;
		++i;
	}
	return hash;
}

Heu... pourquoi supposer que le compilateur va faire le boulot pour toi?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
unsigned int hachageString(char *chaine,int max){
	unsigned int hash = 0;
        while (*chaine != 0)   // strlen va chercher le 0 qui termine la chaine
                hash = (hash * 26) + *chaine++; 
	return hash % max;
}
// le nombre magique 26 mériterait un #define d'une 
// constante clarifiant son choix.

- W




retourne dans quelle case du tableau effectuer la rechercher

[Médinoc]

Il n'est possible de garantir l'absence de collisions que dans le cs où l'ensemble des clés possibles est:

1. fini
2. connu à l'avance

Pour des cas comme ceux-là, il existe des utilitaires qui génèrent un hash parfait.

Dans tous les autres cas, c'est impossible.

[étoile de mer]

Si tu veux une fonction de hachage générique pour les chaines de caractères, tu peux utiliser celle que Kernighan montre dans son bouquin "The practice of programming" (que je te conseilles) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enum { MULTIPLIER = 31 };
 
unsigned int hash(char *str)
{
    unsigned int h;
    unsigned char *p;
 
    h = 0;
 
    for (p = (unsigned char *) str; *p != '\0' ; p++)
        h = MULTIPLIER * h + *p;        
 
    return h % NHASH;
}

NHASH étant la taille de la table..

Toujours selon Kernighan, le choix de 31 et 37 pour le multiplicateur sont empiriquement les meilleurs choix...

merci

[Médinoc]

Ça manque de const, ce code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enum { MULTIPLIER = 31 };
 
unsigned int hash(char const *str)
{
    unsigned int h;
    unsigned char const *p;
 
    h = 0;
 
    for (p = (unsigned char const *) str; *p != '\0' ; p++)
        h = MULTIPLIER * h + *p;        
 
    return h % NHASH;
}

[nicodn02]

quel est l'avantage de mettre les const ?

[Médinoc]

Déjà, c'est plus clair que la fonction ne modifie pas la chaîne.
Et puis, il y a moins de risque qu'elle le fasse quand même à cause d'une erreur de programmation (encore qu'avec les casts C-Style, c'est assez fragile. C'est une des raisons qui me font préférer le C++...)

[nicodn02]

hum d'accord, donc en faite, si on voit que la chaine ne va pas etre modifié, alors tant qu'à faire la mettre en const