Hash Tables

The other general-purpose collection provided by Common Lisp is the hash table. Where vectors provide an integer-indexed data structure, hash tables allow you to use arbitrary objects as the indexes, or keys. When you add a value to a hash table, you store it under a particular key. Later you can use the same key to retrieve the value. Or you can associate a new value with the same key—each key maps to a single value.

With no arguments **MAKE-HASH-TABLE** makes a hash table that considers two keys equivalent if they’re the same object according to **EQL**. This is a good default unless you want to use strings as keys, since two strings with the same contents aren’t necessarily **EQL**. In that case you’ll want a so-called **EQUAL** hash table, which you can get by passing the symbol **EQUAL** as the :test keyword argument to **MAKE-HASH-TABLE**. Two other possible values for the :test argument are the symbols **EQ** and **EQUALP**. These are, of course, the names of the standard object comparison functions, which I discussed in Chapter 4. However, unlike the :test argument passed to sequence functions, **MAKE-HASH-TABLE**‘s :test can’t be used to specify an arbitrary function—only the values **EQ**, **EQL**, **EQUAL**, and **EQUALP**. This is because hash tables actually need two functions, an equivalence function and a hash function that computes a numerical hash code from the key in a way compatible with how the equivalence function will ultimately compare two keys. However, although the language standard provides only for hash tables that use the standard equivalence functions, most implementations provide some mechanism for defining custom hash tables.

The **GETHASH** function provides access to the elements of a hash table. It takes two arguments—a key and the hash table—and returns the value, if any, stored in the hash table under that key or **NIL**.11 For example:

(defparameter *h* (make-hash-table))
(gethash 'foo *h*) ==> NIL
(setf (gethash 'foo *h*) 'quux)
(gethash 'foo *h*) ==> QUUX

Since **GETHASH** returns **NIL** if the key isn’t present in the table, there’s no way to tell from the return value the difference between a key not being in a hash table at all and being in the table with the value **NIL**. **GETHASH** solves this problem with a feature I haven’t discussed yet—multiple return values. **GETHASH** actually returns two values; the primary value is the value stored under the given key or **NIL**. The secondary value is a boolean indicating whether the key is present in the hash table. Because of the way multiple values work, the extra return value is silently discarded unless the caller explicitly handles it with a form that can “see” multiple values.

I’ll discuss multiple return values in greater detail in Chapter 20, but for now I’ll give you a sneak preview of how to use the **MULTIPLE-VALUE-BIND** macro to take advantage of **GETHASH**‘s extra return value. **MULTIPLE-VALUE-BIND** creates variable bindings like **LET** does, filling them with the multiple values returned by a form.

The following function shows how you might use **MULTIPLE-VALUE-BIND**; the variables it binds are value and present:

(defun show-value (key hash-table)
  (multiple-value-bind (value present) (gethash key hash-table)
    (if present
      (format nil "Value ~a actually present." value)
      (format nil "Value ~a because key not found." value))))
 
(setf (gethash 'bar *h*) nil) ; provide an explicit value of NIL
 
(show-value 'foo *h*) ==> "Value QUUX actually present."
(show-value 'bar *h*) ==> "Value NIL actually present."
(show-value 'baz *h*) ==> "Value NIL because key not found."

Since setting the value under a key to **NIL** leaves the key in the table, you’ll need another function to completely remove a key/value pair. **REMHASH** takes the same arguments as **GETHASH** and removes the specified entry. You can also completely clear a hash table of all its key/value pairs with **CLRHASH**.