The less-familiar parts of Lisp for beginners — sxhash

Our next function of interest is sxhash.  This function provides an implementation-defined way to obtain a non-negative integer from a Lisp object.  The programmer can then use this in his or her own implementation of a hash table, or some similar application that requires a similar sparse mapping to positive integers.  Note that the standard-defined hash tables produced with make-hash-table cannot be made to use a custom hashing function, however check your implementation, they may have extended it to allow this.  SBCL 1.1.14, for instance, defines a &key argument to make-hash-table, hash-function, which allows a user-supplied function to replace the normal internal one.  It’s also worth noting that SBCL 1.1.14 uses sxhash internally when no hash-function is supplied by the programmer.  Finally, that version of SBCL also defines an internal implementation psxhash function, not visible to the programmer, for use when the hash-table is constructed with an equalp test instead of the default equal.

As noted above, the sxhash function is implementation defined.  The implementation is encouraged to make a good effort to return values distributed over the set of non-negative fixnums.

There are a few things to note about the implementation of sxhash, they are described in the CLHS.

  1. If two objects are equal, they must have the same hash returned by sxhash.
  2. Simple objects of type “bit vectors, characters, conses, numbers, pathnames, strings, or symbols” (to quote the CLHS), must return the same hash even from objects resident in different Lisp images.  This means, for instance, that a hash computed at compile time in the image that compiles some Lisp code must be the same as a hash recomputed on a similar object in a different image that loads the compiled code.  If this seems mysterious, you might want to review the earlier article on make-load-form.
  3. The hash code of an object must not change as long as that object is unchanged, or only changed in such a way that the object remains equal to its earlier form.
  4. As noted above, sxhash should me a good effort to produce good, spread-out values.
  5. The sxhash function should always terminate, even when presented with circular objects.


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


反垃圾邮件 / Anti-spam question * Time limit is exhausted. Please reload CAPTCHA.