Hashage
Hashage de base
Et voici le grand moment que nous attendions tous : la structure de donnée la plus géniale, selon le grand principe de l'informatique : « c'est con, mais fallait y penser ».
J'ai abordé brièvement les index comme introduction aux arbres, en expliquant que si on faisait une liste d'objets par première lettre de la clé (c'est à dire une liste pour les clés commençant par 'a', une pour 'b', etc...), on divisait le nombre de tests à effectuer pour trouver une définition par 26.
On peut faire mieux : il suffit de faire 26*26 listes, une liste par paire de lettres commençant chaque clé. Croyez-vous que l'on puisse diviser les tests à nouveau par 26, pour faire un facteur de gain de 676 ? On peut en doute : certaines listes seront bien plus remplies que d'autres, et certaines seront carrément vides : il y a fort peu de mots qui commencent par 'mz' et autres 'tp'. Par contre, la liste des 'ma' ou 'le' risque d'être assez longue. Mais on peut peut-être encore gagner de la vitesse par rapport à une lettre unique. Par contre, passer à trois lettres n'offrira pas de gros gains, ou alors à un prix trop élevé pour que ça reste intéressant : un nombre très important de listes sera totalement vide...
Analysons le problème sous un autre angle : après tout, prendre la première lettre de chaque clé pour savoir dans quelle liste elle se trouve se rapporte à associer une nombre entre 0 et 25 à chaque clé. De même, si on décide de prendre les deux premières lettres, c'est un nombre entre 0 et 675 qu'on assigne. Le problème rencontré provient du fait que tous ces nombres ne « sortent » pas avec la même probabilité : certains nombres seront beaucoup plus fréquents que d'autres.
Mais qu'importe, continuons à formaliser notre première méthode : on peut donc dire qu'il existe une sorte de fonction, qui prend un string et qui retourne un entier qui y correspond. A la rigueur, ce qu'on aimerait bien, c'est d'avoir des fonctions qui retournent des entiers entre 0 et un nombre bien précis (autre que 25 ou 675), et si possible avec la même probabilité d'apparition. Cette fonction est appelée la « fonction de hashage ». Elle retourne le « code de hashage » de l'objet passé en paramètre. Par exemple, si on prend comme fonction de hashage celle qui retourne une valeur entre 0 et 25 en fonction de la première lettre d'un string, « Dupont » aura le code de hashage 3.
Il existe des fonctions de hashage qui peuvent effectivement garantir une bonne uniformité des codes de hashage qu'elles donnent, et qui peuvent vous sortir des codes compris entre 0 et N-1, pour un N fixé. J'insiste sur le fait que ce n'est jamais que la généralisation de la méthode initiale.
Et que fait-on avec ce code de hashage ? C'est simple : si les codes sont retournés entre 0 et N-1, créons N listes, exactement comme quand N valait 26, il y avait 26 listes, une pour chaque lettre. Chaque liste contient les éléments dont les clés ont un code de hashage qui correspond au numéro de la liste.
Cette méthode se généralise pour des clés autres que des string : il suffit d'être capable de programmer une fonction de hashage pour l'objet particulier dont on veut se servir comme clé. L'important, c'est de toujours se débrouiller pour que les codes de hashage soient uniformément répartis : c'est à dire qu'il n'y a pas 90% des clé qui ont le même code, sinon ça ne sert à rien.
A présent, si on a fixé N égal à 4000 ou quelque chose du genre, et que la fonction de hashage est bonne, on peut effectivement garantir qu'en moyenne il ne faudra plus que NombreElements/4000 tests pour trouver l'objet qui correspond à une clé donnée. C'est un bon résultat, surtout si NombreElements est de l'ordre de quelques dizaine de mille.
Evidemment, si il y a trois millions d'éléments, ou bien seulement 47, N valant 4000 est soit trop petit, soit trop grand. Trop petit, on est plus assez efficace, trop grand, on gaspille de la mémoire. Il faut donc avoir une bonne idée de l'utilisation que l'on veut faire de la table avant de fixer N.
Il ne sera pas dit que je ferai tout un chapitre sans faire au moins un petit dessin, alors voila ce que peut donner en substance une table de hashage :
J'ai tout de même simplifié mes notations, car je suppose que vous commencez à être assez habitué à la notion de pointeurs et de listes chaînées. Sinon, ben relisez les premiers chapitres :)
Rehash dynamique
L'idée est à présent de ne pas fixer N à priori, mais bien d'adapter N en fonction du nombre d'éléments dans le dictionnaire. Par exemple, si le nombre d'élément dépasse 5*N, on peut décider de multiplier N par 10, et de réorganiser toute la table. Cette réorganisation est quelque chose d'assez lent et coûteux, mais ça arrive relativement rarement. Avec cette méthode, on peut toujours garantir que, en moyenne, il ne faudra pas plus de 5 tests pour trouver un élément dont on connaît la clé, même si il y a quelques millions d'objets dans le dictionnaire !
Les tables de hashage à rehash dynamique sont LA solution aux dictionnaires. Le problème est donc aujourd'hui considéré comme un problème résolu.