Tables de hachage et dictionnaires

Les tables de hachages sont des tableaux dynamiques permettant de créer une association clé-valeur pour une retrouver rapidement une valeur. Les codes proposés ici pour les tables et fonctions de hachages sont écrits en langage Python. Les dictionnaires Python sont également basés sur le principe des tables de hachage et serviront d’outil de comparaison.

Définitions

• Table de hachage : tableau associatif permettant de créer une association clé-valeur. Chaque couple ou valeur se voit attribuer une position dans la table à l’aide d’un entier, appelé valeur de hachage, renvoyé par une fonction de hachage. Cette position dépend de la taille de la table et non de l’ordre d’arrivée. La recherche ou modification d’une valeur, la suppression ou l’ajout d’un couple s’effectuent à l’aide de la clé, elle apparaît donc de façon unique dans la table.
• Fonction de Hachage : fonction associant une valeur entière de taille prédéfinie à un entier, un flottant ou une chaine de caractères de taille non prédéfinie.

Fonction de Hachage

Première approche des fonctions de hachage

Une fonction de hachage prend en paramètre un élément ‘hachable’, c’est-à-dire un élément immuable, en python ce sont les chaines de caractères, un entier, un flottant ou encore un tuple. Le but est de transformer cet élément en un nombre entier de taille définie pour ensuite qu’il devienne un indice correspondant à une position dans la table de hachage.

Réduire des éléments de taille non définie en entier de taille définie risque de causer des collisions, c’est-à-dire qu’au moins deux éléments obtiennent le même résultat. Or selon le format des tables, ces éléments ne peuvent pas occuper la même position (2.3). Ce problème est inévitable lorsque les ajouts d’éléments ne sont pas prédictibles. Le mieux est donc de limiter le nombre de collisions. Pour cela, il faut bien construire la fonction de hachage.