LISP - Tabella hash

La struttura dati della tabella hash rappresenta una raccolta di file key-and-valuecoppie organizzate in base al codice hash della chiave. Usa la chiave per accedere agli elementi nella collezione.

Una tabella hash viene utilizzata quando è necessario accedere agli elementi utilizzando una chiave ed è possibile identificare un valore chiave utile. Ogni elemento nella tabella hash ha una coppia chiave / valore. La chiave viene utilizzata per accedere agli elementi della collezione.

Creazione di una tabella hash in LISP

In Common LISP, la tabella hash è una raccolta generica. È possibile utilizzare oggetti arbitrari come chiave o indici.

Quando si memorizza un valore in una tabella hash, si crea una coppia chiave-valore e la si memorizza in quella chiave. Successivamente è possibile recuperare il valore dalla tabella hash utilizzando la stessa chiave. Ogni chiave è mappata a un singolo valore, sebbene sia possibile memorizzare un nuovo valore in una chiave.

Le tabelle hash, in LISP, potrebbero essere classificate in tre tipi, in base al modo in cui le chiavi potrebbero essere confrontate: eq, eql o uguale. Se la tabella hash viene sottoposta ad hashing su oggetti LISP, le chiavi vengono confrontate con eq o eql. Se la tabella hash ha l'hash sulla struttura ad albero, verrà confrontata utilizzando uguale.

Il make-hash-tableviene utilizzata per creare una tabella hash. La sintassi per questa funzione è:

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

Dove -

  • Il key l'argomento fornisce la chiave.

  • Il :testL'argomento determina il modo in cui le chiavi vengono confrontate: dovrebbe avere uno dei tre valori # 'eq, #' eql o # 'uguale o uno dei tre simboli eq, eql o uguale. Se non specificato, viene assunto eql.

  • Il :sizeL'argomento imposta la dimensione iniziale della tabella hash. Dovrebbe essere un numero intero maggiore di zero.

  • Il :rehash-sizeL'argomento specifica di quanto aumentare la dimensione della tabella hash quando diventa piena. Può essere un numero intero maggiore di zero, che è il numero di voci da aggiungere, oppure può essere un numero a virgola mobile maggiore di 1, che è il rapporto tra la nuova dimensione e la vecchia dimensione. Il valore predefinito per questo argomento dipende dall'implementazione.

  • Il :rehash-thresholdL'argomento specifica quanto può essere piena la tabella hash prima di dover crescere. Può essere un numero intero maggiore di zero e minore di: rehash-size (nel qual caso verrà ridimensionato ogni volta che la tabella viene ingrandita), oppure può essere un numero a virgola mobile compreso tra zero e 1. Il valore predefinito per questo l'argomento dipende dall'implementazione.

Puoi anche chiamare la funzione make-hash-table senza argomenti.

Recupero di elementi da e aggiunta di elementi nella tabella hash

Il gethashla funzione recupera un elemento dalla tabella hash cercando la sua chiave. Se non trova la chiave, restituisce zero.

Ha la seguente sintassi:

gethash key hash-table &optional default

dove -

  • chiave: è la chiave associata

  • hash-table: è la hash-table in cui cercare

  • default: è il valore da restituire, se la voce non viene trovata, che è nullo, se non specificato.

Il gethash la funzione restituisce effettivamente due valori, il secondo è un valore del predicato che è vero se è stata trovata una voce e falso se non è stata trovata alcuna voce.

Per aggiungere un elemento alla tabella hash, puoi utilizzare il setf funzione insieme a gethash funzione.

Esempio

Crea un nuovo file di codice sorgente denominato main.lisp e digita il codice seguente.

(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))

Quando esegui il codice, restituisce il seguente risultato:

(CHARLIE BROWN)
(FREDDIE SEAL)

Rimozione di una voce

Il remhashLa funzione rimuove qualsiasi voce per una chiave specifica nella tabella hash. Questo è un predicato vero se c'era una voce o falso se non c'era.

La sintassi per questa funzione è:

remhash key hash-table

Esempio

Crea un nuovo file di codice sorgente denominato main.lisp e digita il codice seguente.

(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))

Quando esegui il codice, restituisce il seguente risultato:

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

La funzione maphash

Il maphash funzione consente di applicare una funzione specificata a ciascuna coppia chiave-valore su una tabella hash.

Richiede due argomenti: la funzione e una tabella hash e richiama la funzione una volta per ogni coppia chiave / valore nella tabella hash.

Esempio

Crea un nuovo file di codice sorgente denominato main.lisp e digita il codice seguente.

(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)

Quando esegui il codice, restituisce il seguente risultato:

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