Lisp – collezioni – 3

l9Continuando oggi finisco il capitolo del fondamentale Peter.

Hash Tables

Mentre i vettori forniscono una struttura indicizzata da un indice intero le hast tables permettono di usare qualsiasi oggetto come indice, o chiave. Quando si inserisce un valore nella tavola lo si inserisce sotto una chiave particolare. In seguito si potrà utilizzare questa chiave per rintracciare il valore. O associare un nuovo valore alla stessa chiave, ogni chiave mappa un singolo valore.

Senza argomenti make-hash-table crea una hash table che considera due chiavi equivalenti se sono lo stesso oggetto secondo eql. Questo è OK, tranne per l’uso di stringhe come chiavi perché due stringhe con lo stesso contenuto non sono necessariamente uguali per eql (non mi è chiaro ma per il momento lascio correre). In questo caso ci vorrà una cosidetta equal table che si ottiene passando equal come keyword :test alla make-hash-table. Altri valori possibili sono eq e equalp, funzioni già viste anticamente. tuttavia :test non può essere usata per passare una funzione arbitraria, solo eq, eql, equal e equalp. Ma ci sono implementazioni che definiscono hash tables custom…

La funzione gethash fornisce l’accesso agli elementi nella tavola. Ha 2 argomenti, una chiave e la hash table e ritorna il valore, se presente o nil. Esempio:

c11-25

gethash ritorna nil per una chiave non presente e per una con valore nil. Per risolvere questo caso in realtà gethash torna 2 valori, il primo dei quali è il valore immagazzinato o nil; il secondo è un booleano per la presenza nella table. Nel modo ordinario con cui i valori multipli vengono trattati il secondo è scartato silenziosamente, a meno che non venga gestito, cosa che vedremo più avanti, molto più avanti. Però possiamo fin d’ora dare un’occhiata alla macro multiple-value-bind. Esempio:

c11-26

Siccome settare il valore nil per una chiave lascia questa chiave nella tavola è necessaria un’altra funzione per rimuovere la coppia chiave/valore. remhash prende gli stessi valori di gethash e rimuove la chiave specificata. È anche possibile svuotare completamente la table con clrhash.

Iterazioni per la hash table

Ci sono due modi per attraversare una hash table. Il più semplice è maphash, analogo alla funzione map. Prende una funzione con due argomenti e una hash table. Per esempio per scrivere tutti le coppie chiave/valori della tavola si scrive:

c11-27

le conseguenze di aggiungere o rimuovere elementi durante un’iterazione non sono specificate, probabilmente non buone, con due eccezioni: usare setf con gethash per cambiare il valore della chiave corrente e usare remhash per rimuovere la chiave corrente. Per esempio per rimuovere tutte le coppie con valore minore di 10 si può usare:

(maphash #'(lambda (k v) (when (< v 10) (remhash k *h*))) *h*)

L’altro modo, come vedremo in futuro, e di usare un loop; quello per la stampa della tavola, equivalente a quello con maphash è:

(loop for k being the hash-keys in *h* using (hash-value v)
  do (format t "~a => ~a~%" k v))

Ci sarebbe molto da dire, dice Peter, sulle collezioni non liste. Per esempio non si è parlato degli arrays multidimensionali e degli arrays di bit.

Ma adesso è arrivato il momento delle liste –prossimamente :mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: