Common Lisp the Language, 2nd Edition

Next: Hash Table Functions Up: Common Lisp the Language Previous: Association Lists

# 16. Hash Tables

A hash table is a Lisp object that can efficiently map a given Lisp object to another Lisp object. Each hash table has a set of entries, each of which associates a particular key with a particular value. The basic functions that deal with hash tables can create entries, delete entries, and find the value that is associated with a given key. Finding the value is very fast, even if there are many entries, because hashing is used; this is an important advantage of hash tables over property lists.

A given hash table can associate only one value with a given key; if you try to add a second value, it will replace the first. Also, adding a value to a hash table is a destructive operation; the hash table is modified. By contrast, association lists can be augmented non-destructively.

Hash tables come in three kinds, the difference being whether the keys are compared with `eq`, `eql`, or `equal`. In other words, there are hash tables that hash on Lisp objects (using `eq` or `eql`) and there are hash tables that hash on tree structure (using `equal`).

Hash tables are created with the function `make-hash-table`, which takes various options, including which kind of hash table to make (the default being the `eql` kind). To look up a key and find the associated value, use `gethash`. New entries are added to hash tables using `setf` with `gethash`. To remove an entry, use `remhash`. Here is a simple example.

    (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

In this example, the symbols `color` and `name` are being used as keys, and the symbols `brown` and `fred` are being used as the associated values. The hash table has two items in it, one of which associates from `color` to `brown`, and the other of which associates from `name` to `fred`.

Keys do not have to be symbols; they can be any Lisp object. Similarly, values can be any Lisp object.

When a hash table is first created, it has a size, which is the maximum number of entries it can hold. Usually the actual capacity of the table is somewhat less, since the hashing is not perfectly collision-free. With the maximum possible bad luck, the capacity could be very much less, but this rarely happens. If so many entries are added that the capacity is exceeded, the hash table will automatically grow, and the entries will be rehashed (new hash values will be recomputed, and everything will be rearranged so that the fast hash lookup still works). This is transparent to the caller; it all happens automatically.

There is a discrepancy between the preceding description of the size of a hash table and the description of the `:size` argument in the specification below of `make-hash-table`.

X3J13 voted in June 1989 (HASH-TABLE-SIZE) to regard the latter description as definitive: the `:size` argument is approximately the number of entries that can be inserted without having to enlarge the hash table. This definition is certainly more convenient for the user.

Compatibility note: This hash table facility is compatible with Lisp Machine Lisp. It is similar to the hasharray facility of Interlisp, and some of the function names are the same. However, it is not compatible with Interlisp. The exact details and the order of arguments are designed to be consistent with the rest of MacLisp rather than with Interlisp. For instance, the order of arguments to `maphash` is different, there is no ``system hash table,'' and there is not the Interlisp restriction that keys and values may not be `nil`.

- Hash Table Functions
- Primitive Hash Function

Next: Hash Table Functions Up: Common Lisp the Language Previous: Association Lists