% -*- 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 # (setf (gethash "one" table) 1) \EV 1 (gethash "one" table) \EV NIL, \term{false} (setq table (make-hash-table :test 'equal)) \EV # (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 # \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 # \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-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-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-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-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 # (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 # (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 # (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 # (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-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