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.

old_change_begin
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.
old_change_end

change_begin
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.
change_end

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.

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

AI.Repository@cs.cmu.edu