Discussion :

[SweetLeaf]

Bonjour tout le monde !!

J'ai un projet a faire dans le cadre de mes études et pour que ce dernier soit performant j'ai besoin d'une table de hachage.
Je doit créer un Scrabble en C, avec recherche de mots, suivant les 7 lettres en main et les lettres déjà placées sur la grille.

J'ai déjà regarder un peu partout sur le net dans tous les forums (ou presque) pour me renseigner sur cette structure de données.

Le problème est le suivant, je n'ai toujours pas réussi à trouver une doc qui m'explique comment ca fonctionne !
Je n'ai envie que l'on me donne une table de hachage ca ne me serai pas bénéfique, mais si quelqu'un connait une bonne documentation avec laquelle je pourrai créer et implémenter une table de hachage ça me serai d'une grande utilité !

Merci d'avance et bonne journée à tous !

[Médinoc]

Un truc à ne pas oublier, c'est qu'une table de hachage fait une recherche "tout-ou-rien". C'est donc bien pour tester si un mot est dans un dictionnaire, mais pas pour en chercher plusieurs à la fois ou rechercher le plus long possible (pour ce dernier cas, un arbre serait mieux).

La table de hachage, en fait, tu peux la voir comme un truc qui sépare une collection en sous-collections de taille supposée minimale. Le cas habituel introduit dans les écoles suppose que ces sous-collections sont des listes chaînées; la table de hachage est donc, en fait, un tableau de listes chaînées.

L'autre partie importante, c'est la fonction de hachage. C'est elle qui va convertir la clé (par exemple, une chaîne de caractères) en un index dans la table. Si la fonction de hachage retourne la même valeur pour deux clés différentes, on appelle ça une collision. Les collisions sont inévitables s'il existe plus de clés différentes que de valeur de hachage (principe des tiroirs: Si tu as plus de chaussettes que de tiroirs, au moins un tiroir contiendra au moins deux chaussettes).

Il faudra écrire la fonction de hachage de manière à ne pas avoir plus de collisions que nécessaires. Typiquement pour du texte, on a tendance pour chaque caractère à faire un décalage binaire de 5 ou 6 bits et ajouter le caractère.
S'il y a zéro collision dans une table, chaque liste contient au plus un élément.

Ensuite, le fonctionnement est assez simple:

• En recherche:
  
  1. Hacher la clé de ce qu'on veut ajouter
  2. Choisir la liste correspondante dans la table de hachage
  3. Parcourir la liste en comparant à chaque fois la clé jusqu'à égalité ou fin de liste.
• En ajout:
  
  • Faire une recherche de la clé.
  • Ajouter en fin de liste chaînée si on n'a pas trouvé.

Ensuite, on peut faire des trucs plus techniques, comme utiliser des arbres binaires de recherche (ou des tables de hachage sur une clé différente) à la place des listes chaînées. Ça dépend de l'usage, en fait. Vu qu'un dictionnaire est immuable en mémoire, on pourrait probablement utiliser des tableaux triés...

[Thierry Chappuis]

Voici deux discussion qui traitent de différentes fonctions de hachage:
http://www.cse.yorku.ca/~oz/hash.html
http://burtleburtle.net/bob/hash/doobs.html
http://www.concentric.net/~Ttwang/tech/inthash.htm

Dans un premier temps, la fonction djb2 donnée dans le premier de ces trois liens est sans doute un bon point de départ.

Sinon, si ton projet t'autorise l'utilisation de bibliothèques externes, tu peux toujours considérer les structures de données que GLib a à t'offrir, ou t'inspirer de leur implantation.

Thierry