Tables de hachage en

À propos de Tables de hachage

Les tables de hachage en Common Lisp sont des structures de données qui permettent de stocker des données associatives. Elles associent des clés (qui peuvent être n'importe quel objet) à des valeurs (qui peuvent être n'importe quel objet).

Crée des tables de hachage

On peut créer des tables de hachage avec la fonction make-hash-table.

La fonction make-hash-table prend plusieurs paramètres de mot-clé pour ajuster finement la taille initiale de la table de hachage ainsi que son seuil de redimensionnement ; consulte la documentation pour tous les détails à ce sujet. Plus important encore, elle prend aussi un paramètre de mot-clé test qui définit comment les clés sont comparées lors de l'insertion, de la recherche et de la suppression de clés et de valeurs. Les valeurs de l'argument test peuvent être 'eq, 'eql, 'equal ou 'equalp, qui correspondent aux prédicats d'égalité génériques. La valeur par défaut est 'eql.

Opérations courantes sur les tables de hachage

Pour obtenir une valeur à partir de sa clé, on utilise gethash. gethash prend un [argument optionnel][concept-defualt-arguments] qui sert de valeur à renvoyer si la clé n'est pas présente dans la table de hachage. gethash renvoie aussi plusieurs valeurs (expliqué dans un autre concept). La première valeur est la valeur de cette clé dans la table de hachage, la valeur par défaut si elle est fournie, ou NIL. La seconde valeur est un booléen qui indique si la clé était présente ou non dans la table de hachage.

Pour insérer une paire clé-valeur, on utilise setf avec gethash.

Pour supprimer une clé et sa valeur, utilise remhash.

Pour supprimer toutes les clés et toutes les valeurs, utilise clrhash

Bien qu'une table de hachage en Common Lisp, comme dans d'autres langages, n'ait aucun ordre garanti, il peut parfois être utile de la parcourir en traitant chaque paire clé-valeur. On peut le faire avec maphash :

(maphash #'(lambda (key value) (print (cons key value))) *hash-table*)

(Cela affichera chaque clé et chaque valeur sous la forme d'une paire pointée, une par ligne.)

Référence

(setf *hash-table* (make-hash-table))     ; => #<HASH-TABLE :TEST EQL :COUNT 0 {100375FD23}>
(gethash :foo *hash-table*)               ; => NIL
                                          ;    NIL
(gethash :foo *hash-table* 
         :default-value)                  ; => :DEFAULT-VALUE
                                          ;    NIL

(setf (gethash :foo *hash-table*) :bar)   ; => :BAR
(gethash :foo *hash-table*)               ; => :BAR
                                          ;    T

(setf (gethash :key *hash-table*) :value) ; => :RIGHT
(gethash :key *hash-table*)               ; => :VALUE
                                          ;    T

(remhash :key *hash-table*)               ; => T
(gethash :key *hash-table*)               ; => NIL
                                          ; => NIL
                            
(clrhash *hash-table*)                    ; => #<HASH-TABLE :TEST EQL :COUNT 0 {1005A90103}>
(gethash :foo *hash-table*)               ; => NIL
                                          ;    NIL