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]

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

[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