Quelques indications pour le hashage

Le type de hashage

Le but du hashage dans notre exemple n'est pas seulement d'implémenter des fonctions d'ensemble, mais aussi et surtout d'associer un unique entier à chaque ligne (et le même pour deux lignes égales). Le problème vient de la gestion des collisions (voir TD 4). On a deux solutions classiques :

Solution par chaînage

L'entier unique peut alors être l'adresse mémoire.

Solution par adressage ouvert

L'entier unique est alors le numéro de la case dans laquelle est rangée la ligne. Il faut alors penser aux améliorations par double hashage ou hashage quadratique.

Problème de taille de la table

On peut penser à trouver le nombre de lignes de chaque fichiers avant d'allouer l'espace mémoire de la table de hashage.

Les fonctions de hashage

Il faut choisir des fonctions de hashage qui produiront le moins de collisions possible. Ces fonctions de hashage ne devront pas pour autant ètre trop coûteuses. On peut utiliser les charactères dans les lignes comme des entiers. On peut les additionner, les décaler (<< ou >>), en prendre le ou exclusif avant ou après décalage (^). À vous de choisir votre heuristique. Essayez tout de même de ne pas vous contenter de la tête de la ligne...