**Common Lisp the Language, 2nd Edition**

This section documents the functions for hash tables, which
use *objects* as keys and associate other objects with them.

**[Function]**

`make-hash-table &key :test :size :rehash-size :rehash-threshold`

This function creates and returns a new hash table.
The `:test` argument determines how keys are compared;
it must be one of the three values `#'eq`, `#'eql`, or `#'equal`,
or one of the three symbols `eq`, `eql`, or `equal`.
If no test is specified, `eql` is assumed.

X3J13 voted in January 1989
(HASH-TABLE-TESTS)
to add a fourth type of hash table:
the value of `#'equalp` and the symbol `equalp` are to be additional
valid possibilities for the `:test` argument.

Note that one consequence of
the vote to change the rules of
floating-point contagion
(CONTAGION-ON-NUMERICAL-COMPARISONS)
(described in section 12.1)
is to require `=`, and therefore also `equalp`,
to compare the values of numbers exactly and not approximately, making
`equalp` a true equivalence relation on numbers.

Another valuable use of `equalp` hash tables is case-insensitive
comparison of keys that are strings.

The `:size` argument
sets the initial size of the hash table, in entries.
(The actual size may be rounded up from the size
you specify to the next ``good'' size, for example to make it a prime number.)
You won't necessarily be able to store precisely
this many entries into the table
before it overflows and becomes bigger, but this argument does serve
as a hint to the implementation of approximately
how many entries you intend to store.

X3J13 voted in January 1989
(ARGUMENTS-UNDERSPECIFIED)
to clarify that the `:size` argument
must be a non-negative integer.

X3J13 voted in June 1989 (HASH-TABLE-SIZE) to regard the
preceding description of the `:size` argument as definitive: it
is approximately the number of entries that can be inserted
without having to enlarge the hash table.

The `:rehash-size` argument
specifies how much to increase the size of the hash table when it becomes
full. This can be an integer greater than zero,
which is the number of entries to add, or
it can be a floating-point number greater than 1,
which is the ratio of the new size to the old size.
The default value for this argument is implementation-dependent.

The `:rehash-threshold` argument
specifies how full the hash table can get before it must grow.
This can be an integer greater than zero and less than the `:rehash-size`
(in which case it will be scaled whenever the table is grown),
or it can be a floating-point number between zero and 1.
The default value for this argument is implementation-dependent.

X3J13 voted in June 1989 (HASH-TABLE-SIZE) to replace
the preceding specification of the `:rehash-threshold` argument
with the following:
The `:rehash-threshold` argument
specifies how full the hash table can get before it must grow.
It may be any `real` number between `0` and `1`, inclusive.
It indicates the maximum desired level of hash table occupancy.
An implementation is permitted to ignore this argument.
The default value for this argument is implementation-dependent.

An example of the use of `make-hash-table`:

(make-hash-table :rehash-size 1.5 :size (* number-of-widgets 43))

**[Function]**

`hash-table-p object`

`hash-table-p` is true if its argument is a hash table,
and otherwise is false.

(hash-table-p x) == (typep x 'hash-table)

**[Function]**

`gethash key hash-table &optional default`

`gethash` finds the entry in *hash-table* whose key is *key*
and returns the
associated value. If there is no such entry, `gethash` returns *default*,
which is `nil` if not specified.

`gethash` actually returns two values, the second being a predicate
value that is true if an entry was found, and false if no entry was found.

`setf` may be used with `gethash` to make new entries in a hash
table. If an entry with the specified *key* already exists, it is
removed before the new entry is added. The *default* argument may be
specified to `gethash` in this context; it is ignored by `setf`
but may be useful in such macros as `incf` that are related to `setf`:

(incf (gethash a-key table 0))

means approximately the same as

(setf (gethash a-key table 0) (+ (gethash a-key table 0) 1))

which in turn would be treated as simply

(setf (gethash a-key table) (+ (gethash a-key table 0) 1))

**[Function]**

`remhash key hash-table`

`remhash` removes
any entry for *key* in *hash-table*. This is a predicate
that is true if there was an
entry or false if there was not.

**[Function]**

`maphash function hash-table`

For each entry in *hash-table*, `maphash` calls
*function* on two arguments:
the key of the entry and the value of the entry; `maphash` then returns `nil`.
If entries are added to or deleted from the hash table while a `maphash`
is in progress, the results are unpredictable, with one exception:
if the *function* calls `remhash` to remove the entry currently
being processed by the *function*, or performs a `setf` of
`gethash` on that entry to change the associated value, then those
operations will have the intended effect.
For example:

;;; Alter every entry in MY-HASH-TABLE, replacing the value with ;;; its square root. Entries with negative values are removed. (maphash #'(lambda (key val) (if (minusp val) (remhash key my-hash-table) (setf (gethash key my-hash-table) (sqrt val)))) my-hash-table)

X3J13 voted in January 1989
(MAPPING-DESTRUCTIVE-INTERACTION)
to restrict user side effects; see section 7.9.

**[Function]**

`clrhash hash-table`

This removes all the entries from *hash-table*
and returns the hash table itself.

**[Function]**

`hash-table-count hash-table`

This returns the number of entries in the *hash-table*.
When a hash table is first created or has been cleared,
the number of entries is zero.

**[Macro]**

`with-hash-table-iterator ( mname hash-table) {form}*`

X3J13 voted in January 1989
(HASH-TABLE-PACKAGE-GENERATORS)
to add the macro `with-hash-table-iterator`.

The name *mname* is bound and defined as if by `macrolet`,
with the body *form*s as its lexical scope, to be a ``generator macro''
such that successive invocations `( mname)` will
return entries, one by one, from the hash table that is the value of the
expression

At each invocation of the generator macro, there are two possibilities.
If there is yet another unprocessed entry in the hash table, then
three values are returned: `t`,
the key of the hash table entry, and
the associated value of the hash table entry.
On the other hand, if there are no more unprocessed entries in the
hash table, then one value is returned: `nil`.

The implicit interior state of the iteration over the hash table
entries has dynamic extent. While the name *mname* has
lexical scope, it is an error to invoke the generator macro
once the `with-hash-table-iterator` form has been exited.

Invocations of `with-hash-table-iterator`
and related macros may be nested, and the generator macro of an
outer invocation may be called from within an inner invocation
(assuming that its name is visible or otherwise made available).

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

(setq turtles (make-hash-table :size 9 :test 'eq)) (setf (gethash 'howard-kaylan turtles) '(musician lead-singer)) (setf (gethash 'john-barbata turtles) '(musician drummer)) (setf (gethash 'leonardo turtles) '(ninja leader blue)) (setf (gethash 'donatello turtles) '(ninja machines purple)) (setf (gethash 'al-nichol turtles) '(musician guitarist)) (setf (gethash 'mark-volman turtles) '(musician great-hair)) (setf (gethash 'raphael turtles) '(ninja cool rude red)) (setf (gethash 'michaelangelo turtles) '(ninja party-dude orange)) (setf (gethash 'jim-pons turtles) '(musician bassist)) (with-hash-table-iterator (get-turtle turtles) (labels ((try (got-one &optional key value) (when got-one ;Remember, keys may show up in any order (when (eq (first value) 'ninja) (format t "~%~:(~A~): ~{~A~^, ~}" key (rest value))) (multiple-value-call #'try (get-turtle))))) (multiple-value-call #'try (get-turtle)))) ;Prints 4 lines Michaelangelo: PARTY-DUDE, ORANGE Leonardo: LEADER, BLUE Raphael: COOL, RUDE, RED Donatello: MACHINES, PURPLE => nil

**[Function]**

`hash-table-rehash-size hash-table `

X3J13 voted in March 1989 (HASH-TABLE-ACCESS)
to add four accessor functions that return values suitable for use in a call to
`make-hash-table` in order to produce a new hash table with state
corresponding to the current state of the argument hash table.

`hash-table-rehash-size` returns the current rehash size of a hash table.

`hash-table-rehash-threshold` returns the current rehash threshold.

`hash-table-size` returns the current size of a hash table.

`hash-table-test` returns the test used for comparing keys.
If the test is one of the standard test functions, then the result
will always be a symbol, even if the function itself was specified
when the *hash-table* was created. For example:

(hash-table-test (make-hash-table :test #'equal)) => equal

Implementations that extend `make-hash-table` by providing additional
possibilities for the `:test` argument may determine how the
value returned by `hash-table-test` is related to such additional tests.

AI.Repository@cs.cmu.edu