LISP - Table de hachage

La structure de données de la table de hachage représente une collection de key-and-valuepaires organisées en fonction du code de hachage de la clé. Il utilise la clé pour accéder aux éléments de la collection.

Une table de hachage est utilisée lorsque vous devez accéder à des éléments à l'aide d'une clé et que vous pouvez identifier une valeur de clé utile. Chaque élément de la table de hachage a une paire clé / valeur. La clé est utilisée pour accéder aux éléments de la collection.

Créer une table de hachage dans LISP

Dans Common LISP, la table de hachage est une collection à usage général. Vous pouvez utiliser des objets arbitraires comme clé ou index.

Lorsque vous stockez une valeur dans une table de hachage, vous créez une paire clé-valeur et la stockez sous cette clé. Plus tard, vous pouvez récupérer la valeur de la table de hachage en utilisant la même clé. Chaque clé correspond à une valeur unique, bien que vous puissiez stocker une nouvelle valeur dans une clé.

Les tables de hachage, dans LISP, peuvent être classées en trois types, en fonction de la façon dont les clés peuvent être comparées - eq, eql ou égal. Si la table de hachage est hachée sur des objets LISP, les clés sont comparées à eq ou eql. Si la table de hachage hachait sur la structure arborescente, elle serait alors comparée en utilisant equal.

le make-hash-tableLa fonction est utilisée pour créer une table de hachage. La syntaxe de cette fonction est -

make-hash-table &key :test :size :rehash-size :rehash-threshold

Où -

  • le key l'argument fournit la clé.

  • le :testL'argument détermine comment les clés sont comparées - il doit avoir l'une des trois valeurs # 'eq, #' eql, ou # 'égal, ou l'un des trois symboles eq, eql ou égal. S'il n'est pas spécifié, eql est supposé.

  • le :sizeL'argument définit la taille initiale de la table de hachage. Cela doit être un entier supérieur à zéro.

  • le :rehash-sizeL'argument spécifie de combien augmenter la taille de la table de hachage lorsqu'elle devient pleine. Cela peut être un entier supérieur à zéro, qui est le nombre d'entrées à ajouter, ou il peut s'agir d'un nombre à virgule flottante supérieur à 1, qui est le rapport entre la nouvelle taille et l'ancienne taille. La valeur par défaut de cet argument dépend de l'implémentation.

  • le :rehash-thresholdL'argument spécifie le niveau de remplissage de la table de hachage avant de devoir croître. Cela peut être un entier supérieur à zéro et inférieur à: rehash-size (auquel cas il sera mis à l'échelle chaque fois que la table est agrandie), ou il peut s'agir d'un nombre à virgule flottante compris entre zéro et 1. La valeur par défaut pour cela L'argument dépend de l'implémentation.

Vous pouvez également appeler la fonction make-hash-table sans argument.

Récupérer des éléments et ajouter des éléments dans la table de hachage

le gethashLa fonction récupère un élément de la table de hachage en recherchant sa clé. S'il ne trouve pas la clé, il renvoie nil.

Il a la syntaxe suivante -

gethash key hash-table &optional default

où -

  • key: est la clé associée

  • table de hachage: est la table de hachage à rechercher

  • par défaut: est la valeur à renvoyer, si l'entrée n'est pas trouvée, qui est nulle, si non spécifiée.

le gethash La fonction renvoie en fait deux valeurs, la seconde étant une valeur de prédicat qui est vraie si une entrée a été trouvée et fausse si aucune entrée n'a été trouvée.

Pour ajouter un élément à la table de hachage, vous pouvez utiliser le setf fonction avec le gethash fonction.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList))

Lorsque vous exécutez le code, il renvoie le résultat suivant -

(CHARLIE BROWN)
(FREDDIE SEAL)

Supprimer une entrée

le remhashLa fonction supprime toute entrée pour une clé spécifique dans la table de hachage. C'est un prédicat qui est vrai s'il y avait une entrée ou faux s'il n'y en avait pas.

La syntaxe de cette fonction est -

remhash key hash-table

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList)) 
(terpri)
(write (gethash '003 empList))  
(remhash '003 empList)
(terpri)
(write (gethash '003 empList))

Lorsque vous exécutez le code, il renvoie le résultat suivant -

(CHARLIE BROWN)
(FREDDIE SEAL)
(MARK MONGOOSE)
NIL

La fonction maphash

le maphash La fonction vous permet d'appliquer une fonction spécifiée sur chaque paire clé-valeur sur une table de hachage.

Il prend deux arguments - la fonction et une table de hachage et appelle la fonction une fois pour chaque paire clé / valeur dans la table de hachage.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)

Lorsque vous exécutez le code, il renvoie le résultat suivant -

3 => (MARK MONGOOSE)
2 => (FREDDIE SEAL)
1 => (CHARLIE BROWN)