dpans/dict-hash-tables.tex

% -*- Mode: TeX -*-
%
% !!!
% Barrett:
%  What about errors for these?
%
% !!!
% JonL:
%  I'll bet we don't define "grow" (as a verb -- trivial point would be to
%  put this in passive voice rather than active; better, simply say "before
%  the table size has to be enlarged.")
%  Given that fuzziness (about "grow") it is still unclear what the interaction
%  between SIZE and THRESHOLD is.  Since THRESHOLD later is described as being 
%  merely a "hint", then maybe all one needs to say is that the the programmer 
%  is permitted to express his intent that no enlargements will be forced until 
%  after about SIZE different entries have been made, and at that the time of 
%  enlargement, the actual storage size of the table may be larger than SIZE by 
%  an amount indicated by the THRESHOLD parameter -- that is the SIZE parameter
%  will be at the "threshold" value rather than the "actual size" value.

%-------------------- Hash-Table Type --------------------

\begincom{hash-table}\ftype{System Class}

\label Class Precedence List::
\typeref{hash-table},
\typeref{t}

\label Description::

%% 16.0.0 3 (has been mostly gutted)

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

\label See Also::

{\secref\HashTableConcepts},
{\secref\PrintingOtherObjects}

\label Notes::

% This is to satisfy JonL.
The intent is that this mapping be implemented by a hashing mechanism,
such as that described in Section 6.4 ``Hashing'' of {\KnuthVolThree}
(pp506-549).  In spite of this intent, no \term{conforming implementation} 
is required to use any particular technique to implement the mapping.

\endcom%{hash-table}\ftype{System Class}

%%% ========== MAKE-HASH-TABLE
\begincom{make-hash-table}\ftype{Function}

\label Syntax::

\DefunWithValues make-hash-table {{\key} test size rehash-size rehash-threshold}
		 {hash-table}

\label Arguments and Values::

\param{test}---a \term{designator} for one of the \term{functions}
	       \funref{eq},
	       \funref{eql},
	       \funref{equal}, or
\issue{HASH-TABLE-TESTS:ADD-EQUALP}
	       \funref{equalp}.
\endissue{HASH-TABLE-TESTS:ADD-EQUALP}
  \Default{\funref{eql}}

%% 16.0.0 13
\issue{ARGUMENTS-UNDERSPECIFIED:SPECIFY}
\param{size}---a non-negative \term{integer}.
\endissue{ARGUMENTS-UNDERSPECIFIED:SPECIFY}
  \Default{\term{implementation-dependent}}

%% 16.0.0 14
\param{rehash-size}---a \term{real} of \term{type} \f{(or (integer 1 *) (float (1.0) *))}.
  \Default{\term{implementation-dependent}}

%% 16.0.0 15
\issue{HASH-TABLE-SIZE:INTENDED-ENTRIES}  
\param{rehash-threshold}---a \term{real} of \term{type} \f{(real 0 1)}.
  \Default{\term{implementation-dependent}}
% KMP thinks HASH-TABLE-SIZE:INTENDED-ENTRIES implies this can no longer be an integer.
% Moon concurs.
\endissue{HASH-TABLE-SIZE:INTENDED-ENTRIES}  

\param{hash-table}---a \term{hash table}.

\label Description::

%% 16.0.0 12
Creates and returns a new \term{hash table}.

\param{test} determines how \term{keys} are compared.
%This seemed to need elaboration, so I added the rest of this paragraph. -kmp 27-Feb-91
An \term{object} is said to be present in the \param{hash-table}
if that \term{object} is the \term{same} under the \term{test} 
as the \term{key} for some entry in the \param{hash-table}.

\param{size} is a hint to the \term{implementation} about how much initial space
to allocate in the \param{hash-table}.
\issue{HASH-TABLE-SIZE:INTENDED-ENTRIES}
%It specifies
%% For JonL, I substituted the next line:
This information, taken together with the \param{rehash-threshold}, controls
the approximate number of entries which it should be possible
to insert before the table has to grow.
\endissue{HASH-TABLE-SIZE:INTENDED-ENTRIES}
The actual size might be rounded up from \param{size} to the next `good' size;
for example, some \term{implementations} might round to the next prime number.

\param{rehash-size} specifies a minimum amount to increase the size of the 
\param{hash-table} when it becomes full
enough to require rehashing; 
see \param{rehash-theshold} below.
\issue{HASH-TABLE-REHASH-SIZE-INTEGER}
If \param{rehash-size} is an \term{integer},
the expected growth rate for the table is additive and
the \term{integer} is the number of entries to add;
if it is a \term{float},
the expected growth rate for the table is multiplicative and
the \term{float} is the ratio of the new size to the old size.
\endissue{HASH-TABLE-REHASH-SIZE-INTEGER}
As with \param{size}, the actual size of the increase might be rounded up.

\param{rehash-threshold} specifies how full the \param{hash-table} can get 
before it must grow.
\issue{HASH-TABLE-SIZE:INTENDED-ENTRIES}
It specifies the maximum desired hash-table occupancy level.
%If \param{rehash-threshold} is an \term{integer} 
%it will be scaled whenever the table is grown.

\issue{HASH-TABLE-REHASH-SIZE-INTEGER}
The \term{values} of \param{rehash-size} and \param{rehash-threshold} do not constrain the
\term{implementation} to use any particular method for computing when and by how much
the size of \param{hash-table} should be enlarged.  Such decisions are   
\term{implementation-dependent}, and these \term{values} only hints
from the \term{programmer} to the \term{implementation}, and the \term{implementation}
is permitted to ignore them.
\endissue{HASH-TABLE-REHASH-SIZE-INTEGER}
\endissue{HASH-TABLE-SIZE:INTENDED-ENTRIES}

\label Examples::

%% 16.0.0 16
\code
 (setq table (make-hash-table)) \EV #<HASH-TABLE EQL 0/120 46142754>
 (setf (gethash "one" table) 1) \EV 1
 (gethash "one" table) \EV NIL, \term{false}
 (setq table (make-hash-table :test 'equal)) \EV #<HASH-TABLE EQUAL 0/139 46145547>
 (setf (gethash "one" table) 1) \EV 1
 (gethash "one" table) \EV 1, T
 (make-hash-table :rehash-size 1.5 :rehash-threshold 0.7) 
\EV #<HASH-TABLE EQL 0/120 46156620>
\endcode

\issue{HASH-TABLE-SIZE:INTENDED-ENTRIES}
% I removed this example because it uses an integer :rehash-threshold. -kmp 21-May-91
%  (make-hash-table :size 100 :rehash-size 50 :rehash-threshold 75)
% \EV #<HASH-TABLE EQL 0/100 46152651>
\endissue{HASH-TABLE-SIZE:INTENDED-ENTRIES}

\label Affected By:\None.

\label Exceptional Situations:\None.

\label See Also::

\funref{gethash},
\typeref{hash-table}

\label Notes:\None.

%% JonL says this is "redundant, and perhaps confusing". -kmp 3-Feb-92
% There are \term{hash tables} that hash on \term{object} identity
% (using \funref{eq} or \funref{eql})
% and there are \term{hash tables} that hash on \term{object} structure 
% (using \funref{equal} and \funref{equalp}).

\endcom

%%% ========== HASH-TABLE-P
\begincom{hash-table-p}\ftype{Function}

\label Syntax::

\DefunWithValues hash-table-p {object} {generalized-boolean}

\label Arguments and Values::

\param{object}---an \term{object}.

\param{generalized-boolean}---a \term{generalized boolean}.

\label Description::

%% 16.0.0 17
\TypePredicate{object}{hash-table}

\label Examples::

\code
 (setq table (make-hash-table)) \EV #<HASH-TABLE EQL 0/120 32511220>
 (hash-table-p table) \EV \term{true}
 (hash-table-p 37) \EV \term{false}
 (hash-table-p '((a . 1) (b . 2))) \EV \term{false}
\endcode

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations:\None!

\label See Also:\None.

\label Notes::

\code
 (hash-table-p \param{object}) \EQ (typep \param{object} 'hash-table)
\endcode

\endcom

%%% ========== HASH-TABLE-COUNT
\begincom{hash-table-count}\ftype{Function}

\label Syntax::

\DefunWithValues hash-table-count {hash-table} {count}

\label Arguments and Values::

\param{hash-table}---a \term{hash table}.

\param{count}---a non-negative \term{integer}.

\label Description::

%% 16.0.0 25
Returns the number of entries in the \param{hash-table}.
If \param{hash-table} has just been created 
or newly cleared (see \funref{clrhash})
the entry count is \f{0}.

\label Examples::

\code
 (setq table (make-hash-table)) \EV #<HASH-TABLE EQL 0/120 32115135>
 (hash-table-count table) \EV 0
 (setf (gethash 57 table) "fifty-seven") \EV "fifty-seven"
 (hash-table-count table) \EV 1
 (dotimes (i 100) (setf (gethash i table) i)) \EV NIL
 (hash-table-count table) \EV 100
\endcode

\label Side Effects:\None.

\label Affected By::

\funref{clrhash},
\funref{remhash},
\SETFof{gethash}

\label Exceptional Situations:\None.

\label See Also::

\funref{hash-table-size}

\label Notes::

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

\code
 (hash-table-count \param{table}) \EQ
 (loop for value being the hash-values of \param{table} count t) \EQ
 (let ((total 0))
   (maphash #'(lambda (key value)
                (declare (ignore key value))
                (incf total))
            \param{table})
   total)
\endcode

\endcom

%%% ========== HASH-TABLE-REHASH-SIZE
\begincom{hash-table-rehash-size}\ftype{Function}

\issue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\label Syntax::

\DefunWithValues hash-table-rehash-size {hash-table} {rehash-size}

\label Arguments and Values:: 

\param{hash-table}---a \term{hash table}.

\param{rehash-size}---a \term{real} of \term{type} \f{(or (integer 1 *) (float (1.0) *))}.

\label Description::

Returns the current rehash size of \param{hash-table},
suitable for use in a call to \funref{make-hash-table} 
in order to produce a \term{hash table} 
with state corresponding to the current state of the \param{hash-table}.

\label Examples::

\code
 (setq table (make-hash-table :size 100 :rehash-size 1.4))
\EV #<HASH-TABLE EQL 0/100 2556371>
 (hash-table-rehash-size table) \EV 1.4
\endcode

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations::

\Shouldchecktype{hash-table}{a \term{hash table}}

\label See Also::

\funref{make-hash-table},
\funref{hash-table-rehash-threshold}

\label Notes::

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

\endissue{HASH-TABLE-ACCESS:X3J13-MAR-89}
\endcom


%%% ========== HASH-TABLE-REHASH-THRESHOLD
\begincom{hash-table-rehash-threshold}\ftype{Function}

\issue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\label Syntax::

\DefunWithValues hash-table-rehash-threshold {hash-table} {rehash-threshold}

\label Arguments and Values::

\param{hash-table}---a \term{hash table}.

\issue{HASH-TABLE-SIZE:INTENDED-ENTRIES}
\param{rehash-threshold}---a \term{real} of \term{type} \f{(real 0 1)}.
% KMP thinks HASH-TABLE-SIZE:INTENDED-ENTRIES implies this can no longer be an integer.
% Moon concurs.
\endissue{HASH-TABLE-SIZE:INTENDED-ENTRIES}

\label Description::

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

\label Examples::

\code
 (setq table (make-hash-table :size 100 :rehash-threshold 0.5))
\EV #<HASH-TABLE EQL 0/100 2562446>
 (hash-table-rehash-threshold table) \EV 0.5
\endcode

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations::

\Shouldchecktype{hash-table}{a \term{hash table}}

\label See Also::

\funref{make-hash-table},
\funref{hash-table-rehash-size}

%% Per X3J13. -kmp 05-Oct-93
\label Notes:\None.

\endissue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\endcom


%%% ========== HASH-TABLE-SIZE
\begincom{hash-table-size}\ftype{Function}

\issue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\label Syntax::

\DefunWithValues hash-table-size {hash-table} {size}

\label Arguments and Values:: 

\param{hash-table}---a \term{hash table}.

\param{size}---a non-negative \term{integer}.

\label Description::

Returns the current size of \param{hash-table}, which is suitable for use in
a call to \funref{make-hash-table} in order to produce a \term{hash table} 
with state corresponding to the current state of the \param{hash-table}.

\label Examples:\None.

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations::

\Shouldchecktype{hash-table}{a \term{hash table}}

\label See Also::

\funref{hash-table-count},
\funref{make-hash-table}

%% Per X3J13. -kmp 05-Oct-93
\label Notes:\None.

\endissue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\endcom


%%% ========== HASH-TABLE-TEST
\begincom{hash-table-test}\ftype{Function}

\issue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\label Syntax::

\DefunWithValues hash-table-test {hash-table} {test}

\label Arguments and Values::

\param{hash-table}---a \term{hash table}.

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

\label Description::

Returns the test used for comparing \term{keys} in \param{hash-table}.

\label Examples:\None.

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations::

\Shouldchecktype{hash-table}{a \term{hash table}}

\label See Also::

\funref{make-hash-table}

%% Per X3J13. -kmp 05-Oct-93
\label Notes:\None.

\endissue{HASH-TABLE-ACCESS:X3J13-MAR-89}

\endcom

%%% ========== GETHASH
\begincom{gethash}\ftype{Accessor}

\label Syntax::

\DefunWithValues gethash {key hash-table {\opt} default} {value, present-p}
\Defsetf         gethash {key hash-table {\opt} default} {new-value}

\label Arguments and Values::

\param{key}---an \term{object}.

\param{hash-table}---a \term{hash table}.

\param{default}---an \term{object}.
 \Default{\nil}

\param{value}---an \term{object}.

\param{present-p}---a \term{generalized boolean}.

\label Description::

%% 16.0.0 18
\param{Value} is the \term{object} in \param{hash-table} whose \term{key} 
is the \term{same} as \param{key} under the \param{hash-table}'s equivalence test.
If there is no such entry, \param{value} is the \param{default}.

%% 16.0.0 19
\param{Present-p} is \term{true} if an entry is found; otherwise, it is \term{false}.

%% 16.0.0 20
\macref{setf} may be used with \funref{gethash} to modify the \term{value}
associated with a given \term{key}, or to add a new entry.
\issue{SETF-GET-DEFAULT:EVALUATED-BUT-IGNORED}
When a \funref{gethash} \term{form} is used as a \macref{setf} \param{place},
any \param{default} which is supplied is evaluated according to normal
left-to-right evaluation rules, but its \term{value} is ignored.
% \param{Default} may be supplied to \funref{gethash} 
% in this context; it is ignored by the
% \macref{setf} expander function for \funref{gethash}, but
% may be useful in such macros 
% as \macref{incf} that are related to \macref{setf}:
\endissue{SETF-GET-DEFAULT:EVALUATED-BUT-IGNORED}

\label Examples::

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

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations:\None.

\label See Also::

\funref{remhash}

\label Notes::

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

\endcom

%%% ========== REMHASH
\begincom{remhash}\ftype{Function}

\label Syntax::

\DefunWithValues remhash {key hash-table} {generalized-boolean}

\label Arguments and Values:: 

\param{key}---an \term{object}.

\param{hash-table}---a \term{hash table}.

\param{generalized-boolean}---a \term{generalized boolean}.

\label Description::

%% 16.0.0 21
Removes the entry for \param{key} in \param{hash-table}, if any.
Returns \term{true} if there was such an entry, or \term{false} otherwise.

\label Examples::
\code
 (setq table (make-hash-table)) \EV #<HASH-TABLE EQL 0/120 32115666>
 (setf (gethash 100 table) "C") \EV "C"
 (gethash 100 table) \EV "C", \term{true}
 (remhash 100 table) \EV \term{true}
 (gethash 100 table) \EV NIL, \term{false}
 (remhash 100 table) \EV \term{false}
\endcode

\label Side Effects::

The \param{hash-table} is modified.

\label Affected By:\None.

\label Exceptional Situations:\None.

\label See Also:\None.

\label Notes:\None.

\endcom

%%% ========== MAPHASH
\begincom{maphash}\ftype{Function}

\label Syntax::

%% 16.0.0 23
\DefunWithValues maphash {function hash-table} {\nil}

\label Arguments and Values::

\param{function}---a \term{designator} for a \term{function} of two \term{arguments},
		     the \term{key} and the \term{value}.

\param{hash-table}---a \term{hash table}.

\label Description::

%% 16.0.0 22
Iterates over all entries in the \param{hash-table}.  For each entry,
the \param{function} is called with two \term{arguments}--the \term{key} 
and the \term{value} of that entry.

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

\label Examples::

\code
 (setq table (make-hash-table)) \EV #<HASH-TABLE EQL 0/120 32304110>
 (dotimes (i 10) (setf (gethash i table) i)) \EV 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) \EV 285
 (hash-table-count table) \EV 10
 (maphash #'(lambda (key val)
               (when (oddp val) (remhash key table)))
           table) \EV NIL
 (hash-table-count table) \EV 5
 (maphash #'(lambda (k v) (print (list k v))) table)
(0 0) 
(8 64) 
(2 4) 
(6 36) 
(4 16) 
\EV NIL
\endcode

\label Side Effects::

None, other than any which might be done by the \param{function}.

\label Affected By:\None.

\label Exceptional Situations:\None.

\label See Also::

\macref{loop},
\macref{with-hash-table-iterator},
\issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
{\secref\TraversalRules}
\endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}

\label Notes:\None.

\endcom

%%% ========== WITH-HASH-TABLE-ITERATOR
\begincom{with-hash-table-iterator}\ftype{Macro}

\issue{DECLS-AND-DOC}

\issue{HASH-TABLE-PACKAGE-GENERATORS:ADD-WITH-WRAPPER}

\label Syntax::

\DefmacWithValues with-hash-table-iterator 
		  {\paren{name hash-table} 
	           \starparam{declaration} \starparam{form}}
		  {\starparam{result}}

\label Arguments and Values::

\param{name}---a name suitable for the first argument to \specref{macrolet}.

\param{hash-table}---a \term{form}, evaluated once, that should produce a \term{hash table}.

\param{declaration}---a \misc{declare} \term{expression}; \noeval.

\param{forms}---an \term{implicit progn}.
                                   
\param{results}---the \term{values} returned by \param{forms}.

\label Description::

%!!! KMP: Are declarations permitted?
% JonL: Let's say No because this provides no name bindings, except for the MACROLET.
%       Can always use LOCALLY anyway.
% KMP&Barrett: We added them anyway.

Within the lexical scope of the body, \param{name} is defined via \specref{macrolet} 
such that successive invocations of \f{(\param{name})} return the items,
one by one, from the \term{hash table} that is obtained by evaluating
\param{hash-table} only once.
 
An invocation \f{(\param{name})} returns three values as follows:

\beginlist
%\itemitem{1.} A flag indicating whether an entry is returned
%	      (true means an entry is returned).
\itemitem{1.} A \term{generalized boolean} that is \term{true} if an entry is returned.
\itemitem{2.} The key from the \param{hash-table} entry.
\itemitem{3.} The value from the \param{hash-table} entry.
\endlist
After all entries have been returned by successive invocations of
\f{(\param{name})}, then only one value is returned, namely \nil.
 
%!!! Barrett: Doesn't this just mean the macro has dynamic extent?
It is unspecified what happens if any of the implicit interior state 
of an iteration is returned outside the dynamic extent of the 
\macref{with-hash-table-iterator} \term{form}
such as by returning some \term{closure} over the invocation \term{form}.
 
Any number of invocations of \macref{with-hash-table-iterator} 
can be nested, and the body of the innermost one can invoke all of the
locally \term{established} \term{macros}, provided all of those \term{macros}
have \term{distinct} names.

\label Examples::
 
The following function should return \t\ on any 
\term{hash table}, and signal
an error if the usage of \macref{with-hash-table-iterator} does not agree
with the corresponding usage of \funref{maphash}.
 
\code
 (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))
\endcode
% "#'equal" => "(hash-table-test hash-table)" in the above per JonL.
% There are maybe other problems as well. Mail sent to Quinquevirate.
% -kmp 2-Feb-92

The following could be an acceptable definition of 
\funref{maphash}, implemented by \macref{with-hash-table-iterator}.
 
\code
 (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)))))
\endcode

\label Side Effects:\None.

\label Affected By:\None.

\label Exceptional Situations::

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

\label See Also::

\issue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}
{\secref\TraversalRules}
\endissue{MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE}

\label Notes:\None.

\endissue{HASH-TABLE-PACKAGE-GENERATORS:ADD-WITH-WRAPPER}
\endissue{DECLS-AND-DOC}

\endcom

%%% ========== CLRHASH
\begincom{clrhash}\ftype{Function}

\label Syntax::

\DefunWithValues clrhash {hash-table} {hash-table}

\label Arguments and Values:: 

\param{hash-table}---a \term{hash table}.

\label Description::

%% 16.0.0 24
Removes all entries from \param{hash-table},
and then returns that empty \term{hash table}.

\label Examples::

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

\label Side Effects::

The \param{hash-table} is modified.

\label Affected By:\None.

\label Exceptional Situations:\None.

\label See Also:\None.

\label Notes:\None.

\endcom


%%% ========== SXHASH
\begincom{sxhash}\ftype{Function}

\issue{SXHASH-DEFINITION:SIMILAR-FOR-SXHASH}

\label Syntax::

\DefunWithValues sxhash {object} {hash-code}

\label Arguments and Values::

\param{object}---an \term{object}.

\param{hash-code}---a non-negative \term{fixnum}.

\label Description::

%% 16.0.0 27
\funref{sxhash} returns a hash code for \param{object}. 

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

\beginlist
\itemitem{1.}
  \f{(equal \param{x} \param{y})} implies \f{(= (sxhash \param{x}) (sxhash \param{y}))}.

\itemitem{2.}
  For any two \term{objects}, \param{x} and \param{y},
       both of which are 
          \term{bit vectors},
          \term{characters}, 
          \term{conses},
          \term{numbers},
          \term{pathnames},
          \term{strings},
       or \term{symbols},
   and which are \term{similar},
   \f{(sxhash \param{x})} and \f{(sxhash \param{y})}
   \term{yield} the same mathematical value 
   even if \param{x} and \param{y} exist in different \term{Lisp images} of
   the same \term{implementation}.
   \Seesection\LiteralsInCompiledFiles.


\itemitem{3.}
  The \param{hash-code} for an \term{object} is always the \term{same}
  within a single \term{session} provided that the \term{object} is not
  visibly modified with regard to the equivalence test \funref{equal}.
  \Seesection\ModifyingHashKeys.

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

\itemitem{5.}
  Computation of the \param{hash-code} must terminate, 
  even if the \param{object} contains circularities.  
\endlist

\label Examples::

\code
 (= (sxhash (list 'list "ab")) (sxhash (list 'list "ab"))) \EV \term{true}
 (= (sxhash "a") (sxhash (make-string 1 :initial-element #\\a))) \EV \term{true}
 (let ((r (make-random-state)))
   (= (sxhash r) (sxhash (make-random-state r))))
\EV \term{implementation-dependent}
\endcode

\label Side Effects:\None.

\label Affected By::

The \term{implementation}.

\label Exceptional Situations:\None!

\label See Also:\None.

\label Notes::

Many common hashing needs are satisfied by \funref{make-hash-table} and the
related functions on \term{hash tables}.  \funref{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 \term{hash tables}.

The hash codes returned by \funref{sxhash} are not necessarily related to 
any hashing strategy used by any other \term{function} in \clisp.

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

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

\endissue{SXHASH-DEFINITION:SIMILAR-FOR-SXHASH}

\endcom