common-lisp
Tables de hachage

Créer une table de hachage

Les tables de hachage sont créées par make-hash-table :

(defvar *my-table* (make-hash-table))

La fonction peut prendre des paramètres de mot clé pour spécifier davantage le comportement de la table de hachage résultante:

• test : Sélectionne la fonction utilisée pour comparer les clés pour l'égalité. Peut-être un désignateur pour l'une des fonctions eq , eql , equal ou equalp . La valeur par défaut est eq .
• size : un indice sur l'implémentation de l'espace éventuellement requis.
• rehash-size : Si un entier (> = 1), la table de hachage augmentera sa capacité par le nombre spécifié lors de la reprise. Si sinon un float (> 1.0), la table de hachage augmentera sa capacité au produit de la rehash-size et de la capacité précédente.
• rehash-threshold : Spécifie le niveau de remplissage de la table de hachage afin de déclencher une rehash.

Itération sur les entrées d'une table de hachage avec maphash

(defun print-entry (key value)
  (format t "~A => ~A~%" key value))

(maphash #'print-entry *my-table*) ;; => NIL

L'utilisation de maphash permet de parcourir les entrées d'une table de hachage. L'ordre d'itération n'est pas spécifié. Le premier argument est une fonction acceptant deux paramètres: la clé et la valeur de l'entrée en cours.

maphash renvoie toujours NIL .

Itération sur les entrées d'une table de hachage avec boucle

La macro de boucle prend en charge l'itération sur les clés, les valeurs ou les clés et les valeurs d'une table de hachage. Les exemples suivants montrent des possibilités, mais la syntaxe en boucle complète permet plus de combinaisons et de variantes.

Plus de clés et de valeurs

(let ((ht (make-hash-table)))
  (setf (gethash 'a ht) 1
        (gethash 'b ht) 2)
  (loop for k being each hash-key of ht
     using (hash-value v)
     collect (cons k v)))
;;=> ((A . 1) (B . 2))

(let ((ht (make-hash-table)))
  (setf (gethash 'a ht) 1
        (gethash 'b ht) 2)
  (loop for v being each hash-value of ht
     using (hash-key k)
     collect (cons k v)))
;;=> ((A . 1) (B . 2))

Plus de clés

(let ((ht (make-hash-table)))
  (setf (gethash 'a ht) 1
        (gethash 'b ht) 2)
  (loop for k being each hash-key of ht
       collect k))
;;=> (A B)

Survaleurs

(let ((ht (make-hash-table)))
  (setf (gethash 'a ht) 1
        (gethash 'b ht) 2)
  (loop for v being each hash-value of ht
       collect v))
;;=> (1 2)

Itération sur les entrées d'une table de hachage avec un itérateur de table de hachage

Les clés et les valeurs d'une table de hachage peuvent être répétées à l'aide de la macro avec table de calcul-itérateur . Cela peut être un peu plus complexe que maphash ou loop , mais il pourrait être utilisé pour implémenter les constructions d'itération utilisées dans ces méthodes. with-hash-table-iterator prend un nom et une table de hachage et lie le nom dans un corps tel que les appels successifs au nom produisent plusieurs valeurs: (i) un booléen indiquant si une valeur est présente; (ii) la clé de l'entrée; et (iii) la valeur de l'entrée.

(let ((ht (make-hash-table)))
  (setf (gethash 'a ht) 1
        (gethash 'b ht) 2)
  (with-hash-table-iterator (iterator ht)
    (print (multiple-value-list (iterator)))
    (print (multiple-value-list (iterator)))
    (print (multiple-value-list (iterator)))))

;; (T A 1) 
;; (T B 2) 
;; (NIL)