Chapitre 20. Tables de hachage

Définition 20.1. Une table de hachage est un objet qui émule un ensemble ou un dictionnaire en appliquant la technique du hachage-adressage.
Les trois méthodes de base d’une table de hachage x sont :contains : pour savoir si un élément appartient à x ;add : pour ajouter un élément à x ;remove : pour supprimer un élément de x.
En fait, si x émule un dictionnaire, x.contains(k) retourne vrai si x possède un item (k,*), c’est-à-dire si k est une clé de x ; add sert à ajouter un item (k,v) à x (on dit alors que k est une clé et v la valeur associée) ; x. remove(k) sert à effacer l’item (k,v). Les tables de hachage émulant des dictionnaires possèdent également une méthode valeur . Concrètement, si (k,v) est un item de x alors x.valeur(k) retourne v (c’est l’intérêt des dictionnaires !)Note. Par extension, si x émule un ensemble, il est courant de dire « k est une clé de x » lorsque k est un item de x.
L’intérêt du hachage-adressage réside dans la vitesse d’exécution.
Les tables de hachage de type interne sont les objets de type set, dict et frozenset (ce dernier est un cas un peu particulier puisqu’il ne possède pas les méthodes add et remove).Note. Chez les objets de type dict, ce sont les méthodes spéciales setitem, delitem et getitem qui remplissent le rôle de add, remove et valeur .
Avant de montrer le mécanisme du hachage-adressage, commençons par montrer la manière la plus simple et naturelle d’implémenter des ensembles et des dictionnaires. Ceci permettra de voir les problèmes de lenteur qui se posent quand on travaille avec de telles structures…