Next: Blocs et Contextes Up: Tableaux et structures Previous: Structures
Une table de hachage est un tableau dans lequel on accède à un élément à l'aide d'une clé. Chaque clé correspond à un seul élément. Une tentative d'insérer un deuxième élément ayant une clé identique à celle d'un élément existant provoque le remplacement de l'élément existant.
Common Lisp ne permet pas au programmeur de définir sa propre fonction de comparaison de clés. Cette fonction doit être l'une des quatre fonctions de test d'égalité : eq, eql, equal ou equalp. Cette restriction vient du fait que Common Lisp doit connaître cette fonction afin d'en déduire une fonction de hachage. La fonction de test obtenue par défaut est eql qui s'applique à des objets simples comme les nombres, les symboles, etc.
L'utilisation de tables de hachage avec les fonctions equal et equalp est relativement délicate, car les clés comparées avec ces deux fonctions peuvent être modifiées de manière destructive. Une telle modification peut avoir des conséquences dramatiques sur le comportement de la table de hachage. Les deux fonctions eq et eql ne comparent que des objets immuables.
La création d'une table de hachage se fait à l'aide de la fonction make-hash-table. La fonction gethash est utilisée à la fois pour accéder à un élément et (avec setf) pour insérer ou remplacer un élément. Pour supprimer un élément sans le remplacer, utiliser remhash.
La fonction gethash renvoie deux valeurs. La première est l'élément trouvé avec la clé donnée en argument, ou nil si aucun élément n'existe avec la clé donnée - il est donc impossible de distinguer la situation où aucun élément n'existe et la situation où un élément existe et cet élément est nil - la deuxième valeur est nil si et seulement si aucun élément n'existe. Un programme qui ne stocke jamais l'objet nil dans une table de hachage peut se contenter d'utiliser la première valeur de retour. Exemples :
Irene DURAND