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.