dotfiles/gcl-info/chap-18.texi

@node Hash Tables, Filenames, Sequences, Top
@chapter Hash Tables

@menu
* Hash Table Concepts::		
* Hash Tables Dictionary::	
@end menu

@node Hash Table Concepts, Hash Tables Dictionary, Hash Tables, Hash Tables
@section Hash Table Concepts

@c including concept-hash-tables

@menu
* Hash-Table Operations::	
* Modifying Hash Table Keys::	
@end menu

@node Hash-Table Operations, Modifying Hash Table Keys, Hash Table Concepts, Hash Table Concepts
@subsection Hash-Table Operations

Figure 18--1 lists some @i{defined names} that are applicable 
to @i{hash tables}.  The following rules apply to @i{hash tables}.

@table @asis

@item --  
A @i{hash table} can only associate one value with a given
key. If an attempt is made to add a second value for a given key,
the second value will replace the first.
Thus, adding a value to a @i{hash table} is a destructive operation;
the @i{hash table} is modified.  

@item --  
There are four kinds of @i{hash tables}:
  those whose keys are compared with @b{eq},
  those whose keys are compared with @b{eql},
  those whose keys are compared with @b{equal}, and

  those whose keys are compared with @b{equalp}.  

@item --  
@i{Hash tables} are created by @b{make-hash-table}. 
@b{gethash} is used to look up a key and find the associated value.
New entries are added to @i{hash tables} using @b{setf} with @b{gethash}.
@b{remhash} is used to remove an entry.
For example:

@example
 (setq a (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32536573>
 (setf (gethash 'color a) 'brown) @result{}  BROWN
 (setf (gethash 'name a) 'fred) @result{}  FRED
 (gethash 'color a) @result{}  BROWN, @i{true}
 (gethash 'name a) @result{}  FRED, @i{true}
 (gethash 'pointy a) @result{}  NIL, @i{false}
@end example

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

@item --  
A key or a value may be any @i{object}.

@item --  
The existence of an entry in the @i{hash table} can be determined
from the @i{secondary value} returned by @b{gethash}.
@end table

@group
@noindent
@w{  clrhash           hash-table-p     remhash  }
@w{  gethash           make-hash-table  sxhash   }
@w{  hash-table-count  maphash                   }

@noindent
@w{     Figure 18--1: Hash-table defined names   }

@end group

@node Modifying Hash Table Keys,  , Hash-Table Operations, Hash Table Concepts
@subsection Modifying Hash Table Keys

The function supplied as the @t{:test} argument to @b{make-hash-table}
specifies the `equivalence test' for the @i{hash table} it creates.

An @i{object} is `visibly modified' with regard to an equivalence test
if there exists some set of @i{objects} (or potential @i{objects})
which are equivalent to the @i{object} before the modification but are
no longer equivalent afterwards.

If an @i{object} O_1 is used as a key in a @i{hash table} H
and is then visibly modified with regard to the equivalence test of H,
then the consequences are unspecified if O_1, or any @i{object}
O_2 equivalent to O_1 under the equivalence test (either before
or after the modification), is used as a key in further operations on H.
The consequences of using O_1 as a key are unspecified 
even if O_1 is visibly modified 
and then later modified again in such a way as 
to undo the visible modification.

Following are specifications of the modifications which are visible to the
equivalence tests which must be supported by @i{hash tables}.  The modifications
are described in terms of modification of components, and are defined
recursively.  Visible modifications of components of the @i{object} are 
visible modifications of the @i{object}.

@menu
* Visible Modification of Objects with respect to EQ and EQL::	
* Visible Modification of Objects with respect to EQUAL::  
* Visible Modification of Conses with respect to EQUAL::  
* Visible Modification of Bit Vectors and Strings with respect to EQUAL::  
* Visible Modification of Objects with respect to EQUALP::  
* Visible Modification of Structures with respect to EQUALP::  
* Visible Modification of Arrays with respect to EQUALP::  
* Visible Modification of Hash Tables with respect to EQUALP::	
* Visible Modifications by Language Extensions::  
@end menu

@node Visible Modification of Objects with respect to EQ and EQL, Visible Modification of Objects with respect to EQUAL, Modifying Hash Table Keys, Modifying Hash Table Keys
@subsubsection Visible Modification of Objects with respect to EQ and EQL

No @i{standardized} @i{function} is provided that is capable of visibly
modifying an @i{object} with regard to @b{eq} or @b{eql}.

@node Visible Modification of Objects with respect to EQUAL, Visible Modification of Conses with respect to EQUAL, Visible Modification of Objects with respect to EQ and EQL, Modifying Hash Table Keys
@subsubsection Visible Modification of Objects with respect to EQUAL

As a consequence of the behavior for @b{equal},
the rules for visible modification of @i{objects} not explicitly mentioned in this
section are inherited from those in @ref{Visible Modification of Objects with respect to EQ and EQL}.

@node Visible Modification of Conses with respect to EQUAL, Visible Modification of Bit Vectors and Strings with respect to EQUAL, Visible Modification of Objects with respect to EQUAL, Modifying Hash Table Keys
@subsubsection Visible Modification of Conses with respect to EQUAL

Any visible change to the @i{car} or the @i{cdr} of a @i{cons}
is considered a visible modification with regard to @b{equal}.

@node Visible Modification of Bit Vectors and Strings with respect to EQUAL, Visible Modification of Objects with respect to EQUALP, Visible Modification of Conses with respect to EQUAL, Modifying Hash Table Keys
@subsubsection Visible Modification of Bit Vectors and Strings with respect to EQUAL

For a @i{vector} of @i{type} @b{bit-vector} or of @i{type} @b{string}, any visible change
     to an @i{active} @i{element} of the @i{vector},
  or to the @i{length} of the @i{vector} (if it is @i{actually adjustable} 
					           or has a @i{fill pointer})
is considered a visible modification with regard to @b{equal}.

@node Visible Modification of Objects with respect to EQUALP, Visible Modification of Structures with respect to EQUALP, Visible Modification of Bit Vectors and Strings with respect to EQUAL, Modifying Hash Table Keys
@subsubsection Visible Modification of Objects with respect to EQUALP

As a consequence of the behavior for @b{equalp},
the rules for visible modification of @i{objects} not explicitly mentioned in this
section are inherited from those in @ref{Visible Modification of Objects with respect to EQUAL}.

@node Visible Modification of Structures with respect to EQUALP, Visible Modification of Arrays with respect to EQUALP, Visible Modification of Objects with respect to EQUALP, Modifying Hash Table Keys
@subsubsection Visible Modification of Structures with respect to EQUALP

Any visible change to a @i{slot} of a @i{structure}
is considered a visible modification with regard to @b{equalp}.

@node Visible Modification of Arrays with respect to EQUALP, Visible Modification of Hash Tables with respect to EQUALP, Visible Modification of Structures with respect to EQUALP, Modifying Hash Table Keys
@subsubsection Visible Modification of Arrays with respect to EQUALP

In an @i{array}, any visible change
     to an @i{active} @i{element},
     to the @i{fill pointer} (if the @i{array} can and does have one),
  or to the @i{dimensions} (if the @i{array} is @i{actually adjustable})
is considered a visible modification with regard to @b{equalp}.

@node Visible Modification of Hash Tables with respect to EQUALP, Visible Modifications by Language Extensions, Visible Modification of Arrays with respect to EQUALP, Modifying Hash Table Keys
@subsubsection Visible Modification of Hash Tables with respect to EQUALP

In a @i{hash table}, any visible change
     to the count of entries in the @i{hash table},
     to the keys,
  or to the values associated with the keys
is considered a visible modification with regard to @b{equalp}.

Note that the visibility of modifications to the keys depends on the equivalence test
of the @i{hash table}, not on the specification of @b{equalp}.

@node Visible Modifications by Language Extensions,  , Visible Modification of Hash Tables with respect to EQUALP, Modifying Hash Table Keys
@subsubsection Visible Modifications by Language Extensions

@i{Implementations} that extend the language by providing additional mutator
functions (or additional behavior for existing mutator functions) must
document how the use of these extensions interacts with equivalence tests and
@i{hash table} searches.

@i{Implementations} that extend the language by defining additional acceptable
equivalence tests for @i{hash tables} (allowing additional values for the @t{:test}
argument to @b{make-hash-table}) must document the visible components of these
tests.

@c end of including concept-hash-tables

@node Hash Tables Dictionary,  , Hash Table Concepts, Hash Tables
@section Hash Tables Dictionary

@c including dict-hash-tables

@menu
* hash-table::			
* make-hash-table::		
* hash-table-p::		
* hash-table-count::		
* hash-table-rehash-size::	
* hash-table-rehash-threshold::	 
* hash-table-size::		
* hash-table-test::		
* gethash::			
* remhash::			
* maphash::			
* with-hash-table-iterator::	
* clrhash::			
* sxhash::			
@end menu

@node hash-table, make-hash-table, Hash Tables Dictionary, Hash Tables Dictionary
@subsection hash-table                                                   [System Class]

@subsubheading  Class Precedence List::
@b{hash-table},
@b{t}

@subsubheading  Description::

@i{Hash tables} provide a way of mapping any @i{object} (a @i{key})
to an associated @i{object} (a @i{value}).

@subsubheading  See Also::

@ref{Hash Table Concepts},
@ref{Printing Other Objects}

@subsubheading  Notes::

The intent is that this mapping be implemented by a hashing mechanism,
such as that described in Section 6.4 ``Hashing'' of {The Art of Computer Programming, Volume 3}
(pp506-549).  In spite of this intent, no @i{conforming implementation} 
is required to use any particular technique to implement the mapping.

@node make-hash-table, hash-table-p, hash-table, Hash Tables Dictionary
@subsection make-hash-table                                                  [Function]

@code{make-hash-table}  @i{{&key} test size rehash-size rehash-threshold} @result{}  @i{hash-table}

@subsubheading  Arguments and Values::

@i{test}---a @i{designator} for one of the @i{functions}
	       @b{eq},
	       @b{eql},
	       @b{equal}, or

	       @b{equalp}.

  The default is @b{eql}.

@i{size}---a non-negative @i{integer}.

  The default is @i{implementation-dependent}.

@i{rehash-size}---a @i{real} of @i{type} @t{(or (integer 1 *) (float (1.0) *))}.
  The default is @i{implementation-dependent}.

@i{rehash-threshold}---a @i{real} of @i{type} @t{(real 0 1)}.
  The default is @i{implementation-dependent}.

@i{hash-table}---a @i{hash table}.

@subsubheading  Description::

Creates and returns a new @i{hash table}.

@i{test} determines how @i{keys} are compared.
An @i{object} is said to be present in the @i{hash-table}
if that @i{object} is the @i{same} under the @i{test} 
as the @i{key} for some entry in the @i{hash-table}.

@i{size} is a hint to the @i{implementation} about how much initial space
to allocate in the @i{hash-table}.

This information, taken together with the @i{rehash-threshold}, controls
the approximate number of entries which it should be possible
to insert before the table has to grow.

The actual size might be rounded up from @i{size} to the next `good' size;
for example, some @i{implementations} might round to the next prime number.

@i{rehash-size} specifies a minimum amount to increase the size of the 
@i{hash-table} when it becomes full
enough to require rehashing; 
see @i{rehash-theshold} below.

If @i{rehash-size} is an @i{integer},
the expected growth rate for the table is additive and
the @i{integer} is the number of entries to add;
if it is a @i{float},
the expected growth rate for the table is multiplicative and
the @i{float} is the ratio of the new size to the old size.

As with @i{size}, the actual size of the increase might be rounded up.

@i{rehash-threshold} specifies how full the @i{hash-table} can get 
before it must grow.

It specifies the maximum desired hash-table occupancy level.

The @i{values} of @i{rehash-size} and @i{rehash-threshold} do not constrain the
@i{implementation} to use any particular method for computing when and by how much
the size of @i{hash-table} should be enlarged.  Such decisions are   
@i{implementation-dependent}, and these @i{values} only hints
from the @i{programmer} to the @i{implementation}, and the @i{implementation}
is permitted to ignore them.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 46142754>
 (setf (gethash "one" table) 1) @result{}  1
 (gethash "one" table) @result{}  NIL, @i{false}
 (setq table (make-hash-table :test 'equal)) @result{}  #<HASH-TABLE EQUAL 0/139 46145547>
 (setf (gethash "one" table) 1) @result{}  1
 (gethash "one" table) @result{}  1, T
 (make-hash-table :rehash-size 1.5 :rehash-threshold 0.7) 
@result{}  #<HASH-TABLE EQL 0/120 46156620>
@end example

@subsubheading  See Also::

@ref{gethash}
,
@b{hash-table}

@node hash-table-p, hash-table-count, make-hash-table, Hash Tables Dictionary
@subsection hash-table-p                                                     [Function]

@code{hash-table-p}  @i{object} @result{}  @i{generalized-boolean}

@subsubheading  Arguments and Values::

@i{object}---an @i{object}.

@i{generalized-boolean}---a @i{generalized boolean}.

@subsubheading  Description::

Returns @i{true} if @i{object} is of @i{type} @b{hash-table};
otherwise, returns @i{false}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32511220>
 (hash-table-p table) @result{}  @i{true}
 (hash-table-p 37) @result{}  @i{false}
 (hash-table-p '((a . 1) (b . 2))) @result{}  @i{false}
@end example

@subsubheading  Notes::

@example
 (hash-table-p @i{object}) @equiv{} (typep @i{object} 'hash-table)
@end example

@node hash-table-count, hash-table-rehash-size, hash-table-p, Hash Tables Dictionary
@subsection hash-table-count                                                 [Function]

@code{hash-table-count}  @i{hash-table} @result{}  @i{count}

@subsubheading  Arguments and Values::

@i{hash-table}---a @i{hash table}.

@i{count}---a non-negative @i{integer}.

@subsubheading  Description::

Returns the number of entries in the @i{hash-table}.
If @i{hash-table} has just been created 
or newly cleared (see @b{clrhash})
the entry count is @t{0}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32115135>
 (hash-table-count table) @result{}  0
 (setf (gethash 57 table) "fifty-seven") @result{}  "fifty-seven"
 (hash-table-count table) @result{}  1
 (dotimes (i 100) (setf (gethash i table) i)) @result{}  NIL
 (hash-table-count table) @result{}  100
@end example

@subsubheading  Affected By::

@b{clrhash},
@b{remhash},
@b{setf} of @b{gethash}

@subsubheading  See Also::

@ref{hash-table-size}

@subsubheading  Notes::

The following relationships are functionally correct, although in practice
using @b{hash-table-count} is probably much faster:

@example
 (hash-table-count @i{table}) @equiv{}
 (loop for value being the hash-values of @i{table} count t) @equiv{}
 (let ((total 0))
   (maphash #'(lambda (key value)
                (declare (ignore key value))
                (incf total))
            @i{table})
   total)
@end example

@node hash-table-rehash-size, hash-table-rehash-threshold, hash-table-count, Hash Tables Dictionary
@subsection hash-table-rehash-size                                           [Function]

@code{hash-table-rehash-size}  @i{hash-table} @result{}  @i{rehash-size}

@subsubheading  Arguments and Values:: 

@i{hash-table}---a @i{hash table}.

@i{rehash-size}---a @i{real} of @i{type} @t{(or (integer 1 *) (float (1.0) *))}.

@subsubheading  Description::

Returns the current rehash size of @i{hash-table},
suitable for use in a call to @b{make-hash-table} 
in order to produce a @i{hash table} 
with state corresponding to the current state of the @i{hash-table}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table :size 100 :rehash-size 1.4))
@result{}  #<HASH-TABLE EQL 0/100 2556371>
 (hash-table-rehash-size table) @result{}  1.4
@end example

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{make-hash-table}
,
@ref{hash-table-rehash-threshold}

@subsubheading  Notes::

If the hash table was created with an @i{integer} rehash size,
the result is an @i{integer},
indicating that the rate of growth of the @i{hash-table} when rehashed
is intended to be additive;
otherwise,
the result is a @i{float}, 
indicating that the rate of growth of the @i{hash-table} when rehashed
is intended to be multiplicative.
However, this value is only advice to the @i{implementation};
the actual amount by which the @i{hash-table} will grow upon rehash is
@i{implementation-dependent}.

@node hash-table-rehash-threshold, hash-table-size, hash-table-rehash-size, Hash Tables Dictionary
@subsection hash-table-rehash-threshold                                      [Function]

@code{hash-table-rehash-threshold}  @i{hash-table} @result{}  @i{rehash-threshold}

@subsubheading  Arguments and Values::

@i{hash-table}---a @i{hash table}.

@i{rehash-threshold}---a @i{real} of @i{type} @t{(real 0 1)}.

@subsubheading  Description::

Returns the current rehash threshold of @i{hash-table}, which is
suitable for use in a call to @b{make-hash-table} in order to
produce a @i{hash table} with state corresponding to the current 
state of the @i{hash-table}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table :size 100 :rehash-threshold 0.5))
@result{}  #<HASH-TABLE EQL 0/100 2562446>
 (hash-table-rehash-threshold table) @result{}  0.5
@end example

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{make-hash-table}
,
@ref{hash-table-rehash-size}

@node hash-table-size, hash-table-test, hash-table-rehash-threshold, Hash Tables Dictionary
@subsection hash-table-size                                                  [Function]

@code{hash-table-size}  @i{hash-table} @result{}  @i{size}

@subsubheading  Arguments and Values:: 

@i{hash-table}---a @i{hash table}.

@i{size}---a non-negative @i{integer}.

@subsubheading  Description::

Returns the current size of @i{hash-table}, which is suitable for use in
a call to @b{make-hash-table} in order to produce a @i{hash table} 
with state corresponding to the current state of the @i{hash-table}.

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{hash-table-count}
,
@ref{make-hash-table}

@node hash-table-test, gethash, hash-table-size, Hash Tables Dictionary
@subsection hash-table-test                                                  [Function]

@code{hash-table-test}  @i{hash-table} @result{}  @i{test}

@subsubheading  Arguments and Values::

@i{hash-table}---a @i{hash table}.

@i{test}---a @i{function designator}.
 For the four @i{standardized} @i{hash table} test @i{functions}
 (see @b{make-hash-table}), the @i{test} value returned
 is always a @i{symbol}.  If an @i{implementation} permits additional 
 tests, it is @i{implementation-dependent} whether such tests are
 returned as @i{function} @i{objects} or @i{function names}.

@subsubheading  Description::

Returns the test used for comparing @i{keys} in @i{hash-table}.

@subsubheading  Exceptional Situations::

Should signal an error of @i{type} @b{type-error}
			      if @i{hash-table} is not a @i{hash table}.

@subsubheading  See Also::

@ref{make-hash-table}

@node gethash, remhash, hash-table-test, Hash Tables Dictionary
@subsection gethash                                                          [Accessor]

@code{gethash}  @i{key hash-table {&optional} default} @result{}  @i{value, present-p}

(setf (@code{         gethash} @i{key hash-table {&optional} default}) new-value)@*

@subsubheading  Arguments and Values::

@i{key}---an @i{object}.

@i{hash-table}---a @i{hash table}.

@i{default}---an @i{object}.
 The default is @b{nil}.

@i{value}---an @i{object}.

@i{present-p}---a @i{generalized boolean}.

@subsubheading  Description::

@i{Value} is the @i{object} in @i{hash-table} whose @i{key} 
is the @i{same} as @i{key} under the @i{hash-table}'s equivalence test.
If there is no such entry, @i{value} is the @i{default}.

@i{Present-p} is @i{true} if an entry is found; otherwise, it is @i{false}.

@b{setf} may be used with @b{gethash} to modify the @i{value}
associated with a given @i{key}, or to add a new entry.

When a @b{gethash} @i{form} is used as a @b{setf} @i{place},
any @i{default} which is supplied is evaluated according to normal
left-to-right evaluation rules, but its @i{value} is ignored.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32206334>
 (gethash 1 table) @result{}  NIL, @i{false}
 (gethash 1 table 2) @result{}  2, @i{false}
 (setf (gethash 1 table) "one") @result{}  "one"
 (setf (gethash 2 table "two") "two") @result{}  "two"
 (gethash 1 table) @result{}  "one", @i{true}
 (gethash 2 table) @result{}  "two", @i{true}
 (gethash nil table) @result{}  NIL, @i{false}
 (setf (gethash nil table) nil) @result{}  NIL 
 (gethash nil table) @result{}  NIL, @i{true}
 (defvar *counters* (make-hash-table)) @result{}  *COUNTERS*
 (gethash 'foo *counters*) @result{}  NIL, @i{false}
 (gethash 'foo *counters* 0) @result{}  0, @i{false}
 (defmacro how-many (obj) `(values (gethash ,obj *counters* 0))) @result{}  HOW-MANY
 (defun count-it (obj) (incf (how-many obj))) @result{}  COUNT-IT
 (dolist (x '(bar foo foo bar bar baz)) (count-it x))
 (how-many 'foo) @result{}  2
 (how-many 'bar) @result{}  3
 (how-many 'quux) @result{}  0
@end example

@subsubheading  See Also::

@ref{remhash}

@subsubheading  Notes::

The @i{secondary value}, @i{present-p},
can be used to distinguish the absence of an entry
from the presence of an entry that has a value of @i{default}.

@node remhash, maphash, gethash, Hash Tables Dictionary
@subsection remhash                                                          [Function]

@code{remhash}  @i{key hash-table} @result{}  @i{generalized-boolean}

@subsubheading  Arguments and Values:: 

@i{key}---an @i{object}.

@i{hash-table}---a @i{hash table}.

@i{generalized-boolean}---a @i{generalized boolean}.

@subsubheading  Description::

Removes the entry for @i{key} in @i{hash-table}, if any.
Returns @i{true} if there was such an entry, or @i{false} otherwise.

@subsubheading  Examples::
@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32115666>
 (setf (gethash 100 table) "C") @result{}  "C"
 (gethash 100 table) @result{}  "C", @i{true}
 (remhash 100 table) @result{}  @i{true}
 (gethash 100 table) @result{}  NIL, @i{false}
 (remhash 100 table) @result{}  @i{false}
@end example

@subsubheading  Side Effects::

The @i{hash-table} is modified.

@node maphash, with-hash-table-iterator, remhash, Hash Tables Dictionary
@subsection maphash                                                          [Function]

@code{maphash}  @i{function hash-table} @result{}  @i{@b{nil}}

@subsubheading  Arguments and Values::

@i{function}---a @i{designator} for a @i{function} of two @i{arguments},
		     the @i{key} and the @i{value}.

@i{hash-table}---a @i{hash table}.

@subsubheading  Description::

Iterates over all entries in the @i{hash-table}.  For each entry,
the @i{function} is called with two @i{arguments}--the @i{key} 
and the @i{value} of that entry.

The consequences are unspecified if any attempt is made to add or remove
an entry from the @i{hash-table} while a @b{maphash} is in progress,
with two exceptions:
   the @i{function} can use can use @b{setf} of @b{gethash}
   to change the @i{value} part of the entry currently being processed, 
or it can use @b{remhash} to remove that entry.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32304110>
 (dotimes (i 10) (setf (gethash i table) i)) @result{}  NIL
 (let ((sum-of-squares 0))
    (maphash #'(lambda (key val) 
                 (let ((square (* val val)))
                   (incf sum-of-squares square)
                   (setf (gethash key table) square)))
             table)
    sum-of-squares) @result{}  285
 (hash-table-count table) @result{}  10
 (maphash #'(lambda (key val)
               (when (oddp val) (remhash key table)))
           table) @result{}  NIL
 (hash-table-count table) @result{}  5
 (maphash #'(lambda (k v) (print (list k v))) table)
(0 0) 
(8 64) 
(2 4) 
(6 36) 
(4 16) 
@result{}  NIL
@end example

@subsubheading  Side Effects::

None, other than any which might be done by the @i{function}.

@subsubheading  See Also::

@ref{loop}
,
@ref{with-hash-table-iterator}
,

@ref{Traversal Rules and Side Effects}

@node with-hash-table-iterator, clrhash, maphash, Hash Tables Dictionary
@subsection with-hash-table-iterator                                            [Macro]

@code{with-hash-table-iterator}  @i{@r{(}name hash-table@r{)} 
	           @{@i{declaration}@}{*} @{@i{form}@}{*}} @result{}  @i{@{@i{result}@}{*}}

@subsubheading  Arguments and Values::

@i{name}---a name suitable for the first argument to @b{macrolet}.

@i{hash-table}---a @i{form}, evaluated once, that should produce a @i{hash table}.

@i{declaration}---a @b{declare} @i{expression}; not evaluated.

@i{forms}---an @i{implicit progn}.

@i{results}---the @i{values} returned by @i{forms}.

@subsubheading  Description::

Within the lexical scope of the body, @i{name} is defined via @b{macrolet} 
such that successive invocations of @t{(@i{name})} return the items,
one by one, from the @i{hash table} that is obtained by evaluating
@i{hash-table} only once.

An invocation @t{(@i{name})} returns three values as follows:

@table @asis

@item 1.  
A @i{generalized boolean} that is @i{true} if an entry is returned.
@item 2.  
The key from the @i{hash-table} entry.
@item 3.  
The value from the @i{hash-table} entry.
@end table

After all entries have been returned by successive invocations of
@t{(@i{name})}, then only one value is returned, namely @b{nil}.

It is unspecified what happens if any of the implicit interior state 
of an iteration is returned outside the dynamic extent of the 
@b{with-hash-table-iterator} @i{form}
such as by returning some @i{closure} over the invocation @i{form}.

Any number of invocations of @b{with-hash-table-iterator} 
can be nested, and the body of the innermost one can invoke all of the
locally @i{established} @i{macros}, provided all of those @i{macros}
have @i{distinct} names.

@subsubheading  Examples::

The following function should return @b{t} on any 
@i{hash table}, and signal
an error if the usage of @b{with-hash-table-iterator} does not agree
with the corresponding usage of @b{maphash}.

@example
 (defun test-hash-table-iterator (hash-table)
   (let ((all-entries '())
         (generated-entries '())
         (unique (list nil)))
     (maphash #'(lambda (key value) (push (list key value) all-entries))
              hash-table)
     (with-hash-table-iterator (generator-fn hash-table)
       (loop     
         (multiple-value-bind (more? key value) (generator-fn)
           (unless more? (return))
           (unless (eql value (gethash key hash-table unique))
             (error "Key ~S not found for value ~S" key value))
           (push (list key value) generated-entries))))
     (unless (= (length all-entries)
                (length generated-entries)
                (length (union all-entries generated-entries
                               :key #'car :test (hash-table-test hash-table))))
       (error "Generated entries and Maphash entries don't correspond"))
     t))
@end example

The following could be an acceptable definition of 
@b{maphash}, implemented by @b{with-hash-table-iterator}.

@example
 (defun maphash (function hash-table)
   (with-hash-table-iterator (next-entry hash-table)
     (loop (multiple-value-bind (more key value) (next-entry)
             (unless more (return nil))
             (funcall function key value)))))
@end example

@subsubheading  Exceptional Situations::

The consequences are undefined if the local function named @i{name}
@i{established} by @b{with-hash-table-iterator} is called after it has
returned @i{false} as its @i{primary value}.

@subsubheading  See Also::

@ref{Traversal Rules and Side Effects}

@node clrhash, sxhash, with-hash-table-iterator, Hash Tables Dictionary
@subsection clrhash                                                          [Function]

@code{clrhash}  @i{hash-table} @result{}  @i{hash-table}

@subsubheading  Arguments and Values:: 

@i{hash-table}---a @i{hash table}.

@subsubheading  Description::

Removes all entries from @i{hash-table},
and then returns that empty @i{hash table}.

@subsubheading  Examples::

@example
 (setq table (make-hash-table)) @result{}  #<HASH-TABLE EQL 0/120 32004073>
 (dotimes (i 100) (setf (gethash i table) (format nil "~R" i))) @result{}  NIL
 (hash-table-count table) @result{}  100
 (gethash 57 table) @result{}  "fifty-seven", @i{true}
 (clrhash table) @result{}  #<HASH-TABLE EQL 0/120 32004073>
 (hash-table-count table) @result{}  0
 (gethash 57 table) @result{}  NIL, @i{false}
@end example

@subsubheading  Side Effects::

The @i{hash-table} is modified.

@node sxhash,  , clrhash, Hash Tables Dictionary
@subsection sxhash                                                           [Function]

@code{sxhash}  @i{object} @result{}  @i{hash-code}

@subsubheading  Arguments and Values::

@i{object}---an @i{object}.

@i{hash-code}---a non-negative @i{fixnum}.

@subsubheading  Description::

@b{sxhash} returns a hash code for @i{object}. 

The manner in which the hash code is computed is @i{implementation-dependent},
but subject to certain constraints:

@table @asis

@item 1.  
@t{(equal @i{x} @i{y})} implies @t{(= (sxhash @i{x}) (sxhash @i{y}))}.

@item 2.  
For any two @i{objects}, @i{x} and @i{y},
       both of which are 
          @i{bit vectors},
          @i{characters}, 
          @i{conses},
          @i{numbers},
          @i{pathnames},
          @i{strings},
       or @i{symbols},
   and which are @i{similar},
   @t{(sxhash @i{x})} and @t{(sxhash @i{y})}
   @i{yield} the same mathematical value 
   even if @i{x} and @i{y} exist in different @i{Lisp images} of
   the same @i{implementation}.
   See @ref{Literal Objects in Compiled Files}.

@item 3.  
The @i{hash-code} for an @i{object} is always the @i{same}
  within a single @i{session} provided that the @i{object} is not
  visibly modified with regard to the equivalence test @b{equal}.
  See @ref{Modifying Hash Table Keys}.

@item 4.  
The @i{hash-code} is intended for hashing.  This places no verifiable
  constraint on a @i{conforming implementation}, but the intent is that
  an @i{implementation} should make a good-faith effort to produce
  @i{hash-codes} that are well distributed within the range of
  non-negative @i{fixnums}.

@item 5.  
Computation of the @i{hash-code} must terminate, 
  even if the @i{object} contains circularities.  
@end table

@subsubheading  Examples::

@example
 (= (sxhash (list 'list "ab")) (sxhash (list 'list "ab"))) @result{}  @i{true}
 (= (sxhash "a") (sxhash (make-string 1 :initial-element #\a))) @result{}  @i{true}
 (let ((r (make-random-state)))
   (= (sxhash r) (sxhash (make-random-state r))))
@result{}  @i{implementation-dependent}
@end example

@subsubheading  Affected By::

The @i{implementation}.

@subsubheading  Notes::

Many common hashing needs are satisfied by @b{make-hash-table} and the
related functions on @i{hash tables}.  @b{sxhash} is intended for use
where the pre-defined abstractions are insufficient.  Its main intent is to
allow the user a convenient means of implementing more complicated hashing
paradigms than are provided through @i{hash tables}.

The hash codes returned by @b{sxhash} are not necessarily related to 
any hashing strategy used by any other @i{function} in @r{Common Lisp}.

For @i{objects} of @i{types} that @b{equal} compares 
with @b{eq}, item 3 requires that the @i{hash-code} be
based on some immutable quality of the identity of the object.
Another legitimate implementation technique would be to have 
@b{sxhash} assign (and cache) a random hash code for these
@i{objects}, since there is no requirement that @i{similar} but
non-@b{eq} objects have the same hash code.

Although @i{similarity} is defined for @i{symbols} in terms
of both the @i{symbol}'s @i{name} and the @i{packages} in which 
the @i{symbol} is @i{accessible}, item 3 disallows using @i{package}
information to compute the hash code, since changes to the package status 
of a symbol are not visible to @i{equal}.

@c end of including dict-hash-tables

@c %**end of chapter