Can you have hash tables in lisp?

问题:

Can you have hash tables or dicts in Lisp? I mean the data structure that is a collection of pairs (key, value) where values can be acceded using keys.

回答1:

Common Lisp has at least four different ways to do that (key value storage):

• property lists (:foo 1 :bar 2)
• assoc lists ((:foo . 1) (:bar . 2))
• hash tables
• CLOS objects (slot-value foo 'bar) to get and (setf (slot-value foo 'bar) 42) to set. The slot name can be stored in a variable: (let ((name 'bar)) (slot-value foo name)) .

For simple usage assoc lists or property lists are fine. With a larger number of elements they tend to get 'slow'. Hash tables are 'faster' but have their own tradeoffs. CLOS objects are used like in many other object systems. The keys are the slot-names defined in a CLOS class. Though it is possible to program variants that can add and remove slots on access.

回答2:

If you're referring to Common Lisp, hash tables are provided by a type called hash-table.

Using these tables involves creating one with function make-hash-table, reading values with gethash, setting them by using gethash as a place in concert with setf, and removing entries with remhash.

The mapping from key value to hash code is available outside of hash tables with the function sxhash.

回答3:

Of course - Common Lisp has 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

Property lists are good for very small examples of demonstrative purpose, but for any real need their performance is abysmal, so use hash tables.

回答4:

Clojure has a built-in map type:

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

See http://clojure.org/data_structures

回答5:

Sure. Here's the SRFI defining the standard hash table libraries in Scheme:

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

回答6:

There's built-in hash tables, that use a system hash function (typically SXHASH) and where you can have a couple of different equality checkers (EQ, EQL, EQUAL or EQUALP depending on what you consider to be "the same" key).

If the built-in hash tables are not good enough, there's also a generic hash table library. It will accept any pair of "hash generator"/"key comparator" and build you a hash table. However, it relies on having a good hash function to work well and that is not necessarily trivial to write.

回答7:

In Lisp it's usually called a property list.