Présentation :
Une table de hashage est une manière d’organiser les données pour y accéder très rapidement. L’idée est de générer un nombre avec la donnée qui correspondra à son identifiant. Dans la plupart des cas, on a un tableau de taille N : on a donc cet id modulo la taille du tableau. Cela permet d’ajouter une donnée en O(1) et de la lire en O(1).
Une bonne fonction de hashage génère des nombres très aléatoires de façon à ce que ce ne soit jamais deux fois les mêmes comme le md5.
Elle doit remplir ces grands critères :
- rapidité de la fonction hachage
- taille à réserver pour l’espace de hachage
- réduction du risque des collisions
Dans mon programme, on a un tableau de taille N (choisis dans le main)
On génère un identifiant avec notre fonction de hashage qui est :
caractère[i] * 128 puissance i + caractère[i +1] * 128 puissance i +1 +…… + caractère[i+n] * 128 puissance + i+ n
Ou n est la nombre de caractère de la chaîne.
Résolution des collisions :
Pour gérer les collisions dans mon programme, j’ai utilisé des listes chaînées donc quand une collision survient. Le mot est placé à la fin de la liste chaînée. Ainsi, aucune donnée n’est perdue et l’on ne dépend plus de la taille du tableau. Par contre dans le pire cas, tableau de taille 1 : les temps d’accès sont les mêmes que la liste chaînée.
Source : table-hachage