72 lines
8.4 KiB
HTML
72 lines
8.4 KiB
HTML
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE>CLHS: Function SXHASH</TITLE>
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
|
<LINK REL=PREV HREF="f_clrhas.htm">
|
|
<LINK REL=UP HREF="c_hash_t.htm">
|
|
<LINK REL=NEXT HREF="19_.htm">
|
|
</HEAD>
|
|
<BODY>
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="f_clrhas.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="c_hash_t.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="19_.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
<A NAME="sxhash"><I>Function</I> <B>SXHASH</B></A> <P>
|
|
<P>
|
|
<P><B>Syntax:</B><P>
|
|
<P>
|
|
|
|
<B>sxhash</B> <I>object</I> => <I>hash-code</I><P>
|
|
<P>
|
|
<P><B>Arguments and Values:</B><P>
|
|
<P>
|
|
<I>object</I>---an <A REL=DEFINITION HREF="26_glo_o.htm#object"><I>object</I></A>. <P>
|
|
<I>hash-code</I>---a non-negative <A REL=DEFINITION HREF="26_glo_f.htm#fixnum"><I>fixnum</I></A>. <P>
|
|
<P><B>Description:</B><P>
|
|
<P>
|
|
<A REL=DEFINITION HREF="#sxhash"><B>sxhash</B></A> returns a hash code for <I>object</I>. <P>
|
|
The manner in which the hash code is computed is <A REL=DEFINITION HREF="26_glo_i.htm#implementation-dependent"><I>implementation-dependent</I></A>, but subject to certain constraints: <P>
|
|
<P><DL><DT>1. <TT>(equal </TT><I>x</I><TT> </TT><I>y</I><TT>)</TT> implies <TT>(= (sxhash </TT><I>x</I><TT>) (sxhash </TT><I>y</I><TT>))</TT>. <P><DD>
|
|
<DT>2. For any two <A REL=DEFINITION HREF="26_glo_o.htm#object"><I>objects</I></A>, <I>x</I> and <I>y</I>, both of which are <A REL=DEFINITION HREF="26_glo_b.htm#bit_vector"><I>bit vectors</I></A>, <A REL=DEFINITION HREF="26_glo_c.htm#character"><I>characters</I></A>, <A REL=DEFINITION HREF="26_glo_c.htm#cons"><I>conses</I></A>, <A REL=DEFINITION HREF="26_glo_n.htm#number"><I>numbers</I></A>, <A REL=DEFINITION HREF="26_glo_p.htm#pathname"><I>pathnames</I></A>, <A REL=DEFINITION HREF="26_glo_s.htm#string"><I>strings</I></A>, or <A REL=DEFINITION HREF="26_glo_s.htm#symbol"><I>symbols</I></A>, and which are <A REL=DEFINITION HREF="26_glo_s.htm#similar"><I>similar</I></A>, <TT>(sxhash </TT><I>x</I><TT>)</TT> and <TT>(sxhash </TT><I>y</I><TT>)</TT> <A REL=DEFINITION HREF="26_glo_y.htm#yield"><I>yield</I></A> the same mathematical value even if <I>x</I> and <I>y</I> exist in different <A REL=DEFINITION HREF="26_glo_l.htm#lisp_image"><I>Lisp images</I></A> of the same <A REL=DEFINITION HREF="26_glo_i.htm#implementation"><I>implementation</I></A>. See <A REL=CHILD HREF="03_bd.htm">Section 3.2.4 (Literal Objects in Compiled Files)</A>. <P><DD>
|
|
<DT>3. The <I>hash-code</I> for an <A REL=DEFINITION HREF="26_glo_o.htm#object"><I>object</I></A> is always the <A REL=DEFINITION HREF="26_glo_s.htm#same"><I>same</I></A> within a single <A REL=DEFINITION HREF="26_glo_s.htm#session"><I>session</I></A> provided that the <A REL=DEFINITION HREF="26_glo_o.htm#object"><I>object</I></A> is not visibly modified with regard to the equivalence test <A REL=DEFINITION HREF="f_equal.htm#equal"><B>equal</B></A>. See <A REL=CHILD HREF="18_ab.htm">Section 18.1.2 (Modifying Hash Table Keys)</A>. <P><DD>
|
|
<DT>4. The <I>hash-code</I> is intended for hashing. This places no verifiable constraint on a <A REL=DEFINITION HREF="26_glo_c.htm#conforming_implementation"><I>conforming implementation</I></A>, but the intent is that an <A REL=DEFINITION HREF="26_glo_i.htm#implementation"><I>implementation</I></A> should make a good-faith effort to produce <I>hash-codes</I> that are well distributed within the range of non-negative <I>fixnums</I>. <P><DD>
|
|
<DT>5. Computation of the <I>hash-code</I> must terminate, even if the <I>object</I> contains circularities. <P><DD></DL><P>
|
|
<P><B>Examples:</B><P>
|
|
<P>
|
|
<PRE>
|
|
(= (sxhash (list 'list "ab")) (sxhash (list 'list "ab"))) => <A REL=DEFINITION HREF="26_glo_t.htm#true">true</A>
|
|
(= (sxhash "a") (sxhash (make-string 1 :initial-element #\a))) => <A REL=DEFINITION HREF="26_glo_t.htm#true">true</A>
|
|
(let ((r (make-random-state)))
|
|
(= (sxhash r) (sxhash (make-random-state r))))
|
|
=> <A REL=DEFINITION HREF="26_glo_i.htm#implementation-dependent">implementation-dependent</A>
|
|
</PRE>
|
|
</TT> <P>
|
|
<P><B>Side Effects:</B> None.
|
|
<P>
|
|
<P><B>Affected By:</B><P>
|
|
<P>
|
|
The <A REL=DEFINITION HREF="26_glo_i.htm#implementation"><I>implementation</I></A>. <P>
|
|
<P><B>Exceptional Situations:</B> None.
|
|
<P>
|
|
<P><B>See Also:</B> None.
|
|
<P>
|
|
<P><B>Notes:</B><P>
|
|
<P>
|
|
Many common hashing needs are satisfied by <A REL=DEFINITION HREF="f_mk_has.htm#make-hash-table"><B>make-hash-table</B></A> and the related functions on <A REL=DEFINITION HREF="26_glo_h.htm#hash_table"><I>hash tables</I></A>. <A REL=DEFINITION HREF="#sxhash"><B>sxhash</B></A> 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 <A REL=DEFINITION HREF="26_glo_h.htm#hash_table"><I>hash tables</I></A>. <P>
|
|
The hash codes returned by <A REL=DEFINITION HREF="#sxhash"><B>sxhash</B></A> are not necessarily related to any hashing strategy used by any other <A REL=DEFINITION HREF="26_glo_f.htm#function"><I>function</I></A> in Common Lisp. <P>
|
|
For <A REL=DEFINITION HREF="26_glo_o.htm#object"><I>objects</I></A> of <A REL=DEFINITION HREF="26_glo_t.htm#type"><I>types</I></A> that <A REL=DEFINITION HREF="f_equal.htm#equal"><B>equal</B></A> compares with <A REL=DEFINITION HREF="f_eq.htm#eq"><B>eq</B></A>, item 3 requires that the <I>hash-code</I> be based on some immutable quality of the identity of the object. Another legitimate implementation technique would be to have <A REL=DEFINITION HREF="#sxhash"><B>sxhash</B></A> assign (and cache) a random hash code for these <A REL=DEFINITION HREF="26_glo_o.htm#object"><I>objects</I></A>, since there is no requirement that <A REL=DEFINITION HREF="26_glo_s.htm#similar"><I>similar</I></A> but non-<A REL=DEFINITION HREF="f_eq.htm#eq"><B>eq</B></A> objects have the same hash code. <P>
|
|
Although <A REL=DEFINITION HREF="26_glo_s.htm#similarity"><I>similarity</I></A> is defined for <A REL=DEFINITION HREF="26_glo_s.htm#symbol"><I>symbols</I></A> in terms of both the <A REL=DEFINITION HREF="26_glo_s.htm#symbol"><I>symbol</I></A>'s <A REL=DEFINITION HREF="26_glo_n.htm#name"><I>name</I></A> and the <A REL=DEFINITION HREF="26_glo_p.htm#package"><I>packages</I></A> in which the <A REL=DEFINITION HREF="26_glo_s.htm#symbol"><I>symbol</I></A> is <A REL=DEFINITION HREF="26_glo_a.htm#accessible"><I>accessible</I></A>, item 3 disallows using <A REL=DEFINITION HREF="26_glo_p.htm#package"><I>package</I></A> information to compute the hash code, since changes to the package status of a symbol are not visible to <I>equal</I>. <P>
|
|
<P>
|
|
<P><HR>The following <A REL=META HREF="../Front/X3J13Iss.htm">X3J13 cleanup issue</A>, <I>not part of the specification</I>, applies to this section:<P><UL><LI> <A REL=CHILD HREF="../Issues/iss336.htm">SXHASH-DEFINITION:SIMILAR-FOR-SXHASH</A><P></UL><HR>
|
|
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
|
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
|
</BODY>
|
|
</HTML>
|