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.[129] 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.
Hash Table Iteration
Common Lisp provides a couple ways to iterate over the entries in a hash table. The simplest of these is via the function MAPHASH. Analogous to the MAP function, MAPHASH takes a two-argument function and a hash table and invokes the function once for each key/value pair in the hash table. For instance, to print all the key/value pairs in a hash table, you could use MAPHASH like this:
(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *h*)
The consequences of adding or removing elements from a hash table while iterating over it aren't specified (and are likely to be bad) with two exceptions: you can use SETF with GETHASH to change the value of the current entry, and you can use REMHASH to remove the current entry. For instance, to remove all the entries whose value is less than ten, you could write this:
(maphash #'(lambda (k v) (when (< v 10) (remhash k *h*))) *h*)
The other way to iterate over a hash table is with the extended LOOP macro, which I'll discuss in Chapter 22.[130] The LOOP equivalent of the first MAPHASH expression would look like this:
(loop for k being the hash-keys in *h* using (hash-value v)
do (format t "~a => ~a~%" k v))
I could say a lot more about the nonlist collections supported by Common Lisp. For instance, I haven't discussed multidimensional arrays at all or the library of functions for manipulating bit arrays. However, what I've covered in this chapter should suffice for most of your general-purpose programming needs. Now it's finally time to look at Lisp's eponymous data structure: lists.
12. They Called It LISP for a Reason: List Processing
Lists play an important role in Lisp—for reasons both historical and practical. Historically, lists were Lisp's original composite data type, though it has been decades since they were its only such data type. These days, a Common Lisp programmer is as likely to use a vector, a hash table, or a user-defined class or structure as to use a list.
Practically speaking, lists remain in the language because they're an excellent solution to certain problems. One such problem—how to represent code as data in order to support code-transforming and code-generating macros—is particular to Lisp, which may explain why other languages don't feel the lack of Lisp-style lists. More generally, lists are an excellent data structure for representing any kind of heterogeneous and/or hierarchical data. They're also quite lightweight and support a functional style of programming that's another important part of Lisp's heritage.
Thus, you need to understand lists on their own terms; as you gain a better understanding of how lists work, you'll be in a better position to appreciate when you should and shouldn't use them.
"There Is No List"
Spoon Boy: Do not try and bend the list. That's impossible. Instead . . . only try to realize the truth.
Neo: What truth?
Spoon Boy: There is no list.
Neo: There is no list?
Spoon Boy: Then you'll see that it is not the list that bends; it is only yourself.[131]
The key to understanding lists is to understand that they're largely an illusion built on top of objects that are instances of a more primitive data type. Those simpler objects are pairs of values called cons cells, after the function CONS used to create them.
CONS takes two arguments and returns a new cons cell containing the two values.[132] These values can be references to any kind of object. Unless the second value is NIL or another cons cell, a cons is printed as the two values in parentheses separated by a dot, a so-called dotted pair.
(cons 1 2) ==> (1 . 2)
The two values in a cons cell are called the CAR and the CDR after the names of the functions used to access them. At the dawn of time, these names were mnemonic, at least to the folks implementing the first Lisp on an IBM 704. But even then they were just lifted from the assembly mnemonics used to implement the operations. However, it's not all bad that these names are somewhat meaningless—when considering individual cons cells, it's best to think of them simply as an arbitrary pair of values without any particular semantics. Thus:
129
By an accident of history, the order of arguments to GETHASH is the opposite of ELT—ELT takes the collection first and then the index while GETHASH takes the key first and then the collection.
130
LOOP's hash table iteration is typically implemented on top of a more primitive form, WITH-HASH-TABLE-ITERATOR, that you don't need to worry about; it was added to the language specifically to support implementing things such as LOOP and is of little use unless you need to write completely new control constructs for iterating over hash tables.