Discussion :

[User]

Bonjour à tous,

Je suis heureux de vous présenter un nouvel article consacré aux tables de hachage et au fonctionnement des dictionnaires Python :

Comprendre les tables de hachage grâce aux dictionnaires Python



Au fil de l'article, nous verrons comment fonctionne le hachage, ce que sont les collisions, comment elles sont gérées et ce qu'est un objet hashable, le tout illustré par des exemples en Python.

L'objectif est d'expliquer ces concepts de manière progressive et accessible, sans supposer de connaissances préalables sur les structures de données.

J'espère que cette lecture vous sera utile.

Bonne lecture !

[laurent_ott]

Bonjour,
J’ai bien aimé cette documentation, c’est pourquoi j’ai voulu aller plus loin en m’amusant à programmer un dictionnaire s’appuyant sur les notions présentées. En me contentant de ne gérer que des entrées au format alphabétiques (non vides, et en faisant l’impasse sur les objets complexes, tables de structures et autres).
J’ai vite été confronté à deux problèmes :
- Comment « hacher » rapidement la clé pour obtenir un entier (compris entre 1 et N) qui donne la position où l’enregistrer dans le dictionnaire.
- Comment gérer les collisions lorsque plusieurs clés donnent la même position.

Pour le hachage, j’ai utilisé dans un premier temps l’algorithme MD5. Mais sa lenteur d’exécution m’a poussé à chercher une autre piste, et j’ai trouvé l’algorithme de hachage XxHash : « C'est un algorithme de hachage non cryptographique extrêmement populaire, célèbre pour sa vitesse d'exécution exceptionnelle, jusqu’à 20 fois plus rapide que MD5 ». l’IA m’a bien aidé à le convertir en une version 32 bits optimisée et compatible avec le VBA.

Pour la gestion des collisions, j’ai pensé à une mémoire annexe « Mx », qui contient dans une liste chaînée les clés qui ont la même valeur de hachage. L’indexation permet de passer en revue les données sans avoir à lire la liste en intégralité, d’où un gain de temps. Arbitrairement cette liste annexe est 50% de la taille du dictionnaire. Quand la liste est pleine on double la taille du dictionnaire, et donc de l’annexe, et l’on reconstruit le dictionnaire avec les données existantes, avant d’accueillir les nouvelles.

La mémoire « M » du dictionnaire a trois attributs :
- Clé : la chaine alphabétique qui représente la clé du dictionnaire (par exemple un mot).
- Valeur : la valeur du dictionnaire (par exemple sa définition).
- Index : l’indexation dans la mémoire annexe, soit 0 s’il n’y a pas d’autre clé identique dans la mémoire annexe, soit « j » qui représente l’entrée dans la mémoire annexe.

En résumé :
Chaque clé est hachée. On obtient un entier « i ».
Si M(i).Clé est vide, c’est que la position est libre : on enregistre dans M(i).Clé la clé, dans M(i).Valeur la valeur, et M(i).Index = 0.
Sinon, on va alimenter la mémoire annexe (« Mx » a les mêmes attributs que « M »). C’est le principe d’une liste chainée, je ne vais pas m’y étendre, mais en gros :
M(i).Index = j (à savoir que « j » est incrémenté de 1 à chaque fois), et Mx(j).Clé = la clé, Mx(j).Valeur = la valeur, Mx(j).Index = 0.
Sauf que, si M(i).Index est différent de 0, c’est que l’annexe est déjà occupée, on parcours donc les clés dans Mx() en commençant par j = M(i).Index. Chaque fois Mx(j).Index donne la position suivante dans la liste chainées. Quand Mx(j).Index = 0 alors il n’y a plus de suite. On enregistre dans Mx(j).Index = k+1, ou k est la dernière position de l’annexe. Et dans Mx(k+1) les données.

Je ne vais pas vous embêter avec le code source en VBA, mais je le tiens à votre disposition si cela vous intéresse.
J’ai remarqué que mon dictionnaire est bien plus rapide que la fonction native du VBA qui appelle un objet COM (ActiveX). Explication : « En VBA, chaque appel à ses méthodes (.Add, .Exists) subit une surcharge liée à l'interface COM (COM overhead), ce qui ralentit considérablement les boucles massives. »
Je ne sais pas si c’est le cas avec Python ou dans vos langages de programmation.
En tout cas, je remercie Denis Hulo pour cette excellente documentation qui m’a permis de découvrir un domaine que j’ignorais.
Bonne programmation à vous.

[Invité]

Bonjour,
Je pense que l'algo du hashage est important mais pas décisif car mème si il donne des hashs uniques au final c'est la longueur du tableau qui va créer les collisions on doit choisir une position en tre 1 et N un rang très réduit par rapport la taille du hash, un compromis c'est d'utiliser un algo simple mais rapide et faire plus de comparions