Puoi avere tabelle hash in lisp?

Question

Puoi avere tabelle hash o dit in Lisp? Intendo la struttura dei dati che è una raccolta di coppie (chiave, valore) in cui è possibile accedere ai valori utilizzando le chiavi.

Answer 1

In Lisp viene solitamente definito un elenco di proprietà.

Answer 2

Sicuro. Ecco lo SRFI definire le librerie di tabella hash standard nei Schema:

http://srfi.schemers.org/srfi-69/srfi-69.html

Answer 3

Naturalmente - Common Lisp ha hash tables.

(setq a (make-hash-table)) 
(setf (gethash 'color a) 'brown) 
(setf (gethash 'name a) 'fred) 
(gethash 'color a) => brown 
(gethash 'name a) => fred 
(gethash 'pointy a) => nil 

elenchi di proprietà sono buoni per molto piccoli esempi di scopo dimostrativo, ma per qualsiasi esigenza reale la loro performance è abissale, in modo da utilizzare le tabelle hash.

Answer 4

Se si fa riferimento a Common Lisp, hash tables viene fornito da un tipo chiamato hash-table.

Using these tables comporta la creazione di uno con funzione make-hash-table, leggere i valori con gethash ponendoli utilizzando gethash come place in concerto con setf, e rimuovendo le voci con remhash.

La mappatura dal valore chiave al codice hash è disponibile al di fuori delle tabelle hash con la funzione sxhash.

Answer 5

Clojure ha un tipo di mappa integrata:

user=> (def m {:foo "bar" :baz "bla"}) 
#'user/m 
user=> (m :foo) 
"bar" 

Vedi http://clojure.org/data_structures

Answer 6

Common Lisp ha almeno quattro modi diversi per farlo (memorizzazione valore della chiave):

• immobili liste (: foo 1: bar 2)
• elenchi associati ((: foo. 1) (: bar. 2))
• tabelle hash
• oggetti CLOS (valore di slot foo 'bar) per ottenere e (setf (valore di slot foo' bar) 42) da impostare. Il nome dello slot può essere memorizzato in una variabile: (let ((nome 'bar)) (nome valore foo slot)).

Per semplici elenchi di associazioni di utilizzo o elenchi di proprietà vanno bene. Con un numero maggiore di elementi tendono a diventare 'lenti'. Le tabelle hash sono "più veloci" ma hanno i loro compromessi. Gli oggetti CLOS sono usati come in molti altri sistemi di oggetti. Le chiavi sono i nomi degli slot definiti in una classe CLOS. Sebbene sia possibile programmare varianti che possono aggiungere e rimuovere slot all'accesso.

Answer 7

Sono incorporati hash tables, che utilizzano una funzione di hash di sistema (tipicamente SXHASH) e dove è possibile avere un paio di diversi controlli di uguaglianza (EQ, EQL, EQUAL o EQUALP a seconda di ciò che si considera essere "lo stesso" chiave).

Se le tabelle hash incorporate non sono abbastanza buone, è disponibile anche la libreria a generic hash table. Accetterà qualsiasi coppia di "generatore di hash"/"comparatore di chiavi" e ti costruirà una tabella di hash. Tuttavia, si basa sul fatto che una buona funzione di hash funzioni bene e che non sia necessariamente banale da scrivere.